String::Dictionary

String::Dictionary という Perl のライブラリを作ってみました。

String::Dictionary は検索エンジンその他を作る時に必要になる「辞書」のためのデータ構造 + API です。辞書は単語の集まりですが、これを配列やハッシュなどで持つのではなく、単語をすべて繋げた一つの大きな文字列として保持することでメモリ領域を節約したものです。単語は単に文字列連結で持つだけでなく、Front Coding で圧縮しています。以下簡単な解説です。

辞書は例えば

[0] ･･･ jezebel
[1] ･･･ jezer
[2] ･･･ jezerit
[3] ･･･ jeziah
[4] ･･･ jeziel
...

という風に単語を配列で持つことで実現できます。単語の辞書式順序でソートしておけば二分探索が使えるので目的の単語の配列インデックスは高速に見つけることができます。配列のインデックスが分かれば、あとは例えば他に単語の出現頻度などを格納しておいた同じサイズの配列から検索対象の文字列の出現頻度を引き出すなどして任意のアプリケーションを構成することができます。

String::Dictionary では、この辞書を配列ではなく一続きの文字列として保持します。

7jezebel5jezer7jezerit6jeziah6jeziel...

さすがにこのままでは扱いづらいので、各文字列の開始位置を記録した別途管理用の配列を用います。この管理用配列には二分探索が可能です。このとき領域節約のため文字列開始位置の配列から全単語をポイントするのではなく間隔を空けてポイントするようにします。探索は二分探索と線形探索を組み合わせます。今回の実装では 4 つおきにポイントするようにしました。

7jezebel5jezer7jezerit6jeziah  6jeziel...
*                              *

上記で * のついている位置だけ配列に保持します。これにより文字列中で単語4つが1ブロックを形成するようになります。この各ブロックごとに Front Coding を施します。Front Coding は、ある単語のうち直前の単語と被っている接頭語を数値で置き換える簡易な圧縮手法です。辞書式順序でソート済みの辞書は隣り合った単語の接頭語の被り率が高いので Front Coding が有効です。

例えば上記の最初のブロックは

0,7,jezebel
4,1,r
5,2,it
3,3,iah

となります。数値はそれぞれ直前の文字列と被っている接頭語の長さ、その接頭語を除いた接尾語の長さです。実際には各数字は Variable Byte Code で記録し、またこれまで同様、一続きの文字列として扱います。探索時にはデコードしながら目的の単語を見つけます。

単語を文字列で繋げて 4 つ置きにスキップしてポインタを保持するともともと単語が持っていたスカラーの管理領域(これが結構大きい)が削減されるので全体として容量が節約できますし、Front Coding により単語データそのものも圧縮されます。

中身はこのようなデータ構造で持っていますが、実際には

use String::Dictionary;

my $dict = String::Dictionary->new;
my @terms = sort qw/jezebel jezer jezerit jeziah jeziel jezliah jezoar/; # ソートしておく

for (@terms) {
    $dict->append($_);
}

## 検索!
say $dict->search_index('jezliah'); # 5

というように辞書を構築した後は、配列を探索してインデックスを返すのと全く同様の概念で扱えます。 あとは返ってきたインデックスを使って煮るなり焼くなり、です。

試しに Lorem Ipsum から適当にコピーして辞書を構築してみたところ、配列で合計 10,188 バイトに対しString::Dictionary では 3,878 バイト (辞書文字列と単語ポインタ配列のデータ構造だけに絞ると 3,552 バイト) となりました。単語数が増えると差がより顕著になっていくようです。Variable Byte Code の生成や Front Coding はすべて Pure Perl なので、さすがに配列ままに比べると探索は遅いと思います。

参考文献

この文字列連結 + Front Coding で辞書を扱う手法は [1], [2] にその概要が紹介されています。[2] では、各ブロックの単語の先頭と末尾のそれぞれ接頭語長、接尾語長を省略するようにとありますが、今回の実装ではそこは手を抜きました。

辞書を使うプログラムを省メモリで実装したいケースはそもそも動的言語ではなく C/C++ の出番とも言えますが、この手法は C/C++ でも有効です。参考文献によると、より省メモリを考慮するなら最小完全ハッシュなども検討に値するとのことです。