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

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

クラス	build(ms)	contains(ms)	size(MB)
java.util.HashSet	417	453	160.4
java.util.TreeSet	402	261	160.2
PatriciaTrie	442	244	104.6
TailPatriciaTrie(SuffixTrieTail)	1,220	271	100.8
TailPatriciaTrie(ConcatTail)	517	241	86.0
MultilayerPatriciaTrie	704	386	91.8
MultilayerPatriciaTrie(packed)	2,822	866	82.9
DoubleArray	471	106	48.5
TailDoubleArray(SuffixTrieTail)	3,078	175	37.3
TailDoubleArray(ConcatTail)	2,597	157	42.0
LOUDSTrie(SuffixTrieTail)	777	508	18.1
LOUDSTrie(ConcatTail)	234	483	22.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)

と使い分けるのが良さそうです。