Не так давно мне понадобилось реализовать свою генерацию коротких 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.

Немного погуглив, я натолкнулся на такую функцию, которая и выполняет всю работу (жаль, автор был немец и пришлось рефакторить названия переменных):

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-ричных включительно.

Надеюсь, что смог помочь ищущим истину людям. :)