2

我正在使用动态编程使用 Levenshtein（编辑）距离做一些工作。我想我理解 Wagner-Fischer 算法可以有效地做到这一点。但是，该算法看起来并不具有建设性。如果我计算出两个字符串之间的编辑距离是 10，那么我还想确定一个特定的 10 次编辑序列，它将一个变成另一个。这也能有效地完成吗？如果是这样，怎么做？

4

2 回答 2

5

在尝试实现 Ante 算法时，我得到了错误的结果，这意味着它要么是错误的，要么是我以错误的方式实现它。无论如何，我让它工作了，这是我更详细的算法。请参阅Wagner-Fischer 算法以了解d.

  1. 从单元格开始d(m, n)
  2. 检查单元格d(m - 1, n - 1)，d(m - 1, n)并d(m, n - 1)确定哪一个包含最小值。
    • 如果是d(m - 1, n - 1)（如果是平局，更喜欢这个），那么你有
      • 一个替换 if d(m - 1, n - 1) < d(m, n)。减m一n。
      • 如果没有操作d(m - 1, n - 1) == d(m, n)。减m一n。
    • 如果是，d(m - 1, n)那么你有一个删除。减m一。
    • 如果是，d(m, n - 1)那么你有一个插入。减n一。

如果任何单元格查找会导致负索引，请跳过它们。如果你到达牢房(0, 0)，你就完成了。您将以相反的顺序生成编辑列表。

我用 Python 编写了一个实现，它输出准确的指令，包括每个操作中涉及的字符和偏移量。它还包括一些用于验证输出的测试，并且还演示了输出的格式。

于 2018-08-20T13:40:36.677 回答
2

这是非常有建设性的。使用生成的矩阵，可以找到产生最小距离的所有不同编辑序列。

要查找编辑，您必须在“向后”中传递结果矩阵。从结果单元格开始，(m,n)。

  • 如果单元格的值(m-1, n-1)相同，则这些地方的字符相同，则无需编辑。
  • 如果单元格的值(m-1, n-1)较小，则从 {(m-1, n-1), (m-1, n), (m, n-1)}具有最小值的单元格中查找。具有最小值的单元格的位置决定了是否执行替换、删除或插入。如果有更多具有最小值的单元格，则更多的编辑序列可以产生最小的距离。如果您只需要一个序列而不是选择其中任何一个。

进行相同的检查，直到路径到达 cell (0,0)。

检查路径确定以相反顺序执行的编辑。

于 2014-08-11T08:56:27.327 回答