2013/05/19

LZ77によるテキスト圧縮

 ちょこちょこと改良を続けているTrie4Jでの話。

 LOUDSによるTrieが実装できたことで、木構造を保持するのに必要なメモリは大幅に削減されました。そうなると今度は、TAIL配列の大きさが気になってきます。最新のTailLOUDSTrieの各構成要素をファイルに書きだしてサイズをみてみると、こんな感じ。

サイズ(KB)説明
木構造(LOUDS)756.8Trie木構造をLOUDSで表現したもの
終端フラグ189.3木の各ノードが文字列の終端となるかどうかを表すフラグ
ラベル配列3,054.9木の各ノードに対応するラベル
TAILIndex配列6,053.9木の各ノードに対応する、TAIL配列へのインデックス
TAIL配列9,302.8全ノードのTAILを繋いだ文字列
合計19,329.6
※元データは2012年2月20日のWikipedia日本語タイトル(jawiki-20120220-all-titles-in-ns0.gz)。

 木は十分に小さくなり、ラベル配列以降の文字関連データで95%以上を占める状態になっています。その中でも一番容量を食っているTAIL配列をターゲットに、圧縮方法を考えます。(ちなみにTAILIndex配列は、完備辞書により大幅に圧縮することが可能で、既にTrie4Jで実装していますが、これはまたの機会に)

 いろいろと圧縮方法を調べてみると、少し前に買ってた書籍、「高速文字列解析の世界」 で解説されているLZ-Endという手法が良さそうです。
 LZ-Endは、その論文のタイトル「LZ77-like Compression with Fast Random Access」からもわかるように、LZ77をベースに、高速にランダムアクセス出来るよう拡張されたアルゴリズムです。少々複雑なので、まずはベースとなったLZ77を見てみます(LZ77も同書籍に説明があります)。

 LZ77では、文字列中の同じパターンを見つけ、より後に表れるものを過去のパターンを参照する情報に置き換えることで、圧縮を行います。具体的には、先頭から1文字ずつ見ていき、一致が無い場合は(-1, 0, 不一致文字)、あった場合は一致する文字数を調べて(先頭位置, 文字数, 不一致文字)を出力します(-1, 0の部分は、不一致を表す値であれば他のものでも構いません)。例えば

hello shallow

 という文字列があった場合の処理と出力結果は、以下のようになります。

処理
番号
処理内容出力
1'h'は以前に現れないので、一致しない。(-1, 0, 'h')
2'e'は以前に現れないので、一致しない。(-1, 0, 'e')
3'l'は以前に現れないので、一致しない。(-1, 0, 'l')
4'l'は元文字列の2番目に現れ、1文字だけ一致し、次の'o'は一致しない。(2, 1, 'o')
5' 'は以前に現れないので、一致しない。(-1, 0, ' ')
6's'は以前に現れないので、一致しない。(-1, 0, 's')
7'h'は元文字列の0番目現れ、1文字だけ一致し、次の'a'は一致しない。(0, 1, 'a')
8'l'は元文字列の2番目に現れ、さらに2文字一致し、次の'w'は一致しない。(2, 3, 'w')

 上記の処理番号と、元の文字列の対応は次の通り。処理によって圧縮された部分を赤字にしています。
12345678
helloshallow

 処理の結果、(位置, 文字数, 不一致文字)の3つ組は8個出力されたことになります。それぞれ2byteとしても、3*8*2で48byte、元の文字列は13文字で、1文字2byteとすると26byteです。これからわかるように、LZ77は同じパターンがある程度現れないと、効率よく圧縮できません。ただし長いテキストデータにはある程度同じパターンが出てくるものが多く、一定の圧縮効果は期待できます。

 また、大規模なテキストを考えると、一致を先頭から順に探していては、膨大な時間がかかってしまいます。そのため構築方法に工夫が必要ですが、一般的には
  • 一致を検索するために遡る文字数を制限する
  • 文字の出現位置をハッシュで保持する
 という方法がとられます。
 これらの対応を行い、上記TrieのTAIL配列(9.3MB)に対してLZ77を行なってみると、約85%に圧縮されました。但しTAIL配列は既に先頭一致で重複を省いた後の文字列なので、一般的にはもっと小さくなります。実際、Trieに格納する前のWikipedia日本語タイトル約1千万文字に対して適用すると、約70%になりました。
 コードは下記を参照して下さい。
 LZ77はシンプルながら強力なアルゴリズムで、その派生がたくさんあります。一般的に使われるのはLZSSという拡張のようで、これは常に3つ組を出力するのではなく、一致する場合は(true, 先頭位置, 文字数)、一致しない場合は(false, 不一致文字)を出力する事により、さらにムダを省くものとなっています。しかしこれもランダムアクセスが難しいため、Trie4JではLZSSをさらに拡張するか、LZ-Endを使うかのどちらかにしようと考えています。

2012/08/25

最新の各種トライ速度比較

trie4jの最新の実装で、Wikipedia日本語タイトル127万件を格納する速度(build)、全件を照合する速度(contains)、消費サイズ(size)を測ってみました。

クラスbuild(ms)contains(ms)size(MB)
java.util.HashSet417453160.4
java.util.TreeSet402261160.2
PatriciaTrie442244104.6
TailPatriciaTrie(SuffixTrieTail)1,220271100.8
TailPatriciaTrie(ConcatTail)51724186.0
MultilayerPatriciaTrie70438691.8
MultilayerPatriciaTrie(packed)2,82286682.9
DoubleArray47110648.5
TailDoubleArray(SuffixTrieTail)3,07817537.3
TailDoubleArray(ConcatTail)2,59715742.0
LOUDSTrie(SuffixTrieTail)77750818.1
LOUDSTrie(ConcatTail)23448322.9
  • 補足1 - 今回からbuild, contains共に正味の速度を測るようにした(前回まではWikipediaアーカイブからの要素取得も入っていた)ので、HashSetも前回に比べると速くなっている様に見えている。
  • 補足2 - TailPatriciaTrie(suffixTrieTail)のサイズが大きいのは、SuffixTrieTailBuilderのトライが消費している分がでかい(約23MB)。TailPatriciaTrieは要素追加に対応するので、SuffixTrieTailBuilderもトライを保持しておく必要がある。
  • 補足3 - MultilayerPatriciaTrie(packed)は、ラベルを2層目のトライに追い出した状態。追い出しに時間がかかる(2秒超)が、サイズは10MB弱小さくなる。但し以降要素の追加はできない。また、DoubleArray以降は構築に別のトライを必要とし(今回PatriciaTrieを使用)、構築後は要素の追加はできない(未実装)。
  • 補足4 - DoubleArrayやLOUDSTrieで構築後の要素追加を実装する方法がないわけではないが、実用的な速度で追加するのはかなり難しそう。特にWikipedia級のデータになると1要素ずつ何万件もずらすような操作が発生してしまい、性能が出ない。
  • 補足5 - DoubleArrayの速度が劇的に改善してるのは、文字へのコード採番方式を変更したため。今までHashMapを使っていたが、TreeSet(総数カウント、列挙用)とchar[Character.MAX_VALUE](コード変換テーブル)の2つに置き換えた。

意外とHashSetとTreeSetはがんばってるんだなという印象。Trieの利点であるcommonPrefixSearchやpredictiveSearchは使えないけど。あとメモリ消費はやっぱりでかい。あと、HashSetの方が速いと思ってたんだけど、意外にTreeSetの方が速かった。メモリ消費もこの2つでは変わらない。

MultilayerPatriciaTrieは結構実装がんばってるんだけど、packしない前(要素追加可能)はTailPatriciaTrie(concatTail)に負けてるし、pack後(要素追加不可)はDoubleArray, LOUDSTrieにぼろ負け。結構トリッキーな実装してるし、実装ほんとに苦労したから残念なんだけど、現状存在意義無さそう。experimental状態(src.kitchensink)にしようかな。

あとTailDoubleArrayが遅いのは、DoubleArrayと比較して、空き要素の検索に時間がかかるようになるため。DoubleArrayだと1文字だけのラベル、子供1つだけというノードが大量に存在し、それがbase/checkの隙間を埋めてくれる。一方TailDoubleArrayはラベルをTAIL配列に追い出すことによってそういうノードがなくなるため、空きノードの検索対象が増え、速度が遅くなる。

今のところ、

  • 要素動的追加必須 -> TailPatriciaTrie(ConcatTail)
  • 検索速度重視 -> DoubleArray
  • サイズ重視 -> LOUDSTrie(SuffixTrieTail)
と使い分けるのが良さそうです。

LOUDSTrie実装してみた

よく考えたらblogに載せてなかった(TwitterやGoogle+でつぶやいて載せた気になってた・・)ので、改めて。

LOUDSはLevel-order Unary Degree Sequenceの略。詳しくは書籍「日本語入力を支える技術」(amazon)や下記サイトを参照してください。

要は木構造を01のビット列で表そうというデータ構造で、遅いけどかなり小さく圧縮できる。ただでさえJavaではオブジェクトがメモリを食う(何もフィールド無くてもポインタ2個分消費する)ので、木構造がビット列で表現できれば、絶大なサイズ削減効果があります。

既に構築済みのトライからLOUDS Trieを構築するのは結構簡単で、幅優先でトライを辿り、子の数だけ1を追加、最後に0を追加というのを繰り返すだけ。trie4jではこんな感じに実装してます。

https://github.com/takawitter/trie4j/blob/master/trie4j/src/org/trie4j/louds/LOUDSTrie.java#L53

構築済みのトライを辿るには、ルートから、

  1. 左端の子ノードの位置を求める(簡潔ビット配列のselect0操作)
  2. 右端の子ノードの位置を求める(簡潔ビット配列のselect0操作)
  3. 左端の子ノードのIDを求める(簡潔ビット配列のrank1操作)
  4. 子ノードから適切なラベルを持つものを探す
  5. 子ノードのTAIL配列(2番目以降のラベル文字列)を得て検索文字列と比較

という感じで子ノードの検索、文字列比較を行っていく。これを高速に行うのが結構面倒で、select0やrank1をどう高速化するか、ビット配列の実装が肝になります。

trie4jでは、select0、rank1共にキャッシュを作って高速化してます。また、上記2の処理専用にnext0という操作を簡潔ビット配列クラス(SuccinctBitVector)に追加してます。そこらへんの工夫により、127万件の要素を照合するのに500ms程度と、まずまずの速度を確保してます(もちろんC++で実装されたライブラリに比べれば遅いだろうけど)。

trie4jの実装はこちら https://github.com/takawitter/trie4jからどうぞ。BuildHive使って、最新のスナップショットtrie4j-SNAPSHOT.jarも常にダウンロードできる状態にしてあります。

2012/06/15

各種トライの速度比較

6/17 GCの影響をできるだけ排除するように実装し、測り直しました。

LOUDSTrieの実装が落ち着いてきたので、パトリシアトライ、ダブルアレイ、LOUDSトライの構築、contains速度を測ってみました。

何回か測ってみたけど、だいたいこんな感じ。

構築(ms)contains(ms)
java.util.HashSet1,042816
PatriciaTrie(UTF-16 char[])891662
MultilayerPatriciaTrie(多層トライ)3,5381,354
TailCompactionDoubleArray5,082858
OptimizedTailCompactionDoubleArray5,7601,022
LOUDSTrie9221,025

CPUはCore i7 2.5GHz。データはWikipedia日本語タイトル127万件。パトリシアトライの実装はここ、ダブルアレイの実装はここを参照。DoubleArray2つとLOUDSTrieはPatriciaTrieを使って構築してるので、実際の構築時間はPatriciaTrieの分も必要です。

意外とLOUDSTrieが構築、検索共に頑張ってる印象。というかDoubleArrayってもっと速いんじゃなかったっけ。実装が悪いのかも知れませんが。

実装はTrie4J(GitHub)にて公開してます。

2012/05/16

Wikipedia英語タイトルも格納してみた

Wikipedia英語版のタイトル一覧(2012/4/3版。9,310,564エントリ)も格納して、サイズ測ってみました。
実装配列要素数(base/check等)TAIL配列要素数全体サイズ
OptimizedTailCompactionDoubleArray12,710,31115,699,525162,867,250

各種トライの性能を比較した記事「2011-01-10 marisa-trie 強いな」と比較してみると、エントリ数が1.5倍弱になってることを考慮して、darts-cloneに近いメモリ効率をたたき出してると思う。ただdarts-cloneはTAILをDAWG(Directed Acyclic Word Graph)で保持してるようなので、今のトライ使ったTAIL圧縮だと勝てないかも知れない。あと文字をcharで保持してたり、違いはいろいろ。まぁこっちはJavaなので既に速度的にはだいぶ水開けられてるし(Corei72.5GHzで24秒程度)、元よりあまり有効な比較にはならないかも知れない。構築途中で1.3GBくらいメモリ消費するしねー。

ダブルアレイのサイズ比較

今勉強&実装してるダブルアレイのサイズを測ってみました。詳しい話はまた今度(というつつパトリシアトライの解説もまだ途中だけど・・・)。

データはパトリシアトライと同じく、Wikipedia日本語タイトルの127万エントリ。文字列は全てcharで保持してます。また、予めパトリシアトライを構築し、それをもとにダブルアレイを構築してます。

以下の表にまとめます。
実装配列要素数(base/check等)TAIL配列要素数全体サイズ
DoubleArray*15,668,704048,547,151
TailDoubleArray*21,679,6164,651,339(capacity: 4,718,590)31,947,268
TailCompactionDoubleArray*31,679,6161,797,866(capacity: 2,359,294)27,226,058
OptimizedTailCompactionDoubleArray*41,519,6791,797,86621,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で公開してます。

2012/04/19

パトリシアトライのサイズ比較

 記事が前後しますが。気になったのでちょっと調べてみました。トライの内部形式をchar[]からbyte[]にすることでどれくらいインパクトがあるのか。byte[]にする際、UTF-8、Shift-JIS、EUC、JIS(ISO2022JP)でどのような違いがあるのか。

以下の表にまとめます。

トライのノード文字配列数
エンコーディング(内部形式)サイズサイズ全体サイズ
ISO-2022-JP(byte[])1,763,96758,210,9111,764,14241,189,910123,904,937
UTF-8(byte[])1,736,91057,318,0301,737,08340,404,315123,095,316
Shift_JIS(byte[])1,639,06454,089,1121,639,22935,103,790112,335,651
EUC_JP(byte[])1,633,86553,917,5451,634,03135,089,059112,013,060
UTF-16(char[])1,513,46948,431,0081,515,34635,043,030103,472,496
UTF-16(char[])+フィールド最適化(*1)1,513,469(*3)39,664,136(*4)1,515,33834,688,31291,774,563
UTF-16(char[])+フィールド最適化(*1)+多層トライ(*2)1,995,303(*3)55,082,824(*4)483,714(*5)10,345,546(*5)82,870,660

*1 - 子ノードを持たない/1つだけ/2つ以上、終端である/ないの組み合わせでそれぞれ最適なフィールドを持つノードクラスを使用する。
*2 - ラベルを逆順に持つ圧縮用トライを用意(参考: 多層トライの実験結果 - やた@はてな日記)。本来のトライのノードもその圧縮用トライのノードをフィールドに持つものを使用。
*3 - 全ノードの合計数。
*4 - 全ノードの合計サイズ。
*5 - 文字配列は圧縮用トライ内のもの。本来のトライには文字配列を持たない。

いずれもWikipedia日本語タイトル127.3万件を格納した結果です。フィールド最適化+多層トライのデータでは、圧縮用トライのノードや文字配列のサイズも加算されています。

こうして見てみると、多層トライがいかに圧縮率が高いかと、オブジェクト数の増減がいかにインパクトがあるかがわかります。せっかく多層トライで圧縮したメモリサイズ(24MB)も、ノードオブジェクト数の増加でその効果は半減しています。

結論: Javaではオブジェクト数大事

多層トライの実装はGitHubで公開してます。org.trie4j.trie.patricia.multilayer.MultilayerPatriciaTrieがフィールド最適化と多層トライの実装で、全タイトル挿入後のデータ、挿入してからpack(), morePack()を呼び出した後のデータが表の下2つです。packで多層トライでの圧縮、morePackで多層トライのノードのフィールド最適化を行います(morePack遅いです)。

下記にVisualVMでの主要なオブジェクトのスナップショットを。まずはUTF-16のフィールド最適化のみ。

次にフィールド最適化+多層トライ(もフィールド最適化)。

サイズをオブジェクト数で割るとわかるけど、1オブジェクトで24とか32バイト消費してます。フィールド最適化を行わない場合、40バイト消費することもあります(64bit環境で。32bitなら半分になります。)

結論: Javaではオブジェクト数大事(2回目)

しかしこの画像の小ささ何とかならんかな。

2012/04/13

Trie4J - Java Patricia Trie Implementation

ちょこちょことまとめているパトリシアトライのJava実装ですが、現状のソースをGitHubにあげました。

https://github.com/takawitter/trie4j

記事では簡単のためラベルをString, 子ノードをList<String>で管理しているものを紹介していますが、この実装では
  • ラベルをchar[]、子ノードをNode[]で管理する、org.trie4j.patricia.simple.PatriciaTrie
  • ノードの状態(終端かどうか、子ノードを持つかどうかなど)に応じてクラスを変更し、かつ多層トライによるサイズ圧縮に対応する、org.trie4j.patricia.multilayer.MultilayerPatriciaTrie
の2つが含まれています(もう一つありますが、あまり効果無いのでそのうち消します)。 詳しい解説はまた後ほど(predictive search書けてから)。

JavaでPatriciaTrieで各種検索

前回からの続きで、今回は検索メソッドを実装してみます。実装するのはこの2つ。
  • common prefix search
  • predictive search
common prefix searchは、クエリ"東京国際フォーラム"が与えられた時に、"東"、"東京"、"東京国"、"東京国際フォーラム"をトライから列挙するという検索です(実際これらの単語はWikipedia日本語版にあります)。
上図で赤枠で示したノードをたどりながら、終端ノードを列挙していく処理になります。先頭からノードをたどり、ノードのラベルとクエリを比較し、ノードのラベルを比較し終えたら、終端ノードであれば列挙、そして子ノードから残りのクエリの比較を行う候補を探し、そのノードに対しても同じ処理をしていきます。一方向に辿っていくだけなので再帰は必要なく、単純なループで実現できます。コードを下記に示します。
public Iterable<String> commonPrefixSearch(String query) {
 List<String> ret = new ArrayList<String>(); // 結果配列
 int cur = 0; // query内の照合位置
 Node node = root;
 while(node != null){
  String letters = node.getLetters();
  if(letters.length() > (query.length() - cur)) return ret; // 残りの文字列よりノードのラベルのほうが長ければマッチしないので終了
  for(int i = 0; i < letters.length(); i++){
   if(letters.charAt(i) != query.charAt(cur + i)) return ret;
  }
  if(node.isTerminated()){
   ret.add(query.substring(0 , cur + letters.length()));
  }
  cur += letters.length();
  if(query.length() == cur) return ret;
  node = node.getChild(query.charAt(cur));
 }
 return ret;
}
単純なwhileループで、着目するノード(変数node)を書き換えながら処理を行なっています。
predictive searchは、指定された文字列(prefix)を前方一致検索します。例えば"東京国"が指定されれば、"東京国"、"東京国税局"、"東京国際フォーラム"、"東京国際マラソン"が列挙されます。
上図赤枠のノードが列挙対象になります。まず指定されたprefixを含むノードを探し、見つかったノード以降のノードを全て列挙します。この列挙は部分木全部が対象になるので、再帰で実装するのが楽です(再帰が嫌な場合はQueue使ってもOK)。コードはこんな感じ。
/**
 * 部分木の列挙をする再帰関数。
 */
private static void enumLetters(Node node, String prefix, List<String> letters){
 List<node> children = node.getChildren();
 if(children == null) return;
 for(Node child : children){
  String text = prefix + child.getLetters();
  if(child.isTerminated()) letters.add(text);
  enumLetters(child, text, letters);
 }
}

public Iterable<String> predictiveSearch(String prefix) {
 char[] prefixChars = prefix.toCharArray();
 int cur = 0; // prefixChars内の照合位置
 Node node = root;
 while(node != null){
  String letters = node.getLetters();
  int n = Math.min(letters.length(), prefixChars.length - cur); // 共通部分の比較のためnは短い方に合わせる。
  for(int i = 0; i < n; i++){
   if(letters.charAt(i) != prefixChars[cur + i]){
    return Collections.emptyList();
   }
  }
  cur += n;
  if(prefixChars.length == cur){ // prefixCharsの比較が終われば、あとは部分木の列挙
   List<String> ret = new ArrayList<String>();
   prefix += letters.substring(n);
   if(node.isTerminated()) ret.add(prefix);
   enumLetters(node, prefix, ret);
   return ret;
  }
  // 比較がまだ終わって無ければ、子ノードを探して検索を継続
  node = node.getChild(prefixChars[cur]);
 }
 return Collections.emptyList();
}

2012/03/15

JavaでPatriciaTrieを実装してみた

書籍「日本語入力を支える技術」を読んでテンション上がったので、Javaでパトリシアトライを実装してみました(本当はビットベクタを実装したかったけどとりあえずダブル配列からやろうと思ってそれでも挫折してPatriciaTrieから入門した次第)。また、このエントリで紹介するコードはパトリシアトライの説明用で、全然最適化が行われていないので、メモリ効率も速度も良くないです。そのあたりを最適化したコードは、別のエントリで紹介する予定です。
(↓※アソシエイトIDあり)
ちなみにPatriciaはPractical Algorithm to Retrieve Information Coded in Alphanumericの略らしい(参考: wikipedia:基数木)。構造は至ってシンプルで、いろいろと実装例があります。
wikipediaのパトリシアトライの説明から図を借りると、その構造はこんな感じ:

ちょっとわかりにくいので、形を変えてみると:
空間効率的には、上図右側の各文字列の灰色で示した部分が他の文字列と共有されるので、かなりデータ量は小さくて済みます(wikipedia日本語タイトルデータで50%程度の効率化)。また、検索効率は、検索したい文字列を先頭から順に探して行くだけなので、最悪O(k)で済みます(kは文字列長)。実際は子ノードの探索方法によっては検索速度に影響が出るけど、それはまた後で。

構造がわかったところで、それを表現するクラスを定義します。

public class Node{
 // コンストラクタ、getter、setterは割愛
 private String letters;
 private List<node> children;
 private boolean terminated;
}

各ノードで保持する文字列は変数lettersに、子ノードは変数childrenに格納します。加えて、そのノードで文字列が終わっているかどうかを保持する変数terminatedを設けます。これは、例えば上図の文字列に加え、"rom"や"rubic"が加わった場合、ツリーの途中で文字列が終わることになるので、それに対応するため。上図に、文字列の終端という概念を加えて、あとツリーの途中で文字列が終わるケースを示すために"rom"と"rubic"も挿入されたとして、終端のノード(terminated==true)を太枠で表すと、下図のようになります。


終端については、終端文字列を設けて('$'とか)、それを終端となるノードにぶら下げるのが一般的のようなんですが、コードをシンプルにしたかったので、上記実装にしました(実際はいくつか工夫の余地はあり、今できるだけメモリを使わない方法をトライ中なんですが、それは完成した後に詳しく書く予定)。

さて、まずはある文字列がトライに含まれるかどうかを判定する、containsメソッドを実装してみます。考え方としては、
  1. 自ノードに文字列が設定されている場合、検索文字列との比較を行う。
  2. 自ノードの文字列だけでは比較が終わらない場合、子ノードを探す。
  3. 子ノードが見つかった場合、子ノードに対して同じ操作を行う
という感じで、検索対象文字列の先頭から、ノード内の文字列との比較を行い、どんどん子ノードに降りて行きます。コードは下記。

boolean contains(String word){
 int rest = word.length();
 int n = letters.length();
 if(n > rest) return false; // 自ノードの文字列のほうが長ければ比較失敗。
 for(int i = 0; i < n; i++){
  if(letters.charAt(i) != word.charAt(i)) return false;
 }
 if(n == rest) return terminated; // 文字列が同じであれば、終端かどうかを返す。
 word = word.substring(n); // 比較済み文字列を捨てる。
 if(children != null){
  char c = word.charAt(0); // 子ノードを探す。(*1)
  for(Node n : children){
   if(n.letters.charAt(0) == c){
    return n.contains(word); // 見つかれば、containsを呼び出す。
   }
  }
 }
 return false;
}
自ノードの文字列(letters)、子ノード(children)の順で処理を行なっています。子ノードの検索(*1)は線形探索していて、当然遅いので、実用で使うには、頻度順に並べるとか、childrenはソートしておいて2分探索を使うとか、ハッシュを使うとかする必要がありますが、今は割愛。データ量が膨大になる場合は、各ノードでハッシュを持つとメモリ消費が問題になる可能性があるので、2分探索か頻度順が現実的かと思います(そのぶん構築コストは高いけど)。実際wikipediaの日本語タイトルを挿入してみると、線形探索と2分探索では、処理にかかる時間の桁が違いました(50万件の検索で線形探索1762ms, 2分探索201ms)。

ちなみに2分探索だと、コードは下記のようになります。
boolean contains(String word){
 int rest = word.length();
 int n = letters.length();
 if(n > rest) return false; // 自ノードの文字列のほうが長ければ比較失敗。
 for(int i = 0; i < n; i++){
  if(letters.charAt(i) != word.charAt(i)) return false;
 }
 if(n == rest) return terminated; // 文字列が同じであれば、終端かどうかを返す。
 word = word.substring(n); // 比較済み文字列を捨てる。
 if(children != null){
  char c = word.charAt(0); // 2分探索で子ノードを探す
  int end = children.size();
  int start = 0;
  while(start < end){
   int i = (start + end) / 2;
   Node child = children.get(i);
   int d = c - child.getLetters().charAt(0);
   if(d == 0){
    return child.contains(word);
   }
   if(d < 0){
    end = i;
   } else if(start == i){
    break;
   } else{
    start = i;
   }
  }
 }
 return false;
}

次に要素の挿入です。おおまかに以下の流れで実装しました。
  1. ノード内の文字列(thisLetters)か比較対象の文字列(letters)の短い方の文字数分比較
  2. 全て比較成功
    1. thisLettersとlettersの長さが同じであれば、ノードを終端にして(terminated = true)終了(a)
    2. thisLettersの方が長ければ、ノードを分割して終了(b)
    3. lettersの方が長ければ、比較済み文字列を捨てる
    4. 新しいlettersの先頭文字とマッチする先頭文字を持つ子ノードを探す
    5. 存在すれば、その子ノードに対してinsertChildを呼び出して終了(c)
    6. 存在しなければ、新しい子ノードを作成して追加し終了(d)
  3. 途中で比較が止まった場合、その位置でノードを分割し、lettersの残りも子ノードとして追加する。(e)
コードは下記のようになります。
public void insertChild(String letters){
   int n = Math.min(letters.length(), this.letters.length());
   int i = 0;
   while(i < n && (letters.charAt(i) == this.letters.charAt(i))) i++;
   if(i == n){
    if(letters.length() == this.letters.length()){
     terminated = true; // (a)
     return;
    }
    if(letters.length() < this.letters.length()){
     Node node = new Node( // (b)
       this.letters.substring(letters.length())
       , this.children, this.terminated);
     this.letters = letters;
     this.children = new ArrayList<Node>(1);
     this.children.add(node);
     ((ArrayList<Node>)this.children).trimToSize();
     this.terminated = true;
     return;
    }
    letters = letters.substring(i);
    int index = 0;
    for(Node child : children){
     int c = letters.charAt(0) - child.letters.charAt(0);
     if(c < 0) break;
     if(c == 0){
      child.insertChild(letters); // (c)
      return;
     }
     index++;
    }
    this.children.add(index, new Node(letters)); // (d)
    ((ArrayList<Node>)this.children).trimToSize();
    return;
   }
   String newLetter1 = this.letters.substring(0, i); // (e)
   String newLetter2 = this.letters.substring(i);
   String newLetter3 = letters.substring(i);
   List<Node> newChildren = new ArrayList<Node>(2);
   if(newLetter2.charAt(0) < newLetter3.charAt(0)){
    newChildren.add(new Node(newLetter2, this.children, this.terminated));
    newChildren.add(new Node(newLetter3));
   } else{
    newChildren.add(new Node(newLetter3));
    newChildren.add(new Node(newLetter2, this.children, this.terminated));
   }
   this.letters = newLetter1;
   this.terminated = false;
   this.children = newChildren;
  }

なお、子ノードは全て昇順でソートされるようにして、探索は線型探索を使っています(ここも2分探索にすれば高速化できる)。また、メモリ利用量を抑えるため、子ノードの配列は正味のサイズだけ確保するようにしています(その分メモリリアロケーションが増えて速度は落ちているはず)。

ちなみに、上記のコードでは、VMの最大メモリ容量が128MBだと、Wikipedia日本語タイトル(127万件)はメモリに載りません(180MB程度必要です。ちなみにlettersをchar[]に、childrenをArrayListではなくNode[]に変えれば載ります)。ですが、まぁ一応機能はするので、次はTrieの特徴であるcommon prefix searchを実装してみます。