文法圧縮を使った完備辞書(簡潔ビットベクトル)を作った

計算機科学

@marugorithmさんの文法圧縮の解説資料(http://research.preferred.jp/2014/03/nlp2014_grammar/)があまりにも有益すぎて感動したので、文法圧縮を使った完備辞書(簡潔ビットベクトル)を作った。
文法圧縮の部分は実装の簡単さからRe-Pairアルゴリズムを使った。

https://github.com/echizentm/GCFID


作ってみて感じたメリット・デメリットをメモしておく。
簡単に言うと、rank、selectがO(1)でないという欠点があるものの理解のしやすさ、実装のしやすさを考えると利点が大きいように感じた。

文法圧縮を用いて完備辞書を作るメリット

  • ビット列が変換規則(X1 => X2, X3みたいなの)の集合で表現できるのでpopcountとかのややこしいビット演算が不要
  • ビット演算が不要なのでperl,pythonなどスクリプト言語で実装しやすい
  • rank, selectが完全に対称的な実装になるので理解がしやすい
  • ビット列長に対して変換規則数が充分に小さいなら大きな効果がありそう(ビット列長がnのとき、変換規則数は最良でO(log n)、最悪でO(n)？あまり自信ない)

文法圧縮を用いて完備辞書を作るデメリット

  • rank、selectが変換規則数に対してO(1)ではない
  • O(log 変換規則数)となる(最良でO(log log n)、最悪でO(log n)？)
  • 構築に空間計算量がO(n)、時間計算量がO(n * 変換規則数)かかる(このへんは効率のよい文法圧縮の方法を使えば解消できるかも。よく調べてない)