1

我想使用 Levenshtein 算法来比较 VB.NET 中的两个文件。我知道我可以使用 MD5 哈希来确定它们是否不同，但我想知道这两个文件有多大不同。我正在使用的文件都在 250 兆左右。我已经尝试了不同的方法来做到这一点，我意识到我真的无法将两个文件都加载到内存中（各种与字符串相关的问题）。所以我想我只是流式传输我需要的字节。美好的。但是我发现的 Levenshtein 算法的实现都是一个长度为 1 * 长度为 2 的矩阵，在这种情况下是不可能使用的。我听说有一种方法可以只用两个向量而不是整个矩阵来做到这一点。

如何在不声明作为文件大小乘积的矩阵的情况下计算两个大文件的 Levenshtein 距离？

4

1 回答 1

1

请注意，Levenshtein 矩阵的每一行中的值仅取决于其上方行中的值。这意味着您只需要两个一维数组：一个包含当前行的值；另一个包含当前行的值。另一个填充了您可以从当前行计算的新值。然后，您交换他们的角色（“新”行变为“当前”行，反之亦然）并继续。

请注意，这种方法只允许您计算 Levenshtein 距离（这似乎是您想要的）；它无法告诉您必须执行哪些操作才能将一个字符串转换为另一个字符串。该算法有一个非常巧妙的修改，可以让您在不使用nm内存的情况下重建编辑操作，但我忘记了它是如何工作的。

于 2012-10-09T20:36:51.143 回答