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

cf. https://groonga.doorkeeper.jp/events/31604

全文検索概要説明

input と output

"何かの仕組みを考えるときは input と output で考える"

  • input
    • クエリ
    • キーワード
  • output
    • マッチした文書

探し方について

"検索対象文書を頭から検索する" のは効率が悪い
"辞書他書籍にあるような、索引 (index) " が効率を上げる手助けをする
検索エンジンはあらかじめ index を作っておくことで検索性能の向上を図っている
groonga は index をリアルタイムにつくる(そこが強み!)

では、index をどうやってつくるか

単純化のため、英語を例に考えると、空白区切りで単語を切り出し、
頭文字をキーとする index を作ればよい。
index 自体の構造も検索しやすいように作らないと、ボトルネックになる。
Groonga では検索対象が増えても遅くなりにくいのでバイナリサーチしている。
イナリサーチするにはキーが何らかのルールで順序づけられることが前提となる。

性能という点ではハッシュ構造も挙げられるが
隣接するキーをも検索するようなケースには不向きとなる。
完全一致の検索(タグでの検索など)にはハッシュ構造が向いている。
実際のところ、隣接するキーも検索できることが求められるケース(前方一致など)が多い。