二バイトコード(UTF-16)を用いてDoubleArrayを構築する際のトライ探索方法
これまではDoubleArrayを構築する際には、ソースとなるトライのノードを深さ優先順で探索しDoubleArrayへと変換していた。
トライのキーセットとなる文字列のエンコーディングがUTF-8等の一バイトコード(?)の場合は深さ優先順探索でも特に問題はないが、UTF-16等の二バイトコード文字列に同様の探索順を採用すると、最終的な配列(DoubleArray)中に占める空き要素(未使用要素)の数が多くなる、という問題がある。※ 少なくとも自分の経験上は。
優先順位探索
二バイトコード文字列をキーとする場合は深さ優先ではなく、各ノードの子ノードの数の多い順にトライを探索(+DoubleArrayに変換)した方が、サイズ効率が良くなる(ように思う)。
以下は、深さ優先探索と子ノード多い順探索でのDoubleArrayのサイズの違い。
※ DoubleArray構築にはjada-0.1.3を用いている
※ キーセットには、MeCabのサイトで配布されているIPADICから取り出した約33万単語を用いている
| 配列サイズ | 未使用要素数 | 配列使用率 | 構築時間 | |
| jada-0.1.3(深さ優先) | 512918 | 102809 | 80.0% | 2.43秒 |
| jada-0.1.3-priority-first(子ノード多い順) | 415434 | 5325 | 98.7% | 10.96秒 |
※ 子ノードの数が多いということは、一般にDoubleArrayに変換した際に生じるフラグメントが多い、ということ。子ノードの多い順探索では、最初の方で生じたフラグメントを、最後の方の小さなノードで埋めていく形になるので、領域を効率的に使用できる(おそらく)。
反面、後者では構築時間が前者に比べてかなり長くなってしまっている*1ので、前者を完全に代替するものとならないが、構築時間よりもサイズが重要なケースでは有用だと思われる*2。
なお、二バイトコードを用いたDoubleArrayの構築に関しては、以下も参照のこと。
・jada: 二バイトコード(UTF-16)を用いてDoubleArrayを構築する際の最適化メモ - sileの日記
