Não Aqui!

Static Double Array Trie (DASTrie) という静的ダブル配列のライブラリをリリースしました．ダブル配列の実装はいろいろありますが，このライブラリの特徴を以下に挙げます．

1. C++テンプレートを利用して，std::mapのような連想配列，std::setのような集合を簡単に実装できる．
2. ダブル配列の要素を４バイト，もしくは５バイトで表現し，データベースをコンパクトにする（通常の実装では要素サイズは８バイト）．
3. 最小接頭辞トライを実装し，データベースのサイズをコンパクトにする．

よくあるダブル配列の実装では，レコードのキーとユニークなIDがトライの中に格納され，レコードのデータは配列などで独自に管理する必要があります．DASTrieはC++のテンプレートで，任意のデータ型をレコードとして使い，レコードをトライの中に格納するので，連想配列として簡単に利用できます．もちろん，トライを（レコードの値がない）集合として使うこともできます．

２番目の特徴は，A compact static double-array keeping character codesという論文に記述されているアイディアを実装したものです．通常のダブル配列は，int（４バイト）を要素サイズとして，BASEとCHECKと呼ばれる２つの（同じ要素数の）配列を使います．つまり，BASEとCHECKをまとめて考えると，ダブル配列の要素のサイズは８バイトということになります．この論文で提案されているのは，CHECKにBASE配列へのバックリンク（インデックス）を作るのではなく，ノード遷移に用いられた文字を格納すれば，CHECK配列は１バイトで済むという提案です．ただし，ダブル配列をこのように修正すると，すべてのBASE値は異ならなければならないという制約が付きます．元々の論文では，BASEを３バイト，CHECKを１バイトで表現して，BASEとCHECKをint（４バイト）で表現することを提案しています．ただし，BASEを３バイトで表現すると，格納できるデータのサイズにかなりの制限がかかるので，DASTrieではBASEを４バイト，CHECKを１バイトとして，従来通り大規模なデータが格納できるトライも実装しました．

せっかくなので，Google Web 1TコーパスとUMLS SPECIALIST Lexiconを用いて，パフォーマンスを評価してみました．Google Web 1Tコーパスは，レコードの数が多いので，ダブル配列の要素を５バイトで表現したDASTrieを用いました．実験結果によると，DASTrieのデータベースは，従来のトライの実装と比べて，1/3～2/3くらいのサイズで格納できることが示されました．

Darts: Double-ARray Trie Systemと比べると，DASTrieのデータベース構築時間がかなり長いですが，これはデータベースのサイズを小さくするために犠牲にした部分です．ダブル配列の構築で一番時間がかかるのは，「あるノードの下のすべての子ノードを格納できるBASE値を探す」という処理です．これは，あるノードのすべての子ノード集合を「クロスワードパズルのピース」のようなもので表現し，そのピースがぴったりはまる「未使用箇所」を，ダブル配列の先頭から探すという操作になります．ダブル配列が断片化されていないときは，格納可能場所を速く見つけることができますが，ダブル配列が断片化されてくると，ぴったりはまる箇所を見つけるのが大変になります．Dartsは，最小接頭辞トライとして実装されていないので，子を一つしか持たないノードを大量に格納し，断片化されたダブル配列の隙間を埋めことができます．また，Dartsはダブル配列の断片化の度合いを計測し，ある程度断片化されたら，その領域を諦め，今後使用しないようにするというヒューリスティックが実装されています．Dartsのデータベースサイズが大きいのはこのためで，速さと引き替えにデータベースサイズが大きくなります．DASTrieは，ダブル配列の空きスペースをできるだけ減らすように頑張るので，Google Web 1Tコーパスのような分枝数が大きいレコードを格納しようとすると，時間がかかります．

DASTrieはダブル配列の実装の中では，かなり頑張っているのですが，Level-Order Unary Degree Sequence (LOUDS) を実装した Tx: Succinct Trie Data structure には，データベースサイズで大きく水をあけられています．Txはすごいですね．ダブル配列は，この辺が限界なのかなぁと思っています．