Archivo

Archive for the ‘SQL’ Category

Realizar búsquedas de palabras fonéticamente similares usando Soundex

septiembre 22, 2010 6 comentarios

Realizar búsquedas es una cosa complicada, y un buen motor de búsquedas requiere redes neuronales, minería de datos y seguramente inteligencia artificial. Dicho eso, uno puede realizar consultas más sencillas sobre una base de datos.

Una de ellas, por supuesto, consiste en utilizar las clásicas consultas SQL usando el operador de igualdad, el operador LIKE, el operador BETWEEN, y otros por el estilo. Por ejemplo, supongamos que tengo una tabla Empleado que contiene tres campos: Nombre, Apellidos y Dirección. Si quiero hacer una búsqueda sobre Nombre, normalmente haría algo así:

select * from Empleado where Nombre like '%Fernando%'

Realizar esta consulta me regresaría todos los empleados cuyo nombre contenga a “Fernando”, por ejemplo, “Fernando Arturo” y “Juan Fernando”. Pero esta consulta oculta muchos problemas. Por ejemplo, supongamos que en lugar de “Fernando”, quiero buscar “Andrés”:

select * from Empleado where Nombre like '%Andrés%'

Por supuesto, esta consulta me regresa todos los de nombre “Andrés”… pero no me regresa los de nombre “Andres”, es decir, sin acento. Peor aún, por ejemplo, si buscamos a alguna “Jimena”, ya que puede haber registros con Gimena y Ximena. Y cuando desarrollamos aplicaciones empresariales, esto es un problema, porque los usuarios suponen que esto no será un impedimento. Y obvio, no querrán modificar toda su base de datos para revisar cuestiones gramaticales.

Siendo este el contexto, me gustaría comentar sobre un algoritmo de búsqueda por sonidos que SQL Server soporta, que ayuda a solucionar lo anterior. Pero para ello, necesitamos una breve historia…

[me reclino en la mecedora mientras enciendo un cigarrillo y agito la copa de coñac]

» Hace mucho tiempo cuando no había bases de datos ni computadoras ni electrónica, en la era oscura, cuando Thor buscaba a Jörmungandr y se podía ver a Freyja, vestida de blanco, pasear por los bosques de Midgard… ejem… bueno… quiero decir, que antes de las computadoras, los bibliotecarios, gente del registro civil y en general cualquier persona que tuviera que ordenar datos y realizar búsquedas se las veían negras para localizar información específica. En principio, un ciudadano iba a buscar, digamos, el acta de nacimiento de su padre, John. Sin embargo, John puede escribirse como John, Jon, Jhon, etcétera, por lo que a veces estas diferencias causaban que el dato en cuestión no se encontrara. Imagínate en idiomas como el español: realizar búsquedas incluye buscar con acentos, sin acentos, con H o si H, con Y o doble L… y un larguísimo etcétera.

» En aquellos días oscuros parecía que no habría forma de obtener la información que uno buscaba… parecía que el Ragnarök estaba cerca… Entonces a alguna mente en los Estados Unidos a inicios de siglo XX se le ocurrió diseñar un algoritmo que basara la búsqueda en similitudes fonéticas en lugar de alfabéticas… y dio como resultado un algoritmo para codificar nombres con la misma pronunciación, llamado Soundex. Este algoritmo se basa en codificar letras de sonidos similares, ignorar otras y al final reducir una palabra a cuatro letras. Dos palabras con sonidos iguales (como John y Jon) regresarán una codificación igual, mientras que si son semejantes (digamos, Fernando y Hernando) regresarán una codificación parecida(usualmente, coincidirán tres de las cuatro letras) pero no iguales.

» Soundex probó ser útil y permitió a la oficina de censos de EE.UU. realizar análisis precisos de los censos hechos entre 1890 y 1920. Probó ser tan útil que sobrevivió a la era oscura y llego a la era del Yggdrasil: ha sido incorporada en los motores de bases de datos modernos. De tal suerte que puedes utilizar el algoritmo Soundex en SQL Server para realizar una búsqueda por sonidos.

[abro los ojos, dejo la colilla del cigarrillo y vacío de un trago el resto del coñac]

Bueno, el punto es que SQL Server tiene una función llamada SOUNDEX que toma una cadena de texto y la codifica usando el algoritmo Soundex. Por ejemplo:

select soundex('casa'), soundex('caza'), soundex('cahsa')
go

regresa el siguiente resultado:

C200 C200 C200

Como casa, caza y cahsa se pronuncian igual, pues se regresa el mismo código. De igual forma:

select soundex('Fernando'), soundex('Hernando')
go

regresa:

F655 H655

Como puedes ver, los códigos son muy similares, pero no exactos. Así, tres de las cuatro letras coinciden, por lo que la aproximación debe ser buena, pero no exacta. Entonces, podemos ver que cuando comparamos dos términos, lo que nos interesa es la diferencia que éstos regresan, en un rango del 1 al 4 (1 si prácticamente no se parecen, 4 si se parecen demasiado). Afortunadamente, SQL Server provee una función llamada DIFFERENCE, que internamente hace uso de SOUNDEX y regresa un número del 1 al 4: en esencia, qué tanto se parecen los términos buscados. En efecto:

select difference('casa', 'caza')

regresa, sin sorpresas, un 4, mientras que

select difference('fernando', 'hernando')

regresa un 3. Así, una forma de realizar búsquedas pudiera ser haciendo uso de DIFFERENCE. Por ejemplo:

select nombre, apellidos, direccion
from empleado
where difference(nomrbe, 'fernando') > 2

Esta consulta te regresaría todos los “fernandos” de la tabla, pero también todos los “hernandos” y los “fehrnandos”.

Nota, sin embargo, que SOUNDEX y DIFFERENCE tienen sus puntos débiles. Después de todo, incluso Thor murió envenenado tras matar a Jörmungandr. Este algoritmo está muy bien para buscar nombres y palabras, pero no para buscar frases. Un soundex entre “En algún lugar de un gran país” y “país” te va a regresar códigos diferentes. De hecho, select difference(‘En algún lugar de un gran país’, ‘país’) te regresa apenas un 2. Así, mi recomendación sería utilizar este tipo de búsquedas sobre campos que contengan un solo nombre: por ejemplo, nombres de personas, apellidos, ciudades, países, etc.

Ah, por cierto. No olvides que el tema del idioma es muy importante, ya que por el asunto de la pronunciación, soundex se comporta de forma diferente en inglés que en español (por ejemplo, en inglés Y y J se pronuncian igual, mientras que en español se pronuncian diferente; análogamente, en español LL y Y son iguales mientras que en inglés son diferentes). Así que asegúrate que el idioma de tu base de datos sea el correcto, si vas a utilizar este algoritmo.

En fin, dicho lo anterior… la idea de este post es darte una alternativa más que puedas utilizar en tu desarrollo. Espero te sirva de algo. Ahí me cuentas cómo te fue.

Categorías:Apunte, SQL, SQL Server Etiquetas: