Не так давно мне понадобилось реализовать свою генерацию коротких URL. Существует масса сервисов по укорачиванию URL: bit.ly, is.gd... Продолжать можно очень долго.
Возник вопрос, а как же работает этот алгоритм? В коротком URL, как правило, могут присутствовать символы a-z, A-Z, 0-9, возможно, еще какие-то спецсимволы.
Таким образом, попытаемся представить, что на выходе у нас получается 62-ричное число. На вход же подается очень большая строка, которую также можно представить в виде N-ричного числа, где N, очевидно, заведомо больше 62.
Тут точного ответа по поводу, как именно работают эти сервисы, дать невозможно. Но можно предположить, что у них есть глобальный счетчик 10-ричных чисел, его числа они и переводят в 62-ричную систему счисления. И существует таблица, ставящая в соответствие URL - short URL. Таким образом, до 3 символов включительно могут соответствовать количеству URL:
62 * 62 * 62 = 238328
Применительно к практике, не всегда можно использовать столь небольшие числа. Например, при переводе MD5 хеша в 62-ричное число, разрядность числа превосходит разрядность регистров процессора и обычными инструкциями оперировать уже не получается. Поэтому на помощь приходит так называемая Длинная арифметика и модуль для PHP BC Math.
Немного погуглив, я натолкнулся на такую функцию, которая и выполняет всю работу (жаль, автор был немец и пришлось рефакторить названия переменных):
Первым параметром подается число (может быть и строка с MD5, например). Второй и третий параметры используются для указания из какой в какую систему счисления переводить число.
Массив $stock может быть модифицирован, например, если вы хотите использовать 63 или более -ричную систему счисления. Эта функция по умолчанию поддерживает переводы чисел в систему счисления до 62-ричных включительно.
Надеюсь, что смог помочь ищущим истину людям. :)
Возник вопрос, а как же работает этот алгоритм? В коротком URL, как правило, могут присутствовать символы a-z, A-Z, 0-9, возможно, еще какие-то спецсимволы.
Таким образом, попытаемся представить, что на выходе у нас получается 62-ричное число. На вход же подается очень большая строка, которую также можно представить в виде N-ричного числа, где N, очевидно, заведомо больше 62.
Тут точного ответа по поводу, как именно работают эти сервисы, дать невозможно. Но можно предположить, что у них есть глобальный счетчик 10-ричных чисел, его числа они и переводят в 62-ричную систему счисления. И существует таблица, ставящая в соответствие URL - short URL. Таким образом, до 3 символов включительно могут соответствовать количеству URL:
62 * 62 * 62 = 238328
Применительно к практике, не всегда можно использовать столь небольшие числа. Например, при переводе MD5 хеша в 62-ричное число, разрядность числа превосходит разрядность регистров процессора и обычными инструкциями оперировать уже не получается. Поэтому на помощь приходит так называемая Длинная арифметика и модуль для PHP BC Math.
Немного погуглив, я натолкнулся на такую функцию, которая и выполняет всю работу (жаль, автор был немец и пришлось рефакторить названия переменных):
function bc_base_convert($value, $frombase, $tobase) { $stock = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'; if (max($frombase, $tobase) > strlen($stock)) { trigger_error('Bad Format max: ' . strlen($stock), E_USER_ERROR); } if (min($frombase, $tobase) < 2) { trigger_error('Bad Format min: 2', E_USER_ERROR); } $decimal = '0'; $level = 0; $result = ''; $value = trim((string) $value, "\r\n\t +"); $sign = '-' === $value[0] ? '-' : ''; $value = ltrim($value, "-0"); $len = strlen($value); for ($i = 0; $i < $len; $i++) { $temp = strpos($stock, $value[$len - 1 - $i]); if (false === $temp) { trigger_error('Bad Char in input 1', E_USER_ERROR); } if ($temp >= $frombase) { trigger_error('Bad Char in input 2', E_USER_ERROR); } $decimal = bcadd($decimal, bcmul(bcpow($frombase, $i), $temp)); } if (10 == $tobase) { return $sign . $decimal; } while (1 !== bccomp(bcpow($tobase, $level++), $decimal)) { } for ($i = $level - 2; $i >= 0; $i--) { $factor = bcpow($tobase, $i); $number = bcdiv($decimal, $factor, 0); $decimal = bcmod($decimal, $factor); $result .= $stock[$number]; } $result = empty($result) ? '0' : $result; return $sign . $result; }
Первым параметром подается число (может быть и строка с MD5, например). Второй и третий параметры используются для указания из какой в какую систему счисления переводить число.
Массив $stock может быть модифицирован, например, если вы хотите использовать 63 или более -ричную систему счисления. Эта функция по умолчанию поддерживает переводы чисел в систему счисления до 62-ричных включительно.
Надеюсь, что смог помочь ищущим истину людям. :)
Комментариев нет:
Отправить комментарий