如何修改Levenshtein算法以识别字符的插入、删除或替换？

Question

我正在尝试对Levenshtein算法进行一些改进，想要记录在字符串中做了哪些变换，比如插入了一个"a"，或者把"b"替换成了"c"。

举个例子：

假设我在计算字符串"bbd"和"bcd"之间的编辑距离。

它们的编辑距离是1，而变换的内容是“把b替换成c”。

问题：我该如何解决这个问题呢？因为我看到的实现方式都只关注总的编辑成本，而不关心具体进行了什么操作。

Answer 1

你可以使用这个模块，里面有一个叫editops的函数，它可以返回一个列表，告诉你需要进行哪些操作才能把一个字符串变成另一个字符串。

举个例子：

Levenshtein.editops("FBBDE", "BCDASD")
[('delete', 0, 0), ('replace', 2, 1), ('insert', 4, 3), ('insert', 4, 4), ('replace', 4, 5)]

根据文档的说明：

找到将一个字符串转换成另一个字符串所需的编辑操作序列。

editops(源字符串, 目标字符串)

editops(编辑操作, 源字符串长度, 目标字符串长度)

结果是一个包含三元组的列表（操作，源位置，目标位置），其中操作可以是'相同'、'替换'、'插入'或'删除'；源位置和目标位置分别是第一个（源）字符串和第二个（目标）字符串中字符的位置。这些操作都是针对单个字符的。实际上，返回的列表不包含'相同'这个操作，但所有相关的函数都可以接受包含和不包含'相同'的列表。