Elasticsearchで見る検索エンジンの仕組み(3): インデックス/トークナイズ編

[前回] Elasticsearchで見る検索エンジンの仕組み(2): Kibanaインストール編

はじめに

前回は、Kibanaをインストールし、クエリ実行してみました。
今回は、全文検索のインデックスとトークナイズを理解します。

全文検索(Full text search)とは

• 複数の文書(ファイル)から特定の文字列を検索すること
• 複数文書にまたがって、全文を対象とした検索
  • ファイル名検索や単一ファイル内の文字列検索と異なる

インデックス(Index、索引)とは

• 高速な検索を可能にするため、検索対象文書から作成した索引データ

  • 書籍索引同様、特定単語がどのページで出現したか素早く参照できる
    
    ※ 引用元: https://ja.wikipedia.org/wiki/%E7%B4%A2%E5%BC%95

• インデクシング(Indexing)とは、事前に索引データを作成すること

  • インデクシングにより生成されるデータをインデックス(Index)と呼ぶ

• 転置インデックスの例

単語	単語が含まれた文書ID
全文	2, 6, 7
検索	1, 3
技術	4, 6

• grep型検索 VS. index型検索
  • 検索対象の文書数が膨大な場合
    • grep型検索は、逐次文字列検索するため時間がかかる
    • index型検索は、インデックスを用いて、文字列を高速に検索可能

トークナイズ(単語分割)

日本語文章は単語境界を表すスペースが存在せず、
インデックス作成のため、単語分解の処理が必要。

• 方法1: 形態素解析

  • 解析用の辞書を使用し、検索対象文書を単語分解
  • 形態素解析は単語分割と単語の品詞付けの2つの処理から成り立つ
  • 例、全文検索技術を形態素に分解
    • 全文(名詞)、検索(名詞)、技術(名詞)
  • 形態素解析で作成したインデックスは、検索結果が辞書品質の影響を受ける(辞書に未登録の単語が存在するなど)

• 方法2: N-Gram(Nグラム)

  • 検索対象文書を文字単位で分解し、後続N-1文字を含めた状態で分割
  • Nの値が
    • 1ならユニグラム(uni-gram)
    • 2ならバイグラム(bi-gram)
    • 3ならトライグラム(tri-gram)
  • 例、全文検索技術を2文字ずつ分割
    • 全文 文検 検索 索技 技術 術(終端)
  • N-Gramで作成したインデックスは、検索漏れが生じず、辞書も不要
  • 意図したものと異なる検索結果(ノイズ)が発生する可能性あり
    • 京都で検索すると東京都庁がヒット
  • インデックスのサイズが肥大化

• 形態素解析とN-gramの比較

	形態素解析	N-gram
検索漏れ	多い	少ない
検索ノイズ	少ない	多い
インデクシング速度	遅い	速い
検索速度	速い	遅い
言語依存	辞書必要	辞書不要
インデックスサイズ	小さい	大きい

おわりに

全文検索のインデックスとトークナイズを理解しました。
次回も続きます。お楽しみに。

[次回] Elasticsearchで見る検索エンジンの仕組み(4): サンプルデータでクエリ編