时间戳

首页 > 解决方案 > Levenshtein 算法中的缺失值和 NPE

java - Levenshtein 算法中的缺失值和 NPE

问题描述

我需要创建这个类，但我无法让它工作：

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"); }
    }

}

}

主类：

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)

所以在第一个它不计算最后一列，而在第二个它不起作用。

标签： javalevenshtein-distance

解决方案

我相信您的程序中有几个错误，所以我不会全部解决。

所以在第一个它不计算最后一列，...</p>

tableArray每个维度比单词长度大 2 个单元格（在第一个示例中为 6 x 5），但填充表格的循环仅从 0 运行到每个单词的长度（5 x 4）。因此最后一行和最后一列没有被填充。我怀疑您也在表格中填写了错误的值。可能您没有在某处使用正确的索引。您需要解决此问题并让循环运行一次迭代。

......在第二次它只是不起作用。

i填充表格时，在2 和3的迭代中j，当您执行 时Integer.valueOf(tableArray[i - 1][j])，该表格单元格为空，这会导致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 x 6，所以 bpoundary 是 5 – 2 = 3，所以只有单元格 0、1 和 2 被填充，而您希望单元格 3、4 和 5 也被填充。顺便说一句，以下for循环中的边界也是错误的。

设计技巧

private int[][] table在整个班级中只使用一张桌子your 。不要在你的方法中使用本地表。如果您发现在printTable方法中使用字符串表更容易，那没关系，但从类中的表中填充它，而不是重新计算其全部内容。它会简单得多。

当然，这要求类中的表已经被填充（计算）。我相信构造函数中的这条线应该这样做？

    Levenshtein.table(word1, word2);

但是，它并没有这样做，因为该table方法也适用于自己的表，而不是private int[][] table. 但是，您可以通过将table方法的返回值分配给table变量来轻松解决此问题（混淆变量和方法共享相同的名称，您可能也想更改它）。

推荐阅读