0

単語検索用にインデックスを作成したい大きなドキュメントがあります。（このタイプの配列は実際にはコンコーダンスと呼ばれていると聞きました）。現在、所要時間は約10分です。それを行うための速い方法はありますか？現在、各段落を反復処理しており、以前に遭遇したことのない単語が見つかった場合は、それを単語配列に追加し、補助配列の段落番号とともに、同じ単語に再び遭遇するたびに段落番号を追加しますインデックスに。:

associativeArray={chocolate:[10,30,35,200,50001],parsnips:[5,500,100403]}

これには、5 分ほどかかります。この配列を文字列に変換しようとしましたが、非常に大きいため、ストップ ワードを削除した後でもプログラム ファイルに含めることができず、とにかく配列に変換するのに時間がかかります。

線形ブルート フォース以外のテキスト インデックスを構築するより高速な方法はありますか? 私はインデックスを作成してくれる製品を探しているのではなく、既知の最速のアルゴリズムを探しているだけです。インデックスはあいまいではなく正確である必要があり、部分検索の必要はありません。

4

4 に答える 4

2

最良のアイデアは、trieを作成し、テキストの時点で単語を追加し、葉ごとにその単語を見つけることができる場所のリストを作成することだと思います。

似たような接頭辞を持つ単語を保存すると必要なスペースが大幅に減るため、これによりスペースが節約されるだけでなく、検索も高速になります。検索時間は O(M) で、M は文字列の最大長であり、挿入時間は O(n) で、n は挿入するキーの長さです。

明らかな代替手段はハッシュ テーブルであるため、ここで 2 つの比較をさらに見つけることができます。

于 2013-09-03T08:42:06.407 に答える
1

さて、組み込みの を使用するという MrSmith42 の提案に従うことは別としてHashMap、段落番号の追跡にどれだけの時間を費やしているのだろうか?

代わりに行番号を追跡するように変更した方が速いでしょうか? (特に、入力を 1 行ずつ読み取っている場合)。

于 2013-09-04T04:04:27.143 に答える
1

この方法を使用すると、約O(1)HashMap<String, List<Occurrency>>で単語が既に yoz インデックスにあるかどうかを確認できます。

最後に、すべての単語を収集し、それらを非常に頻繁に検索したい場合は、衝突がまったくない、またはほとんどないハッシュ関数を見つけようとするかもしれません。このようにして、検索にO(1)時間 (まだ衝突がある場合はほぼ O(1)) を保証できます。

于 2013-09-03T08:44:20.720 に答える
0

あなたの質問には、「この配列を文字列に変換しようとしましたが、非常に大きいため、ストップワードを削除した後でも、プログラムファイルに含めることができません。いずれにせよ、配列に戻すにはしばらく時間がかかります。"?! どの配列、段落の配列の形式での入力ですか、それとも単語ごとのコンコーダンス エントリ、または何を意味しますか。

なぜあなたのプログラムがとても遅いのかは不明です.おそらくそこには何か非効率的なものがあります.段落番号があるかどうかを確認するための出現の配列 それは遅い線形検索です。setそこを使用する方が適切です（キーのみを気にするハッシュ/辞書を考えてください）、一種の

concord = {
    'chocolate': {10:1, 30:1, 35:1, 200:1, 50001:1}, 
    'parsnips': {5:1, 500:1, 100403:1}  
}

チェックif paraNum in concord[word]: ...は、ループまたはバイナリ検索の代わりになります。

PS。実際には、出現リストを配列に保持し、テキストを最初の段落から最後の段落までスキャンすると仮定すると、配列はソートされて形成されるため、最後の要素のみを確認する必要がありif word in concord and paraNum == concord[word][-1]:ます。(例は疑似コード/python にありますが、自分の言語に翻訳できます)

于 2013-12-30T03:40:14.393 に答える