python - 如何修改 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), whereoperation is one of 'equal', 'replace', 'insert', or 'delete'; sposand dpos are position of characters in the first (source) and thesecond (destination) strings. These are operations on singlecharacters. In fact the returned list doesn't contain the 'equal',but all the related functions accept both lists with and without'equal's.