如何修改Levenshtein算法,知道它是否插入,删除或替换了一个字符？

Question

所以我试图设计一个Levenshtein算法的旋转,在那里我跟踪我在字符串中做了什么转换(插入a或替换为b).

例:

基本上,我说计算"bbd"和"bcd"的编辑距离

编辑距离为1,转换为"c的替代b"

问题: 我如何处理这个问题,因为我看到的实现并不关心自己知道什么样的操作,而只是总成本？

Answer 1

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

例:

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

来自文档:

查找将一个字符串转换为另一个字符串的编辑操作序列

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

结果是三元组列表(操作,spos,dpos),其中操作是equal',替换',insert', or删除'之一; spos和dpos是第一个(源)和第二个(目标)字符串中字符的位置.这些是对单号字符的操作.实际上,返回的列表不包含equal', but all the related functions accept both lists with and without 等号.