# 転置インデックス ## 定義 転置インデックス(inverted index)とは、全文検索において語(term)をキーとし、その語を含む文書IDの列(postings list)を値とするキーバリュー構造である。全文検索は本質的には多次元クエリの一種とみなせる: テキストに現れうる各語を1次元とみなし、ある語 x を含む文書は次元 x の値が1、含まない文書は0となる。「red apples」の検索は、red 次元と apples 次元がともに1であるような文書を求めるクエリに等しい。文書IDが連番であれば postings list は疎なビットマップとしても表現でき、2つの語を含む文書を求める処理は[[列指向OLAPデータベース]]で説明されるビットマップのビット単位 AND と同型になる。Lucene(Elasticsearch・Solr の基盤)は term から postings list への写像を SSTable ライクなソート済みファイルへ格納し、[[LSMツリー]]と同じログ構造化アプローチでバックグラウンドマージする。PostgreSQL の GIN 索引型も postings list ベースで全文検索と JSON 文書内索引を提供する。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] "Full-Text Search") ## 拡張手法 - **n-gram(トライグラム)索引**: 語分割の代わりに長さ n の部分文字列(n=3ならトライグラム)すべてを索引化する。任意の3文字以上の部分文字列検索や正規表現検索が可能になる一方、索引サイズは大きくなる。 - **fuzzy search(タイポ耐性)**: Lucene は語の集合を文字上の有限状態オートマトン(トライに類似)として保持し、これを Levenshtein automaton へ変換することで指定した編集距離(edit distance)内の語を効率的に検索する。 ## 横断的知見 - 現時点では単一ソースからの導入であるため、複数ソースを突き合わせた横断的知見は未蓄積である。転置インデックスの postings list がビットマップとして表現できるという性質は、[[列指向OLAPデータベース]]のビットマップ符号化・ビット単位AND/ORと同一の演算基盤を共有しており、今後 OLAP 系ソースとの突き合わせで具体的な実装上の共通点・相違点を追記する余地がある。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]]) ## 未解決の問い - Lucene の SSTable ライクなファイルは[[LSMツリー]]のコンパクション戦略(size-tiered / leveled)のどちらに近いか。全文検索特有のワークロード(挿入頻度・検索パターン)がコンパクション戦略選択に与える影響は。 - トライグラム索引のサイズは元テキストの何倍程度になるか。ビットマップ圧縮(roaring bitmap等)を組み合わせた場合の圧縮効果は定量化されているか。 - 転置インデックスによる語彙ベースの全文検索と、[[ベクトル検索インデックス]]による意味検索(semantic search)を同一クエリに対しハイブリッドに組み合わせる設計(BM25 + ベクトル類似度の融合等)は、この概念の範囲でどう位置づけられるか。 ## 関連 - ソース: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] - 概念: [[LSMツリー]] / [[列指向OLAPデータベース]] / [[ベクトル検索インデックス]] / [[多次元索引]] - エンティティ: [[Lucene]] / [[PostgreSQL]] ## 出典 - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]](§Full-Text Search — 転置インデックスの定義、Lucene の SSTable ライク実装、n-gram、Levenshtein automaton)