Не так давно мне понадобилось реализовать свою генерацию коротких 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-ричных включительно.
Надеюсь, что смог помочь ищущим истину людям. :)
