Java中Levenshtein算法的问题

Question

我想使用Levenshtein算法执行以下任务:如果我网站上的用户搜索某些值(他在输入中输入字符),我想立即检查AJAX的建议,就像Google Instant一样.

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

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以上测试值.
• 使用上述测试值,算法似乎无限计算

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

Answer 1

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

Levenshteins距离的递归实现具有指数复杂性.

我建议你使用memoization技术并实现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怎么办？查询和关键字之间的Levenshteins距离会很大(7分).和Levensteins之间的距离apple和bcdfghk(哑弦)也是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.Aftre this - 你将有一组用户查询n-gram.而您所需要的只是匹配搜索引擎中的大多数类似文档.在草案方法中就足够了.

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

PS我建议你仔细阅读"信息检索简介"一书.

Answer 2

您可以使用Apache Commons Lang3 的StringUtils.getLevenshteinDistance()：

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

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

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

Chas Emerick 用 Ja​​va 编写了一个实现，它避免了 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