Tuesday, November 01, 2011

Lapsus: anatomía de un corrector ortográfico V


La búsqueda binaria

Una de las cosas que hacen inevitablemente los correctores ortográficos es buscar en un diccionario si la palabra que buscan existe. Es claro que hay diferentes técnicas para hacer estas búsquedas, pero sin duda la más eficiente es la llamada "búsqueda binaria".

Por ejemplo, supongamos que tenemos 1000 palabras. Asumamos que la lista está desordenada. ¿Cuántas búsquedas tengo que hacer? A lo más 1000, porque la palabra que buscamos pudiese ser la última de la lista. Ahora bien, supongamos que la misma lista está ordenada alfabéticamente, de la A a la Z. ¿Cuántas búsquedas tengo que hacer? 10, porque lo que hacemos es dividir y conquistar, algo así como el procedimiento común que usamos cuando queremos hallar una palabra en un diccionario físico, real: Lo abrimos a la mitad y vemos si ya nos pasamos (es decir, la palabra que buscamos tiene que estar antes), o bien, nos quedamos cortos. Si nos pasamos, tomamos la primera mitad y volvemos a dividir en dos. Vemos de nuevo si nos pasamos o no. Hacemos este procedimiento hasta ver si  está la palabra que buscamos. (La ilustración al inicio de este artículo muestra este procedimiento al tratar de ver si el número 3 está en una lista ordenada de números).

Tratar de encontrar una palabra usando una búsqueda binaria es lo más eficiente, pues a cada paso se van eliminando la mitad de los elementos por  analizar. Por ejemplo, para el caso de un diccionario con 50 millones de palabras, hay que hacer solamente 26 búsquedas. El orden del algoritmo de la búsqueda binaria es logarítmico, es decir, el numero máximo de elementos que consultas es 2 elevado a la n, donde n es el numero de elementos en total.

En una búsqueda elemento por elemento, el orden es N, porque en el peor de los casos, hay que recorrer todo el arreglo para encontrar el elemento (o para verificar que el elemento no existe). En cambio en la busqueda binaria, si se tienen N elementos, en la primera consulta se selecciona N/(2^1) elementos, en la segunda N/(2^2) elementos (queda entonces un cuarto del arreglo por buscar), en la tercera N/(2^3)... así hasta que N/(2^x) sea cero. En otras palabras 2^x > N. donde x es el numero de búsquedas que se realizaron, y vale aproximadamente log2(N+1), que es de orden logaritmico.

Para ilustrar el asunto, muchas veces le pregunto a mis alumnos ¿cuántas búsquedas tienen que hacer si el diccionario tiene 1000 palabras? Alguno responde bien: unas 10. ¿Y si tienen 2000 palabras? Ya algunos se confunden, pero la respuesta correcta son 11 búsquedas. ¿Y si tengo 4000 palabras? 12 búsquedas serán suficientes. Cada vez que duplico la cifra, tengo que aumentar una búsqueda. No creo que exista en este rubro algoritmo más eficiente, amén que encaja perfectamente para el problema de la corrección ortográfica.

Funciones de Hash

Otra alternativa son las funciones de hash. En este caso hablamos d eun  algoritmo o subrutina que mapea un conjunto grande de datos a uno más pequeño, llamado llaves. En el caso de un diccionario, podríamos tomar cada palabra y aplicarle una función que nos regresara un número entero. Así, podríamos usar ese número como un índice en un arreglo para ver si la palabra que está ahí es la que buscamos.

Veamos cómo funciona esto. Asumamos que nuestra función de hash es la suma de los caracteres de la palabra. Para hacerlo más fácil, asumamos que la A es 1, la B es 2, la C es 3, y así sucesivamente. Tomemos por ejemplo, la palabra ROMA. Aplicando la función de hash obtendremos:


R(18) + O(15) + M(13) + A(1) = 47

Ponemos entonces la palabra ROMA en el casillero 47. Así, si busco esa palabra, le aplico la función de hash y me voy al casillero 47 y listo, solamente hice un acceso al diccionario. 

El problema es cuando tenemos otra palabra como AMOR, anagrama de ROMA. En este caso, la función de hash de AMOR será:
A(1) + M(13)+ O(15) + R(18) = 47
 
de nuevo 47. Aquí tenemos lo que se llama una colisión (dos palabras quieren ocupar el mismo casillero). Cuando esto pasa con demasiada frecuencia, es decir, cuando hay muchas colisiones, es momento de buscar una mejor función de hash, aunque hasta donde entiendo, no hay una función que no tenga colisiones. El asunto es minimizar esto y manipular el problema de las colisiones con una lista ligada, por ejemplo. Modos de tratar las colisiones hay muchos, algunos más eficientes que otros, pero finalmente para resolver esto requerimos de tiempo de procesamiento.

Por ejemplo, para evitar las colisiones con nuestra función de hash original, podríamos agregarle peso a la posición de las letras, así multiplicamos por 1 al valor de la primera letra, 2 al valor de la segunda letra, etc. Y con ello resolveríamos el problema de los anagramas, que siempre dan la misma función de hash. En el caso de ROMA y AMOR tendríamos:

Para ROMA:
R(18)(1)+ O(15)(2) + M(13)(3) + A(1)(4) = 
 
R(18) + O(30) + M(39) + A(4) = 91

para AMOR:
A(1)(1) + M(13)(2)+ O(15)(3) + R(18)(4) = 
 
A(1) + M(26)+ O(45) + R(72) = 144

Así evitamos la colisión de ambos anagramas, pero es probable que nuestra función sea muy elemental igualmente y conlleve colisiones con otras palabras. Por ello mismo me inclino a no usar funciones de hash en este problema y mejor aplicar la búsqueda binaria.

7 comments:

Meithan West said...

Es virtualmente imposible evadir colisiones si el número de elementos que se quiere indexar es grande.

La Wikipedia cita como ejemplo que si se quieren indexar 2500 elementos con una función hash que puede producir 1 millón de hashes diferentes, la probabilidad de que dos elementos obtengan el mismo hash es como de 95%, incluso si se seleccionan completamente al azar.

Así que inevitablemente se tiene que implementar un mecanismo para resolver colisiones.

Morsa said...

Así es, Meithan, por eso no se me ha ocurrido usar ninguna función de hash en este proyecto. Y sé que las colisiones son inevitables.

saludos
Manuel

Armando de la Torre said...

Aun cuando se produzcan colisiones, hay que considerar que en un diccionario básico (digamos 10,000 palabras ), una lista ordenada ( o un árbol binario ) requiere unos 14 accesos para encontrar la palabra.

Incluso si una tabla hash tuviera 5 colisiones debería ser mas rápida que una búsqueda binaria.

Armando de la Torre said...

Hice una prueba con c# usando la estructura Dictionary ( tabla hash ) y List (arreglo dinámico )con 1,000,000 de palabras aleatorias de longitud variable. Sorprendentemente ambos algoritmos tuvieron un tiempo de ejecución similar : 1,000,000 de búsquedas en 3.5 - 3.6 segundos.

La ventaja del arreglo ordenado es que nos permite obtener una lista de palabras cercanas con mas facilidad que con la tabla hash.

Saludos,
Armando

Morsa said...

Armando,

¿qué función de hash usaste?

saludos

Armando de la Torre said...

Manuel,

Utilicé la tabla hash que ya viene en la librería de C#. Voy a ver si haciendo mi propia tabla hash mejora el desempeño.

CarlosTrejo2308 said...

Esta muy interesante, pero solo una observación de ortografía en la funciones de Hash :)

"En este caso hablamos d eun algoritmo o subrutina que mapea..."