Coincidencia de patrones bidimensionales

En informática , la búsqueda de patrones bidimensionales es el problema de localizar ocurrencias de una matriz bidimensional de caracteres ("el patrón") en una matriz bidimensional mayor ("la imagen" o, por analogía con la búsqueda de cadenas , "el texto"). ^{[ 1 ]}

Supongamos que se da un patrón${\displaystyle P[m\times m]}$y un texto${\displaystyle T[n\times n]}$, dónde${\displaystyle m\leq n}$. El enfoque más simple es comparar P con cada submatriz de tamaño${\displaystyle m\times m}$en T. Este algoritmo tiene un tiempo en el peor de los casos de${\displaystyle \Theta ((n-m+1)^{2}m^{2})}$. Normalmente se asume que${\displaystyle m\leq n/2}$, de donde esto se puede escribir como${\displaystyle \Theta (n^{2}m^{2})}$.

Ilustraremos una solución más eficiente (debido esencialmente a Bird 1977 ) mediante un ejemplo. Supongamos que tenemos el siguiente patrón y texto.

 abaab aba baaab P = bab T = abaab aba babab Ababa

Primero construimos un autómata de Aho-Corasick para buscar en un texto lineal ocurrencias de las columnas de P. Como subproducto obtenemos un identificador para cada columna, de modo que dos columnas idénticas obtienen el mismo identificador: en nuestro ejemplo, digamos que la primera (y la tercera) columna se identifican con 0, y la columna del medio con 1.

A continuación, ejecutamos el autómata en las columnas de T, obteniendo (en tiempo lineal) una indicación cada vez que una de las columnas de P aparece en T: en nuestro ejemplo, esta será una matriz C de 3×5 como la siguiente (un "-" marca la ausencia de una coincidencia):

 abaab aba baaab P = bab T = abaaa C = 01--- aba babab 10--1 Ababa 010-0

Ahora utilizamos el algoritmo de Knuth-Morris-Pratt para buscar en las filas de C un patrón idéntico a P, es decir, 010. Cuando lo encontramos, hemos identificado una ocurrencia de P en T. Cabe destacar que no es necesario mantener en memoria todo C ni todo T; T se puede leer fila por fila, y de C solo es necesario mantener una fila en memoria, junto con una fila de estados de los autómatas de Aho-Corasick y KMP.

El tiempo de ejecución de este algoritmo es${\displaystyle O(n^{2})}$si se ignora la dependencia del tamaño del alfabeto, que existe en el algoritmo de Aho-Corasick. Teniendo esto en cuenta, la complejidad es${\displaystyle O(n^{2}\log k)}$donde k es el tamaño del alfabeto.

La dependencia del tamaño del alfabeto fue eliminada por un${\displaystyle O(n^{2})}$algoritmo de Galil y Park . ^{[ 2 ]}

• algoritmo de búsqueda de cadenas

• Apostolico, Alberto (1999). «Capítulo 13: Coincidencia general de patrones». En Atallah (ed.). Manual de algoritmos y teoría de la computación . CRC Press. pp. 13–11 . ISBN  0849326494.
• Bird, Richard S. (1977). "Coincidencia de patrones bidimensionales". Information Processing Letters . 6 (5): 168– 170.
• Galil, Zvi; Park, Kunsoo (1996). "Cálculo de testigo bidimensional independiente del alfabeto". SIAM Journal on Computing . 25 (5): 907– 935.