List::FrontCode

先日 Array::Gap という Variable Byte Codes による整列済み整数の圧縮の実装を作りました。(id:naoya:20080906:1220685978)

今日は Front Coding を使った同じような圧縮リストクラス、List::FrontCode を作ってみました。Front Coding は辞書式順に整列済みの文字列リストなどを圧縮する手法です。WEB+DB PRESS Vol.42 のアルゴリズム&データ構造の記事で PFI の岡野原さんによる解説があったので、それを参考に実装しました。

Front Coding

Front Coding は

http://www.hoge.jp
http://www.hoge.jp/a.htm
http://www.hoge.jp/index.htm
http://www.fuga.com/
http://www.fugafuga.com/

という辞書式順序で整列済みの文字列リストを

http://www.hoge.jp
18/a.htm
19index.htm
11fuga.com
15fuga.com

と前の要素との一致部分を文字数に置き換えることにより圧縮効果を得る手法です。URL のように似通った始まり方をするデータが大量にあるときに使える圧縮技法です。

List::FrontCode

List::FrontCode は、整列済み文字列要素を Front Code で圧縮して保持するクラスです。圧縮されたデータは、Array::Gap 同様、イテレータでアクセスすることにより先頭から一要素ずつ解凍しながら取得することができます。

#!/usr/local/bin/perl
use strict;
use warnings;

use FindBin::libs;
use Perl6::Say;
use List::FrontCode;

my @keys = (
    'http://www.hoge.jp',
    'http://www.hoge.jp/a.htm',
    'http://www.hoge.jp/index.htm',
    'http://www.fuga.com/',
    'http://www.fugafuga.com/',
);

my $list = List::FrontCode->new;
for (@keys) {
    $list->push($_);
}

my $it = $list->iterator;
while ($it->has_next) {
    say $it->next;
}

というコードを実行すると、

http://www.hoge.jp
http://www.hoge.jp/a.htm
http://www.hoge.jp/index.htm
http://www.fuga.com/
http://www.fugafuga.com/

という結果になります。

say $list;

とすることで圧縮されている状態を画面に出力することができます。この例での出力は

http://www.hoge.jp/a.htm        index.htm       fuga.com/       fuga.com/

となりました。岡野原さんのサンプルコードでは、一致部分の整数を更に可変バイト符号 (Variable Byte Codes) で表現していたので、それに習って自分の実装も整数部分を可変バイト符号で表現しています。そのため整数部分の出力が空白になっています。

圧縮率ですが、

say sprintf "%d bytes => %d bytes", length(join '', @keys), length $list;

114 bytes => 61 bytes

となりました。半分弱に圧縮できています。

Front Coding は IIR の5章 でも軽く紹介されていましたが、これまで理解が曖昧でした。今回 WEB+DB PRESS を参照しながら実装してみて正しく理解することができました。岡野原さん、技術評論社さんに感謝。

WEB+DB PRESS Vol.42

WEB+DB PRESS Vol.42