¿Que algoritmos de normalización es mejor usar para un MPI Levenshtein, Soundex, Needleman-Wunsch o Metaphone?

Considerar un algoritmos de normalización o fonético mejora la performance de las búsquedas y ayuda a detectar posibles errores de tipeo. Es común que no sepamos escribir un nombre, por ejemplo:

• Lopez o Lopes

• Viviana o Biviana o Bibiana

• Nuñez o Nunes

• Jessica o Yésica

En estos ejemplos si solo tenemos en cuenta la búsqueda por caracteres ASCII nos daría que son palabras totalmente distintas, sin embargo suenan igual y que hayan sido escritas distinto se puede deber a un error de tipeo. Esto es mas común de lo que se cree. Para ayudarnos con este tipo de problemas exiten los algoritmos fonéticos.

Hay varios disponibles:

1.  Soundex es tal vez uno de los más conocidos, se basa en qué tan cerca están dos palabras dependiendo de su pronunciación. Uno de los inconvenientes es que Soundex está optimizado para el inglés y no funciona muy bien en español.

2.   Levenshtein  funciona distinto, mide la diferencia entre dos palabras escritas. 

3. Needleman-Wunsch: El algoritmo Needleman-Wunsch es un algoritmo utilizado en bioinformática para alinear secuencias de proteínas o nucleótidos. Fue una de las primeras aplicaciones de programación dinámica para comparar secuencias biológicas. El algoritmo fue desarrollado por Saul B. Needleman y Christian D. Wunsch y publicado en 1970.

4.    Metaphone: Es un algoritmo fonético, publicado por Lawrence Philips en 1990, para indexar palabras por su pronunciación en inglés. [1] Mejora fundamentalmente el algoritmo Soundex mediante el uso de información sobre variaciones e inconsistencias en la ortografía y pronunciación en inglés para producir una codificación más precisa, que hace un mejor trabajo al combinar palabras y nombres que suenan similares. Al igual que con Soundex, las palabras de sonido similar deberían compartir las mismas claves. Metaphone está disponible como operador integrado en varios sistemas. El autor original más tarde produjo una nueva versión del algoritmo, al que llamó Double Metaphone. Contrariamente al algoritmo original cuya aplicación se limita al inglés solamente, esta versión tiene en cuenta las peculiaridades ortográficas de varios otros idiomas. En 2009, Lawrence Philips lanzó una tercera versión, llamada Metaphone 3, que logra una precisión de aproximadamente el 99% para las palabras en inglés, palabras que no están en inglés familiares para los estadounidenses, y los nombres y apellidos que se encuentran comúnmente en los Estados Unidos, que se han desarrollado de acuerdo con según los estándares de ingeniería modernos contra un arnés de prueba de codificaciones correctas preparadas.

Los más usados son los algoritmos de Soundex y Levenshtein, a veces se usan combinaciones de ambos, pero dependiendo de su caso de uso, puede elegir entre Soundex o Levenshtein u otros algoritmos como el algoritmo Needleman-Wunsch o Metaphone.

Veamos en algunas aplicaciones on-lines cómo funcionan los 2 algoritmos más difundidos, hay varias páginas de este tipo para probar estos algoritmos, yo seleccione al azar alguna que funcione para mostrarles lo que quiero explicar.

Levenshtein Distance calculator

https://planetcalc.com/1721/

Esta página nos permite chequear con funciona el algoritmo de Levenshtein. Calcula on line  la distancia de Levenshtein entre dos palabras,

Ejercicio Levenshtein 1 Para ver cómo funciona primero veamos la diferencia entre 2 palabras iguales

Pusimos viviana en source y viviana en target apretamos calculate y nos da que la distancia de diferencia entre esas 2 palabras es 1

Ejercicio Levenshtein  2  Probemos ahora una leve diferencia

Nos sigue dando que la diferencia entre Viviana y Biviana es 1, aca hay algo importante en una búsqueda estándar ASCII acá nos daría que las palabras son distintas sin embargo para Levenshtein  son iguales.

Ejercicio Levenshtein  3 ahora sumemos diferencias el operador no sabe tipear viviana y lo pone las 2 veces con b larga

Ahora el la distancia aumenta un poco pero siguen para Levenshtein siendo palabras casi iguales, sin embargo la diferencia en ASCII es mucho mayor.

Ejercicio Levenshtein  4 ahora sumemos mas diferencias entre las palabras

comparamos Viviana co bibina, Levenshtein las sigue considerando muy parecidas, pero el número aumento.

Ejercicio Levenshtein  5 ahora sumemos más diferencias entre las palabras

pusimos xibinax y Levenshtein nos dice que la diferencia entre ambas aplabras es mayor

Ejercicio Levenshtein  6 ahora  agrandemos las diferencias entre las palabras

Y vemos que el número es mayor, ya son bastante distintas para este algoritmo las palabras

La rutina de distancia comparativa de cadena de caracteres  Levenshtein es sensilla y eficaz y facil de aplicar en cualquier Apps, les paso un ejemplo de código en C#

public int LevenshteinDistance(string s, string t, out double porcentaje)
{
   porcentaje = 0;
 
   // d es una tabla con m+1 renglones y n+1 columnas
   int costo = 0;
   int m = s.Length;
   int n = t.Length;
   int[,] d = new int[m + 1, n + 1]; 

   // Verifica que exista algo que comparar
   if (n == 0) return m;
   if (m == 0) return n;

   // Llena la primera columna y la primera fila.
   for (int i = 0; i <= m; d[i, 0] = i++) ;
   for (int j = 0; j <= n; d[0, j] = j++) ;
   
   
   /// recorre la matriz llenando cada unos de los pesos.
   /// i columnas, j renglones
   for (int i = 1; i <= m; i++)
   {
        // recorre para j
        for (int j = 1; j <= n; j++)
        {       
            /// si son iguales en posiciones equidistantes el peso es 0
            /// de lo contrario el peso suma a uno.
            costo = (s[i - 1] == t[j - 1]) ? 0 : 1;  
            d[i, j] = System.Math.Min(System.Math.Min(d[i - 1, j] + 1,  //Eliminacion
                          d[i, j - 1] + 1),                             //Insercion 
                          d[i - 1, j - 1] + costo);                     //Sustitucion
         }
    }

   /// Calculamos el porcentaje de cambios en la palabra.
    if (s.Length > t.Length)
       porcentaje = ((double)d[m, n] / (double)s.Length);
    else
       porcentaje = ((double)d[m, n] / (double)t.Length); 
    return d[m, n]; 
}

Conclusión del ejercicio de Levenshtein: A medida que las palabras son más diferentes el número de Levenshtein aumenta. Ejemplos de códigos de este algoritmo en el lenguaje que quieran esta lleno en internet.

Ahora probemos cómo funciona el algoritmo de Soundex. Soundex tienen la propiedad de que las palabras pronunciadas de manera similar producen la misma clave de Soundex y, por lo tanto, pueden usarse para simplificar las búsquedas en bases de datos donde se conoce la pronunciación pero no la ortografía. Lo que hace Soundex  es devolvernos una cadena de 4 caracteres de largo, comenzando con una letra, para ver las diferencias fonéticas entre esas palabras comparamos los códigos Soundex.

Para esto vamos a usar la siguiente página

https://www.ics.uci.edu/~dan/genealogy/Miller/javascrp/soundex.htm

Ejercicio Soundex

Pusimos Mandirola y nos devuelve el código Soundex de 4 caracteres M536

Ahora pusimos Bandirola y nos devuelve un código Soundex distinto pero muy parecido al anterior

Ahora puse Xandirola y vemos que Soundex se está copiando de mi la diferencia en su codigo de 4 dígitos es la primer letra que yo tipeo.

Ahora puse una vocal Oandirola y Soundex se sigue copiando de mí, es como que Soundex le da un tratamiento especial al primer carácter, y que ese primer carácter se refleja en el código que me devuelve.

Probemos que pasa con las otras letras de la palabra.

Ahora en lugar de Mandirola puse Mendirola y ¿Que paso?

Para soundex Mandirola y Mendirola tienen el mismo código es decir son fonéticamente iguales
Probemos con Viviana

Viviana y Vibiana tienen tambien el mismo código Soundex sin embargo Biviana devuelve B150 y Viviana V150 es decir que para la primer letra Soundex es un copión de lo que escribimos, es como que le da otro tratamiento, pero fíjense que la segunda parte del código es bien distinta.

Ejemplo de codigo de Soundex en C#
Esta función devolverá el Soundex de 4 caracteres de una cadena dada.

1. public string Soundex(string data)
3. {
4. StringBuilder result = new StringBuilder();
5. if (data != null && data.Length > 0)
6. {
7. string previousCode, currentCode;
8. result.Append(Char.ToUpper(data[0]));
9. previousCode = string.Empty;
10. for (int i = 1; i < data.Length; i++)
11. {
12. currentCode = EncodeChar(data[i]);
13. if (currentCode != previousCode)
14. result.Append(currentCode);
16. if (result.Length == 4) break;
17. if (!currentCode.Equals(string.Empty))
18. previousCode = currentCode;
19. }
20. }
21. if (result.Length < 4)
22. result.Append(new String(‘0’, 4 – result.Length));
23. return result.ToString();
24. }
25. private string EncodeChar(char c)
26. {
27. switch (Char.ToLower(c))
28. {
29. case ‘b’:
30. case ‘f’:
31. case ‘p’:
32. case ‘v’:
33. return “1”;
34. case ‘c’:
35. case ‘g’:
36. case ‘j’:
37. case ‘k’:
38. case ‘q’:
39. case ‘s’:
40. case ‘x’:
41. case ‘z’:
42. return “2”;
43. case ‘d’:
44. case ‘t’:
45. return “3”;
46. case ‘l’:
47. return “4”;
48. case ‘m’:
49. case ‘n’:
50. return “5”;
51. case ‘r’:
52. return “6”;
53. default:
54. return string.Empty;
55. }
56. }
57. The difference function will match the two Soundex strings and return 0 to 4.
58. 0 means Not Matched
59. 4 means Strongly Matched
60. public int Difference(string data1, string data2)
61. {
62. int result = 0;
63. if (data1.Equals(string.Empty) || data2.Equals(string.Empty))
64. return 0;
65. string soundex1 = Soundex(data1);
66. string soundex2 = Soundex(data2);
67. if (soundex1.Equals(soundex2))
68. result = 4;
69. else
70. {
71. if (soundex1[0] == soundex2[0])
72. result = 1;
73. string sub1 = soundex1.Substring(1, 3); //characters 2, 3, 4
74. if (soundex2.IndexOf(sub1) > -1)
75. {
76. result += 3;
77. return result;
78. }
79. string sub2 = soundex1.Substring(2, 2); //characters 3, 4
80. if (soundex2.IndexOf(sub2) > -1)
81. {
82. result += 2;
83. return result;
84. }
85. string sub3 = soundex1.Substring(1, 2); //characters 2, 3
86. if (soundex2.IndexOf(sub3) > -1)
87. {
88. result += 2;
89. return result;
90. }
91. char sub4 = soundex1[1];
92. if (soundex2.IndexOf(sub4) > -1)
93. result++;
94. char sub5 = soundex1[2];
95. if (soundex2.IndexOf(sub5) > -1)
96. result++;
97. char sub6 = soundex1[3];
98. if (soundex2.IndexOf(sub6) > -1)
99. result++;
100. }
101. return result;
102. }

Los invito a jugar con estos algoritmos y a considerarlos en sus aplicaciones, son de gran utilidad para encontrar diferencias de tipeos y errores y para depurar maestros de pacientes. Nos permiten encontrar candidatos en las búsquedas que con los querys convencionales no podríamos encontrar en las bases de datos.

Referencia
https://www.functions-online.com/soundex.html
http://44jaiio.sadio.org.ar/sites/default/files/cais67-77.pdf
https://es.khanacademy.org/math/arithmetic-home/arith-place-value/arith-comparing-multi-digit-numbers/v/comparing-multi-digit-numbers
https://planetcalc.com/1721/
https://scriptun.com/tools/php/soundex
https://www.ics.uci.edu/~dan/genealogy/Miller/javascrp/soundex.htm
https://techno-soft.com/c-implementation-of-sql.html/