我想使用 Levenshtein algorithm对于以下任务:如果我网站上的用户搜索某个值(他在输入中输入字符)，我想立即使用 AJAX 检查建议，就像 Google Instant 一样。

我的印象是 Levenshtein 算法对于这样的任务来说太慢了。为了检查它的行为，我首先用 Java 实现它，在方法的每次递归调用中打印出两个 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) Levenshtein距离算法改进的几句话

Levenshteins 距离的递归实现具有指数复杂度。

我建议您使用内存技术并在没有递归的情况下实现 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 距离。

但是，如果您的关键字是 apple 并且用户输入的是 green apples 怎么办？查询和关键字之间的编辑距离会很大(7 分)。 apple 和 bcdfghk(哑字符串)之间的 Levensteins 距离为 7 点也!

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

简而言之:
1) 您必须将每个关键字表示为包含 n-gram 的文档:apple -> [ap, pp, pl, le]。

2) 在将每个关键字转换为一组 n-gram 之后 - 您必须在搜索引擎中按 n-gram 索引每个关键字文档。您必须像这样创建索引:

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

3) 所以你有 n-gram 索引。 当您收到查询时 - 您必须将其拆分为 n-gram。在此之后 - 您将拥有一组用户的查询 n-gram。而您所需要做的就是从您的搜索引擎中匹配大多数相似的文档。在草案方法中，这就足够了。

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

P.S. 我建议您通读一下这本书 "Introduction to information retrieval" .

关于java - Java中Levenshtein算法的问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13564464/