全文検索について
NLP関連の分野を勉強してきて、検索について人に説明できなかったので、ネットサーフィンした結果を書く。
以下転置インデックス - Wikipedia参考にして書いた。
索引（転置インデックス）について
grepは索引を作らずに、毎回文字列検索アルゴリズム（ボイヤームーア方法）を用いて検索している為*1、何回も検索する時は非効率である。
その為、前処理としてインデックス（索引）を作っておく。
一般的なのは転置インデックス転置インデックスの実装である。ちなみに「転置」と呼ばれる理由は、単語順に表がソートされる為、文書IDと単語のデータ順がひっくり返るからである。
単純な転置インデックスの例としては各単語がどの文書に含まれているかを、表として保持しておくものである。
以下、転置インデックスの例を示す。
文書1 = 「今日はテニスとサッカーをした」
文書2 = 「今日はテストとサッカーをした」
| 単語 | 文書ID |
|---|---|
| テスト | 2 |
| テニス | 1, 2 |
| サッカー | 2 |
・・以下省略・・
テニスは文書1と2両方に登場し、サッカーは文書2のみに登場する為、上記のような転置インデックスとなった。
・・・とまあ、この分野では結局実装できなければ理解した事にならないので、実装についても第19回 転置インデックスの実装を参考にしながらやっていく。
つまり、今研究で使用しているデータについても検索機能を実装しないといけないよね、という事で頑張ります。いつもgrep使っております。
ちなみに、分散処理基盤であるHadoopを利用して、検索をしたい場合はソースのライセンスと親和性の関係から、Javaの全文検索エンジンであるLuceneとそれを使用した検索サーバSolr等が使用される。
