Java中Levenshtein算法的问题

string algorithm java

2022-09-05 00:31:47

我想使用Levenshtein算法来完成以下任务：如果我网站上的用户搜索某些值（他在输入中输入字符），我想立即使用AJAX检查建议，就像Google Instant一样。

我的印象是，Levenshtein算法对于这样的任务来说太慢了。为了检查它的行为，我首先在Java中实现它，在每次递归调用该方法时打印出两个s。String

public class Levenshtein {
    public static void main(String[] arg){
        String a = "Hallo Zusammen";
        String b = "jfdss Zusammen";

        int res = levenshtein(a, b);

        System.out.println(res);
    }

    public static int levenshtein(String s, String t){
        int len_s = s.length();
        int len_t = t.length();
        int cost = 0;

        System.out.println("s: " + s + ", t: " + t);

        if(len_s>0 && len_t>0){
            if(s.charAt(0) != t.charAt(0)) cost = 1;
        }

        if(len_s == 0){
            return len_t;
        }else{
            if(len_t == 0){
                return len_s;
            }else{
                String news = s.substring(0, s.length()-1);
                String newt = t.substring(0, t.length()-1);
                return min(levenshtein(news, t) + 1,
                            levenshtein(s, newt) + 1,
                            levenshtein(news, newt) + cost);
            }
        }
    }

    public static int min(int a, int b, int c) {
          return Math.min(Math.min(a, b), c);
    }
}

但是，这里有一些要点：

支票是我添加的，因为我得到了一个具有以上测试值的。if(len_s>0 && len_t>0)StringIndexOutOfBoundsException
有了上面的测试值，算法似乎无限计算

是否可以对算法进行优化以使其为我工作，或者我应该使用完全不同的算法来完成所需的任务？

答案 1

1）关于Levenshtein距离算法改进的几句话

Levenshteins distance的递归实现具有指数级复杂性。

我建议您使用记忆技术并在没有递归的情况下实现Levenshtein距离，并将复杂性降低到（需要内存）O(N^2)O(N^2)

public static int levenshteinDistance( String s1, String s2 ) {
    return dist( s1.toCharArray(), s2.toCharArray() );
}

public static int dist( char[] s1, char[] s2 ) {

    // distance matrix - to memoize distances between substrings
    // needed to avoid recursion
    int[][] d = new int[ s1.length + 1 ][ s2.length + 1 ];

    // d[i][j] - would contain distance between such substrings:
    // s1.subString(0, i) and s2.subString(0, j)

    for( int i = 0; i < s1.length + 1; i++ ) {
        d[ i ][ 0 ] = i;
    }

    for(int j = 0; j < s2.length + 1; j++) {
        d[ 0 ][ j ] = j;
    }

    for( int i = 1; i < s1.length + 1; i++ ) {
        for( int j = 1; j < s2.length + 1; j++ ) {
            int d1 = d[ i - 1 ][ j ] + 1;
            int d2 = d[ i ][ j - 1 ] + 1;
            int d3 = d[ i - 1 ][ j - 1 ];
            if ( s1[ i - 1 ] != s2[ j - 1 ] ) {
                d3 += 1;
            }
            d[ i ][ j ] = Math.min( Math.min( d1, d2 ), d3 );
        }
    }
    return d[ s1.length ][ s2.length ];
}

或者，更好的是 - 您可能会注意到，对于距离矩阵中的每个单元格 - 您只需要有关前一行的信息，因此您可以将内存需求减少到O（N）：

public static int dist( char[] s1, char[] s2 ) {

    // memoize only previous line of distance matrix     
    int[] prev = new int[ s2.length + 1 ];

    for( int j = 0; j < s2.length + 1; j++ ) {
        prev[ j ] = j;
    }

    for( int i = 1; i < s1.length + 1; i++ ) {

        // calculate current line of distance matrix     
        int[] curr = new int[ s2.length + 1 ];
        curr[0] = i;

        for( int j = 1; j < s2.length + 1; j++ ) {
            int d1 = prev[ j ] + 1;
            int d2 = curr[ j - 1 ] + 1;
            int d3 = prev[ j - 1 ];
            if ( s1[ i - 1 ] != s2[ j - 1 ] ) {
                d3 += 1;
            }
            curr[ j ] = Math.min( Math.min( d1, d2 ), d3 );
        }

        // define current line of distance matrix as previous     
        prev = curr;
    }
    return prev[ s2.length ];
}

2）关于自动完成的几个词

Levenshtein的距离只有在您需要找到完全匹配时才会被推断出来。

但是，如果您的关键字是苹果和用户输入的青苹果呢？Levenshteins 查询和关键字之间的距离会很大（7 点）。而莱文斯坦在苹果和bcdfghk（哑绳）之间的距离也将是7分！

我建议你使用全文搜索引擎（例如Lucene）。诀窍是 - 您必须使用n-gram模型来表示每个关键字。

简而言之：
1）您必须将每个关键字表示为包含n-gram的文档：。

2）将每个关键字转换为n-gram集后 - 您必须在搜索引擎中按n-gram索引每个关键字文档。您必须像这样创建索引：apple -> [ap, pp, pl, le]

...
ap -> apple, map, happy ...
pp -> apple ...
pl -> apple, place ...
...

3）所以你有n-gram索引。当你得到查询时 - 你必须把它分成n-gram。Aftre this - 您将有一组用户查询n-gram。您所需要的只是匹配搜索引擎中的大多数类似文档。在草案方法中，这就足够了。

4）为了更好的建议 - 你可以按Levenshtein距离对搜索引擎的结果进行排名。

附言我建议你翻阅《信息检索导论》一书。

答案 2

您可以使用Apache Commons Lang3的StringUtils.getLevenshteinDistance（）：

找到两个字符串之间的 Levenshtein 距离。

这是将一个字符串更改为另一个字符串所需的更改数，其中每个更改都是单个字符修改（删除，插入或替换）。

Levenshtein距离算法的先前实现来自 http://www.merriampark.com/ld.htm

Chas Emerick用Java编写了一个实现，它避免了OutOfMemoryError，当我的Java实现与非常大的字符串一起使用时可能发生。

Levenshtein距离算法的这种实现来自 http://www.merriampark.com/ldjava.htm
 StringUtils.getLevenshteinDistance(null, *)             = IllegalArgumentException
 StringUtils.getLevenshteinDistance(*, null)             = IllegalArgumentException
 StringUtils.getLevenshteinDistance("","")               = 0
 StringUtils.getLevenshteinDistance("","a")              = 1
 StringUtils.getLevenshteinDistance("aaapppp", "")       = 7
 StringUtils.getLevenshteinDistance("frog", "fog")       = 1
 StringUtils.getLevenshteinDistance("fly", "ant")        = 3
 StringUtils.getLevenshteinDistance("elephant", "hippo") = 7
 StringUtils.getLevenshteinDistance("hippo", "elephant") = 7
 StringUtils.getLevenshteinDistance("hippo", "zzzzzzzz") = 8
 StringUtils.getLevenshteinDistance("hello", "hallo")    = 1