なるべく短いIDを作る

URL短縮システムを自作する場合など、限られた種類の文字を使って極力短いIDを作りたいことがあります。
例えば65536種類のIDを作りたい場合には、例えば0～65535の一意な数値を16進表記して0～FFFFの最大4桁のIDにできるわけですが、もっと短くできないか、という話です。

なお、IDの予測困難性や衝突耐性などは特に考えないことにします。そんなの考えたら長いID一択ですもんね。
そこで、n種類の短いIDを作るとき、0～n-1の数値と一対一に対応する極力短い文字列を作ることを考えます。
ちなみに、数値以外と対応付ける場合は、データ←→数値←→IDというふうに間接的に対応付けることができます。

要件

数値のなるべく短い文字列表現
文字列は可変長
使用可能な文字には一定の制限あり

3番目は、制御文字やマルチバイト文字を使えない等、実際にIDとして使うときに必要となる制限です。
ここではm種類の文字(例えば0～9、a～z、A～Zの62種類)を使うこととします。

方針

一番シンプルな発想はm進数表記ですが、これには最短にならないケースがあるという問題があります。
例えば、0…Zと続いた後には、10～ZZのIDが続きます。
これでは00～0Zが使われなくてもったいないですね。
量としては些細なものですが、ちょっと気持ち悪いです。

そこで、m進数表記をちょっと発展させます。
桁数が増えたときに、その桁数で改めて0から連番を振りなおすという考え方です。
0～Z(数値の0～61)まで使い切ったら、今度は10(数値の62)ではなく00(数値の0)から始めるということです。
そしてZZ(数値の3843、一桁のときからの通算で3905)まで使い切ったら、今度は000から始めるというわけです。

サンプルコード

PHPで実装したコードは以下のようになります。

<?php
$letters = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
$count = strlen($letters);

function GenerateID    // ID生成
    ($num)
{
    global $letters, $count;
    $ret = '';
    // 何桁で表現すべきかを計算
    $L = 0;
    $n = $count;
    while (true) {
        $L++;
        if ($num<$n) break;
        $num -= $n;
        $n *= $count;
    }
    // 必要な桁数分文字を追加
    for ($i=0; $i<$L; $i++) {
        $ret = GetLetter($num%$count).$ret;
        $num = (int)($num/$count);
    }
    return $ret;
}

function GetLetter
    ($index)
{
    global $letters;
    return substr($letters, $index, 1);
}
?>

動作サンプル

解説

サンプルにするにはあまりよくないコードですが、

$Lが現在の桁数
$numが現在の連番
$nが$L桁で表現できる数

となっています。

動作例

<?php
// 結果：ZVau
echo GenerateID(15000000);
?>

この例では8桁の数値が4桁で表せました。
ちなみに、普通の62進数では10Wbu(5桁)、普通の16進数ではe4e1c0(6桁)となります。

ただ、こんなふうに普通の62進数より短くなるケースは決して多くはありません。
何が何でも最短じゃなきゃ気持ち悪いっていう人だけどうぞ。