编辑距离对称吗？

Question

我得知编辑距离是对称的。当我使用 Google 的 diffMatchPatch 工具计算 Levenshtein 距离（除其他外）时，结果并不意味着 Levenshtein 距离是对称的。也就是说，

Levenshtein(x1, x2)

不等于

Levenshtein(x2, x1)

。编辑距离是否不对称，或者该特定实现是否存在问题？

Answer 1

仅看基本算法，它肯定是对称的 考虑到相同的操作成本 - 从单词 A 到单词 B 的添加、删除和替换次数与从单词 B 到单词 A 的添加、删除和替换次数相同.

如果任何操作的成本不同，则可能会有所不同，例如如果从

Zombie

到

Zombies

的加法成本为 2，删除成本为 1，则距离为 2，反之则为 1 - 不对称。

Answer 2

经典的 Levenshtein 距离算法是对称的 - 从

x1

到

x2

的插入就是从

x2

到

x1

的删除。

不幸的是，该算法是 O(length(

x1

) * length(

x2

)) 。简单浏览一下 Google 的库后，它似乎尝试了一些启发式方法来确保运行时间不会太大。我认为这就是你的差异。

Answer 3

是的，编辑距离是正确意义上的距离，即

dist(a, b) == dist(b, a)

是距离定义的一部分。 如果一个函数不具有此属性，则它不是距离函数。 这表明该实施存在问题。

Answer 4

正如其他人所指出的，根据定义，Levenshtein 的距离是适当的距离。

我使用

ratio

函数发现 fuzzywuzzy 库（又名 thefuzz）也存在同样的问题：

from fuzzywuzzy import fuzz

s1 = """Lorem ipsum dolor sit amet, consectetur adipiscing elit, 
sed do eiusmod tempor incididunt ut labore et dolore 
magna aliqua. Ut enim ad minim veniam, quis nostrud 
exercitation ullamco laboris nisi ut aliquip ex ea 
commodo consequat. Duis aute irure dolor in reprehenderit"""

s2 = """in voluptate velit esse cillum dolore eu fugiat 
nulla pariatur. Excepteur sint occaecat cupidatat 
non proident, sunt in culpa qui officia deserunt 
mollit anim id est laborum."""

fuzz.ratio(s1, s2)
Out [1]: 15

fuzz.ratio(s2, s1)
Out [2]: 2

但是，使用

partial_ratio

时不会发生这种情况：

fuzz.partial_ratio(s1, s2)
Out [3]: 20

fuzz.partial_ratio(s2, s1)
Out [4]: 20

因此问题可能存在于实现中或者是

ratio

函数的预期行为，不幸的是这些函数没有文档。

棘手的部分是，对于许多对字符串

ratio

，无论顺序如何，都会给出相同的结果，这就是为什么我必须使用这么大的字符串来找到正确的示例（但对于较小的字符串仍然会发生）。

Answer 5

请遵循我自己实现的代码

public class ReadTextFile {

    static void readFile(String filepath){
        CharSequence sequence1 = null;
        CharSequence sequence2 = null;
        
        int levenshteinDistance = 0;
        
        String line1 = "";
        String line2 = "";
        int minLevenshteinDistance = -1;
        
        try {
            BufferedReader br = new BufferedReader(new FileReader(filepath));
            String line = "";
            while((line=br.readLine())!=null)
            {
                if(sequence1==null){
                    line  = line.split(" ")[1];
                    sequence1 = line;                   
                    
                    if((line=br.readLine())!=null){                 
                        line  = line.split(" ")[1];
                        sequence2 = line;                   
                    }
                }else{
                    sequence1 = sequence2;
                    line  = line.split(" ")[1];
                    sequence2 = line;                   
                }
                
                if(null!=sequence1 && null!=sequence2){
                    
                    levenshteinDistance = StringUtils.getLevenshteinDistance(sequence1,sequence2);
                    
                    if(minLevenshteinDistance==-1){
                        minLevenshteinDistance = levenshteinDistance;
                        line1= sequence1.toString();
                        line2= sequence2.toString();
                    }else if(levenshteinDistance < minLevenshteinDistance){
                        minLevenshteinDistance = levenshteinDistance;
                        line1= sequence1.toString();
                        line2= sequence2.toString();
                    }
                }
            }
            
            br.close();
            System.out.println("line1 "+line1);
            System.out.println("line2 "+line2);
            System.out.println("minlevenshteinDistance " + minLevenshteinDistance);
        
        }catch (IOException e) {
            System.out.println(e.getMessage());
        }
    }
}