今勉強＆実装してるダブルアレイのサイズを測ってみました。詳しい話はまた今度(というつつパトリシアトライの解説もまだ途中だけど・・・)。
データはパトリシアトライと同じく、Wikipedia日本語タイトルの127万エントリ。文字列は全てcharで保持してます。また、予めパトリシアトライを構築し、それをもとにダブルアレイを構築してます。
以下の表にまとめます。
| 実装 | 配列要素数(base/check等) | TAIL配列要素数 | 全体サイズ |
|---|
| DoubleArray*1 | 5,668,704 | 0 | 48,547,151 |
| TailDoubleArray*2 | 1,679,616 | 4,651,339(capacity: 4,718,590) | 31,947,268 |
| TailCompactionDoubleArray*3 | 1,679,616 | 1,797,866(capacity: 2,359,294) | 27,226,058 |
| OptimizedTailCompactionDoubleArray*4 | 1,519,679 | 1,797,866 | 21,177,535 |
*1 - シンプルなダブルアレイ実装。空き要素の位置を記録して構築高速化、孫ノードの多い子ノードを先に登録してメモリ利用効率向上、TAIL無し。
*2 - TAILあり。
*3 - 接尾辞トライによるTAIL圧縮。
*4 - 構築終了時に配列サイズをtrim。checkの要素をintではなくcharにする。
パトリシアトライの時に苦労していたのが嘘のように、シンプルな実装でいきなり48MBを叩きだしてます。前回Javaではオブジェクト数大事、と連呼してましたが、トライを保持する方法がノードオブジェクトをポインタでつなぐ方法から、int配列2つに変わったことで、TAIL圧縮すらしてないのに約34MB減りました。
結論:
やっぱりオブジェクト数大事
さらにTAIL配列、TAIL配列圧縮等工夫していくことで、最終的に21MBまで小さくなっています。これ以上は、ダブルアレイの仕組みそのものを変えないと大幅な圧縮は期待できず、行き着く先は、トライの保持をビットベクタで行うLOUDS(Level Order Unary Degree Sequence。
参考)です。なので今後はLOUDSを勉強&実装してく予定です。
ダブルアレイの実装について少し。最初のDoubleArrayクラスでは、教科書通りの実装(
こことか参照)に加えて、少し効率化を図ってます。一つは構築速度の効率化として行なっている、空き要素位置の保持です。これは最初の空き要素位置を保持する変数を1個儲け、2番目以降の空き要素位置はcheck配列内に保持してます。ただし真面目にやると大変(時間がかかる)なので、実際見に行って空き要素ではなければ、そこから1つずつ空き要素を探すようにしています。もう一つは孫ノードの多い子ノードを先に登録することで充填率が上がり、結果配列のサイズが小さくなります。これはまぁデータ依存なところはありますが。
TailDoubleArrayクラスは、DoubleArrayにTAIL配列(
ここのMinimal Prefix Double-Arrayあたり参照)を導入したものです。一つしか子持たないノードが続く区間は、ラベルを文字配列内にコピーすることで、メモリ利用効率を上げます。
TailCompcationDoubleArrayクラスは、TAIL配列を可能な限り共有することで、さらに効率を上げます。"world"がTAILに格納されている状態で"javaworld"を格納する場合に"world\0java\1(0)"というように、既に接尾辞の一部が格納されている場合はそれを再利用するという工夫も行なってます。これは、多層トライで使ったテクニックを応用して、TAILを逆順に格納したトライをつくることで実現しています。このあたりはまた別途詳しく書く予定。
OptimizedTailCompactionDoubleArrayクラスは、構築終了時にbase配列やcheck配列の末尾にある使用していない領域を縮小したり、TAIL配列(中身はStringBuilder)をtrimしたりしてます。また、check配列をintではなくcharにしています。文字の種類が32,767を超えると格納できなくなりますし、次の空き要素までの距離が32,768を超えても格納できなくなります。現実的にはどちらもまず起こらない(Wikipedia日本語タイトルでも、文字種は7,564)ので、実用上問題ないんじゃないかと思います(でも念のため別クラスとして実装)。
実装は今までどおり、
GitHubで公開してます。
