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.
Tidak ada komentar:
Posting Komentar