Las cadenas son ubicuos y ambiguo. Cuando un canal de comunicación se ha establecido, un ruido inevitable y malentendidos pueden introducir errores en la transferencia de datos textuales.
En un sistema de la empresa, hay muchos lugares donde este tipo de error puede ocurrir. Nombres, direcciones, nombres de empresas, entre otros. Este tipo de error puede hacer que sea práctico para consultar un registro. Imagínese la triste vida de los famosos actores de películas de acción Arnold Schwarzenegger, ¿cuántas veces tuvo que deletrear su nombre para el operador?
Para resolver este problema, algunos algoritmos se han creado para buscar palabras más cerca, y entre ellos se encuentran los algoritmos fonéticos. Un algoritmo utiliza reglas fonéticas para transformar cadenas en fonemas, tratando de unificar con palabras que suenan parecido. Ejemplos de algoritmos:
Sin embargo, todos estos algoritmos sufren los mismos problemas. Las reglas se escriben específicamente para una determinada lengua, y la mayoría de las implementaciones tienen en Inglés como idioma de destino. Esto no es un problema si su sistema es para usuarios de habla inglesa y no está interesado en realizar aplicaciones en varios idiomas ... Debido a que este mundo está cada vez más globalizado, me resulta muy difícil de ser el caso ...
Pero hay otras soluciones? ¡Buenas noticias! Buscando alternativas, me acordé de las palabras a buscar algoritmos de aproximación de la categoría de distancia de edición, especialmente el algoritmo de distancia Levenshtein . Más robusta y fiable, puede ser utilizado por cualquier programador en cualquier lenguaje sin cambio. E incluso con una pequeña ventaja: no sólo devuelve una respuesta booleana, diciendo que fue un éxito o no en la búsqueda, pero un número que indica cuán semejantes son dos palabras, lo que hace posible ordenar un conjunto de candidatos para su distancia entre el piso solicitado. Esta pequeña ventaja puede ser la diferencia entre páginas y páginas de resultados sin valor, o una lista ordenada con los primeros resultados más relevantes.
El algoritmo de la distancia Levenshtein, que lleva el nombre de su creador, el ruso Vladimir Levenshtein , calcula el costo de la transformación de una palabra a otro, suponiendo que algunas operaciones tales como insertar, eliminar o reemplazar un carácter. Puede ser descrito como sigue:
Sea usted mismo y cadenas de caracteres sj i, j enteros tal que 0 <= i <= tamaño (sí) y 0 <= j <= tamaño (j). Es d (sa, sj) función que calcula la distancia de edición entre el mismo y sj.
Una longitud (si) es igual a 0, entonces d (sa, sj) = longitud (SJ). Lo contrario es válido para sj.
Si usted y sj no son cadenas vacías, entonces se puede escribir como si = sj si'c1 = sj'c2 y, si c1 es el último personaje de sí mismo, y c2 es el último carácter de sj. Así son las cosas:
Si c1 = c2, entonces, evidentemente, d (si, sj) = d (si, "SJ").
Si c1! = C2, entonces d (sa, sj) = min (1 + d (bs ', sj'c2), 1 + d (si'c1, sj "), 1 + d (bs', sj") ) = 1 + (mínimo d (bs ', sj'c2), d (si'c1, sj "), d (bs', sj"))
La última línea merece una explicación. Si C1 es diferente de la c2, entonces la distancia de edición entre el mismo y sj es el menor número de operaciones que realizan se elimine a sí mismo C1, C2 o SJ eliminado, creemos que reemplazar o C1 a C2 (o viceversa .)
Como puede ver, esto nos da un algoritmo recursivo hermosa que puede ser escrito en Java, así:
static int levenshtein(String si, String sj) {
return d(si, si.length() - 1, sj, sj.length() - 1);
}
static int d(String si, int i, String sj, int j) {
if (i == -1) {
return j + 1;
}
if (j == -1) {
return i + 1;
}
if (si.charAt(i) == sj.charAt(j)) {
return d(si, i - 1, sj, j - 1);
}
return 1 + min(d(si, i - 1, sj, j), d(si, i, sj, j - 1), d(si, i - 1, sj, j - 1));
}
static private int min(int i1, int i2, int i3) {
return Math.min(Math.min(i1, i2), i3);
}
Apesar de achar o algoritmo recursivo mais fácil de entender e implementar, infelizmente ele é muito ineficiente. Se acompanhamos a execução para duas cadeias quaisquer, vemos que são calculadas solução para as mesmas subcadeias repetidas vezes. Por exemplo, ao calcular a distância entre as palavras "gente" e "gene" (distância 1), vemos a seguinte pilha de execução:
Calculando distância entre gene e gente
Calculando distância entre gen e gent
Calculando distância entre ge e gent
Calculando distância entre g e gent
Calculando distância entre g e gen
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre ge e gen
Calculando distância entre g e gen
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre ge e ge
Calculando distância entre g e g
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre g e gen
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre gen e gen
Calculando distância entre ge e ge
Calculando distância entre g e g
Calculando distância entre ge e gen
Calculando distância entre g e gen
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre ge e ge
Calculando distância entre g e g
Calculando distância entre g e ge
Calculando distância entre g e g
Distancia 1
Relembrando as aulas de algoritmos da faculdade, podemos ver que este algoritmo possue algumas características importantes: substrutura ótima (a solução ótima contêm soluções ótimas para subproblemas), os subproblemas são independentes e o espaço de subproblemas é tão reduzido que o algoritmo recursivo está o tempo todo resolvendo os mesmos problemas. Terreno fértil para o uso de técnicas de programação dinâmica.
Uma das técnicas mais conhecidas é o da memoização. Simplificando, trata-se simplesmente em construir uma tabela com os resultados parciais assim que são calculados, evitando com isso os recalculos desnecessários. Alterando a implementação recursiva anterior utilizando esta técnica, ficaria:
private static int[][] mem;
static int levenshtein(String si, String sj) {
mem = new int[si.length()][sj.length()];
for (int i = 0; i < si.length(); i++) {
for (int j = 0; j < sj.length(); j++) {
mem[i][j] = -1;
}
}
return d(si, si.length() - 1, sj, sj.length() - 1);
}
static int d(String si, int i, String sj, int j) {
if (i == -1) {
return j + 1;
}
if (j == -1) {
return i + 1;
}
if (mem[i][j] > -1) {
return mem[i][j];
}
if (si.charAt(i) == sj.charAt(j)) {
mem[i][j] = d(si, i - 1, sj, j - 1);
return mem[i][j];
}
mem[i][j] = 1 + min(d(si, i - 1, sj, j), d(si, i, sj, j - 1), d(si, i - 1, sj, j - 1));
return mem[i][j];
}
static private int min(int i1, int i2, int i3) {
return Math.min(Math.min(i1, i2), i3);
}
O que nos dá a seguinte pilha de execução:
Calculando distância entre gene e gente
Calculando distância entre gen e gent
Calculando distância entre ge e gent
Calculando distância entre g e gent
Calculando distância entre g e gen
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre ge e gen
Calculando distância entre ge e ge
Calculando distância entre gen e gen
Distancia 1
Bem melhor que o anterior. Mas infelizmente para quem achava que ia ter esta diversão toda com algoritmos, a triste notícia é que existem excelentes implementações em boas bibliotecas gratuitas, como a implementação de alguns algoritmos fonéticos na Apache Commons Codec , e o Levenshtein no Apache Commons Lang . Com certeza serão implementações bem melhores que as minhas... Mas para um código de brinquedo, já está de bom tamanho!
