定義
ブログ・文書の検索窓のように、「この単語が入った記事の一覧」を素早く取り出したいときに使うデータ構造だ。あらかじめ「どの単語がどの文書に出るか」の表を作っておけば、検索するとき文書を全部漁らずにその表だけを見ればよい。
用語を解くと、**トークン(token)**は文書を検索単位に刻んだ断片(通常は単語一つ)、**逆索引(inverted index)**は「トークン → そのトークンを含む文書の一覧」方向のマッピングだ。元の文書は「文書 → その中の単語たち」の順だが、これを逆に(inverted)ひっくり返したという意味だ。全文検索(full-text search)はこの逆索引をあらかじめ作ってクエリを高速に処理する技法で、その逆索引をプロセスメモリに丸ごと載せて使うのがインメモリ検索だ。
なぜ必要か
文書全体を毎回巡回して部分文字列を探すと、文書数 N とクエリ長に比例して遅くなり、ランキング・タイポ許容・接頭辞マッチングを自前で実装しなければならない。逆索引はこれを事前計算されたデータ構造に移し、検索時点のコストを減らす。常駐検索サーバーを置きにくい環境では、事前ビルドしたインデックスをメモリに載せて同じ探索品質を軽く提供できる。
動作原理
- 索引段階: 各文書をトークン化(単語単位に刻む)し、トークンごとに出現文書 id の一覧(posting list — 一つのトークンが出る文書の名簿)を作る。
- クエリ段階: 検索語を同じ方式でトークン化し、各トークンの posting list を積集合/和集合して候補文書を集める。
- ランキング: フィールド重み(タイトル > タグ > 本文)、TF(term frequency — 一つの文書内でその単語が何回出るか)、近接度(検索語同士がどれだけ近いか)などで候補を採点して並べる。
- prefix/fuzzy マッチング: prefix(接頭辞 — "app" で "apple" までマッチ)と fuzzy(編集距離ベースの近似マッチング — タイポ数文字を許容)で部分入力とタイポを吸収する。
実務適用
索引はビルド成果物として固定し、ランタイム生成コストをなくし、warm インスタンスではシングルトンで再利用する。
トレードオフ
インメモリライブラリ型は外部ホスティングなしで軽く、デプロイが単純だが、文書数が多くなるとメモリ・ロード時間が増え、CJK 形態素解析のような高度な処理に弱い。常駐型検索エンジンは言語別パイプライン・大規模・増分更新に強いが、別プロセス・ホスティングコストがかかる。
使ってはいけない場合
数十万〜数百万文書、複雑なフィルタ・ファセット・言語別形態素品質が核心なら、インメモリライブラリ型は不適だ。このときは常駐型検索エンジンを使う。また、頻繁に変わる文書をリアルタイムに増分索引する必要があるなら、ビルドタイム固定インデックスは合わない。
よくある間違い
- 空白ベースのトークナイザーで CJK テキストを索引し、韓国語検索品質が落ちる。
- 全フィールドを同じ重みにして、タイトル一致が本文一致に埋もれる。
- インデックスをリクエストごとに新しくビルドし、コールドスタート・遅延を増やす(シングルトン未使用)。
関連概念
- serverless-stateless-execution — 常駐エンジンを載せられないとき、ライブラリ型インデックスを関数の中で使う背景。