WhiteDog@Blog: パトリシアトライのサイズ比較

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

以下の表にまとめます。

	トライのノード		文字配列数
エンコーディング(内部形式)	数	サイズ	数	サイズ	全体サイズ
ISO-2022-JP(byte[])	1,763,967	58,210,911	1,764,142	41,189,910	123,904,937
UTF-8(byte[])	1,736,910	57,318,030	1,737,083	40,404,315	123,095,316
Shift_JIS(byte[])	1,639,064	54,089,112	1,639,229	35,103,790	112,335,651
EUC_JP(byte[])	1,633,865	53,917,545	1,634,031	35,089,059	112,013,060
UTF-16(char[])	1,513,469	48,431,008	1,515,346	35,043,030	103,472,496
UTF-16(char[])+フィールド最適化^(*1)	1,513,469^(*3)	39,664,136^(*4)	1,515,338	34,688,312	91,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のフィールド最適化のみ。