Googleはなぜ的確に探せるのか？ ― 第2回
悟空、秘剣「転置インデックス」を手に入れる
2008年12月08日 08時00分更新
検索エンジンを作るまでの高い壁
～キーワードの切り出しとキーワードの高速検索～
パソコンが文書を検索する仕組みのイメージが少しずつつかめてきたでしょうか。「さっぱり分からないんだけど……」という方も多いことでしょう。メモリーにキーワードや文書の情報を表現する仕組みはちょっと複雑なので、イメージできるまでには慣れが必要です。
でも、パソコンが文書検索についてやっている仕事は、本質的には人間が索引を作ったり引いたりするときにやっていることと同じです。「すべての情報をメモリーに載せて扱う必要がある」という「コンピューターの都合」に合わせるためにどうしても避けられない約束事が割り込んできているのです。転置インデックスの本質である「文書ごとにまとめた表をキーワードごとにまとめた表に変換すること」が理解できていれば、まずはそれで十分です。
さて、転置インデックスの仕組みを使って実際に文書検索システムを作るには、どうしても乗り越えなければならない2枚の厚い壁があります。
1枚目の壁:
文書の文字列からどうやってキーワードを切り出すのか？
「はじめに.txt」「第1章.txt」……に含まれるキーワードを切り出す仕組みはいったいどうなっているのか、疑問に思われた方もいることでしょう。じつは「キーワードの切り出し」は昔から多くの研究者を悩ませてきた深遠なテーマなのです。ましてや、コンピューターに「キーワードの切り出し」をさせるのは無謀といってもいいかもしれません!?
2枚目の壁:
「キーワードの列」からどうやってお目当てのキーワードを素早く探し出すのか？
高速な文書検索システムを作るには、利用者から入力されたキーワードの番号を素早く見つける仕組みが必要です。実はこれがけっこう難しいのです。メモリー表現の先頭から探していく方法では、キーワードの数が増えるにしたがって時間が多くかかります。メモリー表現では、番号からキーワードを一瞬で調べられますが、その逆は不可能です。世界中のWeb文書にはおそらく何千万種類ものキーワードが使われています。いくら高速なパソコンでも、何千万種類ものキーワードの配列からお目当てのキーワードを探すにはそれなりの時間がかかってしまいます。
次回とその次の回は、この2枚の壁を乗り越えるためのとっておきの道具「文字N-gram方式」「二分探索法」「ハッシュ表」を紹介します。
この連載の記事
- 第6回 悟空、単語辞書を手に入れる
- 第5回 悟空、秘技「分かち書き」を習う
- 第4回 悟空、キーワードを瞬時に見つける
- 第3回 悟空、キーワードを電光石火で切り出す
- 第1回 悟空、村の中で文書を探す
- この連載の一覧へ
