Как работают сервисы типа "shorten URL"?

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

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