転置インデックスを用いた全文検索の実装

転置インデックスを用いた全文検索の実装


検索システムというものに興味を持ったので調べました。

検索と言ったら
「sqlのSelect文でwhere句にキーワード指定して」
などとやるものかと思ったら違いました。

大量の文章(検索対象)の中からキーワードに合致する文章を取ってくる場合それではものすごい時間がかかります。

そこで現在ほとんどの検索システムは転置インデックスという索引構造を利用して速い検索を実現しています。

今回はこれについて簡単にまとめさらに簡単に実装してみたいと思います。

転置インデックス


特定の単語を含む文章を探す際に個人的に一番素直だと思う方法はすべての文章を片っ端から調べあげることだと思います。
grepコマンドがこの方法をとっているようです。
ですがこの方法だと文章の数が膨大になると、答えを得るまでにかなりの時間がかかってしまいます。

商用で利用されている検索システムのほとんどは転置インデックスというものを利用しています。
これは単語ごとにその単語が出現する文章の一覧を作成し、
検索する際にこの一覧を参照して文章を取得する方法です。
この一覧をポスティングリストというようです。

事前に一覧を作成しておく必要がありますが、全走査にくらべて短時間で文章を取得することができます。


少し適当かもしれませんが、例えば次のような3つの文章があります。

  1. I like Python
  2. You like Java
  3. We like C and Java and Python


この文章に足して転置インデックスの仕組みを適用するとこのような一覧が出来上がります。
2列めの数字は文章を表しているIDのようなものです。

単語文章
I1
like1,2,3
Python1,3
You2
Java2,3
We3
C3
and3


この一覧を使って単語から文章を取得してきます。

例えばPythonという単語を指定して文章を検索した場合、文章1と文章3が取得できます。

複数の単語からなるフレーズで検索する場合、単語の並びも考慮する必要があります。

ちなみにここでは取得対象を文章と読んでいますが、これはシステムによって変わってきます。
web検索エンジンであればwebページですし、書籍の検索システムであれば書籍が検索対象になります。

ポスティングリストをなんとか作成する


ポスティングリストをどのように持つかを決める必要があります。
以下のようなフォーマットでテキストファイルに保存することにしましょう。

{文章ID:単語の出現場所},{文章ID:単語の出現場所}…


「単語の出現場所」は文章の中で単語が出現する場所を0から数えた数です。


文章をいちからたくさん用紙するのは面倒なので、
webページをスクレイピングしてそれを素材に短い文章をできるだけたくさん作っていきましょう。
htmlのpタグごとに文章を抽出します。
一応ポスティングリストのサイズもファイルに出力しておくようにしました。

素材はリーナスさんに関する記事でやってみましょう。


このスクリプトが同一階層にdocumentディレクトリとindexディレクトリを作成します。

document内に文章ID名を持つディレクトリが格納されており、
その中に実際の文章が置かれています。


そしてindex内に単語の名前を持つディレクトリが作成されその中にポスティングリストがテキストファイルで格納されています。

検索してみる


ポスティングリストを作成できればあとは簡単だと思います。
文章IDを取得してくる段取りはだいたい以下の通りです。

  • 単語ごとにポスティングリストを取得
  • 取得したポスティングリストから共通集合を取得
  • キーワードがフレーズの場合は単語の並びを調べ、合致していればIDを取得する


これらをやってくれるスクリプトを書けばいいということです。
こういうのは少しくらい適当でいいんですよ。


fetch_document_id関数はキーワードに指定した単語全てに合致した文章IDの配列と、
フレーズに合致した文章IDのの配列を返してくれます。

実際に動かすとこうなりました。


operating systemをキーワードにすると文章ID6が返ってきました。
どうやらフレーズが合致したようです。

この答えが正しいかgrepコマンドでdocument配下を検索してみましょう。


次はlinusと指定して検索してみましょう


今度は共通集合を取得してきました。
grepで確認してみましょう。
問題ないみたいです。

それで何がしたいのか


特に何かがしたいわけではありません。
検索システムに少し興味が湧いてきたので調べてみただけです。

全文検索ライブラリーとしてApacheLuceneがあります。
それをつかってなにか作ってみるものいいかもしれません。



商用のシステムは大量のアクセスが来るので、ここから更に工夫を凝らして検索を効率化しているのでしょうか。
Googleとかものすごいことしてそう。