Googleはなぜ的確に探せるのか？ ― 第4回

悟空、キーワードを瞬時に見つける

2008年12月26日 08時00分更新

文● 清田陽司／東京大学情報基盤センター図書館電子化研究部門助教

まだまだ問題が！！

　転置インデックスと文字N-gram方式を使った文書検索システムを、2枚の厚い壁を乗り越えて実現するための仕組みをここまで説明してきました。Web全体の文書をどうやって1台のパソコンに格納するかという問題はありますが、原理的には、Web検索エンジンを1台のパソコンで動かすことも不可能ではありません。しかし、Googleと同じように「本当に使える」検索エンジンを作るにはまだまだ乗り越えるべき壁があります。ひとつずつ見ていきましょう。

検索結果にゴミが混ざってしまう

　仮にN-gram方式の検索エンジンを使って、「京都」というキーワードでWeb検索したとしましょう。「京都のおすすめホテル」「京都市の観光名所」などのWebページが見つかります。しかし、なぜか「東京都知事選挙」というWebページまでヒットしてしまいました。京都のことを調べたいのになぜ東京なのでしょうか？

　実は、検索結果に検索要求とは関係のない文書まで混じってしまうのが、文字N-gram方式の重大な欠点なのです。「東京都知事選挙」に文字2-gram方式を適用すると、「東京」「京都」「都知」「知事」「事選」「選挙」というキーワードが抽出されます。「京都」というよけいな「キーワード」がゴミの問題を引き起こしてしまいました。

Nを大きくすると探せない文書が出てしまう

　「ゴミが混ざるのは2文字という短い文字列で切り出しているからじゃない？　たとえば3文字にすれば『東京都知事選挙』から『京都』が切り出されるなんてことは防げるよね」―――そうすると、こんどは「京都」で探すことが不可能になってしまいますよ。文字N-gram方式は、Nを大きくすればゴミを減らすことができる代わりに、検索漏れもたくさんでてきてしまいます。

転置インデックスが巨大になってしまう

　「検索ゴミ問題」とも関係しますが、文字N-gram方式は人間にとって意味のない文字列も区別せずにじゃんじゃんキーワードとして切り出すため、当然転置インデックスも大きくなってしまいます。

転置インデックスの作成に時間がかかる

　転置インデックスを使った文書検索システムは、検索はほぼ一瞬でできるのですが、文書全体からキーワードを切り出したりハッシュ表を作ったりするのに、文書の量に比例した時間がかかります。転置インデックスを作っている間は検索ができない、なんてことになったら困りますよね。本連載では詳しく述べませんが、この問題に対処するには、たくさんのパソコンを並列に動かして転置インデックスを作るとか、転置インデックス作成専用パソコンと検索専用パソコンを別々にもうける、といった工夫が不可欠です。

　転置インデックスの作成に時間がかかる問題はさておき、文字N-gram方式には重大な欠点があることがお分かりいただけたかと思います。この問題のことを、「京都・東京都問題」と呼ぶことにしましょう。次回は、この欠点を克服するための方法「分かち書き」に話を進めます。

■参考サイト

前へ 1 2 3 4 次へ

ツイートする

カテゴリートップへ