1

レーベンシュタイン アルゴリズムを使用して、VB.NET で 2 つのファイルを比較したいと考えています。MD5 ハッシュを使用してそれらが異なるかどうかを判断できることは知っていますが、2 つのファイルがどの程度異なるかを知りたいです。私が扱っているファイルはどちらも約 250 MB です。これを行うさまざまな方法を試してみたところ、実際には両方のファイルをメモリにロードできないことに気付きました (あらゆる種類の文字列関連の問題)。そのため、必要なバイトをストリーミングするだけでよいと考えました。罰金。しかし、私が見つけたレーベンシュタイン アルゴリズムの実装はすべて、長さ 1 * 長さ 2 のサイズの行列を次元化しており、この場合は操作できません。行列全体ではなく、2 つのベクトルだけでこれを行う方法があると聞きました。

ファイルサイズの積である行列を宣言せずに、2 つの大きなファイルのレーベンシュタイン距離を計算するにはどうすればよいですか?

4

1 に答える 1

1

レーベンシュタイン行列の各行の値は、その上の行の値のみに依存することに注意してください。これは、2 つの 1 次元配列のみが必要であることを意味します。1 つは現在の行の値を含みます。もう 1 つは、現在の行から計算できる新しい値が取り込まれます。次に、それらの役割を交換し (「新しい」行が「現在の」行になり、その逆)、続行します。

このアプローチでは、レーベンシュタイン距離のみを計算できることに注意してください (これは、必要なようです)。ある文字列を別の文字列に変換するためにどの操作を実行する必要があるかはわかりません。nmメモリを使用せずに編集操作を再構築できるようにするアルゴリズムの非常に巧妙な変更が存在しますが、それがどのように機能するかを忘れてしまいました。

于 2012-10-09T20:36:51.143 に答える