La aguja en el pajar: cómo buscar un patrón de texto en un documento

20 noviembre, 2014

Una actividad que realizamos con mucha frecuencia es la búsqueda de información dentro de ficheros de texto. Por ejemplo, en un documento en un procesador de texto, una página web en un navegador, un fichero de configuración del sistema operativo, etc.

El objetivo de esta entrada es hablar sobre cómo se realiza esta búsqueda de forma eficiente. Vaaaleee…. pensaréis que esto está chupado y que con un par de bucles todo queda resuelto. Pero si queremos obtener la máxima eficiencia hay que complicarse un poquito la vida. Y, en este problema, la eficiencia puede ser un factor crítico, especialmente si estamos hablando de buscar texto en el fichero de log de una aplicación o una secuencia de nucleótidos en un genoma. Este tipo de ficheros puede ocupar muchísimo espacio (estamos hablando de varios Gb) por lo que estamos buscando una aguja en un pajar: cualquier mejora en la eficiencia por pequeña que sea tendrá un gran impacto en el tiempo de ejecución.

La búsqueda de cadenas tiene gran relevancia en el ámbito de la bioinformática. Fuente: Wikipedia - Licencia: Dominio público
Muchos avances en Bionformática se basan métodos eficientes para buscar y comparar strings. Fuente: Wikipedia – Licencia: Dominio público

El problema que tratamos, llamado string matching en inglés, consiste en encontrar una cadena de caracteres (el patrón) dentro de otra cadena de caracteres (el texto o documento). En ocasiones se asume que el tamaño del patrón (k) es muy pequeño respecto al tamaño del documento (N), es decir, N >> k. Respecto a nuestro objetivo, nos puede interesar buscar la primera aparición del patrón o bien todas las apariciones. Por otro lado, puede interesarnos encontrar apariciones literales del patrón (exact string matching) o bien fragmentos del documento que sean cercanos al patrón, aunque no coincidan exactamente (approximate string matching).

Como os podéis imaginar, la búsqueda exacta de cadenas es más sencilla que la versión aproximada, por lo que en esta entrada nos centraremos en la versión exacta. El algoritmo trivial para resolver este problema es bastante claro:

1. Recorremos el documento carácter a carácter buscando el primer carácter del patrón;

2. Una vez encontrado el primer carácter del patrón en la posición i del documento, comparamos el segundo carácter del patrón con el carácter i+1 del documento y sucesivamente la posición k-del patrón con la i+k-1 del documento;

3. Si todos los caracteres del patrón coinciden con los del documento, hemos hallado un match en la posición i.

4. Si algún carácter del patrón no coincide, volvemos al paso 1 desde la posición i+1 del documento.

5. La condición de final puede ser encontrar el primer match (alcanzar el paso 3) o bien hallarlos todos  (alcanzar la posición N-k-1 del documento en el paso 1).

¿Prueba superada, no? Pues sí, pero podemos hacerlo mucho mejor. Por ejemplo, pensemos qué pasaría sí como patrón usamos la cadena «aaaa» (cuatro a’s consecutivas) y como texto «aaabaaabaaabaaab» (tres a’s consecutivas seguida de b, repetido en múltiples ocasiones). Con estos datos de entrada, el algoritmo llegaría hasta la primera «b» del documento antes darse cuenta que el match no es posible. Después de llegar a esa «b», volvería a la posición 2 dentro del documento y volvería a intentar encontrar el patrón. Es decir, la segunda «a» del documento se comparará dos veces con el patrón, y la tercera «a» tres veces… aun cuando está claro que estamos condenados al fracaso.

Una posible mejora del algoritmo trivial es el algoritmo que se conoce como Knuth-Morris-Pratt: preprocesar el patrón para construir una «tabla de fallo», que  se consulta cuando llegamos a un punto muerto en la comparación del patrón con el documento. En ese caso, la tabla nos indica en qué punto del documento (y del patrón) podemos retomar la búsqueda. Con este método tenemos que realizar un cálculo adicional, construir la tabla de fallo, pero hay que tener en cuenta que preprocesar el patrón (que es pequeño) puede ser beneficioso si nos ahorra tiempo al buscar en el documento (que es muy grande).

El objetivo de la tabla es aprovechar que posiblemente hayamos leído una parte del patrón de entrada donde podamos continuar la comparación. Por ejemplo, con el patrón «abcxyabcwz», si fallamos en la letra «w» sabemos que ya habremos encontrado «abc» en el documento y podemos seguir la comparación desde ese punto. Es decir, nos ahorramos recorrer de nuevo los caracteres «abcxyabc» del documento y retomamos la búsqueda en el cuarto carácter del patrón en lugar de empezar por la «a». Parece una tontería pero nos hemos ahorrado 8 comparaciones de caracteres y en ficheros grandes estas mejoras contribuyen a acelerar la búsqueda.

Ésta es sólo una de la múltiples posibles mejoras del algoritmo trivial: usar autómatas finitos, usar operaciones bit a bit, …. Es todo un mundo donde se han propuesto muchos algoritmos con nombres propios como por ejemplo Boyer-Moore.

En resumen, la búsqueda de patrones en ficheros de texto es un problema fácil de resolver con un algoritmo trivial, pero se complica si se pretende conseguir la máxima eficiencia posible. Por eso, siempre que sea posible es mejor usar algoritmos y herramientas maduros más que reinventar la rueda, p.ej. una librería de un lenguaje de programación o bien alguna herramienta del sistema operativo como grep y equivalentes.

(Visited 181 times, 1 visits today)
Autor / Autora
Robert Clarisó Viladrosa
Comentarios
Daniel S.8 mayo, 2018 a las 10:29 pm

«¿Prueba superada, no? Pues sí, pero podemos hacerlo mucho mejor. Por ejemplo, pensemos qué pasaría sí como patrón usamos la cadena “aaaa” (cuatro a’s consecutivas) y como texto “aaabaaabaaabaaab” (tres a’s consecutivas seguida de b, repetido en múltiples ocasiones). Con estos datos de entrada, el algoritmo llegaría hasta la primera “b” del documento antes darse cuenta que el match no es posible. Después de llegar a esa “b”, volvería a la posición 2 dentro del documento y volvería a intentar encontrar el patrón. Es decir, la segunda “a” del documento se comparará dos veces con el patrón, y la tercera “a” tres veces… aun cuando está claro que estamos condenados al fracaso.»

No necesariamente. Si encontró una «b», la búsqueda se reanuda desde la posición de esa «b» más 1, porque ya se sabe que hasta ahí existe un caracter que no concuerda con la cadena buscada. De lo contrario, sería un disparate. Saludos!

Responder
margui21 agosto, 2019 a las 12:16 pm

informáticos, hacednos la vida más fácil, no nos la compliqueis más de lo que está ya el panorama universitario español que esto es una merienda de negros.

Responder
Deja un comentario