Zenn
🔎

AND検索のポスティング走査アルゴリズムと実装

2024/06/16に公開
PHP
PHP 8
アルゴリズム
全文検索
search
tech

扱うデータ構造

以下のようなデータ構造(転置インデックス)を考えます．配列は全てソートされていることを仮定します．

{
	"word 1": [0, 1, 3, 4, ...], # 単語とdocument idのリスト
	"word 2": [0, 1, 3, 5, ...], # 単語とdocument idのリスト
	...
}

転置インデックスとは

転置インデックス（inverted index）とは、検索エンジンで用いられるデータ構造の一つです．特にテキスト検索の効率を高めるために使用されます．以下，詳細です．

  1. 構造:
    • 転置インデックスは、文書内の各単語をキーとし、その単語が出現する文書のリストを値として持つデータ構造です。
    • 具体的には、「単語」と「文書ID」のペアを記録します。
  2. 動作:
    • 通常のインデックスが「文書 -> 単語」の対応を持つのに対し，転置インデックスは「単語 -> 文書」の対応を持ちます．
    • 例えば，単語Aが文書1と文書3に出現し，単語Bが文書2と文書3に出現する場合，転置インデックスは以下のようになります．
      • A: [文書1, 文書3]
      • B: [文書2, 文書3]

AND検索

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の配列に含まれている 3 が入った配列です．

{
	[3]
}

本来cursorという配列のindexを持つ配列を持っておくのですが，ここでは簡便のため，カーソルを ”” で表現します．まず，最初に以下のようにカーソルが当たっています．

{
	"word 1": ["0", 1, 2, 3, 4],
	"word 2": ["1", 3, 5, 6],
	"word 3": ["2", 3, 4]
}

AND検索の場合，まず，カーソルが当たっているindexの値を比べます．ここでは， ”0", "1", "2”, を比べます．比較して，一致しなかった場合は，カーソルが当たっているindexの値のうち最大値をとっているindex以外を，その最大値以上の値を取るようにカーソルを進めます．

{
	"word 1": [0, 1, "2", 3, 4], # 値が3より以上になるようにカーソルを動かす
	"word 2": [1, "3", 5, 6], # 最大値なのでカーソルを動かさない
	"word 3": ["2", 3, 4] # 値が3より以上になるようにカーソルを動かす
}

再び，カーソルが当たっているindexの値を比べます．今度は一致しているので，戻り値に 3 を追加します．

{
	"word 1": [0, 1, 2, "3", 4],
	"word 2": [1, "3", 5, 6],
	"word 3": [2, "3", 4]
}
# カーソルの指すindexの値が全て一致しているので，戻り値に追加

一致していた場合は，全てのカーソルを一つ前に進めます．

{
	"word 1": [0, 1, 2, 3, "4"],
	"word 2": [1, 3, "5", 6],
	"word 3": [2, 3, "4"]
}

以上の処理を繰り返し，いずれかの配列の最終要素にカーソルが到達したら処理を終了します．

AND検索をPHPで実装する

実装全体，PHP 8系を前提にしています．

PHP Playgroundで試す

<?php

declare(strict_types=1);

/**
 * AND検索を行う関数
 *
 * @param array<string, int[]> $inverted_index
 * @param string[] $terms
 * @return int[]
 */
function and_search(
    array $inverted_index,
    array $terms
): array
{
    // 検索語のポスティングリストを取得
    $posting_lists = get_posting_lists(
        inverted_index: $inverted_index,
        terms: $terms
    );

    // ポスティングリストが空の場合、空のリストを返す
    if (empty($posting_lists)) return [];

    // 各ポスティングリストのカーソルを初期化
    $cursors = array_fill(0, count($posting_lists), 0);

    // AND検索処理
    return scanning_posting_list($posting_lists, $cursors);
}

/**
 * 検索語のポスティングリストを取得する関数
 *
 * @param array<string, int[]> $inverted_index
 * @param string[] $terms
 * @return array<int[]>
 */
function get_posting_lists(
    array $inverted_index,
    array $terms
): array
{
    $posting_lists = [];

    foreach ($terms as $term) {
        if (isset($inverted_index[$term])) {
            $posting_lists[] = $inverted_index[$term];
        } else {
            // 検索語がインデックスにない場合、空のリストを返す
            return [];
        }
    }

    return $posting_lists;
}

/**
 * AND検索処理を行う関数
 *
 * @param array<int[]> $posting_lists
 * @param int[] $cursors
 * @return int[]
 */
function scanning_posting_list(array $posting_lists, array $cursors): array {
    $result = [];
    while (true) {
        // ポスティングリストの数を取得
        $num_lists = count($posting_lists);

        // 各ポスティングリストの現在のドキュメントIDを取得
        $current_docs = [];
        for ($i = 0; $i < $num_lists; $i++) {
            if ($cursors[$i] < count($posting_lists[$i])) {
                $current_docs[$i] = $posting_lists[$i][$cursors[$i]];
            } else {
                // いずれかのポスティングリストが終わったら終了
                return $result;
            }
        }

        // ドキュメントIDの最大値を取得
        $max_doc_id = max($current_docs);

        // 全てのポスティングリストが同じドキュメントIDを指しているかチェック
        if (count(array_unique($current_docs)) === 1) {
            // 全てのポスティングリストが同じドキュメントIDを指している場合、結果に追加
            $result[] = $max_doc_id;
            // 全てのカーソルを進める
            advance_all_cursors($cursors, $num_lists);
        } else {
            // 最大ドキュメントIDに一致しないポスティングリストのカーソルだけを進める
            advance_cursors_to_max_doc($posting_lists, $cursors, $max_doc_id);
        }
    }
}

/**
 * 全てのカーソルを進める関数
 *
 * @param int[] $cursors
 * @param int $num_lists
 * @return void
 */
function advance_all_cursors(
    array &$cursors,
    int $num_lists
): void
{
    for ($i = 0; $i < $num_lists; $i++) {
        $cursors[$i]++;
    }
}

/**
 * 最大ドキュメントIDに一致しないポスティングリストのカーソルだけを進める関数
 *
 * @param array<int[]> $posting_lists
 * @param int[] $cursors
 * @param int $max_doc_id
 * @return void
 */
function advance_cursors_to_max_doc(
    array $posting_lists,
    array &$cursors,
    int $max_doc_id
): void
{
    $num_lists = count($posting_lists);
    for ($i = 0; $i < $num_lists; $i++) {
        // $cursors[$i] < count($posting_lists[$i]);
        // カーソルがポスティングリストの範囲内にあるかをチェック
        // 例: $cursors[$i] = 2, count($posting_lists[$i]) = 5 の場合、2 < 5 は true
        // count($posting_lists[$i]): i番目のポスティングリストの要素数
        // $cursor[$i]: i番目のポスティングリストのカーソル (0, 1, 2, ... count($posting_lists[$i]) - 1)

        // $posting_lists[$i][$cursors[$i]] < $max_doc_id;
        // 現在のドキュメントIDが最大ドキュメントIDより小さいかをチェック
        // 例: $posting_lists[$i][$cursors[$i]] = 4, $max_doc_id = 3 の場合、4 < 3 は false
        // $posting_lists[$i][$cursors[$i]]: i番目のポスティングリストのカーソルが指すドキュメントID
        // $max_doc_id: 最大ドキュメントID

        while ($cursors[$i] < count($posting_lists[$i]) && $posting_lists[$i][$cursors[$i]] < $max_doc_id) {
            $cursors[$i]++;
        }
    }

    }
}

// テストデータ
$inverted_index = [
    "word 1" => [0, 1, 2, 3, 4],
    "word 2" => [1, 3, 5, 6],
    "word 3" => [2, 3, 4]
];

// AND検索を実行
$terms = ["word 1", "word 2", "word 3"];
$result = and_search($inverted_index, $terms);

print_r($result); // 結果: [3]

and_search関数

ポスティングリストの走査を動かすための変数の初期化を行なっています．ちなみに転置インデックスはBag of Wordsという文書集合の行列を転置(transpose)させたものですが，英語ではinverted indexです．

/**
 * AND検索を行う関数
 *
 * @param array<string, int[]> $inverted_index
 * @param string[] $terms
 * @return int[]
 */
function and_search(
    array $inverted_index,
    array $terms
): array
{
    // 検索語のポスティングリストを取得
    $posting_lists = get_posting_lists(
        inverted_index: $inverted_index,
        terms: $terms
    );

    // ポスティングリストが空の場合、空のリストを返す
    if (empty($posting_lists)) return [];

    // 各ポスティングリストのカーソルを初期化
    $cursors = array_fill(0, count($posting_lists), 0);

    // AND検索処理
    return scanning_posting_list($posting_lists, $cursors);
}

get_posting_lists関数

and_search関数に入力された単語のポスティングリストを追加していきます．

/**
 * 検索語のポスティングリストを取得する関数
 *
 * @param array<string, int[]> $inverted_index
 * @param string[] $terms
 * @return array<int[]>
 */
function get_posting_lists(
    array $inverted_index,
    array $terms
): array
{
    $posting_lists = [];

    foreach ($terms as $term) {
        if (isset($inverted_index[$term])) {
            $posting_lists[] = $inverted_index[$term];
        } else {
            // 検索語がインデックスにない場合、空のリストを返す
            return [];
        }
    }

    return $posting_lists;
}

検索語がない場合は，空のリストを追加して，この後に呼び出されるif文でearly returnをします．

// ポスティングリストが空の場合、空のリストを返す
if (empty($posting_lists)) return [];

scanning_posting_list関数

ポスティングリストの走査をする本体の関数です．

/**
 * AND検索処理を行う関数
 *
 * @param array<int[]> $posting_lists
 * @param int[] $cursors
 * @return int[]
 */
function scanning_posting_list(array $posting_lists, array $cursors): array {
    $result = [];
    while (true) {
        // ポスティングリストの数を取得
        $num_lists = count($posting_lists);

        // 各ポスティングリストの現在のドキュメントIDを取得
        $current_docs = [];
        for ($i = 0; $i < $num_lists; $i++) {
            if ($cursors[$i] < count($posting_lists[$i])) {
                $current_docs[$i] = $posting_lists[$i][$cursors[$i]];
            } else {
                // いずれかのポスティングリストが終わったら終了
                return $result;
            }
        }

        // ドキュメントIDの最大値を取得
        $max_doc_id = max($current_docs);

        // 全てのポスティングリストが同じドキュメントIDを指しているかチェック
        if (count(array_unique($current_docs)) === 1) {
            // 全てのポスティングリストが同じドキュメントIDを指している場合、結果に追加
            $result[] = $max_doc_id;
            // 全てのカーソルを進める
            advance_all_cursors($cursors, $num_lists);
        } else {
            // 最大ドキュメントIDに一致しないポスティングリストのカーソルだけを進める
            advance_cursors_to_max_doc($posting_lists, $cursors, $max_doc_id);
        }
    }
}

以下の処理が，

// 全てのポスティングリストが同じドキュメントIDを指しているかチェック
if (count(array_unique($current_docs)) === 1) {
    // 全てのポスティングリストが同じドキュメントIDを指している場合、結果に追加
    $result[] = $max_doc_id;
    // 全てのカーソルを進める
    advance_all_cursors($cursors, $num_lists);
}

前半の解説部分の以下に該当します．

再び，カーソルが当たっているindexの値を比べます．今度は一致しているので，戻り値に `3`  を追加します．

{
	"word 1": [0, 1, 2, "3", 4],
	"word 2": [1, "3", 5, 6],
	"word 3": [2, "3", 4]
}
# カーソルの指すindexの値が全て一致しているので，戻り値に追加

一致していた場合は，全てのカーソルを一つ前に進めます．

{
	"word 1": [0, 1, 2, 3, "4"],
	"word 2": [1, 3, "5", 6],
	"word 3": [2, 3, "4"]
}

また，以下の処理が，

else {
    // 最大ドキュメントIDに一致しないポスティングリストのカーソルだけを進める
    advance_cursors_to_max_doc($posting_lists, $cursors, $max_doc_id);
}

前半部分の以下の部分に対応しています．

本来cursorという配列のindexを持つ配列を持っておくのですが，ここでは簡便のため，カーソルを `””` で表現します．まず，最初に以下のようにカーソルが当たっています．

{
	"word 1": ["0", 1, 2, 3, 4],
	"word 2": ["1", 3, 5, 6],
	"word 3": ["2", 3, 4]
}

AND検索の場合，まず，カーソルが当たっているindexの値を比べます．ここでは， `”0", "1", "2”`,  を比べます．比較して，一致しなかった場合は，カーソルが当たっているindexの値のうち最大値をとっているindex以外を，その最大値以上の値を取るようにカーソルを進めます．

{
	"word 1": [0, 1, 2, "3", 4], # 値が3より以上になるようにカーソルを動かす
	"word 2": [1, "3", 5, 6], # 最大値なのでカーソルを動かさない
	"word 3": [2, "3", 4] # 値が3より以上になるようにカーソルを動かす
}

advance_all_cursor

配列を直接操作するために参照を渡しています．中身は全ての要素をインクリメントするだけです．

https://www.php.net/manual/ja/language.references.pass.php

/**
 * 全てのカーソルを進める関数
 *
 * @param int[] $cursors
 * @param int $num_lists
 * @return void
 */
function advance_all_cursors(
    array &$cursors,
    int $num_lists
): void
{
    for ($i = 0; $i < $num_lists; $i++) {
        $cursors[$i]++;
    }
}

advance_cursors_to_max_doc

恐らくこの関数が鬼門だと思われます．ここでも参照を渡しています．

https://www.php.net/manual/ja/language.references.pass.php

/**
 * 最大ドキュメントIDに一致しないポスティングリストのカーソルだけを進める関数
 *
 * @param array<int[]> $posting_lists
 * @param int[] $cursors
 * @param int $max_doc_id
 * @return void
 */
function advance_cursors_to_max_doc(
    array $posting_lists,
    array &$cursors,
    int $max_doc_id
): void
{
    $num_lists = count($posting_lists);
    for ($i = 0; $i < $num_lists; $i++) {
        // $cursors[$i] < count($posting_lists[$i]);
        // カーソルがポスティングリストの範囲内にあるかをチェック
        // 例: $cursors[$i] = 2, count($posting_lists[$i]) = 5 の場合、2 < 5 は true
        // count($posting_lists[$i]): i番目のポスティングリストの要素数
        // $cursor[$i]: i番目のポスティングリストのカーソル (0, 1, 2, ... count($posting_lists[$i]) - 1)

        // $posting_lists[$i][$cursors[$i]] < $max_doc_id;
        // 現在のドキュメントIDが最大ドキュメントIDより小さいかをチェック
        // 例: $posting_lists[$i][$cursors[$i]] = 4, $max_doc_id = 3 の場合、4 < 3 は false
        // $posting_lists[$i][$cursors[$i]]: i番目のポスティングリストのカーソルが指すドキュメントID
        // $max_doc_id: 最大ドキュメントID

        while ($cursors[$i] < count($posting_lists[$i]) && $posting_lists[$i][$cursors[$i]] < $max_doc_id) {
            $cursors[$i]++;
        }
    }

}

$num_lists = count($posting_lists);
for ($i = 0; $i < $num_lists; $i++) {
	// 各ポスティングリストに対して処理を実行
}

各カーソルの値は対応するポスティングリストの要素数未満である必要があります．

$cursors[$i] < count($posting_lists[$i]);

各ポスティングリストの要素うち，最大のdocument idより小さいidである要素をスキップするための変数です．

$posting_lists[$i][$cursors[$i]] < $max_doc_id;

OR検索とAND検索の速度

AND検索は，ポスティングリストのどれかが終端に達すれば，処理を終了することができます．一方で，OR検索の場合，全てのポスティングリストの終端に達するまで，処理を終了することができません．

また，AND検索は，ポスティングリストがある条件を満たしている場合，カーソルを一気に複数回インクリメントすることができますが．しかし，OR検索は，一つづつしかカーソルを進めることができません．

従って，AND検索はOR検索より基本的に速いです．

Discussion