3

TF-IDF とコサイン類似度を使用した小さな検索エンジンを開発しています。ページが追加されると、別のページで単語の頻度を維持するために逆索引を作成します。ストップワードとより一般的な単語、および複数形/動詞/などを削除します。ステミングされます。

私の逆インデックスは次のようになります。

map< string, map<int, float> > index

[
    word_a => [ id_doc=>frequency, id_doc2=>frequency2, ... ],
    word_b => [ id_doc->frequency, id_doc2=>frequency2, ... ],
    ...
]

このデータ構造を使用すると、 で idf の重みを取得できますword_a.size()。クエリが与えられると、プログラムはキーワードをループし、ドキュメントにスコアを付けます。

データ構造がよくわからないので、質問は次のとおりです。

  1. 検索時にロードするために 500 Mo の転置インデックスを格納する方法は? 現在、ブーストを使用してインデックスをシリアル化しています。

    ofstream ofs_index("index.sr", ios::binary);
boost::archive::bynary_oarchive oa(ofs_index);
oa << index;

    そして、検索時にロードします。

    ifstream ifs_index("index.sr", ios::binary);
boost::archive::bynary_iarchive ia(ifs_index);
ia >> index;

    しかし、非常に遅く、読み込みに 10 秒ほどかかることもあります。

  2. map逆インデックスに対して十分に効率的かどうかはわかりません。

  3. ドキュメントをクラスター化するために、各ドキュメントからすべてのキーワードを取得し、これらのキーワードをループして類似ドキュメントをスコアリングしますが、各ドキュメントを再度読み取ることは避け、この逆インデックスのみを使用したいと考えています。しかし、このデータ構造はコストがかかると思います。

助けてくれてありがとう！

4

1 に答える 1

3

答えは、マシンの RAM と同等またはそれ以上のデータをサポートする必要があるかどうか、および一般的なユース ケースで、インデックス付きデータのすべてにアクセスする可能性が高いか、それともごく一部にアクセスする可能性が高いかによって異なります。

データがマシンのメモリに収まることが確実な場合は、現在使用しているマップ ベースの構造を最適化してみてください。データをマップに保存すると、アクセスがかなり高速になりますが、データをディスクからメモリにロードするときに、常に初期オーバーヘッドが発生します。また、インデックスのごく一部のみを使用する場合、常にインデックス全体を読み書きし、そのすべてをメモリに保持するため、このアプローチは非常に無駄になる可能性があります。

以下に、試してみることができるいくつかの提案を示しますが、それらのいずれかに時間をかけすぎる前に、負荷と実行時間を改善するものとしないものを実際に測定してください。使用する実際のデータで実際に動作するコードをプロファイリングしないと、これらは単なる推測であり、完全に間違っている可能性があります。

  • mapツリー (通常は黒赤ツリー) として実装されます。多くの場合、ahash_mapを使用すると、パフォーマンスが向上し、メモリ使用量も向上します (たとえば、割り当てが少なくなり、断片化が少なくなります)。
  • データのサイズを小さくしてみてください。データが少ないほど、ディスクからの読み取りが高速になり、メモリ割り当てが少なくなる可能性があり、局所性が向上するためメモリ内のパフォーマンスが向上する場合があります。floatたとえば、 を使用して頻度を保存すると考えるかもしれませんがunsigned short、マップ値に出現回数のみを保存し、別のマップに各ドキュメントのすべての単語の数を (短いものとして) 保存することもできます。2 つの数値を使用して頻度を再計算できますが、データをディスクに保存するときに使用するディスク領域が少なくなるため、読み込み時間が短縮される可能性があります。
  • マップにはかなりの数のエントリがあり、カスタム メモリ アロケータを使用するとパフォーマンスが向上することがあります。

データがマシンの RAM のサイズを超えて大きくなる可能性がある場合は、メモリ マップト ファイルを使用してデータを保存することをお勧めします。このようなアプローチでは、データ構造を再モデル化し、代わりにカスタム STL アロケータを使用するか、完全にカスタムのデータ構造を使用する必要がありstd::mapますが、うまく行えばパフォーマンスが桁違いに向上する可能性があります。特に、このアプローチにより、構造全体を一度にメモリにロードする必要がなくなるため、最初に構造のさまざまな部分に触れるため、時間の経過とともに分散されるディスク アクセスに関連するわずかな遅延を犠牲にして、起動時間が劇的に改善されます。時間。主題は非常に広く、マップを調整するだけでなく、コードにさらに深い変更を加える必要がありますが、膨大なデータを処理する予定がある場合は、必ず以下を確認してください。mmapと友達。

于 2014-03-23T13:46:07.557 に答える