Sennaによる部分一致検索の挙動について

Senna

Sennaの部分一致検索時の挙動について、
ACM SIGMOD日本支部大会で質問が出ました。


傀儡師の館 - 組み込み型全文検索エンジン Senna を使ってみる
http://plaza.rakuten.co.jp/kugutsushi/diary/200611120002/
のエントリでも、部分一致検索の挙動についてツッコミが入っています。


というわけで、Sennaの部分一致検索の挙動について説明。
デフォルトでは、以下のような検索処理が行われます。

  1. クエリを形態素解析する
  2. (A) それぞれの形態素が、指定された順番で出現する文書を検索
  3. 1件でもヒットすれば、終了
  4. (B) クエリを形態素解析せずに1つの語として扱い、その語が出現する文書を検索
  5. 1件でもヒットすれば、終了
  6. クエリを形態素解析する。
  7. 複数の形態素が取り出された場合…
    1. 最初の形態素と後方一致する登録語のリストを作る。リストAと呼ぶ
    2. 最後の形態素と前方一致する登録語のリストを作る。リストBと呼ぶ
    3. 上記以外の形態素を、リストCと呼ぶ
    4. (C) 以下の(1)(2)(3)を全て満たすシーケンスが出現する文書を検索。(1)リストAのうち、いずれかの要素で始まり (2)リストCの形態素が、指定された順番で出現し (3) リストBのうち、いずれかの要素で終わる
  8. 単一の形態素が取り出された場合…
    1. (C) クエリ文字列を含む登録語のリストを作り、そのリストのうちいずれかの登録語が出現する文書を検索


「モンゴル航空相撲殺」という文書は「モンゴル」「航空」「相」「撲殺」、
「堰東京都祇園囃子」という文書は「堰」「東京」「都」「祇園」「囃子」と分かち書きされます。
分かち書きのそれぞれの要素がインデックスに登録され、登録語となります。


上記の２文書がインデックスに登録された状態で、
「相撲」という検索語で検索を行う場合を考えます。
まず、「相撲」はこれ以上分かち書きされません。
(A)でも(B)でも検索結果は返ってきません。
(C)では、「相撲」を含む登録語はインデックスに存在しないため、
これも検索結果が返ってきません。


「京都」という検索語で検索を行う場合も同様です。


例えば、
「相 撲」や「京 都」という検索クエリであれば、
(C)によって検索結果が返ってきます。


というわけで、
「航空相撲殺」や「堰東京都祇園囃子」での検索漏れは、
現在のSennaの部分一致検索では救うことが出来ません。


「インド」で検索して「インドネシア」がひっかからないといった検索漏れは、
現在のSennaの部分一致検索で救うことができます。


Sennaでは純粋なN-gramインデックスを作成することが出来ます。
純粋なN-gramインデックスを作成した場合には、
上記の検索漏れを救うことができますが、適合率が落ちてしまいます。


「傀儡師の館」のエントリ内で、

「n-gramインデックスと単語インデックスの特徴を兼ね備えた、高速かつ高精度な転置インデックスタイプのエンジンです。」 ということだから形態素解析の結果にかかわらず n-gram でちゃんとヒットしてほしい。

とツッコまれているが、
上記の売り文句は、

  • 純粋な単語インデックスよりは再現率が向上し適合率が下落
  • 純粋なN-gramインデックスよりは適合率が向上し再現率が下落

という意味なのでした。


この問題を解決するために、
MeCabのソフト分かち書きを使いたいと思っているんだけど、
なかなか手が回っていない状況です。
つ http://sslab.nuee.nagoya-u.ac.jp/nlp-youth/paper/okanohara.pdf
つ http://www-tsujii.is.s.u-tokyo.ac.jp/~hillbig/papers/mozilozy.ppt

・速度・作業領域量の向上
　・確率の高い候補から提示可能な索引

をどうすっかだねえ…