jada: 二バイトコード(UTF-16)を用いてDoubleArrayを構築する際の最適化メモ
二バイトコード
Javaは文字を二バイトコード(UTF-16)で表現しているので、jadaで実装されたトライの各ノードで(遷移に)用いられるコード値の最大値も0xFFFFとなっている。
トライの遷移コードが一バイトであっても二バイトであっても、実装自体はほとんど変わらないのだが、後者の場合、前者に比べて構築に掛かる時間が長くなるという難点がある。
遷移に用いられるコード値の幅(最大値)が大きくなると、各ノードから派生する子ノード(遷移先ノード)群の格納先(空き/使用可能/未割り当てのノード)を探す処理が遅くなり-これはトライ(DoubleArray)構築におけるボトルネックでもあるので-ひいてはトライ構築全体も遅くなる、とった感じらしい。
試したこと
で、その対策としてjadaで試したこと。
- 文字が二バイトコード(0〜65535)で表現されているといっても、実際にはその全てが(トライ構築時に用いられるキーセット中で)使用されている訳ではないので、実際に使われている文字にだけ値(コード値)を割り振るように変更。
- また、キーセットに含まれる各文字の出現頻度をあらかじめカウントしておき、コード値は、高頻度の文字から昇順に割り振る。
- ただし例外として、出現頻度が0の文字には、コード値として一律に0を割り振る。
つまりは、UTF-16のコード値をそのまま使わず、実際に使用されている文字にだけ(出現頻度順に)コード値を割り当てるようにする、ということ。
こうすれば、各ノードからの遷移に用いられるコード群の値のバラツキが抑えられるので、空きノードの探索も効率的になる(と期待した)。
結果
結果。
一応、効果はあった。
以下、MeCabのサイトで配布されているIPADICの単語セットを入力とした場合の構築時間。
## 単語セット作成 ## # 1] mecab-ipadic-2.7.0-20070801.tar.gz をMeCabのサイトより入手/解凍する # 2] 単語名を抽出して、ソート and ユニーク、する。 $ cut -d, -f1 mecab-ipadic-2.7.0-20070801/*.csv | nkf -w | LC_ALL=C sort | LC_ALL=C uniq > words # 単語数 $ wc -l words 325871 words
構築時間:
| 構築所要時間(秒) | |
| UTF-16*1 | 1.825s |
| jada-1.2 | 1.134s |
| UTF-8*2 | 0.608s |
実際にどの程度速くなるかは、その時のキーセットに大きく依存する*3と思われるが、今回の場合は所要時間が半分近くになっている。 それでもまだ、一バイトコード(UTF-8)を使った場合に比べるとだいぶ遅いけど ...。
あと、結果は割愛するが、今回試したことによるトライのキー検索速度に対する影響はほとんどなさそう。
