Base58について勉強+Encode::Base58コード解読

最近流行りのショートURLサービスについて、
どういうロジックなのか興味をもっていたので、
探してみたところ、Base58という単語にいきつきました。

参考:
flic.kr で使われている base58 のデコードを行う javascript のコードCommentsAdd Star
Flickrの短縮URLをRubyで生成

要は、内部的にDBなどでデータを管理するときに、
IDとして数値を採番することはよくあると思うが、
それをもとに、IDの数値をそのまま文字列としてURLなどを作ると、
(ID=12345678901234567890だとする。長い。)

http://example.com/ID/12345678901234567890

と、長くなってしまう。
そこで、可逆化エンコードであるbase58を使うと、

http://example.com/ID/uE87b9NPNGu

と短く表現できる、ということのようです。
(アクセスが着たときに、文字列→数値への変換をサーバ側で行う)

動作確認やロジックを学ぶには、perlのEncode::Base58のソースを
読むのが一番わかりやすかった。(perl使いの自分には。)
miyagawa氏作成のコードです。使い方と動作確認コードは以下。
satoshi@debian:~/git/sample-codes/perl/base58$ cat test.pl
#!/usr/bin/perl

use strict;
use warnings;
use Data::Dumper;

use Encode::Base58;

my $num = 12345678901234567890; # big number

warn "そのまま表示 :\t\t".         $num;
warn "base58 encode:\t\t".         encode_base58($num);
warn "base58 encode->decode:\t". decode_base58(encode_base58($num));
warn "ちゃんともどるか確認 :\t". decode_base58(encode_base58($num))/100000;
satoshi@debian:~/git/sample-codes/perl/base58$ perl test.pl
そのまま表示 :          1.23456789012346e+19 at test.pl line 11.
base58 encode:          uE87b9NPNGu at test.pl line 12.
base58 encode->decode:  1.23456789012346e+19 at test.pl line 13.
ちゃんともどるか確認 :  123456789012346 at test.pl line 14.
コードを読んでみて理解を深めてみた。

1. 短縮URLに用いる文字を定義する(@alpha)
2. その文字がいくつの数字を表すか決める
my %alpha = map { $_ => $i++ } @alpha;
3. encodeするときは、@alphaの定義されてる文字数で割り続けて、
   余りを文字列として表現する
while ($num > 0) {
    my $remain = $num % $base;
    $num = int($num / $base);
    $res = $alpha[$remain] . $res;
}
4. decodeするときは、1文字ずつ下位から取り出し、足し上げる
while (length $str > 0) {
    my $digit = chop $str;
    $decoded += $multi * $alpha{$digit};
    $multi   *= $base;
}

※ chopは下位から1文字ずつ取り出し、元の文字列を削る

@alphaの定義部分を増やせばもっと短くできそうだが、
flickrはこの定義みたいですね。なにか理由があるのか?
# "_"とか"."も入れてみたいと思ったり。

ロジックは勉強になったので、自分もこれからつかってみるぞ、と。