7

問題：

約 20 個の ASCII テキスト ファイルがあり、それぞれのサイズは10^9 バイト未満です。別のASCII テキスト ファイル (たとえば FOO) が与えられます。プログラムは、FOO の内容を指定された 20 個のファイルと戦略的に一致させ、最も近い一致するファイルの名前を出力します。FOO の内容は、部分的にしか一致しない場合があります。

ファイルサイズが大きすぎるので、私は疑問に思っています:

1.Information Retrievalの使い方（IRについてよくわからないので）

2.そのような情報を保存するためにどのデータ構造を使用すればよいですか

3.それを実装するのに最適なアルゴリズムは何ですか。

私はあまりにも多くを求めていることを知っていますが、実際には私はこの問題で立ち往生しており、アプローチ方法を見つけることができません。

4

3 に答える 3

0

Vampire Coder による解決策では、ドキュメントが単語の袋であると想定しています。つまり、単語の順序は重要ではありません。しかし、「部分的に一致する」とは、文の一部が一致することを意味し、それでは何の役にも立ちません。

各ドキュメントを重複するサブセットに分割し、各サブセットのハッシュを取得できます。次に、ドキュメントを一連のハッシュに変換します。次に、ハッシュを比較できます。これは、やりたいことを実行できる 1 つの方法です。

ドキュメントごとに、一致する可能性のあるものを絞り込んだら、ドキュメントを分割する解像度を上げることができます。最初は 2 つに分割したとしますが、今では 10 に分割できます。これは、実行時間を最小限に抑えるためです。

また、次のような地域に依存するハッシュアルゴリズムを使用する必要があります: http://en.wikipedia.org/wiki/Nilsimsa_Hash

于 2014-01-14T04:40:43.983 に答える
0

私の推測では、「最も近い」のは、2 つのファイル間の差分が最小のファイルです。

私は差分アルゴリズム、または最長共通サブシーケンスを探します https://en.m.wikipedia.org/wiki/Longest_common_subsequence_problem

于 2015-07-26T19:03:41.537 に答える