A veces en las empresas donde trabajamos o en los clientes existen múltiples aplicaciones que manejan los mismos datos. Podemos poner a modo de ejemplo dos aplicaciones que gestionan datos de clientes o las direcciones de los mismos. Al no tener centralizada la gestión de estos datos, en ocasiones trabajamos con datos sucios. Dichos datos es conveniente estandarizarlos o limpiarlos alguna vez sino queremos que nuestras bases de datos sean un completo caos.
¿Cómo podemos medir lo parecidas que son dos cadenas de de datos? La respuesta correcta es con la distancia de Levenshtein, que fue ideada por el ruso Vladimir Levenshtein en 1965.
La distancia de Levenshtein, que es una generalización de la distancia de Hamming y la distancia de Damerau-Levenshtein, mide lo similares que son dos cadenas de caracteres.
¿Cómo se mide? Pues es un valor numérico que indica el número mínimo de operaciones elementales que hay que realizar para transformar una cadena en otra. Se entiende como una operación elemental la inserción de un carácter, el borrado de un carácter o la sustitución de un carácter por otro.
Por ejemplo, supongamos que tenemos dos cadenas C1 y C2.
- Si C1 = casa y C2 = casa, la D(C1,C2) = 0, porque no hace falta ninguna transformación ya que son iguales.
- Si C1 = cerdo y C2 = lerdo, la D(C1,C2) = 1, puesto que hace falta realizar una sustitución para que sean iguales.
- Si C1 = moto y C2 = motas, la D(C1,C2) = 2, ya que necesitamos una sustitución y una inserción para que las dos palabras sean iguales.
A continuación veremos un ejemplo de la tabla que genera el algoritmo cuando queremos comparar las palabras HONDA y ONDAS.
El algoritmo de tipo bottom-up utiliza una matriz de (m + 1) x (n + 1), siendo m y n la longitud de las cadenas. La primera fila se rellena con los números desde 0 hasta m mientras que la primera columna se rellena con los números del 0 hasta el n. La distancia de cada casilla D(i,j) será el valor mínimo entre sustituir un carácter, añadir un carácter o sustituir un carácter por otro en las cadenas 1..i y 1..j:
D(i,j) = mínimo (D(i-1,j) + 1, D(i,j-1) + 1, D(i-1,j-1) + ((str[i] == str[j])?0:1))
D(i,j) = mínimo(borrar un carácter, insertar un carácter, sustituir un carácter)
En cada casilla (i,j) de la matriz se indica el número de pasos elementales que es necesario realizar para transformar la cadena 1..i en la 1..j.
La implementación del algoritmo en java es la siguiente:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| 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]; }} |
La implementación del algoritmo en otros lenguajes se puede encontrar aquí.
Entre las aplicaciones prácticas de este algoritmo están:
- Sistemas de reconocimiento de voz
- Sistemas para el análisis de ADN
- Sistemas para la detección de plagios
- Correctores ortográficos automatizados
Espero que la explicación os haya servido para entender el algoritmo y sobre todo para qué podéis utilizarlo en vuestro día a día.
Un saludo
No hay comentarios:
Publicar un comentario