世界でもっとも強力な9のアルゴリズム」という本が非常に面白いので紹介します。

 

私たちが日常的に触れているものの裏にどのような「アルゴリズム」があるのか、それはどのように動いているのかを誰にでも分かるように平易な文章で書いています。

 

著者のジョン・マコーミックが取り上げるアルゴリズムの基準は次の三つです。

 

  1. 普通のコンピュータユーザーが毎日使っていること
  2. 現実の世界の具体的な問題を解決すること
  3. 主にコンピュータサイエンスに関係のあるもの(つまりハードウェアは除外している)

 

これにより選ばれたアルゴリズムは以下の通り。

 

  1. 検索エンジンのインデクシング(世界最大の藁山から針を探す)
  2. ページランク(グーグルを起ち上げたテクノロジー)
  3. 公開鍵暗号法(葉書で機密情報を書き送る)
  4. 誤り訂正符号(自分で誤りを訂正するシステム)
  5. パターン認識(経験から学ぶ)
  6. データ圧縮(無から有を生み出す)
  7. データベース(一貫性の追求)
  8. デジタル署名 (このソフトウェアを本当に書いたのは誰か)

 

 

これを見て頂ければ分かる通り、「検索エンジン」の説明が二つもあるのです!皆さんが普段使っている検索エンジンのアルゴリズムがどのようになっているのか、その「トリック」が簡単に理解出来ます。

 

この本では「トリック」という言葉を使っているのですが、それはどういう意味かというと、

 

それ以外の方法では困難だったり不可能だったりすることを可能にする巧妙なテクニック

 

であると著者は言っています。

 

第2章 検索エンジンのインデクシング

 

この本では「マッチング」と「ランキング」をきちんと分けて説明しています。これを分けて考えるだけでも検索エンジンのことを理解しやすくなると思います。以前、私が書いたポストでも「マッチングとランキングを分けて考えよう」と言っています。

 

ユニナレ流:良い検索エンジンの作り方〜マッチングとランキング〜

 

第2章では検索エンジンの「マッチングアルゴリズム」としてAltavistaを取り上げています。私もよく使っていました:)

 

ここでは、3つのページしかないワールドワイドウェブを想定して、それらのページがどのようにインデクスされ、ユーザーのクエリーとどのようにマッチするのかを説明しています。

 

私も新しい事を学ぶ時には、出来るだけ単純な例に落とし込んで理解するのですが、ここで示されている例はインデクシングを理解するのに非常にシンプルで分かりやすいです。

 

最も単純なインデクス

 

まずは単純なインデクシングの説明をしています。インデクスとはある単語がどのページに出てくるのかという情報をまとめたものです。例えば、”cat”という単語がページ1とページ2に出てくるなら、インデクスでは

 

cat: 1 2

 

となります。本の後ろに出てくる「索引」と全く同じですね。「インデクス」とは「索引」のことです。

 

位置情報のトリック

 

次に位置情報を付けたらどうなるかというトリックの説明をしています。

 

位置情報というのは、ある単語がそのページの何番目に出てくるかという情報です。

例えば、次のようにインデクスする時に単語だけでなく位置情報を付加します。括弧内の数字が位置情報です。

 

 

ページ1:the(1) cat(2) sat(3) on(4) the(5) mat(6)

ページ2:the(1) dog(2) stood(3) on(4) the(5) mat(6)

ページ3:the(1) cat(2) stood(3) while(4) a(5) dog(6) sat(7)

 

 

これらのページから出来るインデクスは次のようになります。「(ページ番号)−(位置情報)」という書き方です。

 

a:        3-5

cat:     1-2 3-2

dog:     2-2 3-6

mat:    1-6 2-6

on:      1-4 2-4

sat:     1-3 3-7

stood:  2-3 3-3

the:     1-1 1-5 2-1 2-5 3-1

while:  3-4

 

この新しいインデクスを見ると「ページ番号」 だけでなくそのページで何番目に登場する単語なのかという「位置情報」が分かります。

 

位置情報が分かるようになると「フレーズ」かどうかが分かります。「フレーズ検索」、「AND検索」という言葉を聞いたことが有るかも知れませんが、

 

フレーズ検索

クエリーが複数の単語の場合、それらの単語がそのままの順番で登場するページがマッチする。

 

AND検索

クエリーが複数の単語の場合、それらの単語がページのどこかに登場するページマッチする。

 

という違いがあります。

 

例えば、上記の例を使うとフレーズ検索の場合、クエリー”cat sat”はページ1とマッチします。

一方、AND検索ではクエリー”cat sat”はページ1およびページ3とマッチします。ページ3では”cat”と”sat”は離れていますが両方とも登場するためAND検索ではマッチするのです。

 

(続く)

 

# Facebok ページで「いいね!」して頂けると、ユニーバーサルナレッジの最新情報を得ることができます。

http://www.facebook.com/universal.knowledge.inc

 

 

1

ユニバーサルナレッジは、EC サイト向けに購買行動に連動した ASP 型サイト内商品検索エンジン、キーワードサジェストエンジン(クエリーサジェストエンジン)を提供しています。