Блог

Главная - Вопросы по программированию - Алгоритм Левенштейна в Java

Алгоритм Левенштейна в Java

#java #levenshtein-distance

#java #Левенштейн-расстояние

Вопрос:

Я пытаюсь реализовать алгоритм Левенштейна на Java, вдохновленный этой статьей в Википедии

 public static int indicator(char a, char b) {
    return (a == b) ? 0 : 1;
}

public static int levenshtein(String token1, String token2) {
    int[] levi = new int[token2.length()   1];
    int[] levi_1 = new int[token2.length()   1];

    // initialize column i=0
    for (int j = 0; j <= token2.length(); j  )
        levi_1[j] = j;

    // columns i=1 -> i=len(token1)
    for (int i = 1; i <= token1.length(); i  ) {
        // lev_a,b(i,0) = i
        levi[0] = i;
        // update rest of column i
        for (int j = 1; j <= token2.length(); j  ) {
            levi[j] = Math.min(Math.min(levi_1[j]   1, levi[j - 1]   1),
                               levi_1[j - 1]   indicator(token1.charAt(i - 1), token2.charAt(j - 1)));
        }

        // save column i to update column i 1
        levi_1 = levi;
    }

    return levi[token2.length()];
}

Но тестирование этого на строках «Maus» и «Haus» дает мне неправильный ответ 4. Можете ли вы помочь мне с тем, что я делаю неправильно?

Комментарии:

1. Что это за indicator метод?

2. добавил его в код.

3. Что возвращает ваш метод? Я вижу, что он должен выводить целое число, не так ли levi[levi.length - 1] ?

4. исправлено. да, он возвращает это

Ответ №1:

Проблема возникает из этой строки:

 levi_1 = levi;

Эта строка не изменяет каждое значение из levi_1 массива, она только изменяет его ссылку; значения остаются теми же, когда вы вызываете levi_1[0] levi_1[1] , и т.д.

Я бы посоветовал вам вместо этого написать эти строки:

 for (int k = 0; k < levi.length; k  )
    levi_1[k] = levi[k];