検索エンジンを作る

「集合知プログラミング」の第四章はみんな大好き検索エンジンの話です。テンション上がりますね!!

集合知プログラミング

概要

ここでは、文書のリストに対して特定のキーワードを用いて検索を行う場合を考えます。普段Googleとかでやってるような検索です。

インデクシング

検索エンジンを作る時には、まず「インデクシング」と呼ばれる操作が必要になります。インデクシングは、通常は文書中に現れた全ての単語の「種類」と「位置」を記録する事を指します(大抵はDBに保存する事になります)。インデクシングによって、検索に使う「単語」と検索対象の「文書」が結びつけられる訳です。

一番単純な検索

一番単純な検索として、特定の単語を含む文書を「全てDBに保存した順に取得する」といった方法が考えられます。 インデクシングによってどの文書にどの単語が出てきたかは多対多のテーブルの形でDBに記録されている為、後から特定の単語に対してクエリを投げる事で、関連する文書の一覧は簡単に取得出来ます。

ただし、この方法では関連性の高い文書も低い文書も一度に取得してしまう為、このままでは実用的ではありません。そこで、取得した文書を優先度順に並べる「ランキング」のアルゴリズムが重要になってきます。

ランキングのアルゴリズム

ある特定の単語で検索を行ったとき、その単語に関連性の高い文書が優先的に取得出来ればその検索エンジンは優秀であると言えます。そこで重要になってくるのが、優先度決め(ランキング)のアルゴリズムです。

文書のリストに対しての検索であれば、単語の「出現頻度」や「出現位置」が重要な判断基準となりえます。単語の「出現頻度」が高い程、また「文章の先頭近くで」単語が出現する程、その単語と文書の関連性は高いと言えます。

また、HTML文書の様なタグでマークアップされた文書なら、「タイトルタグ」や「見出しタグ」の中に検索語が含まれている程、関連性の高い文書であると判断出来ます。これも、特定のキーワード(<title>タグ等)の後に出てくる単語を見ているという意味で「出現位置」を利用したアルゴリズムです。

また、Webページの検索であればページ同士はハイバーリンクで結ばれており、そのリンクを利用したランキング付けも行う事が出来ます。Googleの「PageRankアルゴリズム」なんかが有名な例です。(今はもう違うアルゴリズムらしいですが...)

検索エンジンの要は「ランキングのアルゴリズム」である為、恐らく最も精力的に研究され、発展していってる部分なんじゃ無いかと思います。

とりあえずのまとめ

「検索」とパッと聞くと何か難しそうと思っちゃいますが、「インデクシング」と「ランキング」の組み合わせに過ぎないと思えば、何となく出来そうじゃ無いですか？

多分、ランキングの精度を上げようとすればする程複雑性が増して難しくなって行くとは思いますが、単純な検索であれば意外と簡単なんじゃ無いかと思います。次回以降、実際に手を動かして試してみたいと思います。