Mozc(Google 日本語入力)のコードを読んだメモ(2)

　TSFのメモとMozcのコード読みメモを比較すると、書くのにかかった時間は4,5倍は違う（TSFの方が大変だった）のに、ブックマーク数は逆転どころか桁が2桁違う事になりそうだなぁ、と、あらためてGoogleの人気のすごさを体感した。小町さんは こんなに日本語入力って注目されるんだと嬉しい気持ち と書いておられるが、個人的な感触としては、日本語入力が注目されているというよりはGoogleが注目されている、というあたりが悲しい現実なのではないかと思う。とは言え、自分もChaSenのコードとか読んだことない（mecabは少しだけ読んだ事があるけど）ので、あんまり人の事は言えないが。
　さて、週末にバイグラムコストの保存方法についても現実逃避で読んでしまったので、ついでに解説を試みる。
　前のメモにも書いたが、Google日本語入力のコストモデルは「品詞バイグラム+単語ユニグラム」という構成になっている。品詞バイグラムという事は、接続コストは左側の単語の品詞と右側の単語の品詞で決まる。イメージとしては表の形になっている訳だが、これを単純に1次元配列にして保存するとメモリをかなり食う。Google日本語入力の品詞は語彙化がかなり多いため、3000種類ぐらいある。また、コストは2Byteの整数で保存されているので、単純に保存すると、3000x3000x2 = 18MBものメモリを必要とする。しかし、この表の中の値は大半が同じ値となるので、かなり圧縮が効くはずであるし、実際にMozcでは圧縮した形で保存されている。これを実現するのがSparseArrayImageクラスである。
　ソースコードの位置は src/storage/sparse_array_image.cc のあたりである。重要なのは、この中の SparseArrayImage::Peek(uint32 index) と SparseArrayImage::GetValue(int nth) の2つである。
　使い方は、src/converter/connector.ccのSparseConnector::GetTransitionCostの辺りに書いてある。 だいたい以下のようなコードである。

  int pos = array_image_->Peek(EncodeKey(rid, lid));
  if (pos == invalidIndex)
    return default_cost;
  return array_image_->GetValue(pos);

　EncodeKey(rid, lid) でridとlidのペアをuint32の値に押し込めて（rid, lidはuint16なので、たぶんEncodeKeyはreturn rid << 16 + lidしてるだけ）から、Peekに渡すとintの値が帰ってきて、さらにそれSparseArrayImage::GetValueに渡すとコストの値が返ってくる。
　SparseArrayImageのイメージは、未定義の値を許すスカスカな1次元配列である。スカスカなので、例えば、array[0], array[1], array[5] には値が入っているが、array[2]からarray[4]までの値は未定義、とかそういう感じになる。これを実現するための方法はいくつも考えられるが、SparseArrayImageでは、値自体は普通の配列に保存しておいて、外部から見えるインデックスとその普通の配列へのインデックスの対応を別の特殊なデータ構造に保存している。Peekはこの"特殊なデータ構造"を使って外部インデックスから内部インデックスへの対応を返す関数で、GetValueは単純に与えられた内部インデックスに対応する値を返す関数である。明らかにPeekの方がやっていることが難しく、GetValueは簡単である。
　Peekはどうやってこの対応を求めているのかという事でコードを読むと、"特殊なデータ構造" としてTrieを使っている事がわかる。uint32_tの外部インデックスの値を3bit毎に分割してTrieの辺についた文字として扱い、この文字を使ってTrieを降ってゆき、木の一番下のレベルで左側から何番目にいるかが、内部インデックスの値となる。
　Trie木は高さ毎にbit配列が用意されている。木のどの高さに居るかというlevelと、左から何番目のノードに居るかというオフセットがわかれば自分が木のどこをみているのかがわかる。次のノードがどこにあるかはarray->Rank(offset + 文字)という操作でわかるようなのだが、なぜこれでうまくいくのかはもうちょっとちゃんと考えてみないとわからない。
　以下、疑問点とか感想とか。

  • Peekの実装は、array[index]が1ならrank(index)を返して、それ以外の場合はinvalidIndexを返すとすれば、Trieとか作らずに実現できそうな気がする。しかも、Rankを1回しか呼ばないのでそっちの方が速そう。ただ、単純にビットベクターを保存するとそれだけで3000*3000/8 = 1.1MB強使うので、メモリがちょっと勿体ないかな。
  • GetValueの型がGetValue(uint32 index)になっている。GetValueが内部でPeekを呼び出すという仕様でも良さそうだが、そうなっていないのはなぜ？おそらく拡張性を考えての設計なのだろうが、こうすることでどういう拡張性が与えられるのか？
  • 接続コストとして取り得る値にはかなりの頻度のばらつきがあるだろうから、WaveletTreeのようなバイト列圧縮手法を使ってみたらもっと縮まないだろうか？
    • 実際に実験をしてみたらいい話なんだけど、気力と時間が足りない。
  • 実装コストとメリットのバランスの取り方がうまいと思ったが、こういうのって見習おうと思ってもなかなか身につくもんでもないような気もする。