11

次のタスクにレーベンシュタイン アルゴリズムを使用したいと考えています。私の Web サイトのユーザーが何らかの値を検索する (入力に文字を入力する) 場合、Google インスタントのように、AJAX を使用して提案を即座に確認したいと考えています。

レーベンシュタイン アルゴリズムは、このようなタスクには遅すぎるという印象があります。その動作を確認するために、最初に Java で実装しString、メソッドの再帰呼び出しごとに 2 つの を出力しました。

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) レーベンシュタイン距離アルゴリズムの改善について一言

レーベンシュタイン距離の再帰的な実装には、指数関数的な複雑さがあります。

メモ化手法を使用し、再帰なしでレーベンシュタイン距離を実装し、複雑さを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) オートコンプリートについて一言

レーベンシュタイン距離は、完全一致を見つける必要がある場合にのみ推奨されます。

しかし、キーワードが でapple、ユーザーが入力した場合はどうでしょうgreen applesか? クエリとキーワードの間のレーベンシュタイン距離が大きくなります ( 7 ポイント)。appleとbcdfghk(ダムストリング)の間のレーベンスタイン距離も7 ポイントになります。 全文検索エンジン( Lucene

など) を使用することをお勧めします。秘訣は、各キーワードを表す ためにn-gramモデルを使用する必要があることです。 簡単に言えば: 1)各キーワードをドキュメントとして表現する必要があり、これには n-gram: が含まれます。 2)


apple -> [ap, pp, pl, le]

各キーワードを一連の n-gram に変換した後、検索エンジンで各キーワード ドキュメントを n-gram でインデックス化する必要があります。次のようにインデックスを作成する必要があります。

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

3)したがって、n-gram インデックスがあります。クエリを取得したら、それを n-grams に分割する必要があります。この後、一連のユーザーが n-gram をクエリするようになります。必要なのは、検索エンジンから最も類似したドキュメントを照合することだけです。ドラフトアプローチではそれで十分です。

4)より良い提案のために - 検索エンジンの結果をレーベンシュタイン距離でランク付けすることができます。

PS 「情報検索入門」という本を一読することをお勧めします。

于 2012-11-26T12:04:16.973 に答える
6

Apache Commons Lang3StringUtils.getLevenshteinDistance()を使用できます。

2 つの弦の間のレーベンシュタイン距離を求めます。

これは、1 つの文字列を別の文字列に変更するために必要な変更の数です。各変更は 1 文字の変更 (削除、挿入、または置換) です。

レーベンシュタイン距離アルゴリズムの以前の実装は、http://www.merriampark.com/ld.htmからのものでした。

Chas Emerick が Java で実装を作成しました。これにより、私の Java 実装が非常に大きな文字列で使用されたときに発生する可能性がある OutOfMemoryError が回避されます。

レーベンシュタイン距離アルゴリズムのこの実装は、 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

O( N ^ 2) の複雑さと[上で説明したように] O(N) に比例するメモリのみを使用します。

このライブラリには、damerauLevenshteinDisance() も含まれています。Damerau-Levenshtein は、文字の転置 (スワップ) を 1 回の編集としてカウントしますが、適切なレーベンシュタインはそれを 2 回の編集としてカウントします。Damerau-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 に答える