erika-trieのtail部分にトライを導入してみた

LOUDSを用いたトライのライブラリであるerika-trieを改良した。具体的にはux-trieやmarisa-trieで使われているトライのtail部分を逆向きトライで持たせる、という手法を導入してみた。さしあたり日本語wikipediaを用いた評価をしたのでメモしておく。

erika-trie(実用版)とキーワード抽出ツールerika_extractを作ったよ - EchizenBlog-Zwei
LOUDSトライのライブラリの性能を比較してみた - EchizenBlog-Zwei
(続)LOUDSトライのライブラリの性能を比較してみた - EchizenBlog-Zwei

前回の実験時にはtail部分もすべてノードとして持たせていたのだが、この部分を文字列orトライで選択可能にした。文字列のほうが高速だが、トライのほうがデータサイズは小さくなる。
データサイズについては以下のとおり。トライを用いた場合はux-trieと同程度にまで小さくなった。

元データ			: 26,960,268 byte
marisa-trie		: 7,199,728 byte
ux-trie			: 10,364,932 byte
erika-trie(旧)		: 18,866,382 byte
erika-trie(文字列)	: 15,145,131 byte
erika-trie(トライ)	: 10,859,269 byte

common-prefix-searchの検索速度は以下のとおり。トライを用いた場合の速度低下が気になるがそれでもux-trieよりは速い。

marisa-trie		: 11.9 sec
ux-trie			: 57.2 sec
erika-trie(旧)		: 20.7 sec
erika-trie(文字列)	: 22.3 sec
erika-trie(トライ)	: 31.6 sec

predictive-searchの検索速度は以下のとおり。こちらはトライを用いた場合に絶望的なほど遅くなる。erika-trieはtailのトライからの文字列復元が高速に行えないので、それが影響している気がする(すみません。ちゃんと調べてないです)。

marisa-trie		: 13.5 sec
ux-trie			: 45.8 sec
erika-trie(旧)		: 28.4 sec
erika-trie(文字列)	: 24.2 sec
erika-trie(トライ)	: 62.4 sec

というわけで文字列版のerika-trieは速度への影響が小さいままでデータサイズが小さくなったので結構良い結果が出た気がする。一方でトライ版はデータサイズを小さくした反面predictive-searchに非常に大きな悪影響がでてしまった。うむむ。
あとmarisa-trieに勝てる気がしないんだけど、どうなってるのこれ・・・。