読者です 読者をやめる 読者になる 読者になる

二バイトコード(UTF-16)を用いてDoubleArrayを構築する際のトライ探索方法

Java algorithm

これまではDoubleArrayを構築する際には、ソースとなるトライのノードを深さ優先順で探索しDoubleArrayへと変換していた。
トライのキーセットとなる文字列のエンコーディングUTF-8等の一バイトコード(?)の場合は深さ優先順探索でも特に問題はないが、UTF-16等の二バイトコード文字列に同様の探索順を採用すると、最終的な配列(DoubleArray)中に占める空き要素(未使用要素)の数が多くなる、という問題がある。※ 少なくとも自分の経験上は。

優先順位探索

バイトコード文字列をキーとする場合は深さ優先ではなく、各ノードの子ノードの数の多い順にトライを探索(+DoubleArrayに変換)した方が、サイズ効率が良くなる(ように思う)


以下は、深さ優先探索と子ノード多い順探索でのDoubleArrayのサイズの違い。
※ DoubleArray構築にはjada-0.1.3を用いている
※ キーセットには、MeCabのサイトで配布されているIPADICから取り出した約33万単語を用いている

配列サイズ未使用要素数配列使用率構築時間
jada-0.1.3(深さ優先)51291810280980.0%2.43秒
jada-0.1.3-priority-first(子ノード多い順)415434532598.7%10.96秒
深さ優先探索の場合はDoubleArray全体の二割が未使用領域となっているが、子ノードの多い順の場合はほとんど無駄な領域がない。
※ 子ノードの数が多いということは、一般にDoubleArrayに変換した際に生じるフラグメントが多い、ということ。子ノードの多い順探索では、最初の方で生じたフラグメントを、最後の方の小さなノードで埋めていく形になるので、領域を効率的に使用できる(おそらく)。
反面、後者では構築時間が前者に比べてかなり長くなってしまっている*1ので、前者を完全に代替するものとならないが、構築時間よりもサイズが重要なケースでは有用だと思われる*2


なお、二バイトコードを用いたDoubleArrayの構築に関しては、以下も参照のこと。
jada: 二バイトコード(UTF-16)を用いてDoubleArrayを構築する際の最適化メモ - sileの日記

*1:jada-0.1.3-priority-firstは、java-0.1.3のトライ探索部分を、単純に変更しただけ。ノード割り当て部分を、子ノードの数多い順探索用に工夫すれば、もしかしたらもっと速くなるのかもしれない。

*2:例えばGomokuでは、DoubleArrayの構築に今回書いた方法を使用している。