1

関連するコンテンツを検索したい大量のドキュメント、テキスト ファイルがあります。以下の要件で説明するように、優れたメソッドを実装した検索ツールを見たことがありますが、どこにあるか思い出せません。

私の要件は次のとおりです。

  • 最適化された検索機能が必要です: この検索機能に、スペースで区切られた部分的に完全な (または完全な) 単語のリスト (1 つ以上) を提供します。
  • この関数は、最初の単語で始まる単語またはそれに等しい単語を含むすべてのドキュメントを検索し、2 番目の単語を使用してこれらの検索されたドキュメントを検索し、最後にリンクされている実際の単語を含むリストを返します。それらを含むドキュメント (名前と場所) とともに、単語の完全なリストを取得します。
  • ドキュメントには、リスト内のすべての単語が含まれている必要があります。
  • この関数を使用して、入力時に検索を実行し、結果をツリーのような構造でリアルタイムに表示および更新できるようにしたいと考えています。

私が思いついたソリューションへの可能なアプローチは次のとおりです。「Documents」、「Words」、および「Word_Docs」という 3 つのテーブルを持つデータベースを作成します (ほとんどの場合、mysql を使用します)。

  • 「ドキュメント」には、すべてのドキュメントの (idDoc、名前、場所) があります。
  • 'Words' は (idWord, Word) を持ち、すべてのドキュメントからの一意の単語のリストになります (特定の単語は 1 回だけ表示されます)。
  • 'Word_Docs' は (idWord, idDoc) を持ち、それが出現する各単語とドキュメントの一意の ID の組み合わせのリストになります。

この関数は、各キーストローク (スペースを除く) の編集ボックスの内容で呼び出されます。

  • 文字列はトークン化されています
  • (ここで私の車輪は少し回転します): 単一の SQL ステートメントを作成して、必要なデータセットを返すことができると確信しています: (actual_words, doc_name, doc_location); (私は SQL のホット ナンバーではありません)、代わりに、各トークンの一連の呼び出しと、繰り返されない idDocs の解析ですか?
  • このデータセット (/list/array) が返されます

返されたリスト コンテンツが表示されます。

例: 「seq sta cod」で呼び出すと、次のように表示されます。

sequence - start - code - Counting Sequences [file://docs/sample/con_seq.txt]
         - stop - code - Counting Sequences [file://docs/sample/con_seq.txt]
sequential - statement - code - SQL intro [file://somewhere/sql_intro.doc]

（等々）

これは最適な方法ですか？関数は高速である必要がありますか、それともスペースがヒットした場合にのみ呼び出す必要がありますか? 単語補完を提供する必要がありますか? （データベース内の単語を取得しました）少なくとも、これにより、存在しない単語に対する関数の無駄な呼び出しが防止されます。単語補完の場合: どのように実装されますか?

(たぶん、SO はタグをブラウジングするためにこのタイプの検索ソリューションを使用することもできますか? (メインページの右上にあります))

4

4 に答える 4

2

あなたが話していることは、転置インデックスまたは投稿リストとして知られており、あなたが提案するものと Mecki が提案するものと同様に機能します。転置インデックスに関する文献はたくさんあります。ウィキペディアの記事は、開始するのに適した場所です。

自分で構築しようとするよりも、既存の逆インデックスの実装を使用することをお勧めします。MySQL と最近のバージョンの PostgreSQL の両方に、デフォルトで全文索引が含まれています。また、独立したソリューションとしてLuceneを確認することもできます。適切な転置インデックスを作成するには、トークン化、ステミング、複数単語クエリなど、考慮すべきことがたくさんあります。事前に作成されたソリューションがこれらすべてを行います。

于 2008-09-29T10:11:22.917 に答える
2

最適化されたデータを使用して手動で検索を行うと、選択した検索のパフォーマンスを簡単に上回ることができるため、データベースをまったく使用しないことが最も速い方法です。ドキュメントがあまり頻繁に変更されないと仮定すると、最も速い方法は、インデックス ファイルを作成し、これらを使用してキーワードを検索することです。インデックス ファイルは次のように作成されます。

  1. テキスト ファイル内の一意の単語をすべて検索します。つまり、テキスト ファイルをスペースで単語に分割し、そのリストにまだ見つからない限り、すべての単語をリストに追加します。

  2. 見つけたすべての単語をアルファベット順に並べ替えます。これを行う最も速い方法は、Three Way Radix QuickSortを使用することです。このアルゴリズムは、文字列をソートする際のパフォーマンスに勝るものはありません。

  3. ソートされたリストを 1 行に 1 語ずつディスクに書き込みます。

  4. ドキュメント ファイルを検索する場合は、完全に無視し、代わりにインデックス ファイルをメモリにロードし、バイナリ検索を使用してインデックス ファイルに単語が含まれているかどうかを調べます。並べ替えられた大きなリストを検索する場合、バイナリ検索に勝るものはありません。

または、ステップ (1) とステップ (2) を 1 つのステップにマージすることもできます。InsertionSort (バイナリ検索を使用して正しい挿入位置を見つけ、既に並べ替えられたリストに新しい要素を挿入する) を使用すると、単語が既にリストにあるかどうかを確認するための高速なアルゴリズムがあるだけではありません。そうではなく、挿入する正しい位置をすぐに取得し、常にそのように新しいものを挿入すると、ステップ (3) に到達したときに自動的にソートされたリストが作成されます。

問題は、ドキュメントが変更されるたびにインデックスを更新する必要があることです...しかし、これはデータベース ソリューションにも当てはまりますか? 一方、データベース ソリューションにはいくつかの利点があります。ドキュメントに非常に多くの単語が含まれている場合でも、インデックス ファイルがメモリに収まらない場合でも使用できます (ありそうもないことですが、すべての英単語のリストでさえ、平均的なユーザー PC のメモリに収まります)。ただし、膨大な数のドキュメントのインデックス ファイルをロードする必要がある場合は、メモリが問題になる可能性があります。さて、巧妙なトリック (たとえば、mmap を使用してメモリにマップしたファイル内を直接検索するなど) を使用して回避できますが、これらはデータベースが迅速なルックアップを実行するために既に使用しているトリックと同じです。したがって、なぜ車輪を再発明するのですか？さらに、ドキュメントが変更された場合 (つまり、データベースがユーザーに代わってロックを実行できる場合、または更新または更新をアトミック操作として実行できる場合) に、単語の検索とインデックスの更新の間のロックの問題を防ぐこともできます。リスト更新のための AJAX 呼び出しを使用する Web ソリューションの場合、おそらくデータベースを使用する方が適切なソリューションです (これが C のような低レベル言語で記述されたローカルで実行されるアプリケーションである場合、私の最初のソリューションはかなり適しています)。

1 回の select 呼び出しですべてを実行したい場合 (これは最適ではないかもしれませんが、AJAX を使用して Web コンテンツを動的に更新する場合、通常、これが最も頭痛の少ない解決策であることが証明されています)、3 つのテーブルすべてを結合する必要があります。SQL は少しさびているかもしれませんが、試してみます。

SELECT COUNT(Document.idDoc) AS NumOfHits, Documents.Name AS Name, Documents.Location AS Location 
FROM Documents INNER JOIN Word_Docs ON Word_Docs.idDoc=Documents.idDoc 
INNER JOIN Words ON Words.idWord=Words_Docs.idWord
WHERE Words.Word IN ('Word1', 'Word2', 'Word3', ..., 'WordX')
GROUP BY Document.idDoc HAVING NumOfHits=X

わかりました、おそらくこれは最速の選択ではありません...もっと速くできると思います。とにかく、少なくとも 1 つの単語を含むすべての一致するドキュメントを検索し、ID によってすべての等しいドキュメントをグループ化し、グループ化された数をカウントし、最後に NumOfHits (IN ステートメントで見つかった単語の数) の結果のみを表示します。は、IN ステートメント内の単語数と同じです (10 単語を検索する場合、X は 10 です)。

于 2008-09-29T09:31:58.723 に答える
0

構文についてはわかりません（これはSQLサーバーの構文です）が、次のとおりです。

-- N is the number of elements in the list

SELECT idDoc, COUNT(1)
FROM Word_Docs wd INNER JOIN Words w on w.idWord = wd.idWord
WHERE w.Word IN ('word1', ..., 'wordN')
GROUP BY wd.idDoc
HAVING COUNT(1) = N

つまり、like を使用しません。同様のものははるかに複雑です。

于 2008-09-29T08:47:51.683 に答える
0

Google デスクトップ検索または同様のツールが要件を満たす場合があります。

于 2008-09-29T09:45:05.307 に答える