検索機能は、ほぼすべてのサービスに存在します。
掲示板、ログ検索、ドキュメント検索、そして最近ではLLMを活用したRAGでも検索は中核となるインフラです。
しかし、検索が内部でどのように動作しているかを正確に理解して使っているケースは意外と多くありません。
本記事では、検索システムの基本概念を段階的に解説します。
1. 検索はどのように動作するのか？
以下のようなデータがあるとします。
doc1: OpenSearch uses BM25
doc2: BM25 is a ranking algorithm
doc3: Redis improves performance
ユーザーが検索します：
BM25
検索システムは：
- BM25を含む文書を見つけ
- 関連度の高い順に並べて
- 結果を返します
ここで重要なのは：
どの文書がより関連度が高いのか？
です。
この関連度を計算するのが検索アルゴリズムです。
2. inverted index — 検索が高速な理由
検索の高速化を支えているのが inverted index（転置インデックス）です。
通常のデータ構造：
doc1 → "OpenSearch uses BM25"
doc2 → "BM25 is ranking algorithm"
inverted index：
"OpenSearch" → doc1
"BM25" → doc1, doc2
"Redis" → doc3
つまり：
単語 → 文書リスト
という構造で保存します。
そのため検索時に：
"BM25" → doc1, doc2
とすぐに見つけることができます。
すべての文書をスキャンする必要がないため、非常に高速です。
3. TF-IDF — 最も基本的なスコアリングアルゴリズム
検索では単語が含まれているかどうかだけでなく、
その単語がどれほど重要か
を評価する必要があります。
TF-IDFは、そのための基本的なアルゴリズムです。
TF（Term Frequency）
文書内で単語が出現する回数です。
例：
doc1: BM25 BM25 search
TF：
BM25 → 2
search → 1
出現回数が多いほど重要と判断されます。
IDF（Inverse Document Frequency）
全体の文書の中でどれだけ珍しい単語かを表します。
例：
全体文書数: 1000
BM25を含む文書: 10
BM25は珍しいため重要度が高いです。
逆に：
the → ほぼすべての文書に存在
重要度は低くなります。
TF-IDF スコア
score = TF × IDF
4. TF-IDFの問題点
単語を繰り返すことでスコアが過剰に上がる問題があります。
5. BM25 — 現代検索の標準アルゴリズム
BM25はTF-IDFの改良版です。
主な改善点：
- TFの増加に制限を設ける（saturation）
- 文書長の正規化改善
現在の標準アルゴリズムです。
6. Vector Search — 意味ベースの検索
単語ではなく意味ベクトルで検索します。
例：
car → vector
automobile → vector
意味が近いため一致可能です。
7. KNN — semantic searchの中核
KNNは：
最も近いK個のベクトルを見つけるアルゴリズム
semantic検索の基盤です。
8. BM25とKNNの違い
| 項目 | BM25 | KNN |
|---|---|---|
| ベース | キーワード | ベクトル |
| semantic検索 | 不可 | 可能 |
| 同義語対応 | 不可 | 可能 |