维基百科关于Levenshtein 距离的文章在其可能的修改部分中说,“[w]e 可以分别存储插入、删除和替换的数量”。
这是怎么做到的?我创建了文章中概述的基于矩阵的动态编程解决方案的实现,其中矩阵的每个单元格都有一个单独的删除/插入/替换值,但对于我的生活,我似乎无法解决逻辑。
直观地说,如果我发现需要在同一步骤中进行删除和插入,那么这些应该变成替代。
为了使我想要完全清楚,这是源字符串“mat”和目标字符串“catch”的示例矩阵。我希望这需要一次替换(即,将“m”更改为“c”)和两次插入(即附加“ch”)。每个单元格都是“删除/插入/替换”。
抓住 +-----+-----+-----+------+-----+-----+ |D/I/S|0/1/0|0/2/0|0/3/0|0/4/0|0/5/0| +-----+-----+-----+------+-----+-----+ M |1/0/0|0/0/1|0/1/1|0/2/1|0/3/1|0/4/1| +-----+-----+-----+------+-----+-----+ A |2/0/0|1/0/1|0/0/1|0/1/1|0/2/1|0/3/1| +-----+-----+-----+------+-----+-----+ T |3/0/0|2/0/1|1/0/1|0/0/1|0/1/1|0/2/1| +-----+-----+-----+------+-----+-----+
有人研究过这个算法吗?