ストーリー

要件の整理

interface SearchEngineRequirements {
  functional: {
    fullTextSearch: "全文検索（キーワードでドキュメントを検索）";
    autoComplete: "オートコンプリート（入力中の候補表示）";
    faceting: "ファセット検索（カテゴリ・価格帯で絞り込み）";
    ranking: "関連度によるランキング";
    highlighting: "検索キーワードのハイライト";
  };
  nonFunctional: {
    searchLatency: "p99 < 200ms";
    indexingLatency: "ドキュメント更新から検索可能まで < 1分";
    documentCount: "10億ドキュメント";
    queryQPS: "10,000 QPS";
  };
}

コアコンセプト：転置インデックス

// 転置インデックスの仕組み
// 通常のインデックス: ドキュメントID → 内容
// 転置インデックス: 単語 → ドキュメントIDのリスト

interface InvertedIndex {
  // "TypeScript" → [doc1, doc3, doc7, doc15, ...]
  // "設計" → [doc2, doc3, doc5, doc8, ...]
  // "TypeScript" AND "設計" → 共通: [doc3]
  [term: string]: PostingList;
}

interface PostingList {
  documentIds: number[];      // ドキュメントIDのソート済みリスト
  termFrequency: number[];    // 各ドキュメントでの出現回数
  positions: number[][];      // 各ドキュメントでの出現位置
}

// インデックス構築パイプライン
class IndexingPipeline {
  async index(document: Document): Promise<void> {
    // 1. テキスト抽出
    const text = this.extractText(document);

    // 2. トークナイゼーション（日本語は形態素解析が必要）
    const tokens = this.tokenizer.tokenize(text);
    // "TypeScriptの設計パターン" → ["TypeScript", "設計", "パターン"]

    // 3. 正規化（小文字化、ステミング）
    const normalizedTokens = tokens.map(t => this.normalize(t));

    // 4. 転置インデックスに追加
    for (const token of normalizedTokens) {
      await this.invertedIndex.addPosting(token, document.id);
    }
  }
}

ハイレベル設計

┌──────────────────────────────────────────────────────┐
│                                                      │
│  [検索クエリ]──→[クエリパーサー]──→[検索コーディネーター] │
│                                        │             │
│                           ┌────────────┼────────┐    │
│                           ▼            ▼        ▼    │
│                      [シャード1]   [シャード2]  [シャードN]│
│                      転置インデックス                   │
│                           │            │        │    │
│                           └────────────┼────────┘    │
│                                        ▼             │
│                               [結果マージ&ランキング]  │
│                                        │             │
│  [ドキュメント]──→[インデックスパイプライン]──→[シャード群] │
│                                                      │
│  [オートコンプリート]──→[Trie/Prefix Index (Redis)]     │
│                                                      │
└──────────────────────────────────────────────────────┘

ランキングアルゴリズム

// TF-IDF: 基本的な関連度スコアリング
class TFIDFScorer {
  // TF (Term Frequency): ドキュメント内での出現頻度
  termFrequency(term: string, document: string[]): number {
    const count = document.filter(t => t === term).length;
    return count / document.length;
  }

  // IDF (Inverse Document Frequency): 全ドキュメントでの希少性
  inverseDocumentFrequency(term: string, totalDocs: number, docsWithTerm: number): number {
    return Math.log(totalDocs / (1 + docsWithTerm));
  }

  // TF-IDF = TF * IDF
  score(tf: number, idf: number): number {
    return tf * idf;
  }
}

// BM25: TF-IDFの改良版（Elasticsearchのデフォルト）
class BM25Scorer {
  private readonly k1 = 1.2; // TF飽和パラメータ
  private readonly b = 0.75; // 文書長正規化パラメータ

  score(tf: number, idf: number, docLength: number, avgDocLength: number): number {
    const tfComponent = (tf * (this.k1 + 1)) /
      (tf + this.k1 * (1 - this.b + this.b * (docLength / avgDocLength)));
    return idf * tfComponent;
  }
}

オートコンプリート

// Trieベースのオートコンプリート
class AutoComplete {
  // 入力: "sys" → 候補: ["system design", "system architecture", ...]
  // 実装: Redis Sorted Set + プレフィックス検索
  async getSuggestions(prefix: string, limit: number = 10): Promise<string[]> {
    // 人気度スコアでソートされた候補を返す
    return this.redis.zrevrangebylex(
      'autocomplete',
      `[${prefix}\xff`, `[${prefix}`,
      'LIMIT', 0, limit
    );
  }
}

まとめ

チェックリスト

• 転置インデックスの仕組みを説明できた
• 検索パイプラインの全体像を理解した
• TF-IDFとBM25の違いを把握した
• オートコンプリートの実装方法を理解した

次のステップへ

次は「レコメンデーションシステムの設計」を学びます。ユーザーの行動データから最適なコンテンツを推薦する仕組みを設計しましょう。

推定読了時間: 25分