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

Question

我正在尝试设计一个Levenshtein算法的衍生版本，在此过程中，我会记录对字符串进行的转换（例如插入a或将b替换为c）。

举个例子： 假设我要计算"bbd"和"bcd"之间的编辑距离，则其编辑距离为1，变换为“将b替换为c”。

问题： 由于我看到的实现并不关心操作类型，而只关心总成本，那么我该如何解决这个问题呢？

- Georgi Angelov

Answer 1

你可以使用这个模块python-Levenshtein - 它包含一个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)

结果是一个三元组(operation, spos, dpos)列表，其中 operation可以是 'equal', 'replace', 'insert' 或者 'delete'; spos 和 dpos 是第一个(源)字符串和第二个(目标)字符串中字符的位置。这些都是对单个字符的操作。实际上，返回的列表不包含 'equal'，但是所有相关函数都接受带有和不带有 'equal' 的列表。

- Ivan Genchev