Wesloo
すべてのトピックトピック

検索エンジン

転置インデックス 検索エンジンの仕組みと高速検索の構造

要点

転置インデックスは、文書群に含まれる単語をキーとして、その単語が出現する文書番号や出現位置を値として保持するデータ構造です。全文を先頭から順次走査する代わりに単語から文書群を逆引きできるため、数億件規模の文書群に対してもミリ秒単位での高速な検索処理を可能にします。

ポイント

  • 文書から単語をたどる正方向インデックスに対し、単語から文書番号の一覧(ポスティングリスト)を逆引きする構造を持つ
  • 文書IDのみを記録するレコード単位型と、文書内の出現位置まで記録してフレーズ検索を可能にする単語単位型に大別される
  • ポスティングリストのデータ肥大化を防ぐため、文書IDの差分を記録するデルタ符号化や可変長バイト符号化などの圧縮技術が用いられる
  • 検索クエリのAND処理やOR処理を、ソート済みリスト同士の高速な積集合・和集合計算として効率的に実行できる

転置インデックス 検索エンジンの根幹を成すデータ構造であり、膨大なウェブページ群の中から入力されたキーワードを含むページを瞬時に特定するために利用されています。ウェブ上には天文学的な数の文書が存在するため、検索要求があるたびに全文書の内容を先頭から順に調べる逐次走査(フルスキャン)を行うと、結果の返却までに膨大な計算資源と時間が必要になります。クローラー 仕組み:検索エンジンがページを見つける流れを経て集められた生データは、この転置インデックス形式に変換・整理されて初めて、実用的な速度での検索が可能となります。

転置インデックス 検索エンジンにおける基本原理

転置インデックスの基本概念は、書籍の巻末にある「索引」と同じです。書籍の本文が「ページ番号順に文章が並ぶ構造」であるのに対し、巻末索引は「五十音順に並んだ重要語句から、該当するページ番号を参照できる構造」になっています。

情報検索の分野では、文書番号に対してそこに含まれる単語群を対応付けた状態を「正方向インデックス(Forward Index)」と呼びます。これに対し、主客を反転させて単語をキーとし、その単語が出現する文書群を対応付けた構造が転置インデックス(Inverted Index)です。単語の識別子から対応する文書識別子のリストを直接参照できるため、目的の文書を特定する計算量を大幅に削減できます。

比較項目正方向インデックス転置インデックス
データの対応関係文書ID → 出現する単語群単語 → 出現する文書ID群
得意な処理特定文書の内容確認、更新処理特定単語を含む文書の検索
検索クエリ時の動作全文書を走査して単語の有無を確認単語をキーに該当文書群を一括取得
検索処理速度文書数に比例して遅くなる(O(N))単語の照合により高速に完了(O(1)〜O(log M))

正方向インデックスから転置インデックスを構築する工程

検索システムが文書を収集してから転置インデックスを完成させるまでには、複数のデータ処理工程を経由します。

  1. テキストの抽出と正規化:HTML文書から不要なタグを除去し、全角半角の統一や英文字の大文字小文字の統一を行います。
  2. 形態素解析とトークン化:日本語のように単語間に空白のない言語では形態素解析を実施して文章を単語(トークン)単位に分割します。英語などの場合は空白区切りを基本として語幹処理(ステミング)を施し、単語の基本形を抽出します。
  3. 正方向インデックスの作成:収集した各文書について、「文書ID:単語リスト」という構造を中間データとして構築します。
  4. 単語単位の反転と並べ替え:「文書IDと単語」の組み合わせを「単語と文書ID」へと並べ替えます。全文書から抽出された単語のペアを辞書順(アルファベット順や文字コード順)にソートします。
  5. 辞書とポスティングリストの分割保存:重複する単語を1つにまとめた「単語辞書」と、各単語に紐づく文書IDの配列である「ポスティングリスト(Posting List)」を生成し、ストレージに永続化します。

転置インデックスによって候補文書が絞り込まれた後、各文書の適合度スコアやページランク 仕組みと評価アルゴリズムの計算構造などを組み合わせて最終的な検索結果の掲載順序が決定されます。

レコード単位型と単語単位型の2つのインデックス構造

転置インデックスには、保持する詳細度に応じて大きく2つの形態が存在します。

レコード単位の転置インデックス

レコード単位の転置インデックス(Record-level inverted index)は、単語に対して「その単語が出現する文書IDのリスト」のみを保持する最小限の構造です。データサイズが小さく設計が平易であるため、特定キーワードを含むか否かのみを判定する用途に適しています。しかし、この構造では単語が文書内のどの位置に出現したかまでは把握できません。

単語単位の転置インデックス

単語単位の転置インデックス(Word-level inverted index)は、文書IDに加えて「文書内での単語の出現頻度」や「出現したオフセット位置(何文字目、何単語目か)」まで保持する構造です。完全転置インデックス(Full inverted index)とも呼ばれます。

位置情報を保持することで、2つ以上の単語が連続して出現しているかを判定する「フレーズ検索」や、指定された距離内に単語が存在するかを調べる「近接検索」が可能になります。現代の商用検索システムでは、正確な文脈照合や関連度算出を行うために単語単位のインデックスが広く採用されています。保持する情報量が増えるため、ストレージ使用量とインデックス構築コストは増大します。

ポスティングリストのデータ圧縮と最適化

ウェブ検索エンジンのように数十億件の文書を扱う環境では、ポスティングリストのデータ量がテラバイト規模に膨らみます。特に頻出する単語のポスティングリストは巨大化するため、メモリ配置の効率化とディスクI/O削減を目的とした圧縮アルゴリズムが適用されます。

ポスティングリスト内の文書IDは昇順に並べ替えられているため、絶対的な文書IDそのものを保存するのではなく、1つ前の文書IDとの差分(d-gap)を記録する「デルタ符号化」が基本技術として用いられます。例えば、文書ID列が「100, 104, 105, 110」である場合、差分系列は「100, 4, 1, 5」となります。差分を取ることで格納する数値が小さくなり、1件あたりに必要なビット数を削減できます。

差分数値の保存には、数値の大きさに応じて可変長でバイト列を割り当てる「可変長バイト符号化(Variable Byte Encoding)」や、ビット単位で効率良く記録する「ガンマ符号化(Elias Gamma Coding)」などの可変長符号化技術が組み合わされます。これにより、ポスティングリストのサイズを元の固定長整数配列と比べて数分の一程度に圧縮することが可能になります。

複数単語クエリにおけるブール演算の処理手法

ユーザーが複数のキーワードを入力した際、検索エンジンはそれぞれの単語に紐づくポスティングリストを読み出し、集合演算を行って対象文書を特定します。

  • AND検索(論理積):入力されたすべての単語を含む文書を抽出します。対象となる各単語のソート済みポスティングリストを先頭から順に比較走査し、共通して存在する文書IDのみを結果リストに残します。
  • OR検索(論理和):いずれかの単語を含む文書を抽出します。複数のポスティングリストを統合走査し、出現した文書IDの重複を除去しながら結合します。
  • NOT検索(差集合):指定された除外単語を含む文書IDを、検索結果の候補リストから取り除きます。

ポスティングリストが整列済みであるため、ポインタを先頭から進める線形走査によって積集合を高速に計算できます。リストが長大である場合は、途中のIDをスキップして高速に飛び越える「スキップポインタ」をポスティングリスト内に設けることで、不要な走査ステップを省き処理速度をさらに高めています。

他領域における転置インデックスの応用

転置インデックスはウェブ検索エンジンだけでなく、構造化データベースの全文検索機能やバイオインフォマティクスなど多様な領域で中核技術として利用されています。

生命科学の分野では、断片化されたDNAシーケンスデータを参照ゲノム配列と照合する配列アセンブリ処理において転置インデックスが活躍します。ヒトゲノムは約30億塩基対で構成されており、一定の長さ(k-mer)の塩基部分文字列をキーとし、その出現位置をインデックス化することで、エラーや変異を含む断片配列の元位置を高速に特定できます。Sphinx Searchのようなオープンソースの全文検索ライブラリでも転置インデックスが実装されており、ウェブサービス内の検索エンジン基盤として活用されています。

よくある質問

転置インデックスと通常のデータベースインデックス(B-Treeなど)の違いは何ですか?

B-Treeインデックスは数値や完全一致文字列の範囲検索や等価比較に適していますが、文章中の特定キーワードを探す部分一致検索には適していません。転置インデックスは文章を単語に分解して各単語から文書を引けるように設計されているため、全文検索を高速に処理できます。

転置インデックスの更新頻度はどのくらいですか?

検索エンジンは新規文書の追加や既存文書の変更に対して、メモリ上の中間インデックスとディスク上の主インデックスを階層化して管理することで、ほぼリアルタイムから数分程度の短い間隔で逐次更新を行っています。

AI検索やベクトル検索が普及しても転置インデックスは使われますか?

意味検索を得意とするベクトル検索が登場した後も、型番や固有名詞などの正確なキーワード一致においては転置インデックスが優位性を保っています。現代の先進的な検索基盤では、双方を併用するハイブリッド検索が主流となっています。

関連ページ

  • 初期 検索エンジン 歴史と技術進化の軌跡

    初期の検索エンジンは、FTPサーバー内のファイル名を索引化するツールから始まり、ウェブページの全文を自動巡回・登録するクローラー型へと発展しました。1990年代半ばにはAltaVistaやWebCrawlerによる高速な全文検索が普及し、被リンク構造やユーザー行動を解析するアルゴリズムの登場によって情報アクセスの精度が飛躍的に向上しました。

  • メタ検索エンジン とは?仕組みと特徴・通常検索との違い

    メタ検索エンジンは、入力された1つの検索クエリを複数の独立した検索エンジンへ同時に送信し、返された検索結果を集約・再構成して提示するシステムです。自前でウェブクローラーを巡回させて大規模な索引を構築するのではなく、外部のインデックスやAPIの応答を活用します。重複URLの排除や独自基準によるスコアリングを行い、1つの画面で多様な情報源の回答を横断確認できる点が特徴です。

  • プライベート検索エンジン 仕組みと個人情報保護の技術基盤

    プライベート検索エンジンは、ユーザーのIPアドレスやクエリ履歴、行動ログを収集・保持せずに検索結果を提供するシステムです。通信ヘッダーのサニタイズによる代理中継や、トラッカーを排除した独立インデックスのクロール技術により、個人の属性プロファイル作成を根本から遮断します。

  • セマンティック検索 仕組みとベクトル検索の基礎

    セマンティック検索は、入力文や文書を多次元の数値ベクトルに変換し、単語の字面ではなく文脈や意味の類似性に基づいて情報を取り出す技術です。高速な近似最近傍探索を行うベクトルデータベースと組み合わせることで、画像や音声を含む多様なデータ形式の大規模な検索基盤を構築できます。

  • robots.txt 仕組みと書き方の基本仕様

    robots.txtは、検索エンジンの巡回プログラムに対してサイト内の特定領域へのアクセス許可や制限を指示する平文テキストファイルです。Webサーバーのルート直下に配置され、クローラーのトラフィック制御や無駄な負荷の軽減に利用されます。強制的なアクセス制御ではなく自主的な準拠に基づく規約であり、非公開情報の隠蔽ではなく収集方針の提示を担います。

  • 自然検索 有料検索 違い:費用構造と獲得経路の比較

    自然検索と有料検索の根本的な相違は、掲載枠の獲得手法と課金構造にあります。自然検索はコンテンツの適合性や被リンク評価によって無償枠に表示される一方、有料検索はオークション制のクリック課金(PPC)で即座に広告枠を確保します。

このページの作成方法

執筆の前に、下記の情報源でテーマを調査しました。その後、自動の品質チェックを通過しています。

このページの誤りを報告する