大きなテキスト ドキュメントがあり、検索クエリがあります (例: ロック クライミング)。テキストから最も関連性の高い 5 つの文を返したいと考えています。従うことができるアプローチは何ですか？私はこのテキスト検索ドメインの初心者なので、助けていただければ幸いです。
私が考えることができる1つのアプローチは、ファイルを文ごとにスキャンし、文内の検索クエリ全体を探し、一致する場合は文を返すことです。
上記のアプローチは、一部の文に検索クエリ全体が含まれている場合にのみ機能します。クエリ全体を含む文がなく、一部の文に単語の 1 つだけが含まれている場合はどうすればよいですか? または、単語がまったく含まれていない場合はどうなりますか? 助けはありますか？
もう 1 つの質問は、インデックスの作成を容易にするためにテキスト ドキュメントを前処理できないかということです。trie は前処理に適したデータ構造ですか?
一般に、関連性は、何らかのスコアリング関数を使用して定義するものです。単純なスコアリング アルゴリズムの例と、一般的な検索エンジンのランキング アルゴリズムの 1 つ (ドキュメントに使用されますが、教育目的で文章に変更しました) を示します。
単純なランキング アルゴリズムの例を次に示します。ランキングは次のように単純になります。
BM25 は、クエリに関連してドキュメントをスコアリングするための優れた堅牢なアルゴリズムです。参考までに、 BM25 ランキング アルゴリズムに関するウィキペディアの記事を次に示します。文を扱っているので少し修正したくなるでしょうが、各文を「ドキュメント」として扱うことで同様のアプローチを取ることができます。
ここに行きます。クエリがキーワード q 1、q 2、...、q mで構成されていると仮定すると、クエリQに対する文Sのスコアは次のように計算されます。
SCORE(S, Q) = SUM(i=1..m) (IDF(q i * f(q i , S) * (k 1 + 1) / (f(q i , S) + k 1 * ( 1 - b + b * |S| / AVG_SENT_LENGTH))
k 1と b は自由パラメータです ([1.2, 2.0] の k と b = 0.75 として選択できます -- 経験的にいくつかの適切な値を見つけることができます) f(q i , S) は文中の q iの用語頻度ですS (用語が出現する回数として扱うことができます)、|S| は文の長さ (単語)、AVG_SENT_LENGTH はドキュメント内の文の平均文長です。最後に、IDF(q i ) は q iの逆ドキュメント頻度 (または、この場合は逆文頻度) であり、通常は次のように計算されます。
IDF(q i ) = log ((N - n(q i ) + 0.5) / (n(q i ) + 0.5))
ここで、 Nは文の総数、n(q i ) は q iを含む文の数です。
高速アクセスのために逆インデックスや追加のデータ構造を保存しないと仮定します。これらは、事前に計算できる用語です: N , *AVG_SENT_LENGTH*.
最初に、一致する用語が多いほど、この文のスコアが高くなることに注意してください (合計用語のため)。したがって、クエリから上位k語を取得する場合は、f(q i , S)、|S|、および n(q i )の値を計算する必要がありますO(AVG_SENT_LENGTH * m * k)。最悪の場合、O(DOC_LENGTH * m)kは最も多くの用語が一致したドキュメントの数、mはクエリ用語の数です。各センテンスが約 AVG_SENT_LENGTH であると仮定すると、 kセンテンスごとにm回実行する必要があります。
次に、高速なテキスト検索を可能にする転置インデックスを見てみましょう。私たちはあなたの文を教育目的の文書として扱います。アイデアは、BM25 計算用のデータ構造を構築することです。逆リストを使用して単語の頻度を保存する必要があります。
単語i : (sent_id 1 , tf 1 ), (sent_id 2 , tf 2 ), ... ,(sent_id k , tf k )
基本的に、キーがwordあり、値が(sent_id<sub>j</sub>, tf<sub>k</sub>)文のIDと単語の頻度に対応するペアのリストであるハッシュマップがあります。たとえば、次のようになります。
岩: (1, 1), (5, 2)
これは、単語 rock が最初の文に 1 回、5 番目の文に 2 回出現することを示しています。
この前処理ステップによりO(1)、特定の単語の用語頻度にアクセスできるようになるため、必要に応じて高速になります。
また、文の長さを格納する別のハッシュマップが必要になることもありますが、これはかなり簡単な作業です。
逆索引を作成するには? あなたの場合、ステミングとレンマタイゼーションをスキップしていますが、それについてもっと読んでいただければ幸いです。つまり、ドキュメントをトラバースし、単語を含むハッシュマップのペアを継続的に作成/頻度を増やします。インデックスの作成に関するスライドをいくつか示します。