假设我们有两个字符串:
- ccttgg
- gacgct
这两个字符串的编辑距离为6。
可能的子字符串有:
- cctt--
- gacg--
他们的编辑距离是4。
与原始两个字符串相等的其余部分是:
- ----gg
- ----ct
并且它们的编辑距离是2。
因此4+2=6,这就是原始编辑距离。
这种假设总是正确的吗?
如果不是,有没有一种方法可以使用两个字符串的子字符串的编辑距离来计算它们之间的编辑距离?
编辑:为了更清楚,我对编辑距离的定义是Levenstein距离,如果字符不相同,则插入、删除和替换的代价为1,如果字符相等,则为0。考虑到带有换位的Damerau距离,我不是。
无
反例
考虑字符串:
- aba
- bab
它们通过删除";a";从前面开始;b";直到最后。
如果这些被分解成子字符串,如
- ab,a
- ba,b
则第一子串具有2的编辑距离,第二子串具有1的编辑距离总共3。