11

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

我的印象是 Levenshtein 算法对于这样的任务来说太慢了。String为了检查它的行为，我首先用 Java 实现了它，在方法的每个递归调用中打印出两个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以上测试值。
  • 使用上述测试值，算法似乎可以无限计算

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

4

5 回答 5

28

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怎么办？查询和关键字之间的 Levenshteins 距离会很大（7 分）。apple和bcdfghk（哑弦）之间的莱文斯坦距离也将是7 点！

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

简而言之：
1）您必须将每个关键字表示为文档，其中包含 n-grams: apple -> [ap, pp, pl, le]。

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

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

3）所以你有n-gram索引。当您收到查询时 - 您必须将其拆分为 n-grams。在此之后 - 您将有一组用户查询 n-gram。您所需要的只是匹配搜索引擎中最相似的文档。在草案方法中就足够了。

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

PS我建议你看一下“信息检索简介”一书。

于 2012-11-26T12:04:16.973 回答
6

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

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

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

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

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

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
于 2016-02-15T06:30:04.580 回答
2

有一个开源库 java-util ( https://github.com/jdereg/java-util ) 有一个 StringUtilities.levenshteinDistance(string1, string2) API，它以 O(N^2) 复杂度实现，并且仅使用与 O(N) 成比例的内存 [如上所述]。

该库还包括 damerauLevenshteinDisance() 。Damerau-Levenshtein 将字符转置（交换）计为一次编辑，而适当的 levenshtein 将其计为两次编辑。Damerau-Levenshtein 的缺点是它不像原来的 Levenshtein 那样具有三角等式。

三角等式的精彩描述：

http://richardminerich.com/2012/09/levenshtein-distance-and-the-triangle-inequality/

于 2014-02-24T06:16:55.650 回答
0 
import java.util.Scanner;

public class Algorithmm {
    public static void main(String args[])
    {
        Scanner sc= new Scanner(System.in);
        System.out.println("Enter the correct string ");
        String correct=sc.nextLine();
        System.out.println("Enter the incorrect string ");
        String incorrect=sc.nextLine();
        int i=correct.length(),j=incorrect.length();
        ++i ; ++j;
        int a[][] = new int[i][j];
        int b[] = new int[3];       
        for(int m=0;m<i;m++)
            for(int n=0;n<j;n++)
            {

                        if(m==0 || n==0)
                        {
                          a[0][n]=n;
                          a[m][0]=m;
                        }
                        else
                        {
                            b[0]=a[m-1][n-1]; b[1]=a[m-1][n]; b[2]=a[m][n-1];


                            if ( correct.charAt(m-1) == incorrect.charAt(n-1)  )
                            {
                                a[m][n]=a[m-1][n-1];
                            }

                            else
                            {
                                for(int t=0;t<2;t++)
                                    for(int u=0;u<2-t;u++)
                                        if(b[u]>b[u+1])
                                            b[u]=b[u+1];


                                a[m][n]=b[0]+1;


                            }

                        }

            }


        for(int m=0;m<i;m++)
        {
            for(int n=0;n<j;n++)
                System.out.print( a[m][n] +"  ");  
            System.out.print("\n");                
        }



        System.out.println(" Levenshtein distance :  "+a[i-1][j-1]);

    }

}
于 2013-03-05T05:47:34.383 回答
0 
public class Algorithmm {
    public static void main(String args[])
    {
        Scanner sc= new Scanner(System.in);
        System.out.println("Enter the correct string ");
        String correct=sc.nextLine();
        System.out.println("Enter the incorrect string ");
        String incorrect=sc.nextLine();
        int i=correct.length(),j=incorrect.length();
        ++i ; ++j;
        int a[][] = new int[i][j];
        int b[] = new int[3];       
        for(int m=0;m<i;m++)
            for(int n=0;n<j;n++)
            {               
                        if(m==0 || n==0)
                        {
                           a[0][n]=n;
                           a[m][0]=m;
                        }
                        else
                        {
                            b[0]=a[m-1][n-1]; b[1]=a[m-1][n]; b[2]=a[m][n-1];    
                            if ( correct.charAt(m-1) == incorrect.charAt(n-1)  )                        
                                a[m][n]=a[m-1][n-1];                                                        
                            else
                            {
                       //instead of using the above code for finding the smallest number in       the array 'b' we can simplyfy that code to the following, so that we can reduce the execution time.//

                                if(  (b[0]<=b[1]) && (b[0])<=b[2]  )
                                    a[m][n]=b[0]+1;
                                else if(  (b[1]<=b[0]) && (b[1])<=b[2]  )
                                    a[m][n]=b[1]+1;
                                else
                                    a[m][n]=b[2]+1;    
                            }                            
                        }                
            }               
        for(int m=0;m<i;m++)
        {
            for(int n=0;n<j;n++)
                System.out.print( a[m][n] +"  ");  
            System.out.print("\n");                
        }       
        System.out.println("
Levenshtein distance :
  "+a[i-1][j-1]);        
    }
}
于 2013-03-05T06:11:26.860 回答