naoyaのはてなダイアリー

はてなのこと、技術のこと、ウェブのこと、日々の出来事。

November 19, 2008

■ Shibuya.pm#10 を京都でも

そこで「Shibuya Perl Mongersテクニカルトーク#10 京都サテライト会場」として、弊社・はてなの京都オフィスは、関西在住のPerl Mongersのみなさんや、技術的な話に興味のある方々が集ってshibuya.pmを楽しむ会場を提供いたします。
Shibuya Perl Mongersテクニカルトーク#10 京都サテライト開場のご案内 - antipop

10回目を迎えた Shibuya.pm のテクニカルトーク。毎度のことながら人気のイベントですのであっという間に埋まってしまったそうです。

この Shibuya.pm は東京で開催ですが遠方の参加もなんとかしよう、サテライト会場を設置して楽しもう、ということになりました。京都は弊社スタッフの id:antipop が中心になって弊社オフィスをサテライト会場として開放することに。京都近郊のみなさま、11/27 ははてなの京都オフィス越しに Shibuya.pm に参加してみるのはいかがでしょう?

なお、Shibuya.pm は名前こそ Perl ではありますが、昨今は Perl の枠を超えたセッションが多いので Perl プログラマ以外の方でも楽しめる内容になっています。「Perl は経験あまりないな」という方も是非。

参加方法など詳しくは id:antipop:20081119:1227073598 をご覧ください。

Permalink | コメント(0) | トラックバック(0) | 23:42

■ CodeZine にて KOF 2008 の記事と補足

大阪南港ATCで開催された「関西オープンソース2008」の2日目（11月8日）午前中のセッションで、株式会社はてなCTOの伊藤直也氏が「はてな流大規模データ処理」と題した発表を行った。
「実現したいことを計算機の問題に置き換えることが『技術力』」、伊藤CTOが“はてな流”大規模データ処理の極意を語る：CodeZine

CodeZine で先日の KOF 2008 (あらかじめ言っておきますが King of Fighters ではないですよ、関西オープンフォーラムです) の発表を記事にしていただきました。ありがとうございます。

発表資料は以下のエントリーにありますので一緒にご覧いただければと思います。

http://d.hatena.ne.jp/naoya/20081111/1226395400

さて、記事内容について少し補足をしておきたいと思います。

メモリとディスクの速度比較について

「メモリはディスクの 150 倍」という話ですが、その後知人と話して検索のインデックスをシークする場合などは ms 対 ns くらい違うよ、という風に教えていただきました。詳しくは資料のエントリーの追記をご覧ください。150 倍というのはデータ転送速度です。この文脈の話から行くとシーク速度の話をするべきでした。知識がいたらずすみませんでした。

メモリを増設して I/O を分散する方針について

この補足は蛇足だと思いますが念のため。

I/O 分散はキャッシュサイズのサイジングをしっかり行いましょう...という意味で「単純にメモリを増やすことで、I/O負荷を軽減させることができる」のはその通りです。ですが、それは当然 I/O 回数を最小化するアルゴリズム、ドメインロジックを採用した前提での話になります。「アプリケーションで対応しないでハードで解決しなさい」という意味ではないのであしからず。またページキャッシュに関しては read/write のどちらの負荷を減らすかによって話が違って来ます。

画像 API へのリクエスト数について

画像 API のリクエストは「1億」とありますが、実際にはもっとあります。正確な値がすぐに解らないので適当に数億という数字を出してしまいました。ごめんなさい。

SQL の JOIN を使わない方針について

これも蛇足ですが「JOIN を使わない」というのは分散を前提とすると是なのですが、必ずしも JOIN クエリが悪いという話ではありません。

しっかりインデックスを効かせた上で、それほどデータ量の増加が見込まれないテーブル同士であれば JOIN しても構わないでしょう。また JOIN クエリでなければなかなか出力が難しい計算結果というのがもちろんあります。

巨大なテーブル同士を JOIN していると、そこが密結合して分散時に困るので、データ量的に支配的なテーブルはあらかじめ分散を前提に、JOIN を使わない方法で回避したほうが良い、という風に考えています。

JOIN を使うと分散できないというものでもないし、絶対に使ってはいけないという意味ではありません。

キーワードリンクの実装について

キーワードリンクの実装には Aho-Corasick や Double Array TRIE の話を取り上げましたが、現在のはてなダイアリーやはてなグループでは別の実装を使っています。Aho-Corasick, Double Array TRIE はいずれもキーワードリンクのような機能を高速に実装できる例であって、はてなで利用しているのはまた別という風にご理解ください。

ベクトル空間モデルと Compressed Suffix Arrays について

はてなブックマークの検索は PFI さんが開発した Sedue で実現されています。Sedue は Compressed Suffix Arrays を軸にした、大規模データに対してスケーラブルな検索エンジンです。(Sedue はアルゴリズムが優れているだけでなく実装の技術もハイレベル、高速で素晴らしいエンジンです)

さて、記事中ではベクトル空間モデルに対して CSA が比較されていますが、ここで CSA と比較したいのは転置インデックスです。(ベクトル空間モデルは比較対象としては層が違います。) 転置インデックスの辞書を分かち書きあるいは N-gram 辞書で実現するときの欠点に対して、CSA などの圧縮全文索引があるという風にご理解ください。

ベクトル空間モデルの話は、データベースでは扱い切れない検索要求をどう処理するか、という文脈での紹介になります。ベクトル空間モデルは情報検索だけでなく、クラスタリングやテキスト分類など様々な手法の基盤となるモデルです。ブックマークのテキスト分類でも、Complement Naive Bayes でスコアリングしたものを Cosine Similarity 相当のアルゴリズムで足切りしています。

会場での自分の説明が至らなかったものが多かったと反省しています。申し訳ありません。ほかにも何か間違い、不明な点などありましたら是非フィードバックをお待ちしています。

Permalink | コメント(0) | トラックバック(0) | 19:16

November 16, 2008

■ Wavelet Tree

圧縮全文索引の実装などでしばしば利用される Rank/Select 辞書と呼ばれるデータ構造があります。詳しくは参考文献を参照していただくとして、今回は一般の文字列に対して効率的に Rank/Select を可能とするデータ構造である Wavelet Tree (ウェーブレット木) のライブラリを作りました。

http://github.com/naoya/perl-algorithm-wavelettree/tree/master

my $wt = Algorithm::WaveletTree->new("abccbbabca");

is $wt->rank(6, 'a'), 2;
is $wt->rank(6, 'b'), 3;
is $wt->rank(9, 'b'), 4;

is $wt->select(0, 'a'), 0;
is $wt->select(1, 'a'), 6;
is $wt->select(2, 'a'), 9;

Wavelet Tree の実装は『高速且つ省メモリで文字列を扱うデータ構造「wavelet tree」』を参考にしました。

Wavelet Tree は入力文字列から構築されたハフマン木の節に、簡潔データ構造 (Succinct Data Structure) のビットベクトルを付与したデータ構造です (ビットベクトルについては後述)。今回の自分の実装では、ハフマン木はオブジェクト同士のポインタでツリーを表現したものをヒープを使って構築しています。Wavelet Tree の性格からいくとオブジェクトやポインタのサイズは余計なので、配列などで工夫してより小さいツリーの表現を使うようにしたほうが良さそうです (そもそも実用性を考えるなら LL での実装は微妙ですけれど)。参考文献の実装はそのようになっています。

Wavelet Tree があると Burrows Wheeler Transform (id:naoya:20081016:1224173077) で変換したテキストを使って、圧縮全文索引 (FM-Index) などが実装できます。この辺りについてはまた折りを見て言及したいと思います。

Bit::Vector::Succinct

Wavelet Tree を実装するためにはビットベクトルの簡潔データ構造が必要でした。そこで、Perl の vec() 関数によるビットベクトルに対して Rank/Select を可能にする Bit::Vector::Succinct も作りました。

http://github.com/naoya/perl-bit-vector-succinct/tree/master

同パッケージにある Bit::Vector::Succinct::Raw が vec() 関数をオブジェクト指向で操作できるようラッピングしたクラスです。このビットベクタオブジェクトを Bit::Vector::Succinct に渡すと、Rank/Select 辞書が得られます。

my $vec = Bit::Vector::Succinct::Raw->new;
$vec->set(1);
$vec->set(2);
$vec->set(3);

my $sucbv = Bit::Vector::Succinct->new($vec);

## rank1
is $sucbv->rank(0, 1),   0;
is $sucbv->rank(1, 1),   1;
is $sucbv->rank(2, 1),   2;

## select1
is $sucbv->select(0, 1), 1;
is $sucbv->select(1, 1), 2;
is $sucbv->select(2, 1), 3;

rank メソッドの実装は『高速かつ省メモリなbit vector「sucBV」を作る』の実装を参考にしました。select はいまのところ簡単のため、rank の二分探索で実装しています。

参考文献

R. Grossi, A. Gupta, J.S. Vitter "High-Order Entropy-Compressed Text Indexes" SODA '03, 2003
定兼邦彦: 『圧縮データ構造とその最新動向』, RAMP2006, 2006
岡野原大輔: 『圧縮索引とその周辺』, 2005
岡野原大輔: 『現実的な圧縮付全文索引』, 夏のプログラミングシンポジウム 2005, 2005
岡野原大輔: 『高速かつ省メモリなbit vector「sucBV」を作る』, CodeZine, 翔泳社, 2006
岡野原大輔: 『高速且つ省メモリで文字列を扱うデータ構造「wavelet tree」』, CodeZine, 翔泳社, 2006
岡野原大輔: 『大規模データを高速・コンパクトに処理するデータ構造』 WEB+DB PRESS Vol.42, 技術評論社 2006
広井誠: 『Algorithms with Python / シャノン・ファノ符号とハフマン符号』, 2007

付録: Algorithm::Huffman 0.09 のパッチ

ハフマン木を構築するにあたって、結局はヒープから構築するコードを実装しましたが、途中 Algorithm::Huffman を試しました。Algorithm::Huffman 0.09 は Heap::Elem の最新版の実装と相性が悪く、Heap::Elem が新しいと正しく動作しません。Heap::Elem のオブジェクト表現がハッシュから配列に変更になったのが原因のようです。

この問題を修正するパッチは以下です。作者にメールしました。

diff -Nur Algorithm-Huffman-0.09.prev/Huffman.pm Algorithm-Huffman-0.09/Huffman.pm
--- Algorithm-Huffman-0.09.prev/Huffman.pm      2002-09-06 20:29:16.000000000 +0900
+++ Algorithm-Huffman-0.09/Huffman.pm   2008-11-14 17:13:41.000000000 +0900
@@ -189,31 +189,34 @@

 our @ISA = qw/Exporter Heap::Elem/;

+use constant KEY   => 2;
+use constant VALUE => 3;
+
 sub new {
    my ($proto, $key, $value) = @_;
    my $class = ref($proto) || $proto;

    my $self = $class->SUPER::new;

-   $self->{"KeyValuePair::key"}   = $key;
-   $self->{"KeyValuePair::value"} = $value;
+   $self->[ KEY ]   = $key;
+   $self->[ VALUE ] = $value;

    return $self;
 }

 sub cmp {
    my ($self, $other) = @_;
-   $self->{"KeyValuePair::value"} <=> $other->{"KeyValuePair::value"};
+   $self->[ VALUE ] <=> $other->[ VALUE ];
 }

 sub key {
     my $self = shift;
-    return $self->{"KeyValuePair::key"};
+    return $self->[ KEY ];
 }

 sub value {
     my $self = shift;
-    return $self->{"KeyValuePair::value"};
+    return $self->[ VALUE ];
 }

 1;

Permalink | コメント(0) | トラックバック(0) | 22:11

November 11, 2008

■ KOF 2008 の発表資料

KOF 2008 での発表資料「はてな流大規模データ処理」を以下にアップロードしました。

http://bloghackers.net/~naoya/ppt/081108huge_data.ppt

一部参考文献からの引用 (Introduction to Information Retrieval から Vector space model の図、たつをの ChangeLog から転置インデックスの図) があります。この場を借りて感謝。

環境によってはおそらくフォントの表示がいまいちだと思いますが、ご了承ください。

追記

SlideShare にアップロードしました。

081108huge_data.ppt

View SlideShare presentation or Upload your own. (tags: linux mysql)

追記: メモリはディスクの 150 倍について

資料中に記載している「メモリはディスクの 150 倍」ですが、これはデータの転送速度の差を表しています。

一方、これは知人から教えてもらったのですが、ディスクとメモリのシークの差はディスクが ms 単位、メモリが ns 単位でその差は数十万倍にもなるそうです。

情報検索でインデックスをディスクから検索するのとメモリ上で検索するのとではこのシーク速度が支配的になり、結果としてメモリ上で計算できると数十万倍以上高速である、と言えるそうです。(CPU の L1, L2 キャッシュがあるので、更に差がつきます。)

大変勉強になりました。

Permalink | コメント(8) | トラックバック(11) | 18:23

November 07, 2008

■ KOF 2008: 関西オープンフォーラム

はてなが扱うデータ量は日々増加している。単一マシンで扱いきれない量のデータを現実的な時間で処理する類の要件も多い。大規模データを扱いながらウェブサービスを提供していくにあたって、どのようなアプローチを取るか、またどのようなアルゴリズムの知識が基礎として必要か、その詳細について解説する。
KOF 2008：関西オープンフォーラム

今日・明日は大阪で関西オープンフォーラムです。自分も明日のスピーチ枠を一ついただいています。

この夏にインターンの学生向けに色々講義をした中でも評判の良かった大規模データの取り扱い方について、アレンジを加えたものを発表したいと思っています。

ちょうどブックマークのベータ (http://bbeta.hatena.ne.jp/) リリースしたところで、やや大変な目にあったりした直後ですので語れる苦労が少しはあります。

Permalink | コメント(0) | トラックバック(0) | 18:16

October 19, 2008

■ Algorithm::MTF / BWT → MTF → Range Coder によるデータ圧縮

先日言及した Burrows Wheeler Transform (id:naoya:20081016:1224173077) による変換後のテキストは圧縮に使えたり、全文索引に利用できたりと応用範囲は広いです。

BWT により変換したテキストを圧縮するには、そのまま圧縮するのではなく先頭移動法 (Move-To-Front http://ja.wikipedia.org/wiki/Move_To_Front) を適用することでより情報に偏りを持たせてから圧縮するのがセオリーです。

今日は先頭移動法の Perl 実装を作ってみました。Algoritm::MTF です。

http://github.com/naoya/perl-algorithm-mtf/tree/master

に置いています。

use Algorithm::MTF;

my $encoder = Algorithm::MTF::Encoder->new;
my $code = $mtf->encode("aaabac");         # [ 97, 0, 0, 98, 1, 99 ]

my $decoder = Algorithm::MTF::Decoder->new;
say $mtf->decode([ 97, 0, 0, 98, 1, 99 ]); # "aaabac"

のように使います。

試しに /etc/httpd/conf/mime.types を BWT にかけると

# MIME type                     Extensions
application/activemessage
application/andrew-inset        ez
application/applefile
application/atom+xml            atom
application/atomicmail
application/batch-smtp
application/beep+xml
application/cals-1840
application/cnrp+xml
application/commonground
application/cpl+xml
application/cybercash
...

というファイルが

...
.-..ssv.        agaooooooeoooaogabgacioaoiaeiozeoooooppraoououioiiouoooooiiiooo
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
oooooooooooooooooooooooooooooooooooooooooooooooooooooooiidaaaaaagrrre/ooirgg...
...

となって、これれに MTF を施すと

...
1 0 0 1 1 0 0 0 1 1 1 5 0 0 13 0 0 0 2 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 13 1 13
1 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 3 1 0 0 0 0 0 0 0 0 0 0 0 6 1 2
1 6 1 0 1 1 0 0 8 1 26 0 8 2 0 0 0 0 0 0 0 5 27 2 0 0 27 0 0 0 0 14 2 0 0 7 1 
16 1 15 1 0 0 0 0 7 14 0 0 1 2 1 13 2 0 0 0 0 0 0 2 14 2 0 0 0 9 1 1 1 43 15 0 
2 1 10 11 3 8 1 0 4
...

という数字の羅列且つ 0 や 1 などの小さな数字がたくさん登場するより偏った状態に変換できました。このぐらい出現頻度に偏りがあると、エントロピー符号化に有利です。

Algorithm::MTF は内部では一方向連結リストで実装しています。配列の実装も作ってベンチマークを取りましたが、想定通りリストの方が高速という結果になりました。いまのところ MTF-1 や MTF-2 は実装していません。

自作ライブラリで圧縮

さて、ここ最近作ったライブラリを集めて一通りの圧縮アルゴリズムを適用した圧縮プログラムを作る事ができるようになりました。

Algorithm::DivSufSort (id:naoya:20081016:1224173077) で Suffix Array を作り、BWT に変換
変換したテキストに Algorithm::MTF で先頭移動法を適用
Algorithm::RangeCoder (id:naoya:20080927:1222512024) でエントロピー符号化

です。実装して実行してみました。

% perl compressor.pl /etc/httpd/conf/mime.types
[1] Block sorting ... Building SA ... Split text ... Covert SA to BWT ... done
[2] Move-to-front ... done
[3] Packing integers ... done
[4] Range coder ... done

15020 bytes => 5042 bytes (66.4%)

1 trial of SA (30.001ms total)
1 trial of split (30ms total)
1 trial of BWT (30.001ms total)
1 trial of MTF (800.012ms total)
1 trial of pack (0s total)
1 trial of RC (1.490s total)

decompress ... done ... OK

と、mime.types ファイルを圧縮率 66.4 % で圧縮することができました。(Range Coder 用の頻度表は含めていません。また、これは実装が甘い箇所が色々とあって下限からはまだ遠いです。)

速度の方は、褒められたものではないですね。MTF と Range Coder が支配的です。Suffix Array の構築は divsufsort() 任せなので高速 ... ということで結局、自分がスクラッチから実装した箇所がボトルネックという結果になってしまいました。とほほ。MTF はポインタ操作、Range Coder は整数演算が相当回数発生するので、実用を考えるならこの辺は C/C++ で実装すべきなのでしょう。圧縮は特に空間コスト/計算量コストがシビアな世界で、実装の詰めや処理系の選択などアルゴリズムの理解から実用までのギャップは大きいです。

ベンチ用のコードがごちゃ混ぜになって見苦しいコードですが、以下に記載しておきます。

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

use Perl6::Say;
use FindBin::libs;
use Path::Class qw/file/;

use Algorithm::DivSufSort;
use Algorithm::MTF;
use Algorithm::RangeCoder;

use Benchmark::Timer;

use constant EOF => "\0";

my $timer = Benchmark::Timer->new;

sub bs_encode ($) {
    my $text = shift;

    $timer->start('SA');
    printf STDERR "Building SA ... ";
    my $sa = divsufsort $text;
    $timer->stop('SA');

    $timer->start('split');
    printf STDERR "Split text ... ";
    my @text = unpack('C*', $text);
    $timer->stop('split');

    $timer->start('BWT');
    printf STDERR "Covert SA to BWT ... ";
    my $bwt = join '', map { chr $text[$_ - 1] } @$sa;
    $timer->stop('BWT');

    return $bwt;
}

sub bs_decode ($) {
    my $data = shift;

    my $pos = - 1;
    my @data = split //, $data;
    my $len  = length $data;
    my @count;

    for (my $i = 0; $i < 0x100; $i++) {
        $count[$i] = 0;
    }

    for (my $i = 0; $i < $len; $i++) {
        if ($data[$i] eq EOF) {
            $pos = $i;
        }
        $count[ ord $data[$i] ]++;
    }

    for (my $i = 0; $i < 0x100; $i++) {
        $count[$i] += $count[$i - 1];
    }

    my @LFmapping;
    for (my $i = $len - 1; $i >= 0; $i--) {
        $LFmapping[ --$count[ ord $data[$i] ] ] = $i;
    }

    my @buff;
    for (0..$len - 1) {
        $pos = $LFmapping[ $pos ];
        push @buff, $data[ $pos ];
    }

    return join '', @buff;
}

my (@freq, @cum);

sub range_encode ($) {
    my $text = shift;

    my @char = unpack('C*', $text);
    for (my $i = 0; $i < 0x100; $i++) {
        $freq[$i] = 0;
    }

    for my $c (@char) {
        $freq[$c]++;
    }

    @cum = (0);
    for (my $i = 0; $i < 0x100; $i++) {
        $cum[$i + 1] = $cum[$i] + $freq[$i];
    }

    my $rc = Algorithm::RangeCoder->new;
    $rc->freq    = \@freq;
    $rc->cumfreq = \@cum;

    return $rc->encode($text);
}

sub range_decode ($) {
    my $bin = shift;

    my $rc = Algorithm::RangeCoder->new;
    $rc->freq    = \@freq;
    $rc->cumfreq = \@cum;

    return $rc->decode($bin);
}

sub compress ($) {
    my $text = shift;

    print STDERR "[1] Block sorting ... ";
    my $bwt = bs_encode $text;
    print STDERR "done\n";

    $timer->start('MTF');
    printf STDERR "[2] Move-to-front ... ";
    my $mtf  = Algorithm::MTF::Encoder->new;
    my $code = $mtf->encode($bwt);
    print STDERR "done\n";
    $timer->stop('MTF');

    $timer->start('pack');
    printf STDERR "[3] Packing integers ... ";
    my $packed = pack('C*', @$code);
    print STDERR "done\n";
    $timer->stop('pack');

    $timer->start('RC');
    printf STDERR "[4] Range coder ... ";
    my $bin = range_encode $packed;
    print STDERR "done\n";
    $timer->stop('RC');

    $bin;
}

sub decompress ($) {
    my $bin = shift;
    my $packed = range_decode $bin;
    my @code   = unpack('C*', $packed);
    my $mtf    = Algorithm::MTF::Decoder->new;
    my $bwt    = $mtf->decode(\@code);
    bs_decode $bwt;
}

my $file = shift or die "usage: $0 <file>";
my $text = file($file)->slurp;

my $bin = compress $text . EOF;

my $rate = 1 - length($bin) / length($text);

warn sprintf "\n%d bytes => %d bytes (%.1f%%)\n\n", length $text, length $bin, $rate * 100;
warn scalar $timer->reports, "\n";

printf STDERR "decompress ... ";
my $de = decompress $bin;
printf STDERR "done ... ";

## remove EOF
substr($de , -1, 1) = '';

printf STDERR $text eq $de ? "OK\n" : "NG";

参考文献

Move To Front - Wikipedia
- 先頭移動法のアルゴリズムの概要
Algorithms with Python / ブロックソート
- Python による先頭移動法の実装あり。MTF-1、MTF-2 についても解説あり
図解入門よくわかる最新データ圧縮技術の基本と仕組み―情報圧縮技術とアルゴリズムの基礎講座 (How‐nual Visual Guide Book)
- 主要な圧縮アルゴリズムの概要が平易に解説されている書籍。(絶版)

Permalink | コメント(0) | トラックバック(0) | 23:42