【2026年10月版】

索引と探す技術（第3回）― 語による検索と順位付け

公開日: 2026/10/02
読了時間: 約 24分

第2回では、キーが一致するかを調べる構造を扱った。第3回は、文字列や語で探し、見つかった文書に順位をつける方法を扱う。

1. 文字列走査の古典アルゴリズム

一つの文字列の中を検索する場合も、前処理や要約を使って比較の回数を減らせる。

たとえば ABABC というパターンを探していて、入力の ABAB までが一致し、次の文字で食い違ったとする。一致した ABAB の末尾の AB はパターンの先頭の AB と同じなので、パターンを二文字ずらせばその AB はすでに一致済みだと分かり、入力を読み戻すことなく続きの文字から比べられる。クヌース・モリス・プラット法は、一致した部分の末尾がパターンの先頭とどれだけ重なるかを前処理で表にしておき、食い違うたびにその表を引いてパターンをずらす。教科書ではこれを、既に一致したパターンの接頭辞と接尾辞の情報を使い、不一致が起きたときも入力の読み位置を進めたまま検索を続ける方法と説明する。入力の各文字を読み戻すことなく進むので、前処理と検索を合わせて入力とパターンの長さに比例する時間、つまり線形時間で終わる。

ボイヤー・ムーア法はパターンの末尾側から比較し、不一致になった文字や一致済みの接尾辞をもとに大きく読み飛ばす。自然言語のような入力では、読み飛ばせる文字の分がそのまま速さにつながる。

ラビン・カープ法は、パターンと同じ長さの窓を入力の上で一文字ずつずらしながら、窓から出る文字の分を引いて入る文字の分を足すことで、窓の中の部分文字列のハッシュを少ない計算で作り直す。これをハッシュのローリング更新と呼び、パターンと同じハッシュを持つ位置だけを詳しく比較する。複数パターンの扱いや、第2回で扱った変更検知とのつながりが分かりやすい方式である。

エイホ・コラシック法は複数のパターンをトライ木と有限オートマトンにまとめ、一度の走査で多数のパターンを検索する。ウイルス定義、禁止語の検出、IDS、ログ分類のように、パターンの数が多い用途に向く。

いずれの方式も、安価な要約で候補を絞り、必要な箇所だけを正確に確認するという構図を共有している。

どの方式が速いかは、文字の種類とパターンの長さによって変わる。Faro と Lecroq の評価は、80を超える照合アルゴリズムを、アルファベットの大きさを2から256まで、パターンの長さを4段階に分けて比較した。2値のアルファベットの長いパターンでは SSEF が、256文字のアルファベットの最も短いパターンでは FJS が最速になるというように、条件ごとに最速のアルゴリズムが入れ替わった。これは2010年時点のアルゴリズム集合での結果であり、使う側は、必ず自分のテキストの文字種とパターン長で測り直す必要がある。

2. 転置索引 ― 語から文書への対応

通常の DB 索引が文書 ID から属性を引くのに対し、転置索引は語から文書 ID を引く。

database -> [3, 18, 42, 91]
index    -> [7, 18, 55]
search   -> [1, 7, 18, 23]

実際の転置索引は、文書 ID のほかに出現回数、文書内の位置、フィールド、ペイロード、スコア計算用の統計、圧縮した docID の差分も保持する。構造は辞書とポスティングリストに分かれており、語ごとに対応する文書集合を取り出す。

3. スコアの系譜 ― TF-IDF から BM25 へ

語の出現回数だけで順位をつけると、どの文書にも現れる語が順位を決めてしまう。スパーク・ジョーンズは1972年に、語の重みは文書集合での出現頻度に応じて決めるべきだと論じた。技術文書の集まりを例にとると、「データ」のようにほとんどの文書に出てくる語は、一致しても文書を見分ける手がかりとして弱い。「ブルームフィルタ」のように一部の文書にだけ出てくる語が一致すれば、その文書が探しているものである見込みはずっと高くなる。まれで特異な語での一致は、頻出する語での一致より価値が大きいという考え方で、これを、その語を含む文書が少ないほど重みを大きくする形で表したものが IDF(逆文書頻度)になる。論文は3つのテストコレクションで、この単純な手続きによって性能が大きく向上したと報告している。

BM25 はその後、確率的関連度モデルの研究から生まれた。ロバートソンとウォーカーが1994年に提案した、2-ポアソンモデルの近似に由来する重み付けである。このモデルは、ある語の出現回数を、その語が主題になっている文書と、ついでに触れただけの文書という二種類の文書の混ざりとして見る。

BM25 は単語の希少性、文書内頻度、文書長をもとに文書を並べる方式で、順位付けに長く使われている。検索語が文書に一度現れることには大きな意味があり、二度目、三度目と増えるにつれて一回あたりの意味は小さくなっていくので、同じ単語が繰り返されたときの寄与は、回数とともに上限へ近づいて飽和するように設計されている。文書長も同じ考え方で扱い、長い文書は多くの語を含むぶん偶然に検索語を含みやすいため、文書が長いほど出現回数の重みを割り引く。

全文検索は、転置索引から候補を取り出し、BM25 などで順位をつける二段階で動く。この二段目の計算をさらに削るのが WAND や Block-Max WAND である。上位 k 件を探している途中では、その時点で k 番目に入っている文書のスコアが合格ラインになる。語ごとにスコアの最大値を前もって記録しておけば、まだ読んでいない文書がどれほど条件に合っても届く点数の上限を見積もれるので、その上限が合格ラインを下回る文書はスコアを計算する前に飛ばせる。論文の言葉では、その時点の上位 k 件の閾値をスコアの上限が下回るポスティングを途中で除外する、という処理になる。Lucene はポスティングリストをブロックに分け、ブロックごとにスコアの上限を持たせている。MAXSCORE や WAND 系のスコアラーがブロック単位で読み飛ばす最適化は、現在も改良が続いている。

そのため全文検索の実行時間を左右するのは、条件に一致するポスティングの総数ではない。上位 k 件の閾値によって、そのうち何割を読み飛ばせるかで決まる。

4. リンク構造による順位付け ― PageRank とリンク解析

語の一致が見ているのは文書の内容だけだが、文書同士のリンクも順位の信号になる。

ブリンとペイジが1998年の論文で示した PageRank は、リンクを辿り続ける利用者(ランダムサーファー)がそのページを訪れる確率を、ページの重要度とする。この利用者はリンクを先へ辿る操作だけを繰り返し、ときどき飽きて別のランダムなページから辿り直す。ページ A に T1 から Tn がリンクしているとき、PR(A) = (1−d) + d × (PR(T1)/C(T1) + … + PR(Tn)/C(Tn)) と定義される。C(T) は T の出リンク数、d はダンピング係数で、論文は通常 0.85 に設定すると書いている。式の後半は、リンク元の Ti が持つ値を出リンクの本数で等分し、そのうち A へ向かう一本分を A が受け取ることを表しているので、多くのページから、それも値の大きいページからリンクされるほど A の値は大きくなる。式の上では、サーファーが d の割合でリンクを辿り、残りの 1−d の割合でリンクと関係なく別のページへ移ると読める。全ページに同じ値を配ってからこの式を何度も当てはめると、値はやがてほとんど動かなくなり、その落ち着いた値が PageRank になる。線形代数の言葉では、PageRank は正規化したリンク行列の主固有ベクトルに対応し、この単純な反復で計算できる。論文は、2,600万ページの PageRank を中規模のワークステーションで数時間で計算できると述べている。

ジャンプ先を特定のページ群に限る変種を使うと、順位を個人ごとに変えられる。この Personalized PageRank は現在、グラフ検索にも使われている。HippoRAG は LLM で文書から知識グラフを作り、質問に含まれる概念を起点に Personalized PageRank を走らせて文書を探す。

ウェブ検索でも PageRank は使われ続けている。Google はランキングシステムの解説で、PageRank を最初のリリース当時から使っているコアランキングシステムの一つに挙げ、仕組みは当時から大きく進化したものの、今もコアランキングシステムの一部だと説明している。リンクが順位を押し上げる仕組みは、リンクスパムも生んだ。その対策である TrustRank は、人手で評価した200サイト未満のシード集合を起点に、リンクを辿って信頼を伝播させる。実験では、ウェブ上のスパムのうち有意な割合を除外できたと報告している。

5. 信号の統合 ― ランキング学習とリランカー

BM25 のスコア、PageRank、クリック率のような信号を一つの順位にまとめるとき、各信号の重みを学習するのがランキング学習（Learning to Rank）である。Burges の概説によると、RankNet は、同じクエリに対する二つの文書の組を取り出し、関連の高いほうが上に来ているかを確かめて、上下が逆になっている組が減るように学習する。概説の言葉では、文書対の誤りの数を滑らかに近似して最適化する。その最適化の目的は、NDCG のように上位を重視する指標とずれている。文書のスコアを少しずつ動かしても、順位は二つの文書が入れ替わる瞬間にだけ段差のように変わるので、並べ替えを含むこうした指標は微分不能で、学習に必要な改善の向きを指標から直接得るのが難しい。そこで LambdaRank は、コスト関数を書き下す代わりに、文書ごとに上下どちらへどれだけ動かすべきかという望ましい勾配(λ)を直接定める。その大きさを、二つの文書を入れ替えたときに NDCG がどれだけ変わるかに合わせるので、上位での並びの誤りほど強く直される。これを勾配ブースティング木で実装したのが LambdaMART で、そのアンサンブルは2010年の Yahoo! Learning To Rank Challenge の Track 1 で優勝した。

表形式の数値特徴をまとめる場面では、木ベースの手法が強い。Qin らの ICLR 2021 の論文は、当時のニューラルな順位付けモデルの多くが、公開されている木ベースの最良の実装に大差で劣ることを示し、その差を縮める枠組みを提案した。ただしこの結論は、人手で設計した特徴を使う設定に限って成り立つ。

文書の本文を直接読んで順位をつける役割は、ニューラルなモデルが担う。monoBERT は MS MARCO のパッセージ検索で、MRR@10 を従来の最良から相対で27%上回った。ただしクエリと文書を一緒に BERT に通すため、再順位付けの計算が重い。ColBERT はクエリと文書を別々に符号化し、軽い類似度計算で突き合わせる late interaction を使う。文書側の符号化は索引を作るときに済ませておけるので、検索のたびに重いモデルに通すのはクエリだけになり、あとはクエリの各語について文書の中で最も近い語を探し、その近さを足し合わせてスコアにする。BM25 の上位1,000件を再順位付けする設定で、MRR@10 は 34.9 と BERT-base の 34.7 に並び、遅延は 61 ms で BERT-base の 10,700 ms の約175分の1だった。BM25 単独の MRR@10 は 16.7 である。

LLM に順位を直接生成させる方法もある。RankGPT は BM25 の候補を再順位付けし、BEIR の平均 nDCG@10 を BM25 の 43.42 から GPT-4 で 53.68 に上げた。BEIR では、GPT-3.5 が再順位付けした上位30件を GPT-4 が再順位付けする設定にしてコストを抑えている。TREC では1クエリあたり約19,890トークンを使い、当時の API 価格で約0.6ドルかかった。再順位付けで拾えるのは、第一段の候補に含まれる文書だけである。第一段の再現率が、そのまま性能の上限を決めてしまう。

6. 順位の評価指標と評価データ

順位の評価指標として、MS MARCO は MRR@10 を、BEIR は nDCG@10 と Recall@100 を使う。MRR@10 は、上位10件の中で最初に正解が現れた順位の逆数をクエリごとに求めて平均したもので、正解が一位なら満点、二位なら半分になり、上位10件の外なら零として数える。利用者が上から読んで最初の当たりに出会うまでの近さを測る指標といえる。nDCG@10 は、上位10件それぞれの関連度を、下の順位ほど割り引いてから足し合わせ、理想的な並びで得られる値を満点として割合で表す。「とても関連する」「少し関連する」のような段階のある判定を、そのまま点数に使える。Recall@100 は、正解の文書のうち上位100件に入った割合で、後段の再順位付けに渡す候補が正解をどれだけ拾えているかを見るのに向く。Burges の整理では、MRR と MAP は関連の有無という二値の判定向けで、NDCG は多段階の関連度と順位による割引を扱う。

評価データそのものにも偏りがある。TREC の評価データは、参加システムの出力を集めて関連を判定するプーリングで作られる。Voorhees の研究は、判定者によって関連判定が違っても、システムの順位は非常に高い相関を保つことを示した。ただしそれが言えるのは、あくまでプールに貢献したシステム群の範囲に限られる。新しい方式がプールの外にある文書を返すと、その文書は未判定のため無関連として扱われ、新しい方式が不利になる。

BEIR は、18のデータセットで10のシステムをゼロショットで比較した。TREC-COVID では、上位10件に含まれる未判定の文書の割合が、BM25 で6.4%、ANCE で14.4%、TAS-B で31.8%あった。未判定の980組を手作業で追加判定して nDCG@10 を計算し直すと、BM25 は 0.656 から 0.668 と微増にとどまり、ANCE は 0.654 から 0.735 に上がって BM25 を上回った。評価データの作られ方が、BM25 に有利に働いていたことになる。

BEIR の結果表では、データセットごとに勝者が入れ替わる。Touché-2020 では BM25 の 0.367 が、DPR、ANCE、TAS-B、GenQ、ColBERT の 0.131 から 0.240 を上回る。Quora では ANCE の 0.852 と TAS-B の 0.835 が、BM25 の 0.789 を上回る。論文は、BM25 は頑健なベースラインであり、学習したデータでの成績は別のデータでの成績の目安にならない、と結論づけている。

MS MARCO は、1つのクエリに既知の関連文書がほぼ一つだけの疎なラベルで作られている。Arabzadeh らの調査では、評価者は現代のニューラルモデルの上位の結果を判定済みの正解より好むことが多く、MRR が満点になる理想的な順位付けよりも好んだ。評価データの側が、手法の進歩に遅れをとっていたわけだ。

データによって手法の順位が入れ替わる問題は、第8回で、手法を選ぶ観点から改めて扱う。

第4回では、語が異なっていても内容の近いものを探す場合に進み、文書や画像を距離の近さで探すベクトル検索と、利用者の履歴から項目を薦める推薦を扱う。