Groongaで学ぶ全文検索 2015-09-18に参加

groonga

投稿日 2015年09月18日


私はGroongaドキュメント読書会 新リリース自慢会には参加した事がありましたが、全文検索自体よくわかっていない人です
そしてある日twitterのタイムラインを見ていたら@ktouさんが

Groongaの新リリース会で肉ばっか食ってる場合じゃねーぞ!

と思い

お手伝いできることなら手伝ってみたいとの気持ちで返信

そこから一日後。。。。

という事でGroongaで学ぶ全文検索 2015-09-18に参加してきました

まずは、自己紹介のあと自分はどんなことが知りたい・やりたいのかを聞かれました

私は、Groongaを使って何かを作ってみたい

何かを作れるように頑張りたいと思います
まずは、レポートを書かなければ

Groongaで学ぶ全文検索 方針

このGroongaで学ぶ全文検索は自分の理解度を示すために、質問されたら答える!
正解していれば 正しく理解できている!
間違っていれば 正しい回答を得て間違いを直せる

を繰り返し成長していく会です

そして勉強会の中でブログを書き出来れば公開するところまでする勉強会です
間違っていたらその都度修正していけばいいと思います

記念すべき第一回は。。。

全文検索ってなんですか?からスタート

全文検索とは

コンピュータにおいて、複数の文章(ファイル)から特定の文字で検索すること

コンピュータの検索

入力 -> 全文検索 -> 出力
  • 入力
    • クエリー
    • キーワード
  • 出力
    • マッチした文書

今回は日本語のエンコード等の話が出てくるとややこしくなるため
英単語 "hello"を例に検索していく

  • 逐次検索(シーケンシャルサーチ)

    1. 検索対象の文書の先頭から1文字目(helloで言うh)を探す
    2. 見つかったら単語の2文字目(e)が隣にあるかを探す
    3. すべてヒットするまで繰り返す 検索単語と検索対象の文書が増えると検索結果を取得するまでに時間がかかります
  • 索引(インデックス)検索
    システムが検索を行う場合、ファイル一つ一つに検索を行うと非常に時間がかかる
    そのため辞書同様に索引(インデックス)を作成する必要がある

    1. 全文書内から単語ごとに索引(インデックス)を作る
      • このインデックス作成にすごい時間がかかるがGroongaは動的にインデックスを作成する機能もある
    2. 単語を検索する 検索結果は逐次検索より早い さらにGroongaでも利用しているアルゴリズムの話がでた

二分探索とは

初めて聞いた単語なのでwikiより

二分探索とは検索のアルゴリズムの一つで 二分探索、バイナリサーチと呼ばれています
ソート済みのリストや配列に入ったデータに対する検索を行う場合に中央の値をみて検索したい値の大小関係を用いて検索したい値が中央の値の右にあるか左にあるかを判断し、確かめながら検索を行っていく

大小関係を用いるため、未ソートの場合は利用できない

重要なのがまず、一定のルールでソートされていること
今回の場合はアルファベットでの話だったので
アルファベットは小文字26文字+大文字26文字ですが今回は小文字のみの話
索引の配列 index[0] 〜 index[25]まであるとする

helloの文字を二分探索!!

アルファベットの順番のルールに従いhがindex[13]より前半ということが判断できる

次にまたindex[7]の前半か後半かまたヒットか判断

繰り返す

この方法だと文章が増加しても検索結果が早く見つけられる

今回はここまで
次回は質問された時に答えられれば理解できているはず!!

最後に

検索は日々なにげなく使っているが、こんな考え方があったのかといろいろ学べた
本当に初歩ではあるが、少しずつ前進して行ければいいなと思いました

次回、Groongaで学ぶ全文検索 2015-10-02


2016 GakuBlog