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

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

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

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

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

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

пожалуйста, следуйте коду, который добавлен 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());
    }

}

}