検索エンジンの日本語トークナイズメモ

はじめに

検索エンジントークナイズ処理の部分で行われている基本処理や工夫を少し調べてみたのでメモ。

トークナイズ処理

  • 「検索クエリ」に対してマッチする「ドキュメント」を高速に検索するためにインデクス(索引)を作成する
    • 本の最後の方にある「用語 - ページ」のような感じで、速く目的の用語が書いてあるページを調べられる
  • インデクスは、日本語の場合文字が連続しているため、「形態素」や「(文字)N-gram」などが使われる
文1「六本木ヒルズに行った」
文2「青山さんから電話があった」

【形態素でインデクスを作成する場合の例】
文1:「六本木ヒルズ」「に」「行く」「た」
文2:「青山」「さん」「から」「電話」「が」「あっ」「た」

【文字2-gram(bigram)でインデクスを作成する場合】
文1:「六本」「本木」「木ヒ」「ヒル」「ルズ」「ズに」「に行」「行っ」「った」
文2:「青山」「山さ」「さん」「んか」「から」「ら電」「電話」「話が」「があ」「あっ」「った」
  • 「転置インデクス」はこれを逆にしたもので、以下のように保持することで、そのインデクスを持つ文を高速に探せる
六本木ヒルズ:文1
青山:文2
た:文1、文2
...

トークナイズ処理における問題

  • 六本木ヒルズ」というインデクスを作ってしまうと、検索クエリで「ヒルズ」が来た場合、転置インデクス内には完全マッチするものはないので、検索できず検索漏れになる
    • なので、できるだけ短めの単位でインデクスが作られている方がよかったりするが、短くすると意味が違ってしまうものまで拾ってしまう可能性がでてくる
  • また、検索クエリ側でもインデクスと同じ処理をし単位をそろえる必要があるが、形態素解析などを使うと「クエリの解析結果」と「文章中での解析結果」がちょっと変わってしまったりすることがある
  • カタカナ、アルファベット、数字、記号などは、日本語の形態素解析ではきちんと解析されない場合、それらを含む検索に失敗する可能性もある
    • 字種交じりだと切れ目がおかしくなりやすい

基本処理・工夫

形態素N-gramでのハイブリットインデクシング

http://www.slideshare.net/techblogyahoo/17lucenesolr-solrjp-apache-lucene-solrnbest

  • インデクスを「形態素」と「N-gram」を一緒に使うことで、「形態素」インデクスで意味の合う検索を抑えつつ、「N-gram」インデクスで検索漏れを防げる
  • 検索ノイズ(意味の合わないドキュメントが検索される)が大量に発生してしまう可能性がある
  • インデクスサイズが大きくなる
辞書登録による解析単位の調整

同上

  • 短い単位に解析されるよう辞書に登録
  • 登録するのが大変(保守も大変)
N-Bestによるトークン拡張

同上

  • 複数の解釈が可能な文などは、どの解析が正しいかを判断するのは難しい
  • 解析結果の上位N個(正確には、一番スコアが高い解析結果からのコスト差が閾値以下)を利用する
kuromojiのSEARCH MODE

http://atilika.org/

  • KuromojiにはSEARCH MODEというできるだけ短い単位で形態素解析するモードがついている
  • 処理内容としては、長い形態素の場合、形態素コストにペナルティを加算し出にくくする、ということをしている模様
    • code
    • 追記:solrだと短い形態素だけでなく長い形態素もインデクシングされるのなんでかなと思ったら、プログラムが違うようで、以下が実際の処理だった
    • JapaneseTokenizer.java
  • EXTENDED MODEというのは、さらに未知語を1文字ずつに解析させる処理が加わるそう
品詞や文字の正規化・除外・ストップワード

http://www.rondhuit.com/solr%E3%81%AE%E6%97%A5%E6%9C%AC%E8%AA%9E%E5%AF%BE%E5%BF%9C.html

  • 区切り文字、記号、助詞、助動詞などを検索したい場合は少ないので、ノイズとなりうるそれらの品詞でフィルタ
    • ただし、記号とかは意味のある場合が多いので、注意が必要そう
  • 全角、半角はあまり区別する必要がないことが多いので、どちらかに統一しておく
  • 動詞や形容詞などの活用語は基本形に直す
    • ただし、動詞の連用形は名詞と揺れやすい気がするので、注意が必要そう
  • 組文字(㍑など)、異体字とかも(下記の書籍参照)
  • 中黒(「・」)の処理、など
  • よく出てきて意味のないものは「ストップワード」として除外する
トークンの部分一致検索

山田,末永,「検索エンジン自作入門」,技術評論社

  • (長めの)形態素の部分文字列を高速に検索できるようにしておくことで、検索ヒット数が少ない場合の検索再現率を改善
  • 形態素(トークン)に対して、半無限文字列(i文字目から最後の文字までの部分文字列)を前方一致で検索
    • suffix array的な感じ。パトレシアトライなどを使っている模様
表記ゆれ、同義語の考慮

同上

  • 表記が「サーバー」「サーバ」や「バイオリン」「ヴァイオリン」など揺れる可能性がある
  • これらを同一視できるような辞書を用意して統一しておく