20

検索エンジンは逆索引からの結果をどのようにマージしますか?

たとえば、"dog" と "bat" という単語の逆インデックスを検索すると、2 つの単語のうちの 1 つを含むすべてのドキュメントの 2 つの巨大なリストが作成されます。

検索エンジンがこれらのリストを一度に 1 文書ずつ調べて、リストの結果と一致するものを見つけようとしているとは思えません。このマージ プロセスを高速化するために、アルゴリズム的に何が行われますか?

4

2 に答える 2

10

実際、検索エンジンはこれらのドキュメント リストをマージします。それらは他のテクニックを使用することで良好なパフォーマンスを得ることができますが、その中で最も重要なのはプルーニングです: たとえば、すべての単語について、ページランクの降順でドキュメントが保存され、最初の 10 に入る可能性がある結果が得られます (これにより、ユーザーに表示される) 犬とコウモリのリストのごく一部、たとえば最初の 1000 個をトラバースすることができます。(そしてもちろん、キャッシュがありますが、それはクエリ実行アルゴリズムとは関係ありません)

その上、結局のところ、犬やコウモリに関するドキュメントはそれほど多くありません。たとえ数百万であっても、適切な実装で一瞬に変わります。

PS 私はわが国の主要な検索エンジンで働いていましたが、私たちの主力の検索製品のエンジンそのものではありませんでしたが、その開発者と話をしたところ、クエリ実行アルゴリズムが実際にはかなり馬鹿げていることを知って驚きました。許容可能な時間範囲への膨大な量の計算。もちろん、それはすべて非常に最適化されていますが、魔法も奇跡もありません。

于 2010-03-06T22:11:27.357 に答える
7

逆索引は docId によって順序付けられるため、非常に高速にマージできます。[単語の 1 つが docId 23 で始まり、2 番目が docId 100001 で始まる場合、最初のリストでも docId 100001 以上にすぐに早送りできます。]

典型的なドキュメントの交差はせいぜい数百万であるため、非常に高速にランク付けすることができます。私は 'dog cat' [非常に一般的な 2 語] を検索しましたが、5,400 万件しかヒットしませんでした。

1000 万のランダムな整数の並べ替えは、シングル スレッド コードを使用した私の Mac では 2.3 秒しかかかりませんでした [100 万で 206 ミリ秒かかりました!]。

コードを書くのが面倒で、並べ替えの速度を試したい場合は、次のコードを使用してください。

import java.lang.*;
import java.math.*;
import java.util.*;

public class SortTest {
   public static void main(String[] args) {
   int count = Integer.parseInt(args[0]);

Random random = new Random();
int[] values = new int[count];
int[] bogusValues = new int[100000]; //screw cache
    for(int i = 0; i < values.length;++i) {
    values[i] = random.nextInt(count);
}
for(int i = 0; i < bogusValues.length;++i) {
    bogusValues[i] = random.nextInt(count);
}
long start = System.currentTimeMillis();
System.out.println(start);
        Arrays.sort(values);
System.out.println(System.currentTimeMillis());
System.out.println(System.currentTimeMillis()-start);
    Arrays.sort(bogusValues);
 }

}

于 2010-03-06T22:24:17.127 に答える