🔍
OR検索のポスティング走査アルゴリズムと実装
扱うデータ構造
以下のようなデータ構造(転置インデックス)を考えます．配列は全てソートされていることを仮定します．
{
"word 1": [0, 1, 3, 4, ...], # 単語とdocument idのリスト
"word 2": [0, 1, 3, 5, ...], # 単語とdocument idのリスト
...
}
転置インデックスとは
転置インデックス（inverted index）とは、検索エンジンで用いられるデータ構造の一つです．特にテキスト検索の効率を高めるために使用されます．以下，詳細です．
-
構造:
- 転置インデックスは、文書内の各単語をキーとし、その単語が出現する文書のリストを値として持つデータ構造です。
- 具体的には、「単語」と「文書ID」のペアを記録します。
-
動作:
- 通常のインデックスが「文書 -> 単語」の対応を持つのに対し，転置インデックスは「単語 -> 文書」の対応を持ちます．
- 例えば，単語Aが文書1と文書3に出現し，単語Bが文書2と文書3に出現する場合，転置インデックスは以下のようになります．
- A: [文書1, 文書3]
- B: [文書2, 文書3]
OR検索のアルゴリズム
word 1, word 2, word 3のいずれかを含んでいるidを取り出すことを考えます．
{
"word 1": [0, 1, 2, 3, 4],
"word 2": [1, 3, 5, 6],
"word 3": [2, 3, 4]
}
期待する結果は，上記の全てのwordの配列に含まれている 0-6 が入った配列です．
{
[0, 1, 2, 3, 4, 5, 6]
}
初期化はAND検索と同様です．比較して，一致しなければ，最小値を戻り値に追加します．ここでは ,
0 を追加しています．そして，最小値をとった配列のカーソルを一つ進めます．
{
"word 1": ["0", 1, 2, 3, 4],
"word 2": ["1", 3, 5, 6],
"word 3": ["2", 3, 4]
}
カーソルを進めたら再び，比較を行います．同様に 1 を追加します．今度は最小値をとった， word 1 , word 2 の二つのカーソルを一つ前に進めます．
{
"word 1": [0, "1", 2, 3, 4],
"word 2": ["1", 3, 5, 6],
"word 3": ["2", 3, 4]
}
カーソルを進めたら再び，比較を行います．同様に 2 を追加します．今度は最小値をとった， word 1 , word 3 の二つのカーソルを一つ前に進めます．
{
"word 1": [0, 1, "2", 3, 4],
"word 2": [1, "3", 5, 6],
"word 3": ["2", 3, 4]
}
同様にして進めます．全てのカーソルが一致している場合は，全てのカーソルを一つ進めます．
{
"word 1": [0, 1, 2, "3", 4],
"word 2": [1, "3", 5, 6],
"word 3": [2, "3", 4]
}
word 1 と word 3 はカーソルが最後に達しました．この二つの語彙はこれ以上走査の必要がないので外します．(実際にはloop次にSkip処理をする)
{
"word 1": [0, 1, 2, 3, "4"],
"word 2": [1, 3, "5", 6],
"word 3": [2, 3, "4"]
}
その後も同様に進めます．
{
"word 2": [1, 3, "5", 6], # 5を戻り値に追加
}
{
"word 2": [1, 3, 5, "6"], # 6を戻り値に追加
}
これで走査は終了です．
OR検索をPHPで実装
実装はPHP 8系を前提にしています．OR検索をPHP Playgroundで試す．
実装全体
OR検索はAND検索に比べると，簡単なアルゴリズムです．
<?php
declare(strict_types=1);
/**
* OR検索を行う関数
*
* @param array<string, int[]> $invertedIndex 転置インデックス
* @param string[] $terms 検索語
* @return int[] 検索結果の配列
*/
function or_search(array $invertedIndex, array $terms): array
{
// 検索語のポスティングリストを取得
$postingLists = get_posting_lists($invertedIndex, $terms);
// 各ポスティングリストのカーソルを初期化
$cursors = array_fill(0, count($postingLists), 0);
// スキャン処理を実行
return scan_posting_lists($postingLists, $cursors);
}
/**
* ポスティングリストのスキャン処理を行う関数
*
* @param int[][] $postingLists ポスティングリストの配列
* @param int[] $cursors 各ポスティングリストのカーソル
* @return int[] スキャン結果の配列
*/
function scan_posting_lists(array $postingLists, array $cursors): array
{
$result = [];
while (true) {
// document idの最小値とそのdocument idを持つ語彙のkeyを見つける
//
// ["word 1": [1, 3, 5, 6], "word 2": [2, 3, 4]]
// word 1 => key = 0, key => index = 1
// 最小のidが1, keys => [0]
// 最小のidが2, keys => [1]
// 最小のidが3, keys => [0, 1]
[$minDocumentId, $minKeys] = find_minimum_document_id($postingLists, $cursors);
// 全てのポインタが配列の範囲外になったら終了
if ($minDocumentId === PHP_INT_MAX) {
break;
}
// 結果に最小値を追加
$result[] = $minDocumentId;
// 最小のdocument idを持つ語彙を指しているカーソルを進める
advance_cursors($cursors, $minKeys);
}
return $result;
}
/**
* 最小値とそのキーを見つける関数
*
* @param int[][] $postingLists ポスティングリストの配列
* @param int[] $cursors 各ポスティングリストのカーソル
* @return array{int, int[]} 最小値とそのキーの配列
*/
function find_minimum_document_id(array $postingLists, array $cursors): array
{
$minValue = PHP_INT_MAX;
$minKeys = [];
foreach ($postingLists as $i => $postingList) {
// 走査が終了したポスティングリストはスキップ
if ($cursors[$i] >= count($postingList)) {
continue;
}
$currentValue = $postingList[$cursors[$i]];
if ($currentValue < $minValue) {
// 最小値を更新した場合はキーを初期化
$minValue = $currentValue;
$minKeys = [$i];
} elseif ($currentValue === $minValue) {
// 最小値と同じ場合はキーを追加
$minKeys[] = $i;
}
}
return [$minValue, $minKeys];
}
/**
* 最小値のポインタを進める関数
*
* @param int[] $cursors 各ポスティングリストのカーソル
* @param int[] $minKeys 最小値を持つキー
* @return void
*/
function advance_cursors(array &$cursors, array $minKeys): void
{
foreach ($minKeys as $key) {
$cursors[$key]++;
}
}
/**
* 検索語のポスティングリストを取得する関数
*
* @param array<string, int[]> $invertedIndex 転置インデックス
* @param string[] $terms 検索語
* @return int[][]
*/
function get_posting_lists(array $invertedIndex, array $terms): array
{
$postingLists = [];
foreach ($terms as $term) {
if (isset($invertedIndex[$term])) {
$postingLists[] = $invertedIndex[$term];
}
}
return $postingLists;
}
// テストデータ
$invertedIndex = [
"word 1" => [0, 1, 2, 3, 4],
"word 2" => [1, 3, 5, 6],
"word 3" => [2, 3, 4]
];
// OR検索を実行
$terms = ["word 1", "word 2", "word 3"];
$result = or_search($invertedIndex, $terms); // [0, 1, 2, 3, 4, 5, 6]
print_r($result); // 結果の表示
or_search関数
特段難しいことはしていないですが，転置インデックスの英名がtransposeではなく，invertedなので注意してください．採取的に検索したい語彙を持つdocumentのidの配列を得ることができます．
/**
* OR検索を行う関数
*
* @param array<string, int[]> $invertedIndex 転置インデックス
* @param string[] $terms 検索語
* @return int[] 検索結果の配列
*/
function or_search(array $invertedIndex, array $terms): array
{
// 検索語のポスティングリストを取得
$postingLists = get_posting_lists($invertedIndex, $terms);
// 各ポスティングリストのカーソルを初期化
$cursors = array_fill(0, count($postingLists), 0);
// スキャン処理を実行
return scan_posting_lists($postingLists, $cursors);
}
scan_posting_lists関数
OR検索の処理本体です．OR検索の場合，全てのポスティングリストの走査が終わるまで処理を終えることができないことに注意してください．
/**
* ポスティングリストのスキャン処理を行う関数
*
* @param int[][] $postingLists ポスティングリストの配列
* @param int[] $cursors 各ポスティングリストのカーソル
* @return int[] スキャン結果の配列
*/
function scan_posting_lists(array $postingLists, array $cursors): array
{
$result = [];
while (true) {
// document idの最小値とそのdocument idを持つ語彙のkeyを見つける
//
// ["word 1": [1, 3, 5, 6], "word 2": [2, 3, 4]]
// word 1 => key = 0, key => index = 1
// 最小のidが1, keys => [0]
// 最小のidが2, keys => [1]
// 最小のidが3, keys => [0, 1]
[$minDocumentId, $minKeys] = find_minimum_document_id($postingLists, $cursors);
// 全てのポインタが配列の範囲外になったら終了
if ($minDocumentId === PHP_INT_MAX) {
break;
}
// 結果に最小値を追加
$result[] = $minDocumentId;
// 最小のdocument idを持つ語彙を指しているカーソルを進める
advance_cursors($cursors, $minKeys);
}
return $result;
}
get_posting_lists関数
検索クエリの語彙に対応するポスティングリストを，転置indexから取得する関数です．
/**
* 検索語のポスティングリストを取得する関数
*
* @param array<string, int[]> $invertedIndex 転置インデックス
* @param string[] $terms 検索語
* @return int[][]
*/
function get_posting_lists(array $invertedIndex, array $terms): array
{
$postingLists = [];
foreach ($terms as $term) {
if (isset($invertedIndex[$term])) {
$postingLists[] = $invertedIndex[$term];
}
}
return $postingLists;
}
find_minimum_document_id関数
ポスティング走査が完了していないポスティングリストに対して以下の処理をする関数です．
- 最小値を更新した場合はキーのリストを作り直す
- 最小値と同じ場合はキーのリストに追加
/**
* 最小値とそのキーを見つける関数
*
* @param int[][] $postingLists ポスティングリストの配列
* @param int[] $cursors 各ポスティングリストのカーソル
* @return array{int, int[]} 最小値とそのキーの配列
*/
function find_minimum_document_id(array $postingLists, array $cursors): array
{
$minValue = PHP_INT_MAX;
$minKeys = [];
foreach ($postingLists as $i => $postingList) {
// 走査が終了したポスティングリストはスキップ
if ($cursors[$i] >= count($postingList)) {
continue;
}
$currentValue = $postingList[$cursors[$i]];
if ($currentValue < $minValue) {
// 最小値を更新した場合はキーを初期化
$minValue = $currentValue;
$minKeys = [$i];
} elseif ($currentValue === $minValue) {
// 最小値と同じ場合はキーを追加
$minKeys[] = $i;
}
}
return [$minValue, $minKeys];
}
advance_cursors関数
参照渡しを使っています．参照渡しについては公式ドキュメントをご覧ください．Advanceという単語は「進める」という意味を持ちます．プログラミング言語のスキャナーを作る時などにも登場することがあるので覚えておいて損はないと思います．
/**
* 最小値のポインタを進める関数
*
* @param int[] $cursors 各ポスティングリストのカーソル
* @param int[] $minKeys 最小値を持つキー
* @return void
*/
function advance_cursors(array &$cursors, array $minKeys): void
{
foreach ($minKeys as $key) {
$cursors[$key]++;
}
}
OR検索とAND検索の速度
AND検索は，ポスティングリストのどれかが終端に達すれば，処理を終了することができます．一方で，OR検索の場合，全てのポスティングリストの終端に達するまで，処理を終了することができません．
また，AND検索は，ポスティングリストがある条件を満たしている場合，カーソルを一気に複数回インクリメントすることができますが．しかし，OR検索は，一つづつしかカーソルを進めることができません．
従って，OR検索はAND検索より基本的に遅いです．
Discussion