最近流行りのショート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はこの定義みたいですね。なにか理由があるのか?
# "_"とか"."も入れてみたいと思ったり。
ロジックは勉強になったので、自分もこれからつかってみるぞ、と。