确定产生 Levenshtein 距离的一系列编辑

Question

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

Answer 1

在尝试实现 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)（如果是平局，则更喜欢这个）那么你要么
     • 一个替代，如果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编写了一个实现，它输出精确的指令，包括每个操作中涉及的字符和偏移量。它还包括一些验证输出的测试，还演示了输出的格式。