•  02-07-2019
  •  | 
  •  

質問

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

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

  • 最適化された検索機能が必要です。この検索機能には、スペースで区切られたリスト（1つまたは複数）の部分的に完全な（または完全な）単語を指定します。
  • 関数は、最初の単語以上の単語を含むすべてのドキュメントを検索し、2番目の単語を使用して同じ方法でこれらの検索されたドキュメントを検索し、最後に実際の単語の完全なリストのために、それらを含むドキュメント（名前と場所）にリンクされていることが検出された単語。
  • ドキュメントには、リスト内の単語がすべて含まれている必要があります。
  • この関数を使用して入力したままの検索を行い、結果をリアルタイムでツリー状の構造で表示および更新できるようにします。

私が思いついた解決策への可能なアプローチは次のとおりです。 「Documents」、「Words」、「Word_Docs」の3つのテーブルでデータベースを作成します（ほとんどの場合mysqlを使用します）。

  • 「Documents」には、すべてのドキュメントの（idDoc、Name、Location）が含まれます。
  • 「Words」は（idWord、Word）を持ち、すべてのドキュメントの一意の単語のリストになります（特定の単語は1回だけ表示されます）。
  • 「Word_Docs」は（idWord、idDoc）を持ち、各単語とそれが現れる文書の一意のid組み合わせのリストになります。

その後、各キーストロークで編集ボックスのコンテンツを使用して関数が呼び出されます（スペースを除く）：

  • 文字列はトークン化されます
  • （ここで私の車輪は少し回転します）：必要なデータセットを返すために、単一のSQLステートメントを構築できると確信しています： （私はSQLのホット番号ではありません）、代わりに各トークンの呼び出しのシーケンスと非繰り返しidDocsを解析しますか？
  • このデータセット（/ list / array）が返されます

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

e.g .:次のように呼び出されます：＆quot; seq sta cod＆quot; 表示：

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]

（など）

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

（タグの閲覧にこのタイプの検索ソリューションを使用することもできますか？（メインページの右上））

役に立ちましたか？

解決

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

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

他のヒント

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

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

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

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

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

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

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

1回の選択呼び出しですべてを実行したい場合（最適ではないかもしれませんが、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です）。

構文についてはわかりません（これは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を使用しません。似たようなものはもっと複雑です。

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top