こんにちは！株式会社ペライチでフロントエンドエンジニアをしている秋本です。
この記事では、全文検索エンジンのしくみについて説明します。
現代社会において、私たちは日々膨大な情報にアクセスしています。検索バーにキーワードを入力し、エンターキーを押すと、ほんの一瞬で関連する Web ページが表示されます。この驚くべきスピードと精度の裏には、どのような技術としくみが隠されているのでしょうか？本記事では、その鍵を握る「転置インデックス」というデータ構造と、検索結果の関連性を評価するアルゴリズムについて、詳しく解説します。
目次
転置インデックスとは？
転置インデックスは、単語（ターム）がどの文書に含まれているかを効率的に検索するためのデータ構造です。これは、図書館の索引や辞書のようなものです。索引では、特定のキーワードがどのページに登場するかが一覧化されています。同様に、転置インデックスでは、Web 上のすべての文書に含まれる単語と、その単語が出現する文書の対応関係が記録されています。
このしくみにより、検索エンジンはユーザーが入力したキーワードに関連する文書を迅速に見つけ出すことができます。
データ構造の詳細
転置インデックスの基本的な構成要素は、ターム（Term） と ポスティングリスト（Posting List） です。
- ターム（Term）: 文書内に出現する単語やフレーズ。検索のキーとなる要素。
- ポスティングリスト（Posting List）: 各タームがどの文書で、どの位置に出現しているかを示すリスト。
ターム辞書
ターム辞書は、すべてのタームを整理・管理するためのデータ構造です。この辞書には、各タームとそれに対応するポスティングリストへのポインタが含まれています。
ポスティングリスト
ポスティングリストは、特定のタームが出現する文書 ID（ドキュメント ID）や、場合によってはその位置情報を含むリストです。これにより、タームがどの文書でどの位置に現れるかを詳細に追跡できます。
データ圧縮
膨大な量のデータを扱うため、転置インデックスではデータ圧縮が重要です。一般的な手法としては、差分符号化や可変長エンコーディングが使用されます。これにより、ストレージの節約と検索速度の向上が図られます。
具体例で理解する転置インデックス
実際に、以下の 3 つの英語の文を例にして転置インデックスを構築してみましょう。
- Document A: "He always starts his day with morning coffee."
- Document B: "After work, he often buys coffee to take home."
- Document C: "In this text, the word morning appears first, and coffee is mentioned later."
タームの抽出
各文からタームを抽出し、ターム辞書を作成します。一般的には、ストップ Word（頻出するが意味の薄い単語） の除去や、ステミング（単語の原形への変換） が行われます。ですが、ここでは簡略化のためそのまま使用します。
ポスティングリストの作成
| ターム | ポスティングリスト |
|---|---|
| he | A:[1] |
| always | A:[2] |
| starts | A:[3] |
| his | A:[4] |
| day | A:[5] |
| with | A:[6] |
| morning | A:[7] C:[7] |
| coffee | A:[8] B:[7] C:[11] |
| after | B:[1] |
| work | B:[2] |
| he | B:[4] |
| often | B:[5] |
| buys | B:[6] |
| to | B:[8] |
| take | B:[9] |
| home | B:[10] |
| in | C:[1] |
| this | C:[2] |
| text | C:[3] |
| the | C:[4] |
| word | C:[5] |
| appears | C:[8] |
| first | C:[9] |
| and | C:[10] |
| is | C:[12] |
| mentioned | C:[13] |
| later | C:[14] |
※出現位置は各文書内の単語の順序を示しています。
検索の流れ
たとえば、「morning coffee」で検索する場合、以下の手順を踏みます。
- タームの正規化: キーワードをタームに分割し、必要に応じてステミングやストップ Word の除去する。
- ポスティングリストの取得: 各タームのポスティングリストをターム辞書から取得。
- 文書の集合演算: 各ポスティングリストをもとに、共通の文書を特定。
- 関連性の評価: タームの出現位置や頻度をもとに、関連性スコアを計算。
この例では、ターム「morning」と「coffee」がともに含まれる文書は A と C です。さらに、タームの出現位置が近い文書 A のほうが、関連性が高いと評価されます。
そのため、以下のような検索結果が表示されることになります。
A > C > B
検索結果の関連性を評価するアルゴリズム
検索エンジンは、単にキーワードが含まれているだけでなく、ユーザーが求める情報にどれだけ適しているかを評価する必要があります。そのために、以下のようなアルゴリズムが使用されます。
TF-IDF（Term Frequency-Inverse Document Frequency）
TF-IDFは、各タームの重要度を数値化するための指標です。
- Term Frequency（TF）: タームが文書内でどれだけ頻繁に出現するか。
- Inverse Document Frequency（IDF）: タームがどれだけ希少か（全体の文書数を、そのタームを含む文書数で割ったものの対数）。
TF と IDF を掛け合わせることで、一般的な単語の影響を減らし、重要なタームを強調します。
PageRank
PageRankは、Web ページの重要度を評価するアルゴリズムで、リンク構造を利用します。
- 基本原理: 多くのページからリンクされているページは重要である。
- 計算方法: 各ページの PageRank 値は、そのページにリンクしている他のページの PageRank 値によって計算される。
このアルゴリズムにより、信頼性の高い情報源が検索結果の上位に表示されます。
なぜ検索が一瞬で終わるのか
検索エンジンは、膨大なデータを扱いながらも、高速な応答を実現しています。その理由は以下のとおりです。
- 事前処理の徹底: Web クローラによって収集されたデータは、転置インデックスの形で整理・保存される。
- 効率的なデータ構造: 転置インデックスや B 木、ハッシュテーブルなどのデータ構造を活用し、高速な検索を可能にしている。
- 分散処理: 複数のサーバーやデータセンターで処理を分散し、負荷を軽減する。
- キャッシュの利用: よく検索されるクエリやデータはキャッシュに保存され、アクセス時間を短縮する。
- 最適化されたアルゴリズム: TF-IDF や PageRank などのアルゴリズムが高度に最適化されており、関連性の高い結果を迅速に提供する。
まとめ
日常的に利用している Web 検索の背後には、転置インデックスを始め、高度なデータ構造とアルゴリズムが存在します。これらの技術が組み合わさることで、私たちは必要な情報へ瞬時にアクセスできています。
次回検索バーにキーワードを入力するとき、このしくみに少し思いを馳せてみてはいかがでしょうか。
採用情報
現在エンジニア募集しています！
▼ 採用ページ
▼ 選考をご希望の方はこちら（募集職種一覧）
▼ まずはカジュアル面談をご希望の方はこちら
募集中の職種についてご興味がある方は、お気軽にお申し込みください（CTO がお会いします）
Discussion