\def\vector#1{\boldsymbol{#1}}

全文検索

2024年7月5日 #FullTextSearch #InvertedIndex

1. 概要

全文検索 (full-text search) はテキストデータベースや文書集合として存在する非構造化テキストから特定の単語やフレーズを含む文書とその出現位置を取得する検索技術である。情報検索におけるキーワード検索 (索引語検索、疎検索) に相当し、文書とクエリーをターム (単語) の集合として表現し、転置インデックスを用いて照合する方法を指す。

テキストの先頭から末尾までを走査してパターンに一致する位置を見つけ出す逐次検索 (sequential search) (文字列マッチング) と異なり、全文検索はあらかじめ文書集合から転置インデックスを構築しておくことで、文書数の増加に対して検索時間が伸びにくい索引検索 (index search) を行う。

1. 概要
2. テキスト解析
3. インデックス作成
4. 検索
5. クエリと文書の拡張
1. 5.1. クエリ拡張
2. 5.2. 文書拡張
6. ランキング付きの検索
7. 参考文献

2. テキスト解析

全文検索におけるテキスト解析 (text analysis) は文書を効率的に検索できるようにテキストを構造化する。インデックス (索引) を作成するための前処理である。

2.1. トークン化

トークン化 (tokenization) は文書を検索対象となる単位のトークン (token) に分割するテキスト解析の最初のステップである。トークン化を行う処理をトークナイザー (tokenizer) と呼ぶ。

トークン化の方法は言語や用途によって異なる。例えば英語では単純に空白文字を区切り文字として利用できる一方で、単語の区切りの曖昧な日本語では一般に MeCab, Kuromoji, ChaSen といった形態素解析器や N-gram を利用する。

2.1.1. 形態素解析

形態素解析は辞書を用いて単語の活用形や品詞などからトークンの区切りを推定する。IPAdic は MeCab や Kuromoji などで広く使われている形態素解析に利用可能な辞書であり、他にも Juman, UniDic などの辞書が利用できる。

例えば「東京都知事選挙」を形態素解析すると「東京」「都知事」「選挙」の 3 つのトークンに分割される。形態素解析器は文書の意味を理解するために重要な情報を提供するが、辞書に登録されていない単語や造語に対しては適切な解析ができないという欠点がある。形態素解析を使用する場合、新しい言葉に対応するために継続的な辞書のメンテナンスが必要である。

2.1.2. N-gram

N-gram は文章を $N$ 文字ごとに区切りトークン化する手法である。 $N=1$ の場合を unigram (ユニグラム)、 $N=2$ を bigram (バイグラム)、 $N=3$ を trigram (トライグラム) などと呼ぶ。N-gram は OCR で読み込んだようなノイズの多い文章や、形態素解析器が利用できない未知の言語の文章をトークン化するのに適している。

例えば「東京都知事選挙」を 2-gram でトークン化すると「東京」「京都」「都知」「知事」「事選」「選挙」となる。N-gram を使った全文検索は形態素解析と比べて精度が低い反面、辞書を使用しないため新しい単語や造語、業界特有の言い回しなどにも適応できる利点がある。

2.2. 正規化

トークン化された文字列は活用や表記などの表現上の変化を含んでいるため、それらが検索時に意味的に同じ言葉として正しくヒットするように一貫した形式に変換する必要がある。

ここでは正規化されたトークンのことをターム (term) と呼ぶ。正規化されたタームの集合を bag-of-words (BoW) と呼ぶ。

N-gram によって切り出されたトークンは意味づけされていないためいくつかの正規化手法は難しい。

2.3. ストップワード

一般的でどのような文章にも含まれる助詞や冠詞などのタームは検索時にノイズとして作用することが多く、またインデックスを肥大化する要因にもなる。そのようなタームをインデックスに含めない (検索対象外とする) ために指定するタームの集合をストップワード (stop word) と呼ぶ。例えば「は」「が」「the」「is/are」などのタームはストップワードに含まれることが多い。

ただし、最近の検索エンジンではインデックス時にはストップワードの除外処理を行わず、検索時に選択的にストップワードを除外する使い方が多くなっている [2]。

3. インデックス作成

3.1. 転置インデックス

全文検索の基本的なアルゴリズムは転置インデックス (inverted index) と呼ばれるデータ構造を用いる。このデータ構造は事実上すべての情報検索システムが中核に採用している [1]。転置インデックスは、文書集合に含まれるターム (正規化されたトークン) とその出現位置を記録したデータ構造である。1 つのタームに対する出現位置のリストをポスティングリスト (posting list) と呼ぶ。ポスティングリストの位置情報は昇順にソートされている。

タームに関連づけられた文書ID集合(ポスティングリスト) / posting list — Fig 1. タームに関連付けられたポスティングリスト (出現位置リスト)。

例として 3 つの文書をテキスト解析して作成した転置インデックスを Fig 1 に示す。それぞれの文書はテキスト解析を受けてタームに分割され、それぞれのタームに対して出現位置として文書 ID が関連付けられ転置インデックスに記録されている。

転置インデックスの作成 / inverse index — Fig 2. 3 つの文書をテキスト解析し転置インデックスを作成する過程。

3.2. 語彙目録

転置インデックスに含まれているタームの集合を語彙目録 (lexicon) または辞書 (dictionary) と呼ぶ (形態素解析器が単語の区切りを推定するために使用する IPAdic などの辞書とは異なる)。

語彙目録の役割はクエリーに含まれるタームからそのポスティングリストが保存されている位置を取得することである。したがって、少なくとも高速な完全一致検索が可能であることが要件となるが、現実的な検索システムでは comput* のような前方一致検索や、ある範囲のタームを対象とする範囲検索のように、選択するデータ構造でタームの順序をどう保持するかも焦点となる。

ハッシュテーブル: 完全一致検索を $O(1)$ で行うことができる。ただしタームの順序が失われるため、前方一致検索や範囲スキャンには向いていない。
ソート済み配列と二分探索: 実装が単純で空間効率が良く順序も保たれるが、タームの追加のコストが高い。
トライ (trie): 共通の接頭辞を共有する木構造。前方一致検索に適しており、ダブル配列や LOUDS といった表現を用いることで空間効率を高めることができる。
FST (finite state transducer): 接頭辞に加えて接尾辞も共有する非巡回グラフでトライよりもコンパクトになる。Apache Lucene が語彙目録に採用している。

語彙目録は検索のたびに参照されるためメモリ上に常駐させることが望ましいが、そのサイズは文書集合の増加とともに大きくなる。文書集合に含まれる異なるタームの数 $|V|$ は、その文書集合の総トークン数 $n$ に対して、式 ( $\ref{heaps}$ ) に示す Heaps の法則 (Heaps' law) と呼ばれる経験則に従うことが知られている [1]。 $\begin{equation} |V| = k \, n^{\beta} \label{heaps} \end{equation}$ ここで $k$ と $\beta$ は文書集合の性質によって決まる定数であり、英語の文書集合では $30 \le k \le 100$ 、 $\beta \approx 0.5$ 程度の値を取る。 $\beta \lt 1$ より、タームの増加は文書量の増加よりは緩やかだが、頭打ちになることはなく、語彙目録には空間効率の良いデータ構造が必要となる。

3.3. ポスティングリストの実装

転置インデックスの記憶容量の大部分はポスティングリストが占め、また検索の処理時間もポスティングリストの走査が支配的である。このため、検索システムの性能はどれだけコンパクトかつ高速に走査できるデータ構造を選ぶかが重要になる。

ポスティングリストに含まれる文書 ID は昇順にソートされているため、値そのものではなく直前の値との差分として格納することができる。これをギャップ符号化 (gap encoding) と呼ぶ。例えば文書 ID のリスト [3, 4, 7, 9, 11] は [3, 1, 3, 2, 2] となり、出現頻度の高いタームほど小さい値に偏る。この偏りを利用して、小さい値ほど短いビット列で表現できる整数符号を適用する。

可変長バイト符号 (VByte): 7 ビットずつバイト境界で区切る単純な方式。圧縮率は高くないが復号が速い。
γ 符号 / δ 符号: 値の桁数を単進符号で、値そのものを二進符号で表す。圧縮率は高いがビット単位の処理となるため復号のコストが大きい。
PForDelta, Simple-9/16: 一定個数の値をまとめて固定ビット幅で詰め込み、その幅に収まらない例外だけを別に記録する。ワード単位で処理できるため復号が高速で SIMD 命令とも相性が良い。
Elias-Fano 符号: 単調増加列を情報理論的な下界に近い空間で表現しながら、任意の位置へのランダムアクセスも可能にする簡潔データ構造。

一方で、AND 検索やフレーズ検索ではポスティングリストを先頭から順に読むことよりも「ある文書 ID 以上の要素まで一気に読み飛ばす」操作が支配的となる。このためポスティングリストを一定件数ごとのブロックに区切り、各ブロックの先頭の文書 ID と格納位置をスキップポインタ (skip pointer) として別に保持する実装が用いられる。読み飛ばすべき距離が事前に分からない場合は、探索幅を 1, 2, 4, 8, … と倍々に広げて範囲を絞ってから二分探索に切り替えるギャロッピング探索 (galloping search; 指数探索) が有効である。

なお、タームの出現頻度は Zipf の法則に従い、一般に少数の高頻度タームが全体の大部分を占めている。ポスティングリストの長さもタームによって数件から数千万件まで大きく偏るため、短いリストと長いリストで異なる表現を使い分ける実装も多い。

4. 検索

検索エンジンやデータベースに情報を問い合わせるための入力をクエリー (query) と呼ぶ。全文検索でのクエリーは、ユーザが求めている特定の情報を記述するキーワードやフレーズで構成される。

本セクションではクエリーに一致する文書の集合を求めるマッチングを扱い、一致した文書に順序を与えるランキングについては次セクション以降で説明する。

4.1. AND 検索

AND 検索 (AND search) は複数のキーワードがすべて含まれる文書を検索する手法である。例えばクエリー cats AND dogs と検索すると "cats" と "dogs" の両方が含まれる文書が検索される。

例としてクエリー $x$ AND $y$ AND $z$ に対する検索方法を考える。まず、転置インデックスの中から $x$ , $y$ , $z$ のポスティングリストを取得し、それぞれの先頭にカーソルを置いたところから開始する。

1. もっとも大きい文書 ID はカーソル $c_y$ の指している 3 であるため、それ以外の $c_x$ と $c_z$ のカーソルを 3 以上の文書 ID を検出するまで進める。

2. カーソルを進めたことで、もっとも大きい文書 ID は $c_z$ の指す 4 となった。このため、それ以外の $c_x$ と $c_y$ のカーソルを 4 以上の文書 ID を検出するまで進める。

3. カーソルを進めたことで、もっとも大きい文書 ID は $c_y$ の指す 7 となった。このため、それ以外の $c_x$ と $c_z$ のカーソルを 7 以上の文書 ID を検出するまで進める。

4. カーソルを進めたことで、もっとも大きい文書 ID は $c_x$ の指す 9 となった。このため、それ以外の $c_y$ と $c_z$ のカーソルを 9 以上の文書 ID を検出するまで進める。

5. カーソルを進めたことで、もっとも大きい文書 ID は $c_y$ の指す 11 となった。このため、それ以外の $c_x$ と $c_z$ のカーソルを 11 以上の文書 ID を検出するまで進める。

6. カーソルを進めたことで、すべてのカーソルの文書 ID が 11 となった。したがって文書 ID = 11 の文書をクエリーに一致する文書として取り出す。

このような処理を $x$ , $y$ , $z$ のポスティングリストの末尾まで繰り返すことで、クエリー $x$ AND $y$ AND $z$ に一致する文書 ID の集合を取り出すことができる。

ここでは説明のためにカーソルを一つずつ進めているが、実際の実装で行われているのは「指定した文書 ID 以上の要素までカーソルを進める」操作であり、前述のスキップポインタやギャロッピング探索が用いられる。特に、ごく短いポスティングリストと非常に長いポスティングリストの AND を取る場合、長い方を線形に走査するかどうかで処理時間が大きく変わる。

4.2. OR 検索

OR 検索 (OR search) は複数のキーワードのいずれかが含まれる文書を検索する手法である。例えばクエリー cats OR dogs を用いて検索すると "cats" または "dogs" が含まれる文書を検索する。

クエリー $x$ OR $y$ OR $z$ に一致する文書 ID の集合を取り出すためには、AND 検索と同様に $x$ , $y$ , $z$ のポスティングリストを取得し、それぞれの先頭にカーソルを置いたところから開始する。

1. カーソルの中でもっとも小さい文書 ID の 1 を取得し、 $c_x$ を一つ進める。

2. カーソルの中で最も小さい文書 ID の 2 を取得し、 $c_z$ を一つ進める。

3. カーソルの中で最も小さい文書 ID の 3 を取得し、 $c_x$ と $c_y$ を一つ進める。

4. カーソルの中で最も小さい文書 ID の 3 を取得し、 $c_z$ を一つ進める。

上記の処理を $x$ , $y$ , $z$ のポスティングリストの末尾まで繰り返すことで、クエリー $x$ OR $y$ OR $z$ に一致する文書 ID の集合を取り出すことができる。

4.3. フレーズ検索

フレーズ検索 (phrase search) は複数の単語が特定の順序で連続して現われる文書を検索する手法である。例えばクエリー "information retrieval" と検索すると、ターム information の直後に retrieval が存在する文書だけが検索対象となる。

フレーズ検索では文書 ID に加えてそのタームが文書中のどこに現われたかを示す情報が必要になる。フレーズ検索の転置インデックスのポスティングリストは [文書ID] $\mapsto$ [文書内位置リスト] 形式の位置情報で構成されているものとする。

クエリー " $x$ $y$ $z$ " のフレーズ検索ではまず AND 検索ですべてのタームを含む文書 ID を特定し、その文書内位置リストの先頭にカーソルを設定する。

1. $c_x$ が 1、 $c_y$ が 4 であることから、 $c_x \ge 3$ となる位置まで $c_x$ を移動する。

2. $c_x$ , $c_y$ が 3, 4 を指しているが、 $c_z$ が 7 を指していることから、 $c_x \ge 5$ , $c_y \ge 6$ となる位置までそれぞれを移動する。

3. $c_x$ が 8 に対して $c_y$ が 6、 $c_z$ が 7 を指していることから、 $c_y \ge 9$ , $c_z \ge 10$ となる位置までそれぞれを移動する。

4. $c_x$ が 8 に対して $c_y$ が 9、 $c_z$ が 10 となったことからこの位置に検索対象のフレーズが存在することが分る。

5. クエリと文書の拡張

ここまでに説明した方法は、クエリーと文書に共通のタームが一つも含まれていなければ、両者が同じ内容を指していても照合することができない。この問題を語彙不一致 (vocabulary mismatch) と呼ぶ。例えば「PC」というクエリーで「パソコン」や「コンピュータ」について書かれた文書を見つけることはできない。

語彙不一致に対処するには、クエリーにタームを追加して文書側の表現に近づけるか、逆に文書にタームを追加してクエリー側の表現に近づけるかの二つの方向がある。前者をクエリ拡張 (query expansion)、後者を文書拡張 (document expansion) と呼ぶ [3]。

5.1. クエリ拡張

もっとも単純なクエリ拡張は、シソーラス (同義語辞書) を用いてクエリーのタームを同義語や上位語に展開し、それらの OR 検索として扱う方法である。実装は容易だが辞書の整備コストがかかり、また多義語に対しては無関係な文書を大量に呼び込む原因にもなる。

検索結果そのものを手がかりにする方法もある。適合性フィードバック (relevance feedback) はユーザが検索結果の中から適合する文書を指定し、そこに出現するタームを使ってクエリーを修正する。式 ( $\ref{rocchio}$ ) に示す Rocchio のアルゴリズムはクエリーベクトル $\vector{q}$ を適合文書の集合 $D_r$ の方向へ、非適合文書の集合 $D_{nr}$ から遠ざかる方向へ移動させる。 $\begin{equation} \vector{q}_m = \alpha \, \vector{q} + \frac{\beta}{|D_r|} \sum_{\vector{d} \in D_r} \vector{d} - \frac{\gamma}{|D_{nr}|} \sum_{\vector{d} \in D_{nr}} \vector{d} \label{rocchio} \end{equation}$ ここで $\alpha$ , $\beta$ , $\gamma$ は元のクエリーと各文書集合の寄与を調整する定数である。

ただし実際のユーザが適合判定を入力してくれることは稀である。そこで、最初の検索結果の上位数件を無条件に適合文書とみなして同じ操作を行う疑似適合性フィードバック (PRF; pseudo relevance feedback) が用いられる。上位の検索結果が実際に適合していれば精度が向上する一方、外れていた場合はクエリーが誤った方向に移動して結果が悪化する。この現象をクエリドリフト (query drift) と呼ぶ。

5.2. 文書拡張

文書拡張は、その文書を探し当てるであろうクエリーをあらかじめ生成して文書に付加しておく手法である。doc2query は言語モデルを用いて文書から想定されるクエリーを生成し、それを文書の一部としてインデックスに追加する。また SPLADE のように、言語モデルを用いて文書とクエリーを語彙数次元の疎なベクトルへ展開し、その重みごと転置インデックスに格納する手法もある。

クエリ拡張が検索のたびに追加の計算を必要とするのに対して、文書拡張の計算はインデックス作成時に一度だけ行われ、検索時には通常の転置インデックスの走査のみで完結する。これらは言語モデルの推論という高価な処理を行う事前計算による償却の考えに基づいた手法と言える。

6. ランキング付きの検索

ランキング (ranking) は検索クエリーに一致した文章のうち、よりユーザの関心が高いと考えられる結果を上位に配置するプロセスである。前セクションで説明した転置インデックスを用いてクエリーがどのように文書と一致判定されるかに加えて、このセクションでは検索結果にどのように順位付けするかを説明する。

ランキングは一般的に検索クエリーと文書との類似度を算出し、よりクエリーと関連する文書を上位に表示する。例えば Apache Solr や Elasticsearch ではデフォルトのスコアリングに BM25 を使用して類似度を算出している。さらに、実用的な検索システムでは検索対象の属性情報 (価格や評価数、リリース日など) を用いてスコアを再調整することが一般的である。この属性情報によるスコアリングの調整はブースト (boost) と呼ばれ、類似度との関連をチューニングすることでランキングの精度を向上させる。

6.1. 類似度を使用したランキング

基本的なランキング手法では、文書 $d$ にクエリーに含まれるターム $t$ が出現する頻度であるターム頻度 (term frequency) から類似度を算出して比較する。転置インデックスに基づくランキングでは TF-IDF とコサイン類似度を使用することができる。

6.1.1. TF-IDF

TF (term frequency) ( $\ref{tf}$ ) は特定のターム $t$ が文書 $d$ 内で出現する頻度であり、文書内でのそのタームの重要性を表す。 $\begin{equation} {\rm tf}_{t,d} = \frac{n_{t,d}}{\sum_{\forall i \in d} n_{i,d}} \label{tf} \end{equation}$ ここで $n_{t,d}$ はある文書 $d$ においてターム $t$ が出現する回数、 $\sum_{\forall i \in d} n_{i,d}$ は文書 $d$ に含まれているすべてのタームの出現数の総和である。

IDF (inverse document frequency) ( $\ref{idf}$ ) は特定のタームが全体の文書集合においてどれだけ一般的かを表しており、その単語の希少性を表している。 $\begin{equation} {\rm idf}_t = \log \frac{N}{N_t} \label{idf} \end{equation}$ ここで $N$ は文書の総数、 $N_t \gt 0$ はターム $t$ を含む文書数である。

最終的に ${\rm tf\mbox{-}idf}$ は ${\rm tf}$ と ${\rm idf}$ を乗算することで得られる特徴ベクトルである。 $\begin{equation} {\rm tf\mbox{-}idf}_d = ({\rm tf}_{1,d} \times {\rm idf}_1, \ldots, {\rm tf}_{t,d} \times {\rm idf}_t, \ldots, {\rm tf}_{n,d} \times {\rm idf}_n) \label{tfidf} \end{equation}$

6.1.2. コサイン類似度

コサイン類似度 (cosine similarity) は 2 つのベクトル間の類似度を計る指標である。ベクトルがなす角度が小さいほど 1 に近づき類似度が高いと見なすことができる。ある文書を (TF-IDF のような) 特徴ベクトルで表現した文書ベクトル $\vector{d}$ と、検索クエリーを同様に特徴ベクトルで表現したクエリーベクトル $\vector{q}$ のコサイン類似度は式 ( $\ref{cossim}$ ) のように表される。 $\begin{equation} {\rm sim}(\vector{d},\vector{q}) = \frac{\vector{d} \cdot \vector{q}}{|\vector{d}||\vector{q}|} \label{cossim} \end{equation}$ ただし検索においては過去の研究から「ベクトル長による正規化をしない方が検索精度が上がる」ことが知られている [2] ことから、式 ( $\ref{cossim}$ ) の分子のみをスコアとして考慮する。さらに、クエリーベクトルについては ${\rm tf\mbox{-}idf}$ ではなく「タームが出現するかどうか」を 1 と 0 で表すのみとすると、 $\vector{d}$ との内積演算は「クエリーに含まれているタームの $\vector{d}$ における要素の値を足し合わせる」操作のみでスコアを算出することができる。 $\begin{equation} {\rm score}(\vector{d},\vector{q}) = \vector{d} \cdot \vector{q} = \sum_{\forall t \in q} \left\{ {\rm tf}_{t,d} \times {\rm idf}_t \right\} \label{cossim2} \end{equation}$

6.1.3. BM25

式 ( $\ref{cossim2}$ ) のスコアは ${\rm tf}_{t,d}$ に比例するため、あるタームが 20 回出現する文書は 2 回出現する文書より 10 倍関連性が高いと評価される。しかし実際には、出現回数が 2 回から 4 回に増えることの意味は大きくても、20 回から 40 回に増えることの意味は小さい。また文書が長いほどタームの出現回数は自然に増えるため、長い文書が一方的に有利になる。

式 ( $\ref{bm25}$ ) に示す Okapi BM25 はこの 2 点を補正した確率的なランキング関数であり、Apache Solr や Elasticsearch のデフォルトのスコアリングにも採用されている。 $\begin{equation} {\rm score}(\vector{d},\vector{q}) = \sum_{\forall t \in q} {\rm idf}'_t \cdot \frac{n_{t,d} \, (k_1 + 1)}{n_{t,d} + k_1 \left(1 - b + b \frac{|d|}{\rm avgdl} \right)} \label{bm25} \end{equation}$ ここで $n_{t,d}$ は文書 $d$ におけるターム $t$ の出現回数、 $|d|$ は文書 $d$ のターム数、 ${\rm avgdl}$ は文書集合全体の平均のターム数である。

第 2 項は分母にも $n_{t,d}$ が現われるため、出現回数がいくら増えてもスコアは $k_1 + 1$ が上限となる。この飽和の速さを調整するのがパラメータ $k_1$ であり、一般に $1 \le k_1 \lt 2$ の値が使われる。パラメータ $b$ は文書長による正規化の強さを調整するもので、 $b = 0$ で正規化なし、 $b = 1$ で平均文書長に対する完全な正規化となる。

IDF についても式 ( $\ref{idf}$ ) ではなく、確率的に導出された式 ( $\ref{bm25idf}$ ) が用いられる。 $\begin{equation} {\rm idf}'_t = \log \frac{N - N_t + 0.5}{N_t + 0.5} \label{bm25idf} \end{equation}$ この定義は、半数を超える文書に出現するターム ( $N_t \gt N/2$ ) に対して負の値を取るため、実装によっては全体に 1 を加えるなどの補正が行われる。BM25 の詳細は Okapi BM25 を参照。

6.1.4. ランキング OR 検索

例として TF-IDF を使用したランキング付き OR 検索について説明する。転置インデックスを作成するときに ${\rm tf}_{t,d}$ はポスティングリストの各文書 ID に、 ${\rm idf}_t$ はターム集合の各タームにそれぞれ関連付けて保存されているものとする。

1. カーソルの中で最も小さい文書 ID の 1 を取得して $c_x$ を一つ進める。ここで ${\rm tf\mbox{-}idf}_1 = 1.7672\times 0.0029$ を算出してスコアを得る。

2. カーソルの中で最も小さい文書 ID の 2 を取得して $c_z$ を一つ進める。ここで ${\rm tf\mbox{-}idf}_2 = 1.0613\times 0.0011$ を算出してスコアを得る。

3. カーソルの中で最も小さい文書 ID の 3 を取得して $c_x$ と $c_y$ を一つ進める。ここで ${\rm tf\mbox{-}idf}_3 = 1.7672\times 0.0003+0.5503\times 0.0003$ を算出してスコアを得る。

4. 同様の操作でそれぞれのポスティングリストの末尾まで処理を進める。得られた ${\rm tf\mbox{-}idf}_d$ リストを降順にソートしたものがランキング付きの検索結果となる。

6.2. 上位 $k$ 件の効率的な取得

前述のランキング OR 検索はすべてのポスティングリストを末尾まで走査してから結果を並べ替えている。しかしユーザが実際に目を通すのは上位の数十件であり、最終的な順位に影響しない文書のスコアを計算することは無駄である。文書集合が大規模になるほどこの無駄は無視できなくなる。

このため、走査の途中で上位 $k$ 件に入り得ないと判断できる文書を読み飛ばす動的枝刈り (dynamic pruning) が行われる [1]。現在までに得られた上位 $k$ 件を優先度付きキューで保持しておくと、その $k$ 番目のスコアが「これ以降の文書が検索結果に入るために超えなければならない閾値 $\theta$ 」となる。

WAND (weak AND) はこの閾値を利用する代表的な手法である。インデックス作成時に、各タームについてそのターム単独で与えうるスコアの最大値 ${\rm ub}_t$ (upper bound) を計算して語彙目録に保存しておく。検索時にはカーソルの指す文書 ID の小さい順にタームを並べ、先頭から ${\rm ub}_t$ を累積していって初めて $\theta$ を超えたタームをピボット (pivot) とする。ピボットより手前のカーソルが指す文書は、残りのタームをすべて含んでいたとしてもスコアが $\theta$ に届かないため、スコアを計算することなくピボットの文書 ID までカーソルを進めてよい。

Block-Max WAND (BMW) はこれをさらに細かくしたもので、ポスティングリスト全体ではなくブロックごとにスコアの上限を保持する。ターム単独の上限はごく一部の文書によって決まることが多く、リスト全体の上限は大半のブロックにとって過大な見積もりとなる。ブロック単位の上限を用いることで枝刈りの機会が大幅に増える。

これらの手法は、得られる上位 $k$ 件が枝刈りを行わない場合と完全に一致することを保証しており、この性質を安全 (safe) であるという。閾値 $\theta$ を意図的に高く見積もることで枝刈りをさらに強めることもできるが、その場合は正確な上位 $k$ 件が得られる保証を失う。

動的枝刈りではスコアの計算 (ランキング) の結果によって走査 (マッチング) の範囲が変化することに注意。マッチングとランキングは概念としては分離できるが、転置インデックスに基づく検索の実装においては互いに分離できない。

6.3. 機械学習によるランキング

検索システムでの機械学習は「文書の順序関係」を予測するために利用する。この手法はランキング学習 (learning to rank; LTR) と呼ばれる。TF-IDF や BM25 といった従来の手法は主に単語の頻度などの静的な特徴量に依存している。ランキング学習モデルはユーザのクリックやメタデータ、履歴など、さまざまな特徴量を統合してランク付けを行うことができる。

6.4. 近接度によるランキング

ターム近接度 (term proximity) によるランキングは、複数の検索タームが互いに近くに出現する文書の方がランクが上に評価されるべきであるという考えに基づく。

7. 参考文献

Stefan Buttcher, Charles L. A. Clarke, Gordon V. Cormack. 情報検索 :検索エンジンの実装と評価. 森北出版 (2020)
打田智子, 古澤智裕, 大谷純, 加藤遼, 鈴木翔吾, 河野晋策. 検索システム実務者のための開発改善ガイドブック. ラムダノート (2022)
佐藤竜馬. 検索システム ― なぜ検索システムは欲しい情報を見つけられるのか、あるいはなぜ見つけられないのか ―. 講談社 (2026)