目次を表示する

システム設計とCS概念

全文検索エンジン ── 転置インデックスとランキング

全文検索エンジン ── 転置インデックスとランキング

扱うCS概念：転置インデックス、TF-IDF、BM25、Segmentマージ（LSM-Tree）、シャーディング

検索エンジン内部 — 転置インデックス・BM25・ベクトル検索

この章で何ができるようになるか：全文検索エンジンの内部構造（インデックス構築・クエリ処理・ランキング）を説明できるようになる。Elasticsearch / OpenSearch の設計思想と、RDBMS の LIKE 検索との違いを説明できるようになる。

問題設定

「10億件のウェブページから “分散システム 設計” に関連するものを100ms以内に返せ」

RDBMS でこれをやろうとすると：

-- ❌ 全文LIKE検索（フルスキャン）
SELECT * FROM pages WHERE content LIKE '%分散システム%' AND content LIKE '%設計%';
-- 10億行に対してフルテーブルスキャン → 数時間かかる

なぜ遅いか：LIKE 検索はインデックスを使えない（前方一致インデックスは使えるが、中間一致は不可）。

全文検索エンジンはこれを「事前にインデックスを構築しておく」ことで解決する。

転置インデックス（Inverted Index）

検索エンジンの核心。単語（トークン）から文書IDへのマッピングを事前に作っておく。

文書1: "分散システムの設計と実装"
文書2: "データベースの設計パターン"
文書3: "分散キャッシュの実装"

転置インデックス：
  "分散"   → [文書1, 文書3]
  "システム" → [文書1]
  "設計"   → [文書1, 文書2]
  "実装"   → [文書1, 文書3]
  "データベース" → [文書2]
  "パターン" → [文書2]
  "キャッシュ" → [文書3]

クエリ "分散システム 設計" の処理：

"分散"   → [1, 3]
"システム" → [1]
"設計"   → [1, 2]

AND 演算（全単語を含む文書）：
[1, 3] ∩ [1] ∩ [1, 2] = [1]
→ 文書1 が返る

ポスティングリスト（Posting List）：各単語に対応する（文書ID, 出現位置）のリスト。

posting_list = {
    "分散": [(doc_id=1, positions=[0, 12]), (doc_id=3, positions=[0])],
    "設計": [(doc_id=1, positions=[8]), (doc_id=2, positions=[7])],
}

出現位置（positions）を持つことで「“分散” の直後に “システム” が来る」というフレーズ検索が可能になる。

インデックス構築のパイプライン

graph TD
    Crawl[クローラー<br/>Web ページ収集] --> Parse[HTML パーサー<br/>テキスト抽出]
    Parse --> Tokenize[トークナイザー<br/>単語分割・正規化]
    Tokenize --> Index[インデックスビルダー<br/>転置インデックス構築]
    Index --> Segment[セグメントファイル<br/>ディスクに書き出し]
    Segment --> Merge[セグメントマージ<br/>定期的に統合]
    Merge --> SearchIndex[検索インデックス<br/>クエリ処理]

トークナイズ

日本語の場合、スペースで単語が区切られないため形態素解析が必要だ。

# MeCab（日本語形態素解析器）を使ったトークナイズ
import MeCab

def tokenize_japanese(text: str) -> list[str]:
    tagger = MeCab.Tagger()
    node = tagger.parseToNode(text)
    tokens = []
    while node:
        feature = node.feature.split(',')
        pos = feature[0]  # 品詞
        # 名詞・動詞・形容詞のみをインデックス対象に
        if pos in ['名詞', '動詞', '形容詞']:
            base_form = feature[6] if feature[6] != '*' else node.surface
            tokens.append(base_form)
        node = node.next
    return tokens

# "分散システムの設計" → ["分散", "システム", "設計"]

英語では Porter Stemmer などで語尾変化を吸収する：

"running" → "run"
"distributed" → "distribut"
"designs" → "design"

ランキング：TF-IDF から BM25 へ

「関連する文書」は複数ある。どれを上位に表示するか。

TF-IDF（Term Frequency - Inverse Document Frequency）

TF（Term Frequency）：その文書内での単語の出現頻度
  TF(t, d) = (文書d内の単語tの出現回数) / (文書d内の全単語数)

IDF（Inverse Document Frequency）：単語の希少性
  IDF(t) = log(全文書数 / 単語tを含む文書数)

TF-IDF スコア：TF × IDF
import math
from collections import Counter

def compute_tf_idf(corpus: list[list[str]], query_terms: list[str]):
    N = len(corpus)
    scores = []

    for doc_id, doc in enumerate(corpus):
        score = 0.0
        tf_counter = Counter(doc)
        
        for term in query_terms:
            # TF: 文書内の出現頻度
            tf = tf_counter[term] / len(doc) if len(doc) > 0 else 0
            
            # DF: 何文書にこの単語が出現するか
            df = sum(1 for d in corpus if term in d)
            
            # IDF: 希少な単語ほど高いスコア
            idf = math.log((N + 1) / (df + 1)) + 1  # +1 でゼロ除算回避
            
            score += tf * idf
        
        scores.append((doc_id, score))
    
    return sorted(scores, key=lambda x: -x[1])  # スコア降順

IDF の直感：「の」「は」「が」のような助詞は全文書に出現するため IDF が低い。「量子コンピューター」のような専門用語は少数の文書にしか出ないため IDF が高い。

BM25（Best Matching 25）

現代の検索エンジンで標準的に使われるランキングアルゴリズム。TF-IDF の改良版で、文書長のバイアスを補正する。

def bm25_score(term: str, doc: list[str], corpus: list[list[str]],
               k1: float = 1.2, b: float = 0.75) -> float:
    """
    k1: TF の飽和パラメーター（高いほど出現頻度の影響が強い。標準デフォルト=1.2）
    b:  文書長の正規化強度（0=正規化なし, 1=完全正規化）
    """
    N = len(corpus)
    df = sum(1 for d in corpus if term in d)
    idf = math.log((N - df + 0.5) / (df + 0.5) + 1)

    tf = doc.count(term)
    doc_len = len(doc)
    avg_doc_len = sum(len(d) for d in corpus) / N

    # 文書長による TF の正規化
    # 長い文書ほど単語が多く出るバイアスを補正
    tf_normalized = tf * (k1 + 1) / (tf + k1 * (1 - b + b * doc_len / avg_doc_len))

    return idf * tf_normalized

TF-IDF との違い：

TF-IDF の問題：
  文書A（100単語）: "設計" が 5回 → TF = 0.05
  文書B（1000単語）: "設計" が 10回 → TF = 0.01
  → 文書A の方が "設計" に特化しているのに、文書Bの方がスコアが高くなりうる

BM25 の改善：
  文書長で TF を正規化 → 短い文書でも公平に評価される
  TF の飽和：同じ単語が100回出ても10回の10倍にはならない（収穫逓減）

セグメントとマージ（LSM-Tree）

大量の文書を継続的にインデックスに追加する際、毎回全インデックスを再構築するのは非効率だ。Elasticsearch（Lucene ベース）はセグメントという単位でこれを解決する。

graph TD
    NewDocs[新規文書] --> Buffer[メモリバッファ]
    Buffer -->|閾値を超えたら| Seg1[Segment 1<br/>不変・小]
    Buffer -->|閾値を超えたら| Seg2[Segment 2<br/>不変・小]
    Buffer -->|閾値を超えたら| Seg3[Segment 3<br/>不変・小]
    Seg1 & Seg2 & Seg3 -->|バックグラウンドマージ| Seg4[Segment 4<br/>不変・大]
    Seg4 -->|さらにマージ| Seg5[Segment 5<br/>不変・より大]

セグメントは不変（Immutable）：一度書き出したら変更しない。

削除のしかた：実際には削除せず「削除済みフラグ」を別ファイル（.del ファイル）に記録する。クエリ結果から除外するのはフラグを見て行い、実際のストレージ解放はマージ時に行う。

なぜこの設計か：

  • ランダム書き込みを避け、シーケンシャル書き込みに変換（高速）
  • セグメント内部はソート済みのため、マージは O(N) でできる（マージソート）
  • 検索はすべてのセグメントを並列に検索して結果をマージ

これは **LSM-Tree（Log-Structured Merge-Tree）**のアイデアそのものだ。Cassandra、LevelDB、RocksDB も同じ原理を使っている。

分散検索：シャーディングとレプリカ

1台のサーバーに収まらない規模（100億文書など）では、インデックスを分割する必要がある。

graph TD
    Query[クエリ] --> Coordinator[コーディネーターノード]
    Coordinator --> Shard1[シャード1<br/>文書0〜10億]
    Coordinator --> Shard2[シャード2<br/>文書10〜20億]
    Coordinator --> Shard3[シャード3<br/>文書20〜30億]
    Shard1 --> R1[各シャードの<br/>上位10件を返す]
    Shard2 --> R1
    Shard3 --> R1
    R1 --> Coordinator
    Coordinator --> Merge2[全体の上位10件に<br/>再ランキング]
    Merge2 --> Result[結果を返す]

分散ランキングの問題：各シャードは自分のシャード内のスコアでランキングするが、IDF の計算に「全文書数」が必要だ。シャード1は全体の文書数を知らない。

解決策：

  1. グローバル IDF を事前計算：全シャードから DF（単語の出現文書数）を集計し、グローバル IDF テーブルを作って全シャードで共有
  2. 2フェーズクエリ：第1フェーズで各シャードのスコアを収集 → 第2フェーズで正確な IDF でリランキング

ベクトル検索（近似最近傍探索）

2025年以降、LLM の埋め込み（embedding）と組み合わせたベクトル検索が普及している。キーワード検索では「同じ意味だが違う単語」を拾えない問題をベクトル類似度で解決する。

from sentence_transformers import SentenceTransformer
import numpy as np

model = SentenceTransformer('sentence-transformers/paraphrase-multilingual-MiniLM-L12-v2')

# 文書をベクトル化してインデックス
documents = [
    "分散システムの設計パターン",
    "マイクロサービスアーキテクチャ入門",
    "猫の飼い方ガイド"
]
doc_vectors = model.encode(documents)

# クエリのベクトル化
query = "スケーラブルなシステムを作るには"
query_vector = model.encode([query])[0]

# コサイン類似度でランキング
def cosine_similarity(a, b):
    return np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b))

scores = [(i, cosine_similarity(query_vector, dv)) for i, dv in enumerate(doc_vectors)]
scores.sort(key=lambda x: -x[1])

# → 文書0（分散システム）が最も類似
# → キーワード "分散" が含まれなくても意味で検索できる

HNSW（Hierarchical Navigable Small World）：ベクトル空間での近似最近傍探索を高速化するグラフ構造。完全探索は O(N) だが HNSW は O(log N) に近い速度で近似結果を返す。Elasticsearch、pgvector、Pinecone がこれを実装している。

まとめ

課題解決策CS概念
LIKE 検索が遅い転置インデックス事前計算 + 空間・時間トレードオフ
関連度のランキングBM25（文書長補正あり）TF-IDF の改良
継続的なインデックス更新セグメント + バックグラウンドマージLSM-Tree
削除の扱いソフトデリート（.del ファイル）不変データ構造
大規模な水平スケールシャーディング + グローバルIDF共有分散集計
意味的類似検索ベクトル埋め込み + HNSW近似最近傍探索

次章（エピローグ）でシリーズ全体を振り返る。