Groongaで学ぶ全文検索の仕組みに関して理解したことをまとめてみたの巻
ひょんなことからGroongaで学ぶ全文検索に参加してきましたので、レポートをまとめてみます。
会場はクリアコードさん
講師&司会進行はリーダブルコード解説者の@ktouさんです。豪華！！！
国産の全文検索エンジンGroongaを使って全文検索（とGroonga）について学ぶ会で、
参加者にもGroonga開発者にもメリットがあること
参加者は、説明を聞き、理解した内容をまとめてそれを確認してもらうことで正しく理解できるようになります。参加者は全文検索に関する知識があるとうれしい人なはずなのでこれはメリットになるはずです。
Groonga開発者は、参加者がまとめたブログ記事によりユーザーが増えるとメリットになります。
というのを目的にとした会で、隔週開催予定とのこと。今回は第1回目です。
はじめに、皆さんはGroonga知ってますか？
私は完全に「名前は・・」程度でした。
何かと言われると国産の全文検索エンジンなのですが、まぁそれを聞いたとて「？？？」という感じです。なので超初心者がまとめたレポートになります。
自分が後で振り返っても理解できるように具体的に書きましたが、知見がある人から見ると厳密には違うんだけどな…みたいなところ、あると思います。
でも最初の理解はこんなもので良いと言われたので暖かい目でお読みください。
冒頭から名言なのですが、
「何かの仕組みを考える時は入力、出力で考えるとよい」とのこと。
今回は全文検索の話なのでその形式で当てはめると以下のようになります。
入力(クエリ)→全文検索→出力(ヒットした文書)
前提として、日本語はエンコードが難しいのでひとまず置いといて、今回は英単語(1キーワード 例：hello)を例にして、検索していくとします。
まずは
①一番シンプルな検索方法(逐次検索)
- 検索対象の文書の先頭から英単語1文字目(helloで言うh)を探していく
- ↓
- 見つかったら単語の2文字目(e)が隣にあるかを探す
- ↓
- 繰り返す
当然、検索単語と検索対象文書が増えるとものすごく時間がかかります 
なので他に方法を考えてみましょう。
②索引(インデックス)を使った方法
辞書(辞書は横の索引も含めて3次元であるが)のように索引があった方が良いですね。
全文検索システムを作る時は大抵最初に索引を頑張って作っているそうです。
最初にアルファベットA〜Zまでの全ての単語を全文書内から探し、ページ番号とページ位置を保存してインデックスを作ります。
この作業は全てを読み込んでいくので、とても時間掛かかります 
（その分、作る際に工夫のしがいがあるそうで、リアルタイムで索引を作っていくGroongaはここが得意とのこと。）
その後は索引で探していくので時間が①より早くなります！
更に索引での探し方として、配列を使うとより早くなります。
③索引(インデックス)×2分探索を使った方法
アルファベットは26文字なので、索引の配列がindex[0]~index[25]まであるとしますが、これを先頭の0からそのまま探していくのは大変です 
そこで2分探索！
※ちなみに2分探索を使うためには索引にはアルファベットの順番のように、順番のルールがあることが前提
- アルファベットの順番のルールに従うとhがindex[13]より前半ということが判断できる
- ↓
- 次にまたindex[7]の前半か後半かを判断
- ↓
- 繰り返す
この方法だと単語数が増えても早く見つけられる！
ちなみに全文検索にはアルゴリズムの考えがよく出てくるとのこと。
理解したと思ってあやふやにしていたら、その内わからなくなってしまうので注意ですね
アルゴリズムといえば、参加するにあたり、さすがに知識ゼロすぎてやばかろう・・と思い、「予習いらない」と書いてありましたが、当日の昼休みに少し本を読んでみました。
ちょうど2章が検索エンジンのインデクシングの話で、そのうち知ることになるであろうキーワード、「トークナイザ、形態素解析、N-gram」なども出てこず、基本的な内容なので、とても前提知識としてよかったです。表紙とタイトルから受ける印象よりわかりやすい内容でした。
というわけで飛び込んでみましたが、大変有意義な時間になりました！
会に参加して
検索結果で何をヒットさせるか、何を大事に考えるか(例えば記号は普通無視するが、プログラミングのサイトだと記号重要！だったり)を開発者が考えて作っていたのだな！！というのが新鮮で、これから検索するときに裏でどんな動きをしているか想像することができて、愛着がわきました。
こういう裏の仕組みを知るの、好きだな〜と改めて思いました 
楽しかったです！会に参加された全ての皆さま、ありがとうございました！