Problemas com o algoritmo de Levenshtein em Java
quero usar o algoritmo de Levenshtein para a seguinte tarefa: se um utilizador do meu site Procurar por algum valor (ele introduz caracteres numa entrada), quero verificar instantaneamente as sugestões com o AJAX, como faz o Google Instant.
Tenho a impressão de que o algoritmo de Levenshtein é demasiado lento para tal tarefa. Para verificar o seu comportamento, implementei-o pela primeira vez em Java, imprimindo os doisStringem cada chamada recursiva do método.
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);
}
}
No entanto, Aqui estão alguns pontos:
- a verificação
if(len_s>0 && len_t>0)foi adicionada por mim, porque eu estava a receber umStringIndexOutOfBoundsExceptioncom valores de teste acima. - com valores acima dos valores de ensaio, o algoritmo parece calcular infinitamente
Existem optimizações que podem ser feitas no algoritmo para que funcione para mim, ou devo usar uma completamente diferente para realizar a tarefa desejada?
5 answers
Algumas palavras sobre a melhoria do algoritmo de distância Levenshtein
A implementação recursiva da distância de Levenshteins tem complexidade exponencial .
Eu sugiro que você use técnica de memoização e implemente a distância Levenshtein sem recursão, e reduza a complexidade para O(N^2) (necessidades O(N^2) memória)
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) Algumas palavras sobre completar automaticamente
A distância do Levenshtein só é inferida se precisar de encontrar as correspondências exactas.
Mas e se a tua palavra-chave fosse apple e o utilizador dactilografado green apples? A distância entre a consulta e a palavra-chave seria grande (7 pontos). E Levensteins distância entre apple e bcdfghk (string Idiota) seriam também 7 pontos!
Sugiro que use um motor de busca de texto completo (por exemplo Lucene). O truque é ... que tens de usar N-grama modelo para representar cada palavra-chave.
Em poucas palavras:
1) tem de representar cada palavra-chave como documento, que contém n-gramas: apple -> [ap, pp, pl, le].
2) Depois de transformar cada palavra-chave num conjunto de N-gramas-tem de indexar cada palavra-chave-documento por n-gram no seu motor de busca. Você terá que criar um índice como este:
...
ap -> apple, map, happy ...
pp -> apple ...
pl -> apple, place ...
...
3) então tens Índice de n-gram. Quando se recebe uma consulta, tem de-se dividi-la em n-gramas. Aftre isto-você terá um conjunto de Usuários de pesquisa n-gramas. E tudo o que você precisa - é combinar a maioria dos documentos semelhantes do seu motor de busca. No projecto de abordagem seria suficiente.
4) para melhor sugerir-Você pode classificar os resultados do motor de busca por Levenshtein distancia.
Você pode usar Apache Commons Lang3's StringUtils.getLevenshteinDistance():
Encontre a distância Levenshtein entre duas cordas.
Este é o número de alterações necessárias para mudar um texto para outro, onde cada mudança é uma única modificação de caráter (supressão, inserção ou substituição).
A implementação anterior do algoritmo de distância Levenshtein foi de http://www.merriampark.com/ld.htm
Chas Emerick escreveu um implementação em Java, que evita Erro do omemoryerror que pode ocorrer quando a minha implementação Java é usada com cordas muito grandes.
Esta implementação do algoritmo de distância Levenshtein é de 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
Existe uma biblioteca de código aberto, java-util (https://github.com/jdereg/java-util ) que tem uma Stringuitilities.levenshteinDistance(string1, string2) API que é implementado na complexidade O(n^2) e usa memória apenas proporcional a O (N) [Como discutido acima].
Esta biblioteca também inclui damerauLevenshteinDisance (). Damerau-Levenshtein conta a transposição de caracteres (swap) como uma edição, onde como Levenshtein adequado conta-a como duas edições. A desvantagem para Damerau-Levenshtein é que não tem igualdade triangular como o levenshtein original.
Grande representação da igualdade triangular:Http://richardminerich.com/2012/09/levenshtein-distance-and-the-triangle-inequality/
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]);
}
}
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]);
}
}