2

私の仕事は、非常に短い (たとえば 200 文字の長さの) ドキュメントのリストから文字列またはパターンを検索することです。しかし、そんな時代の文書が100万件もあるとは。この検索を実行する最も効率的な方法は何ですか? 各ドキュメントをトークン化し、単語をキー、ドキュメント番号を値としてハッシュテーブルに入れ、単語のバッグを作成することを考えていました。次に、単語検索を実行し、この単語を含むドキュメントのリストを取得します。私が見ることができることから、この操作には O(n) 操作が必要です。他に方法はありますか？ハッシュテーブルを使用しない可能性がありますか?。

また、効率的に検索できるpythonライブラリやサードパーティのパッケージはありますか？

4

4 に答える 4

4

ライブラリを探しているので、PyLucene を調べましたか?

http://lucene.apache.org/pylucene/features.html

Lucene は通常、完全一致ではなく、ランク付けされた検索 (相対スコアに基づく一致) を実装しますが、正確なフレーズ検索に使用できます。Lucene を使用して正確なフレーズを検索する方法については、次のリンクを参照してください。Javaで書かれていますが、アイデアは次のとおりです。

Lucene を使用した正確なフレーズ検索?

あなたの質問は、特に効率について尋ねました。効率はどのように？ユーザーにとって最速のルックアップ時間を意味していたと思います。ユーザーのルックアップ時間の観点から純粋に速度について話している場合、コーパス内のすべてのドキュメントをインデックス化するための最初の時間を許容できる場合、ドキュメント内のすべての単語を実際にインデックス化するよりも高速な方法はありません。. インデックス作成は 1 回限りのイベントであり、ユーザー検索は頻繁に発生するため、通常はこれが論理的な選択です。ただし、明らかに、これにはかなりのメモリ使用量が伴います。したがって、メモリ使用量の観点から効率性について話している場合は、すべてのドキュメントをループして、各ドキュメントに対して正規表現検索を実行する必要があります。インデックス作成の最初のルックアップ時間を回避したい場合にも、この方法を使用します。ただし、コーパスのサイズが大きい場合、これが論理的な制限要因になる可能性は低く、懸念事項は通常、作成するユーザーを満足させることです。複数のクエリ。

私が指摘する他の唯一のことは、単語だけでなくパターンを検索していると述べたので、パターンのクエリをサポートしようとしている場合、単語のみのインデックス作成は役に立たないということです（そのパターンがドキュメント！）

Lucene を使用せず、代わりに独自に実装したい場合は、逆インデックスを使用したインデックス作成を検討してください。フレーズ クエリを実行する場合に、逆インデックスを作成する方法についての優れた説明を次に示します。

http://www.searchenginepeople.com/blog/how-search-really-works-the-index-2.html

于 2012-10-28T05:57:01.227 に答える
3

ほとんどの検索エンジンは、逆索引の原則に従って動作します。基本的に、トークン (単語、トリグラムなど) ごとに、このトークンを含むドキュメントの並べ替えられたリストを格納します。クエリを照合するときは、必要なすべてのトークンのリストをマージ結合して、候補ドキュメントのリストを作成します。インデックスの一致によってクエリの一致が保証されない場合は、一致したドキュメントでクエリ式を再テストする必要があります。

転置インデックスを格納するソリューションは多数ありますが、そのうちのいくつか (Lucene、Sphinx、PostgreSQL FTS) は、転置インデックスでの式の評価を既にサポートしています。

検索エンジンの魔法は、主にドキュメントの前処理とトークン化、およびユーザー要求からの検索クエリの生成で発生します。前処理のトリックには、単語をステミングし、単語ごとに複数の異なる表現を格納することによる単語の正規化が含まれます。クエリの構築では、同義語の置換などを行うことができます。正規表現は少しトリッキーですが、PostgreSQL で正規表現検索のインデックス サポートを実装することについての素晴らしい話があります。

于 2012-10-28T09:53:07.713 に答える
1

ハッシュテーブルを使用して単語の袋を作成するというアイデアは楽しいように聞こえますが、各ファイルを開いてメモリに読み込み、トークン化し、ハッシュテーブルを作成し、各トークンをハッシュテーブルに入れ、検索語をハッシュしてから、単語を含む各ドキュメントのドキュメント ID を見つけるためにハッシュテーブルを使用すると、正規表現を使用して各ファイルを検索する場合よりもはるかに多くの時間を費やしたことになります。

import re
import os
import sys

searchterm = sys.argv[1]
searchexp = re.compile("(%s)" % searchterm, re.M)

for filename in os.listdir(sys.argv[2]):
    f = open(os.path.join(sys.argv[2], filename), 'r')
    contents = f.read()
    f.close()
    if searchexp.search(contents):
        print(filename)

それは遅すぎますか？

于 2012-10-28T04:51:05.337 に答える
1

残念なことに廃止された Google コード検索エンジンのために彼が開発した、Russ Cox によってここで説明されているものよりも、この問題に対するより良い解決策はないと思います。

于 2012-10-28T04:54:40.673 に答える