note_表紙

古典的な情報検索の課題とその解決方法 インデックス編

こんにちは!
IT企業でデータ活用プロダクトの開発に従事しているrilmayerです。
この記事はアドベントカレンダー「Search&Discovery 全部俺」4日目の記事となります。

さて本日は情報検索の古典的な課題やどのような研究分野があるかを紹介していきたいと思います。内容的には2日目で図書館情報学について紹介した際に情報検索の始まりからGoogleが登場するまで一気にジャンプした間を埋めていくような形となります。

ちょっと長くなってしまったので、パートを分けて紹介していきます。

古典的な情報検索の世界では文章で表現されたアイテムについて、利用者のニーズに適したものをいかに提供できるかというのが基本的な課題感となります。

情報検索の幕開け:文字列マッチングで対応できない!

さて、大量の文書中から、キーワードを軸として探したい文書を探す方法を考えてみましょう。

画像1

単純な方法として考えられるのが、逐次文字スキャンです。グレッピング(grep)とも言います。
つまり文字列を順に追っていきながら、マッチする部分や文書を見つけるという方法です。

画像2

この方法は良さそうに見えますが、大きな課題がありました。
それが「見つけるまでにだいぶ時間がかかる」ということです。
(複数単語の扱いや結果の並び替えと行った問題もあります)

ちなみに現在のコンピューターは当時に比べ、性能が高いためそこまで問題なくグレッピングできます。それでもドキュメントの数が数万、数億と増えていくと現実的な時間で検索はできなくなってしまいます。
とはいえ、今でもグレッピングは有効な検索手法であり続けていることに注意が必要ではあります。

より早く効率的なインデックスという方法

そうして考えられたのがインデックスを作成するという方法です。
この方法では以下のようにまず単語を取り出して、その単語に対して文書を紐付けます。こうして得られた、単語→文章群のデータをインデックスと言います。情報検索ではこれらの単語群を少し抽象化したトークンという形で扱いますが、今の所は単語という理解でOKです。

画像3

そうすることによって、単語群のみをスキャンすればよくなり非常に効率がよくなりました。

画像4

どのくらい効率がよくなったのか考えてみましょう。
例えば、100万文章から検索を行いたい場合に一つの文書につき平均100語含まれているとして、100語×100万文章=1億の単語をチェックしなくてはなりません。
ここで、「全ての文書で半分の単語は共通しており、その総数はだいたい1000語」という仮定をおくと(実はジップの法則と呼ばれる法則に従うとあながち乱暴な仮定ではないということになります)、50単語×100万文章+1000=約5000万語となり処理量が約半分になります。

実際に私たちが使っているような検索サービスでは、例え対象の文章が数億近くあったとしても、単語群の数はたかだか数万〜数十万くらいなのでより効率的です。

このインデックスによる検索では文字列スキャンに比べて嬉しいことがいくつかあります。その1つが複数語を用いてより効率よく検索することができるということです。

単語に紐付く文書群に対して集合演算を用いることで、いわゆるAND検索やOR検索を実現することができます。

画像5

こうして従来と比べより効率的に「複数のキーワードによる文書検索」ができるようになりました。
(上記の話に関して「よく考えると文字列スキャンでも同じことできるのでは?」と思うかもしれません。しかし、厳密にはインデックスと呼ばれるものの実態は単語×文書の行列となり、特定単語に特有な横向きのベクトルを取得して、ブール演算をすることによって特定のヒットする文書群を得ています。これにより効率の良い検索を実現しています。)

もっと効率の良いインデックスを求めて

さて、上記で大量の文書からなるアイテムをより効率良く扱うための基本的な考えを紹介しました。
この基本的なインデックス(単語に文書が紐づいたデータ構造)の考え方は現在でも検索の基礎となっています。

さて、このようなインデックスですが実際のシステムを構築する際は、以下のようなシステム構成が一般的となります。

画像6

このシステムの中でインデックスに関してより良い検索結果を得たり、よりスピーディーに検索結果を得るために様々な研究が行われてきました。「より良い検索結果をどう作るか」については次回お話しようと思います。
インデックスの構築や文書の取得について、どのように単語を生成するかや、どのようにより巨大なインデックスを扱うかといった課題があります。

1つの文章を正確な単語に分けると言うのは実は結構難しいタスクです。
例えば「白猫が魚を食べる」と言う文章を「白猫 が 魚 を 食べる」といった具合に区切って単語を作ることなどがそうです。こうした課題は自然言語処理の世界では形態素解析などと呼ばれています。
その他にも、活用形を一つにまとめたり(食べる・食べた・食べろ、などを「食べ」に統合しておくなど)、使わない単語を消去するなど(例えば助詞など)をしてより良いインデックスを作成することができます。
こうしたより良い単語を作る技術を情報検索の世界ではトークナイズなどと言ったりします。

巨大なインデックスを扱うために複数のコンピューターにデータを分散させる方法などもあります。
今では複数のコンピュータで処理を分散させたり、データを小分けに保持したりすることは一般的な方法になっていますが、初期はマップリデュースとしてGoogleがその技術を牽引していました。

その他、インデックスのデータ構造を工夫したり(例えば木構造を用いたりポインタをうまく活用したり)、データを圧縮したり、インデックス走査のアルゴリズムを工夫したりするなどして、より効率の良い検索が実現されています。

現在に到るまで研究者・技術者たちのたゆまぬ努力の甲斐あって、今こうして私たちは検索技術の恩恵にあやかることができています。
そして現在でもこうした技術は日々アップデートされており、より良い仕組みが日夜更新されています。

おわりに

本日は古典的な情報検索の内容、特にインデックスによる検索の方法について紹介しました。
今日の検索技術の基礎となっているので、検索に興味がある場合は押さえておくのが良いかもしれません。

次回は本日の続きを話そうと思います!

参考図書

今日の話はだいたいこの本に書いてます。


この記事が気に入ったらサポートをしてみませんか?