Algoritmos fonéticos: Soundex
Detalles- Detalles
- Categoría: Programación
- Publicado el Martes, 03 Octubre 2006 04:05
Los algoritmos de búsqueda fonética (o simplemente, algoritmos fonéticos), tienen utilidad en varios campos, pero especialmente en la gestión. Permiten realizar búsquedas por nombres, apellidos, localidades... pero basándose en la pronunciación en lugar de en la grafía. La idea es que una búsqueda, por ejemplo, del apellido "Gómez", también encuentre otros apellidos fonéticamente cercanos, como "Gómis" o "Gómes".
En muchas aplicaciones de gestión es necesario hacer búsquedas en cadenas no muy largas que representan nombres de personas o de lugares. En muchos casos es posible que no conozcamos exactamente cómo se escribe un apellido, pero sí sabemos más o menos cómo se pronuncia. En esos casos, quizá sea de aplicación una búsqueda fonética.
El problema no es sencillo, ya que no siempre existe una correlación entre cómo suena un nombre y cómo se escribe. Además, el problema se agrava si pensamos que cada idioma tiene sus propias reglas de pronunciación.
A lo largo de la historia han surgido varios algoritmos fonéticos, cuya pretensión es clasificar nombres, apellidos y localidades, de tal manera que dada una cadena que contiene, por ejemplo, un apellido, se transforme en un "código" que sea el mismo para esa cadena y para todas las consideradas fonéticamente cercanas.
Expresado con teoría de conjuntos, estos algoritmos dividen el conjunto de todos los posibles apellidos en diversos subconjuntos, agrupando en cada subconjunto apellidos fonéticamente cercanos. Algunos algoritmos, como Soundex, que da título a este artículo crean subconjuntos disjuntos: es decir, un mismo apellido no puede pertenecer simultáneamente a dos o más de estos subconjuntos (con lo que se crea una partición del conjunto de todos los apellidos). Otros algoritmos, como la versión Soundex de Daitch-Mokotoff, crean subconjuntos no disjuntos, lo cual significa que un mismo apellido puede estar simultáneamente en varios de estos conjuntos. Esto mismo se aplicaría a un conjunto de nombres o a uno de localidades, aunque los creadores de algoritmos fonéticos suelen diseñarlos pensando normalmente en apellidos.
Vamos a intentar aproximarnos a los algoritmos fonéticos mediante uno de los más simples: Soundex.
El algoritmo Soundex original data de los años 20 del siglo XX, y fué diseñado y patentado por Robert Russell y Margaret Odell. Su idea era codificar fonéticamente los apellidos en inglés. Dada una cadena que contiene un apellido, se codifica con este algoritmo y se obtiene una cadena que contiene un código que se supone idéntico para los apellidos fonéticamente cercanos. Establecer la línea que separa fonéticamente a un apellido de otro es un tema muy complejo, y que daría lugar a muchas discusiones, pero creo que la pretensión de los algoritmos fonéticos no es crear polémica, sino ayudar en las búsquedas, y cualquier ayuda es buena, aunque no sea perfecta.
Pero vamos ya con Soundex. La entrada de soundex es una cadena con un apellido, y la salida será una letra seguida de varios números. La longitud de la salida nunca excederá los cuatro carácteres. Las vocales y la "H", "W" e "Y" son ignoradas, a menos que el apellido empiece por una de ellas, en cuyo caso, sólo esa primera letra será tenida en cuenta. Las consonantes son substituidas por códigos numéricos del 1 al 6, según el grupo fonético en el que se incluyan.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | función Soundex(entrada: cadena):cadena -Pasar entrada a mayúsculas -Asignar a salida la primera letra de entrada -Para cada carácter c de entrada a partir del segundo hacer: -Si c es una de estas: AEIOUYWH, no hacer nada -Si c es una de estas: BFPV, añadir un "1" a salida -Si c es una de estas: CGJKQSXZ, añadir un "2" a salida -Si c es una de estas: DT, añadir un "3" a salida -Si c es una de estas: L, añadir un "4" a salida -Si c es una de estas: MN, añadir un "5" a salida -Si c es una de estas: R, añadir un "6" a salida -fin de para -Si en salida hay dos o más carácteres adyacentes iguales, sustituirlos por uno solo (Ej: Si salida es A3392221, se debe quedar en A3921) -Devolver los cuatro primeros carácteres de salida fin de función |
Ejemplo: Los apellidos "Lawrence" y "Lorenz" son codificados por este algoritmo como L652.
Si diseñamos una búsqueda de tal manera que al introducir un apellido lo codifiquemos con el algoritmo fonético, y luego comparemos esa codificación con las codificaciones de los apellidos que tenemos almacenados, obtendremos todos los fonéticamente cercanos.
No obstante, como comentabamos antes, Soundex deja mucho que desear, pero al menos sirve para ilustrar la idea básica de estos algoritmos. Por ejemplo, "SMITH" y "SCHMIDT" no son fonéticamente cercanos para Soundex. Lo mismo pasaría con "Lawrence" y "Lorentz" (con una T)... y del español mejor ni hablamos. (Prueba con "Herrero" y "Ferrero", o con "Fernández y Ferrandis".
Pero tampoco pasa nada. Soundex ya tiene muchos años (se creó cuando no existían los ordenadores, así que hay que valorarlo en su justa medida). A lo largo de estos años han surgido muchos otros.
Cabe destacar, por ejemplo, una versión mejorada de Soundex desarrollada por Randy Daitch y Gary Mokotoff, en la que amplían el Soundex original para que funcione mejor con apellidos germánicos o eslavos de origen judío. Tienen en cuenta no sólo el grupo fonético de cada consonante individual, sino su asociación con otras consonantes o vocales e incluso su posición dentro de la palabra. Aun así, no es un algoritmo demasiado bueno para otros idiomas.
Hay muchas más variantes, como por ejemplo, las denominadas Soundex 2 y Phonex, claramente orientadas al francés...
Pero si estás interesad@ en este tipo de algoritmos, debes saber que hay otros más evolucionados y que no son necesariamente un desarrollo de Soundex. Por ejemplo, el algoritmo DOUBLE METAPHONE, presentado por Lawrence Philips contempla la pronunciación en varios idiomas.
Puedes encontrar más información acerca de DOUBLE METAPHONE en éste artículo de la revista Dr. Dobb's y en éste otro de Codeproject.com.
También debes saber que para este tipo de tareas se utiliza a menudo otro concepto que no tiene nada que ver con la fonética: la distancia de Levenshtein. Este es un concepto introducido en los años 60 por Vladimir Levennshtein. Es una función de distancia que se aplica a cadenas de carácteres, y nos da una idea de lo cercanas que están dos cadenas basándose en contar las operaciones de transformación que hay que hacer a una para llegar a la otra. El concepto es bueno, pero los resultados no son los mismos que con los algoritmos fonéticos. Por ejemplo, las palabras "RATA" y "LACA" están muy próximas según la distancia Levenshtein, pero obviamente no tienen nada que ver fonéticamente".
