Недостающие значения и NPE в алгоритме Левенштейна

Question

Мне нужно создать этот класс, но я не могу заставить его работать:

public void printTable () : печатает таблицу (двумерный массив). (необязательно: распечатайте таблицу с двумя правильными словами позиции в первом ряду и первом столбце соответственно.)

public class Levenshtein {
private String word1;
private String word2;
private int[][] table;

public Levenshtein(String aWord1, String aWord2) {
    word1 = aWord1;
    word2 = aWord2;

    Levenshtein.table(word1, word2);
}

private static int[][] table(String word1, String word2) {

    int[][] distTable = new int[word1.length()+1][word2.length()+1];

    for (int i = 0; i < distTable.length; i++) {
        distTable[i][0] = i;
    }
    for (int j = 0; j < distTable[0].length; j++) {
        distTable[0][j] = j;
    }

    return distTable;

}

private static int min(int i1, int i2, int i3) {
    return Math.min(Math.min(i1, i2), i3);

}

public int distance() {
    int[][] distance = new int[word1.length() + 1][word2.length() + 1];        

    for (int i = 0; i <= word1.length(); i++)                                 
        distance[i][0] = i;                                                  
    for (int j = 1; j <= word2.length(); j++)                                 
        distance[0][j] = j;                                                  

    for (int i = 1; i <= word1.length(); i++)                                 
        for (int j = 1; j <= word2.length(); j++)                             
            distance[i][j] = min(                                        
                    distance[i - 1][j] + 1,                                  
                    distance[i][j - 1] + 1,                                  
                    distance[i - 1][j - 1] + ((word1.charAt(i - 1) == word2.charAt(j - 1)) ? 0 : 1));

    return distance[word1.length()][word2.length()];
}



public void printTable() {
    String tableArray[][] = new String[word1.length()+2][word2.length()+2];

    //Header Row
    for (int i = 0; i < word1.length()+2; i++) {
        if (i == 0 || i == 1) {
            tableArray[i][0] = "*";
        } else {
            String tmp = String.valueOf((word1.charAt(i-2)));
            tableArray[i][0] = tmp;
        }
    }
    //Header Column
    for (int j = 0; j < word2.length()+2; j++) {
        if (j == 0 || j == 1) {
            tableArray[0][j] = "*";
        } else {
            String tmp = String.valueOf((word2.charAt(j-2)));
            tableArray[0][j] = tmp;
        }
    }

    //Initialize column 0 (column 0 = header, start column = 1)
    for (int k = 1; k < tableArray.length-2; k++) {
        int tmp = k;
        tableArray[1][k] = String.valueOf(tmp-1);
    }
    for (int l = 1; l < tableArray.length-1; l++) {
        int tmp = l;
        tableArray[l][1] = String.valueOf(tmp-1);
    }
    System.out.println(tableArray[1][1]);

    //Filling Table
    for (int i = 2; i <= word1.length(); i++)   {                              
        for (int j = 2; j <= word2.length(); j++) {                         
            tableArray[i][j] = String.valueOf(min(
                    Integer.valueOf(tableArray[i - 1][j]) + 1,
                    Integer.valueOf(tableArray[i][j - 1]) + 1,
                    Integer.valueOf(tableArray[i - 1][j - 1]) + ((word1.charAt(i - 1) == word2.charAt(j - 1)) ? 0 : 1)));
        }}

    //Print Table
    for (int m = 0; m < word1.length()+2; m++) {
        //System.out.print(tableArray[m][0]);
        for (int n = 0; n < word2.length()+2; n++) {
            System.out.print(tableArray[m][n] + " | ");
        }
        if (m < word1.length()+2 ) { System.out.print("\n"); }
    }

}

}

MainClass:

public class MainClass {

    public static void main(String[] args) {

        Levenshtein lev = new Levenshtein("face", "ape");
        Levenshtein lev2 = new Levenshtein("ape", "face");

        //System.out.println(lev.distance());

        lev.printTable();
        lev2.printTable();

    }
}

Будет выведено:

0
* | * | a | p | e | 
* | 0 | 1 | 2 | null | 
f | 1 | 1 | 2 | null | 
a | 2 | 2 | 2 | null | 
c | 3 | 3 | 2 | null | 
e | null | null | null | null | 
0
Exception in thread "main" java.lang.NumberFormatException: null
    at java.lang.Integer.parseInt(Integer.java:542)
    at java.lang.Integer.valueOf(Integer.java:766)
    at Levenshtein.printTable(Levenshtein.java:90)
    at MainClass.main(MainClass.java:11)

Так что в первом он не вычисляет последний столбец, а во втором он просто не работает.

Answer 1

Я полагаю, что в вашей программе есть несколько ошибок, поэтому я не рассматриваю все из них.

Так что в первом из них не вычисляется последний столбец,…

tableArray на 2 ячейки больше в каждом измерении, чем длина слова (6 на 5 в вашем первом примере), но цикл, в котором вы заполняете таблицу, проходит только от 0 до длины каждого слова (5 на 4).Поэтому последняя строка и последний столбец не заполняются.Я подозреваю, что вы также вводите неправильные значения в таблицу.Возможно, вы где-то не используете правильные индексы.Вам нужно исправить это и , чтобы цикл выполнялся на одну итерацию дольше.

… а во 2-й он просто не работает.

При заполнении таблицы в итерации, где i равно 2, а j равно 3, когда вы выполняете Integer.valueOf(tableArray[i - 1][j]), эта ячейка таблицы имеет значение null, в результате чего Integer.valueOf выдает NumberFormatException.Эта клетка - tableArray[1][3] - не должна была быть нулевой, так почему?Строка 1 должна была быть заполнена выше, в этом цикле:

    for (int k = 1; k < tableArray.length-2; k++) {
        int tmp = k;
        tableArray[1][k] = String.valueOf(tmp-1);
    }

Но граница tableArray.length-2 неверна.На этот раз таблица 5 на 6, поэтому bpoundary равен 5 - 2 = 3, поэтому заполнены только ячейки 0, 1 и 2, где вы хотели, чтобы ячейки 3, 4 и 5 тоже были заполнены.Кстати, граница в следующем цикле for также неверна.

Советы по проектированию

Используйте только одну таблицу, ваш private int[][] table, в вашем классе.Не используйте локальные таблицы в ваших методах.Если вам проще иметь таблицу строк в вашем методе printTable, это нормально, но заполняйте ее из таблицы в классе, а не заново вычисляйте все ее содержимое.Это будет намного проще.

Это требует, чтобы таблица в классе была заполнена (рассчитана), конечно.Я полагаю, что эта строка в конструкторе должна была сделать это?

    Levenshtein.table(word1, word2);

Но это не так, потому что метод table тоже работает на своей собственной таблице, а не private int[][] table,Вы можете легко это исправить, хотя, присваивая возвращаемое значение из метода table переменной table (путая, что переменная и метод имеют одно и то же имя, вы также можете изменить это).