9 algorithm levenshtein-distance
我被告知Levenshtein距离是对称的.当我使用google的diffMatchPatch工具来计算Levenshtein距离时,其结果并不意味着Levenshtein距离是对称的.即Levenshtein(x1,x2)不等于Levenshtein(x2,x1).Levenshtein是不对称的还是特定实现存在问题？谢谢.
Bro*_*ass 14
仅仅考虑基本算法,它肯定是对称的,因为操作的成本相同 - 从单词A到单词B的加法,删除和替换的数量与从单词B到单词A的相同.
如果在任何不同的操作成本可以有差别,虽然,例如,如果另外有2和删除成本成本1从中获取Zombie到Zombies的结果以2:1的距离,反过来会1 - 不对称.
经典的Levenshtein算法是对称的 - 从x1到x2的插入是从x2到x1的删除.
不幸的是,算法是O(长度(x1)*长度(x2)).在简要了解谷歌的库后,似乎尝试了一些启发式方法来确保运行时不会太大.我认为存在差异.