Posted at

Groongaのインデックスの仕組みをおさらい

More than 3 years have passed since last update.

Groongaで学ぶ全文検索 2016-08-26で学んだ事のまとめ。


インデックスの基本


  • インデックスは、キーを与えると対象のデータがどこに配置されているのかが分かる仕組み。

  • 全文検索の場合は、文字列を分解したものを与えると、その文字列が含まれる文書が得られる。


    • 文字列の分解方式には、NGramや形態素解析のような方式がある。

    • インデックスのキーを語彙、それに対応する対象データをポスティングリストと言う。




インデックスを使った検索


  1. 検索するキーワードをインデックスのキーと同じ方式で分解する。


    • インデックスのキーには、文書をNGram等で分解したものが入っているので



  2. 分解したキーワードでインデックスを検索し、対象のすべての語彙が含まれている文書を得る。

  3. その文書の中に、分解前のキーワードが出現している事を確認する(後述)


    • していたら検索結果として表示する




分解前のキーワードが出現している

例えば「東京都」を検索する際、「東京」と「京都」に分解された場合、2の結果には「東京と京都」という文字列が含まれている文書も得られるが、これは意図した結果ではない。

そのため3において、2で得られた結果のそれぞれの文書に、キーワードが分解前の状態で含まれているのかを確認している。


  1. PostgreSQLで全文検索する場合の確認方法


    • 2で得られた文書をすべてシーケンシャルに検索して、実際に含まれているかを確認する。

    • 長い文書が多い場合、検索のコストが高い。



  2. Groongaでの確認方法


    • インデックス内に文書だけでなく、その文書内での出現位置も保持しているため、インデックスの検索結果だけで確認することができる。

    • 一般的にはインデックスのサイズがpg_bigmに比べるとデータ量が増える。



  3. ※他の検索エンジンについても知っておきたい


スコアリングについて


  • スコアリングとは、検索された結果の表示順を制御するための仕組み。

  • より検索した人の意図に近いと思われるものが先に出力されるようにするために用いられる。

  • 複数の検索項目がある場合、確実性の高い(と思われる)項目や重要な項目がヒットした場合、そちらを優先して出すなど。

  • 具体的な実装方法(どこまでGroongaに任せて、どこからをアプリ側で実装するか)については要学習。