27

全文検索の基本的な側面が逆索引の使用であることを理解しています。そのため、転置インデックスを使用すると、1 語のクエリに答えるのが簡単になります。インデックスが次のように構成されていると仮定します。

some-word -> [doc385, doc211, doc39977, ...] (ランク順、降順)

その単語のクエリに答えるには、インデックスで正しいエントリを見つけ (O(log n) 時間かかります)、インデックスで指定されたリストから特定の数のドキュメント (たとえば、最初の 10) を提示するだけです。

しかし、たとえば 2 つの単語に一致するドキュメントを返すクエリについてはどうでしょうか。最も簡単な実装は次のとおりです。

  1. A を単語 1 を持つドキュメントのセットに設定します (インデックスを検索することにより)。
  2. B を単語 2 (同上) を持つドキュメントのセットに設定します。
  3. A と B の交点を計算します。

さて、ステップ 3 の実行にはおそらく O(n log n) の時間がかかります。非常に大きな A と B の場合、クエリの応答が遅くなる可能性があります。しかし、Google のような検索エンジンは、常に数ミリ秒で回答を返します。したがって、それは完全な答えではありません。

明らかな最適化の 1 つは、Google のような検索エンジンは一致するすべてのドキュメントを返すわけではないため、交差全体を計算する必要がないことです。最小のセット (例: B) から始めて、他のセット (例: A) にも属する十分なエントリを見つけることができます。

しかし、次の最悪のケースはまだあり得ませんか? A を一般的な単語に一致するドキュメントのセットに設定し、B を別の一般的な単語に一致するドキュメントのセットに設定した場合でも、A ∩ B が非常に小さい (つまり、組み合わせがまれである) 場合があります。つまり、検索エンジンは B のすべての要素 x メンバーを直線的に調べ、それらが A の要素でもあるかどうかをチェックして、両方の条件に一致する少数を見つける必要があります。

線形は速くありません。また、検索する単語が 3 つ以上ある場合もあるため、並列処理を採用するだけでは完全な解決策にはなりません。では、これらのケースはどのように最適化されるのでしょうか? 大規模な全文検索エンジンはある種の複合インデックスを使用しますか? ブルームフィルター？何か案は？

4

4 に答える 4

7

あなたが言ったように-単語->[doc385、doc211、doc39977、...]（ランク順、降順）、検索エンジンはこれを行わないかもしれないと思います、ドキュメントリストはドキュメントIDでソートする必要があります、各ドキュメントは言葉によるランク。
クエリが来ると、いくつかのキーワードが含まれます。単語ごとに、ドキュメントリストを見つけることができます。すべてのキーワードについて、マージ操作を実行し、クエリに対するドキュメントの関連性を計算できます。最後に、上位にランク付けされた関連性ドキュメントをユーザーに返します。
また、クエリプロセスを分散して、パフォーマンスを向上させることができます。

于 2011-05-17T15:44:16.067 に答える
5

ランキングがなくても、どうやって 2 つの集合の交点を google がこれほど速く計算できるのだろうか。

明らかに、いくつかの単語 A、B、C の交差を計算するための最悪のシナリオは、それらのインデックスが非常に大きく、交差が非常に小さい場合です。典型的なケースは、さまざまな言語で非常に一般的な (DB 用語で「人気のある」) 単語を検索することです。

中国語では「具体的」と「場所」、日本語では「巨大な」を試してみましょう。

Google で位置を検索すると、 「約1,500,000,000件の結果 (0.28 秒)」 が返されます。

3 つの用語すべてが同じ文書に現れる可能性は非常に低いですが、それらをググってみましょう: 「具体的な位置 ゲイナ」を Google 検索すると、「約 174,000 件の結果 (0.13 秒)」が返されます。

ロシア語の単語「игра」を追加 (ゲーム) игра を検索: 約 212,000,000 件の結果 (0.37 秒)

それらすべてを検索します: " игра 具体的な位置 ＧＡな " が返されます約 12,600 件の結果 (0.33 秒)

もちろん、返される検索結果はナンセンスであり、すべての検索語が含まれているわけではありません。

しかし、構成されたもののクエリ時間を見ると、単語インデックスで計算された交差があるのではないかと思います。すべてが RAM にあり、非常にシャーディングされている場合でも、1,500,000,000 および 2,020,000,000 エントリを持つ 2 つのセットの交差を計算するのは O(n) であり、データが異なるマシンにあり、通信する必要があるため、0.5 秒未満で実行することはほとんどできません。

いくつかの結合計算が必要ですが、少なくとも一般的な単語の場合、これは単語インデックス全体に対して行われるわけではありません。結果が曖昧であるという事実を追加すると、Google が「上位の結果を返し、0.5 秒後に停止する」ような最適化を使用していることは明らかです。

これがどのように実装されているかはわかりません。何か案は？

于 2013-10-28T12:12:12.440 に答える
4

ほとんどのシステムは、何らかの方法でTF-IDFを実装しています。TF-IDFは、関数の項頻度と逆ドキュメント頻度の積です。

IDF関数は、ドキュメントの頻度をコレクション内のドキュメントの総数に関連付けます。この関数の一般的な直感では、少数のドキュメントに表示される用語には高い値を、すべてのドキュメントに表示される用語には低い値を与えて、それらを無関係にする必要があると言われています。

あなたはグーグルについて言及しますが、グーグルはPageRank（リンクイン/アウト）と用語の頻度と近接性で検索を最適化します。Googleはデータを配布し、Map/Reduceを使用して操作を並列化します-PageRank+TF-IDFを計算します。

この背後にある理論の優れた説明は、情報検索：検索エンジンの実装の第2章にあります。さらに調査するもう1つのアイデアは、 Solrがこれをどのように実装するかを調べることです。

于 2011-05-17T15:00:51.780 に答える