如何修改Levenshtein算法，知道它是插入、删除还是替换了一个字符？

Question

因此，我试图设计一个Levenshtein算法的副产品，在这里我跟踪我在字符串中所做的转换（插入a，或者用a代替b）。在

示例：

基本上，假设我在计算“bbd”和“bcd”的编辑距离

编辑距离为1，变换为“b为c”

问题： 我应该如何解决这个问题，因为我所看到的实现并不关心它是什么样的操作，而只关心它的总成本？在

Answer 1

您可以使用this模块-那里有一个editops函数，它返回一个列表，其中包含将一个字符串转换为另一个字符串所需的操作。在

示例：

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

从文件中：

Find sequence of edit operations transforming one string to another.

editops(source_string, destination_string) editops(edit_operations, source_length, destination_length)

The result is a list of triples (operation, spos, dpos), where operation is one of equal',replace', insert', ordelete'; spos and dpos are position of characters in the first (source) and the second (destination) strings. These are operations on signle characters. In fact the returned list doesn't contain the equal', but all the related functions accept both lists with and without equal's.