← 一覧へ
データベース
#역색인#전문검색#BM25#포스팅리스트#Lucene
最終更新 · 2026-11-14

転置インデックス(Inverted Index)と全文検索(Full-Text Search)

1. 概要

定義: 転置インデックス(Inverted Index)とは、「文書 → 単語」の関係を逆転させ、「単語(term) → その単語が出現する文書の一覧(posting list)」として格納するインデックス構造であり、大量のテキストから特定の単語を含む文書を全走査なしに即座に見つけられるようにするものである。全文検索(Full-Text Search)は、この転置インデックスの上でトークン化・正規化・ランキングを組み合わせ、自然言語クエリに対して関連度順に並べた文書を返す検索手法である。

関係データベースのB木インデックスは、「列値と完全に等しいか範囲に入る行」を高速に見つけることに最適化されている。しかし数百万件の投稿・商品説明・ログから「クラウド セキュリティ」という単語を含む文書を探せという要求には適さない。LIKE '%クラウド%'はインデックスを利用できず全テーブルを走査し、一つの文書内に単語が複数回・複数の形で現れる自然言語の特性も反映できない。転置インデックスはこの問題を、文書をあらかじめ単語単位に分割し「どの単語がどの文書にあるか」を逆転させて格納することで解決する。

転置インデックスの核心的な洞察は、「検索は読み取りが圧倒的に多く書き込みは相対的に少ない」というワークロード特性を活用する点にある。インデックス構築(indexing)時点であらかじめコストを払い、単語ごとの文書一覧を整列・圧縮しておけば、クエリ時点では該当単語のポスティングリストを読んで積集合・和集合演算を行うだけでよい。たとえば「クラウド AND セキュリティ」は二つの単語のポスティングリストをマージ(merge)して共通文書を見つけるもので、全文書数ではなく二つのリスト長に比例するコストしかかからない。

全文検索が単なる包含の有無を超える理由は関連度(relevance)にある。同じ単語を含んでいても、その単語がタイトルにあるか本文末にあるか、文書全体でどれほどありふれた単語かによって重要度が異なる。したがって全文検索エンジンはTF-IDF・BM25のようなスコアモデルで文書を整列し、形態素解析・類義語・誤字補正で自然言語の多様性を吸収する。技術士の答案では、転置インデックスを単なるデータ構造としてのみ説明せず、インデックスパイプライン・クエリ処理・ランキング・圧縮・運用を一つの検索システムとして結びつけて記述すべきである。

1.1 登場の背景と必要性

ウェブと企業データの急増により非構造化テキスト検索の需要が高まった。ポータル検索、EC商品検索、ログ分析(ELK)、社内文書検索、顧客問い合わせ検索などはいずれも「キーワードを含み関連度の高い文書を高速に」見つける必要がある。関係DBのLIKE・正規表現走査はデータが大きくなるほど線形に遅くなり、自然言語の語形変化(検索/検索する/検索された)や分かち書き・誤字を扱えない。

転置インデックスは情報検索(Information Retrieval)分野の古いデータ構造であり、Apache Luceneを通じて普及し、Elasticsearch・OpenSearch・Solrの中核エンジンとなった。必要性は明白である。1億件のログから特定のエラーメッセージを探すのに全走査で数分かかれば障害対応は不可能だが、転置インデックスを使えば数十ms以内に応答する。検索品質の面でも、ランキングのない結果は利用者が望む文書を上位に出せず事実上役に立たない。

ただし転置インデックスは無償ではない。インデックス格納領域(原文の数十%〜数倍)、インデックス構築・更新コスト、リアルタイム反映の遅延(near-real-time)、形態素辞書・類義語の管理など運用負担が伴う。したがって「何をインデックス化するか、どれほどリアルタイムであるべきか、ランキングをどう調整するか」を業務特性に合わせて設計しなければならない。

1.2 中核目標

第一の目標はクエリ遅延の最小化である。単語を含む文書を全文書数とは無関係に、該当単語のポスティングリストの大きさに比例する時間で見つけることこそ転置インデックスの存在理由である。第二の目標は関連度に基づく整列であり、単純なマッチングを超えて利用者が望む可能性の高い文書を上位に配置する。第三の目標は自然言語の多様性の吸収であり、語形・類義語・誤字・多言語を解析段階で正規化し再現率(recall)と適合率(precision)の均衡をとる。第四の目標は格納・更新効率であり、ポスティングリストを圧縮しセグメントマージで更新コストを管理する。

2. 転置インデックスの構造とインデックス構築

2.1 全体のインデックスパイプライン

全文検索システムは、文書を受け取り解析(analysis)を経て転置インデックスに反映するインデックスパイプラインと、クエリを解析してポスティングリストをマージ・ランキングする検索パイプラインに分かれる。インデックスパイプラインは原文をトークンに分解し、正規化した後、単語ごとのポスティングリストに文書IDと位置情報を追加する。

flowchart TB
    DOC["原文文書(タイトル/本文)"] --> CA["文字フィルタ(HTML除去/正規化)"]
    CA --> TOK["トークナイザ(形態素/空白分割)"]
    TOK --> TF["トークンフィルタ(小文字化/ストップワード/語幹抽出/類義語)"]
    TF --> TERMS["正規化された用語一覧"]
    TERMS --> DICT["用語辞書(Term Dictionary)"]
    TERMS --> POST["ポスティングリスト更新(docID/頻度/位置)"]
    DICT --> SEG["不変セグメント(Segment)"]
    POST --> SEG
    SEG --> MERGE["セグメントマージ/圧縮"]

解析(analysis)段階は検索品質を左右する核心である。文字フィルタはHTMLタグ除去・Unicode正規化を行い、トークナイザはテキストをトークンに分割する。英語は空白・句読点基準で比較的単純だが、日本語や韓国語は膠着語の特性上、助詞・語尾が付くため形態素解析器(mecab、Nori等)で「検索する → 検索/する」のように意味単位を抽出しなければならない。トークンフィルタは小文字化、ストップワード(the・は・が)除去、語幹抽出(stemming)・見出し語化(lemmatization)、類義語拡張を適用する。インデックス時と検索時に同一の解析器を使わなければマッチングがずれるため、解析器の一貫性は運用の基本原則である。

2.2 中核データ構造 — 用語辞書とポスティングリスト

転置インデックスは大きく用語辞書(term dictionary)とポスティングリスト(posting list)から構成される。用語辞書はインデックス化された全ての一意な単語を整列・格納し、各単語がポスティングリストのどこを指すか(ポインタ)と文書頻度(document frequency)を保持する。高速な単語照会のため、LuceneはFST(Finite State Transducer)に基づく圧縮された辞書を用いる。ポスティングリストはその単語が出現した文書IDを昇順に格納し、ランキングとフレーズ検索のために文書内の出現頻度(term frequency)と位置(position)情報を併せて保持する。

たとえば三つの文書があるとき、「セキュリティ」という単語のポスティングリストは[doc1(tf=2, pos=3,9), doc3(tf=1, pos=5)]の形で格納される。クエリ「セキュリティ」が来ると辞書で「セキュリティ」を見つけてこのリストを即座に読む。フレーズ検索「クラウド セキュリティ」は二つの単語のポスティングリストから文書IDが同じで位置が隣接する場合のみ選別する。このように位置情報はフレーズ・近接検索を可能にするがインデックスサイズを増やす。

構成要素 格納内容 役割 コスト要因
用語辞書 一意な単語/DF/ポインタ 単語照会の入口 一意な単語数
ポスティングリスト docID/TF/位置 マッチング/ランキング/フレーズ検索 総トークン数/位置格納の有無
セグメント 不変の転置インデックス単位 インデックス/検索の物理単位 セグメント数/マージ頻度
ノルム/フィールドデータ 文書長/整列値 ランキング正規化/整列 文書数

2.3 不変セグメントと準リアルタイム更新

Lucene系エンジンは転置インデックスを不変(immutable)セグメント単位で管理する。新しい文書はメモリバッファに溜まり、周期的に(既定で1秒)新しいセグメントへフラッシュされ検索可能になる(near-real-time)。既存セグメントは変更せず、削除は削除マーク(tombstone)で処理する。小さなセグメントが増えると検索が遅くなるため、バックグラウンドでセグメントマージ(merge)によって大きなセグメントに結合し削除文書を整理する。この不変・マージ構造は[[lsm-tree]]と同じ思想で、書き込みを逐次化し読み取りを単純化するが、マージコストと反映遅延を伴う。

3. クエリ処理とランキング

3.1 クエリ処理の流れ

検索クエリもインデックスと同じ解析器を経てトークンに変換された後、各トークンのポスティングリストを読んでブール演算(AND・OR・NOT)で候補文書を得る。次に候補文書にスコアを付け上位K件を返す。

flowchart LR
    Q["ユーザークエリ(クラウド セキュリティ)"] --> QA["クエリ解析(インデックスと同一解析器)"]
    QA --> T1["ポスティング照会: クラウド"]
    QA --> T2["ポスティング照会: セキュリティ"]
    T1 --> MG["リストマージ(AND/OR)"]
    T2 --> MG
    MG --> SC["スコア計算(BM25)"]
    SC --> TOPK["上位K件整列(heap)"]
    TOPK --> RES["結果/ハイライト返却"]

ポスティングリストがdocID昇順に整列されているため、ANDクエリの積集合は二つのリストを同時に前進させるマージでO(リスト長)以内に計算される。長いリストを飛ばすためスキップリスト(skip pointer)を置き不要な比較を減らす。上位K件のみ必要なので全整列の代わりにサイズKのヒープで上位文書を保持し、WAND・Block-Max WANDのような手法で上位に入れない文書を早期に枝刈り(pruning)してクエリを加速する。

3.2 ランキングモデル — TF-IDFとBM25

関連度スコアの基本的直観は二つである。一つは単語頻度(TF)で、ある単語が一つの文書に頻繁に出れば、その文書がその主題である可能性が高い。もう一つは逆文書頻度(IDF)で、全文書にありふれた単語(例:「情報」)は識別力が低いため重みを下げる。[[tf-idf]]はこの二つを掛け合わせて単語-文書の重みを作る。しかし純粋なTF-IDFは頻度が無限に大きくなるほどスコアが線形に増加し文書長を補正できない限界がある。

現代の検索エンジンの既定ランキングはBM25である。BM25はTFを飽和(saturation)させ、同じ単語が10回出ようと100回出ようとスコアが無限に大きくならないようにし(パラメータk1)、文書長で正規化し、長い文書が単に長いという理由で有利にならないようにする(パラメータb、平均文書長に対して)。たとえばElasticsearchは既定でk1=1.2、b=0.75を用いる。実務ではタイトルフィールドに重み(boost)をより与え、新しさ・人気度のような非テキスト信号を関数スコア(function score)で結合して最終順位を調整する。

3.3 フレーズ・近接・誤字・ワイルドカード検索

全文検索は単なる単語の包含を超えて多様なクエリ型を支援する。フレーズ検索(phrase)「クラウド セキュリティ」は二つの単語が文書に共に存在するだけでなく隣接する位置に現れなければならないため、ポスティングリストの位置情報を用いて位置差が1の場合のみ選別する。近接検索(proximity)は二つの単語がN語以内にあればマッチするよう緩和した形である。このようなクエリのために位置情報をインデックスに含めるが、その分インデックスが大きくなるため必要性に応じて選択する。

誤字補正(fuzzy)は編集距離(edit distance)を用いて「セキュリティ」クエリで「セキュリテイ」のような誤字文書まで捉え、LuceneはこのためにLevenshteinオートマトンを用いる。ワイルドカード・接頭辞検索は「クラウド*」のように接頭辞で始まる全ての単語を探すが、このため用語辞書を接頭辞探索が可能な構造に保つ。ただしワイルドカードとファジークエリはマッチ候補の単語が急増しうるため性能コストが大きく、n-gramインデックスや接尾辞処理のような別途戦略で補完する。このようにクエリ型ごとにインデックス設計とコストが異なるため、どの検索機能を提供するかをインデックス時点であらかじめ決めなければならない。

4. 圧縮と性能最適化

ポスティングリストは検索システムで最も大きな格納要素であるため圧縮は必須である。中核技法はデルタエンコーディング(delta encoding)で、整列されたdocIDを絶対値ではなく前の値との差で格納する。たとえば[1024, 1028, 1035]を[1024, 4, 7]に変えると小さな数になり、VByte・PForDelta・FORのような可変長整数圧縮でバイト数を大きく減らす。頻繁に使う単語ほどdocIDの間隔が密で圧縮率が高まるという自然な利点がある。

具体的な数値で見ると、1億件・平均500トークンの文書をインデックス化すると総ポスティングエントリは数百億個に達するが、デルタエンコーディングとVByteでdocIDあたり平均1〜2バイト水準まで減らし、原文の20〜40%の空間に転置インデックスを収められる。頻繁に使う単語の長いリストほど間隔が密で、docIDあたり1バイト未満にも圧縮される。

性能の観点で転置インデックスはディスクI/Oを逐次読み取りにしOSのページキャッシュを活用する。頻繁に使うポスティングはメモリに常駐させ、スキップリストで飛ばし、上位K枝刈りで計算量を減らす。分散環境では文書をシャードに分け、各シャードが地域の転置インデックスを持ち並列検索した後に結果をマージ(scatter-gather)する。ただしIDFのような全域統計がシャードごとに異なりスコア偏差が生じうるため、精密なランキングが必要なら分散頻度集計(DFS query-then-fetch)を用いる。大型ログ分析の事例で数十TBのログを転置インデックス化しキーワード検索を数十msで処理するのがELKスタックの典型的効果である。

5. 比較と適用事例

5.1 転置インデックス vs 逐次走査 vs B木

三つのアプローチは「何に最適化されたか」が異なる。逐次走査(LIKE)はインデックスがなく単純だがデータ規模に線形比例し大規模に不適である。B木は完全一致・範囲検索に優れるが、一つのセル内の複数単語や語形変化・関連度整列を扱えない。転置インデックスは「単語包含 + 関連度整列 + 自然言語解析」に特化し全文検索に適するが、インデックス構築・格納コストとトランザクションの即時性(リアルタイム反映の遅延)を甘受する。

区分 逐次走査(LIKE) B木インデックス 転置インデックス
適したクエリ 少量/単純 正確/範囲一致 単語包含/関連度検索
自然言語解析 不可 不可 トークン化/形態素/類義語
関連度整列 なし なし TF-IDF/BM25
大規模性能 線形劣化 優秀(キー基準) 優秀(単語基準)
書き込み即時性 即時 即時 準リアルタイム(セグメント)

比較の核心は優劣ではなく役割分担である。実務では関係DBが源泉データとトランザクションを担い、変更を[[change-data-capture]]で検索エンジンへ流して転置インデックスを維持するハイブリッド構造が一般的である。

5.2 適用事例

第一に、ログ・可観測性(ELK/OpenSearch)である。アプリケーションログを転置インデックス化しエラーメッセージ・トランザクションIDで即座に検索しダッシュボードで分析する。[[elk-stack]]はこの用途の代表的な組み合わせである。第二に、EC商品検索である。商品名・説明・属性をインデックス化しBM25に在庫・人気度・広告を結合して順位を付け、類義語・誤字補正で「ノート/ラップトップ」「iphone/アイフォン」を併せて捉える。第三に、日本語・韓国語文書検索である。形態素解析(Nori等)で助詞・語尾を除去し複合名詞を分解して再現率を高めつつ、過分解で適合率が下がらないようユーザー辞書と複合語処理を調整する。

6. 深化 — キーワード検索とベクトル検索のハイブリッド

最新動向の核心は疎(sparse)な転置インデックス検索と密(dense)なベクトル検索の結合である。転置インデックスのBM25は単語が正確に一致してこそマッチするため類義語・意味的類似性に弱い(「自動車」クエリが「乗用車」文書を取りこぼす)。逆に埋め込みに基づく[[vector-database]]検索は意味的類似度をよく捉えるが希少なキーワード・固有名詞・正確一致に弱い。そこで二つの結果をRRF(Reciprocal Rank Fusion)などで融合するハイブリッド検索が標準になりつつあり、Elasticsearch・OpenSearchもBM25とkNNベクトル検索を一つのクエリで結合する機能を提供する。

さらに学習された疎表現(SPLADE等)はニューラルネットワークで文書を拡張された単語重みに変換し転置インデックスにそのまま格納することで、転置インデックスの効率と意味拡張を同時に狙う。[[rag]]パイプラインでも一次候補検索にBM25転置インデックスを用いベクトル検索で補強する組み合わせが多い。予想される出題方向としては「① 転置インデックスの構造とクエリ処理を説明しBM25ランキングを論じよ、② キーワード検索とベクトル検索を比較しハイブリッド設計を提示せよ、③ 大規模ログ検索システムを転置インデックス基盤で設計せよ」のような結合型が有力である。

7. 考慮事項および示唆点

第一に、解析器の設計と一貫性である。検索品質の大部分はトークン化・形態素・類義語・ストップワード設計で決まる。インデックス時と検索時に解析器を必ず一致させ、日本語・韓国語は形態素解析器の選択・ユーザー辞書・複合名詞処理で再現率と適合率を秤にかけなければならない。解析器を変えると全体の再インデックス(reindex)が必要なため変更管理手続きを備えるべきである。

第二に、関連度調整と評価体系である。BM25パラメータ、フィールドブースト、新しさ・人気度の結合は業務ごとに異なるべきであり、恣意的な調整ではなくクリックログ・正解集合に基づくNDCG・MRRのような指標でA/B評価しなければならない。ランキングは「感覚」ではなく測定で改善する工学的対象である。

第三に、一貫性とアーキテクチャの境界である。転置インデックスは準リアルタイムで削除・更新が即時に反映されないため、金銭・在庫のように強い一貫性が必要な値は検索結果を信頼の源泉とせず源泉DBで再確認すべきである。源泉DBと検索エンジンの二重化は[[change-data-capture]]・[[transactional-outbox-pattern]]で整合性を保ち、再インデックス・失敗再処理の経路を設計に含める。

第四に、コスト・運用と拡張戦略である。インデックス格納領域・メモリ・セグメントマージ負荷はデータ増加に伴い大きくなる。シャード数・レプリカ・ホット/ウォーム/コールド階層(ILM)でコストと性能を調整し、位置情報のインデックス可否のように機能と容量のトレードオフを業務要求に合わせて選択する。過度なシャードはオーバーヘッドを、過少なシャードは拡張限界を生むため、データ量予測に基づく容量設計が必要である。

第五に、展望と連携技術である。今後の検索はBM25転置インデックス(正確・効率)とベクトル・LLM(意味・対話型)が共存するハイブリッドへ収束し、[[vector-database]]・[[rag]]・[[tf-idf]]・[[lsm-tree]]と併せて理解するとき情報検索全体の地形を一望できる。転置インデックスは数十年来の技術だが、生成AIの時代でも一次候補検索の効率的な基盤として健在である。

参考資料


一言まとめ: 転置インデックスは「単語 → 文書一覧」へ関係を逆転させ大量テキストからキーワードを含む文書を即座に見つけBM25で関連度順に整列する全文検索の中核構造であり、解析器の設計・圧縮・準リアルタイム更新が品質と性能を左右し、今日ではベクトル検索とのハイブリッドへ進化している。