Расстояние Левенштейна симметрично?

Question

Мне сообщили, что расстояние Левенштейна симметрично. Когда я использовал инструмент Google diffMatchPatch, который вычисляет расстояние Левенштейна, помимо прочего, результаты не подразумевают, что расстояние Левенштейна симметрично. Т.е. Левенштейн (x1, x2) не равен Левенштейну (x2, x1). Левенштейн не симметричен или есть проблема с этой конкретной реализацией? Спасибо.

Answer 1

Просто глядя на базовый алгоритм, он определенно является симметричным , учитывая ту же стоимость операций - количество добавлений, удалений и замен, которые нужно получить от слова A к слову B, равнозначно получениюот слова B к слову A.

Если по какой-либо из операций существуют разные затраты, разница может быть, например, если сложение имеет стоимость 2, а удаление 1, чтобы получить от Zombie до Zombies приводит к расстоянию 2, наоборот - 1 - не симметрично.

Answer 2

Классический алгоритм Левенштейна симметричен - то, что вставка идет от x1 до x2, это удаление от x2 до x1.

К сожалению, алгоритм O (длина (x1) * длина (x2)). После краткого взгляда на библиотеку Google, кажется, он пытается эвристики, чтобы убедиться, что время выполнения не слишком велико. Я думаю, в этом и заключается Ваше несоответствие.

Answer 3

Да, расстояние Левенштейна - это расстояние в собственном смысле, то есть dist(a,b)==dist(b,a) является частью определения расстояния.Если функция не имеет этого свойства, она не является функцией расстояния.Это наводит на мысль о проблеме с этой реализацией.

Answer 4

, пожалуйста, следуйте коду, который указан myselef

открытый класс 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());
    }

}

}