sábado, enero 24, 2009

Distancia Léxica

Hace no mucho un compañero y yo tuvimos que enfrentarnos a una ardua tarea. Teniamos un fichero de texto (.properties) y una tabla en la base de datos que debíamos "enlazar", es decir, buscar en la base de datos las cadenas de texto del fichero y ver cuales casaban. Las que tenían una correspondencia exacta era muy sencillo pero en caso contrario... pufff, la cosa parecia imposible (hablamos de más de 2000 lineas en el fichero y de 10.000 filas en la tabla). Tuvimos que implementar un programa que nos hiciera la tarea más asequible: "el programa Pepe". Una de las heurísticas que implementamos fue la distancia léxica, más concretamente la Distancia de Levenshtein. Esta distancia es el número de carácteres a sustituir para que las dos cadenas a comparar sean iguales. Usándolo de forma proporcional a la longitud media de las cadenas a comparar pudimos descartar las ocasiones en las que, por ejemplo, superaban el 30%. Esto no fué suficiente ya que el orden de las palabras influye muy negativamente en esta heurística, por ejemplo: "Coche rojo" y "rojo coche" tiene una distancia muy grande y sin embargo son la misma frase (semánticamente hablando). Para esto implementamos otra heurística, "made in nosotros", que comparaba, también de forma proporcional, el número de palabras que coincidían, es decir, las palabras que estaba en una y otra frase sin importar la posición. Mezclando estas heurísticas y afinando los porcentajes conseguimos una alta coincidencia que nos ahorró muchas horas de trabajo. A continuación os pongo la implementación para java de la Distancia de Levenshtein:


public class LevenshteinDistance {
private static int minimum(int a, int b, int c) {
if(a<=b && a<=c)
return a;
if(b<=a && b<=c)
return b;
return c;
}

public static int computeLevenshteinDistance(String str1, String str2) {
return computeLevenshteinDistance(str1.toCharArray(), str2.toCharArray());
}

private static int computeLevenshteinDistance(char [] str1, char [] str2) {
int [][]distance = new int[str1.length+1][str2.length+1];

for(int i=0;i<=str1.length;i++)
distance[i][0]=i;

for(int j=0;j<=str2.length;j++)
distance[0][j]=j;

for(int i=1;i<=str1.length;i++)
for(int j=1;j<=str2.length;j++)
distance[i][j]= minimum(distance[i-1][j]+1, distance[i][j-1]+1, distance[i-1][j-1]+((str1[i-1]==str2[j-1])?0:1));

return distance[str1.length][str2.length];
}
}

No hay comentarios:

Publicar un comentario