莱文斯坦距离对称？ [英] Levenshtein distance symmetric?

问题描述

笔者获悉Levenshtein距离是对称的。当我用谷歌的diffMatchPatch工具其计算除其他事项Levenshtein距离，其结果，并不意味着Levenshtein距离是对称的。即的Levenshtein（X1，X2）是不等于的Levenshtein（2次，1次）。是莱文斯坦不是对称的或者是有与特定的实现有问题吗？谢谢你。

I was informed Levenshtein distance is symmetric. When I used google's diffMatchPatch tool which computes Levenshtein distance among other things, the results don't imply Levenshtein distance is symmetric. i.e Levenshtein(x1,x2) is not equal to Levenshtein(x2,x1). Is Levenshtein not symmetric or is there a problem with that particular implementation? Thanks.

推荐答案

只看基本算法，它肯定是对称的给予同样的费用为操作 - 的添加，删除和替换的数量从一个字一个一个字B，以获得相同的字B，以获得A字。

Just looking at the basic algorithm it definitely is symmetric given the same cost for the operations - the number of additions, deletions and substitutions to get from a word A to a word B is the same as getting from word B to word A.

如果有任何的操作的不同的成本可以有差别，虽然，如如果另外有2和删除成本为1的成本，从僵尸获得到植物大战僵尸导致的距离2，倒过来是1 - 不是对称的。

If there is a different cost on any of the operations there can be a difference though, e.g. if addition has a cost of 2 and deletion a cost of 1 to get from Zombie to Zombies results in a distance of 2, the other way round would be 1 - not symmetric.

这篇关于莱文斯坦距离对称？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！