coincidencia de patrones n-dimensionales

20

¿Cuáles son algunos resultados conocidos para encontrar una submatriz n-dimensional exacta dentro de una matriz n-dimensional?

En 1D, es solo un problema de coincidencia de cadenas, KMP lo hace en tiempo lineal.

En 2D, este documento muestra que se puede hacer en tiempo lineal con poco espacio extra.

¿Se puede resolver este problema en el peor caso de tiempo lineal para cualquier dimensión fija?

Chao Xu
fuente

Respuestas:

13

Puede resolver el problema en un número fijo de dimensiones extendiendo la solución original de tiempo lineal de Bird desde 1977 http://www.sciencedirect.com/science/article/pii/0020019077900175 (lamentablemente, se necesita una suscripción).

La idea general (en 2D) está en el paso 1 para construir un autómata Aho-Corasick de las filas del patrón 2D y luego alimentar las filas del texto 2D una por una. Luego encontrará todas las posiciones que coinciden con las filas del patrón en el texto. Para terminar, ahora solo necesita hacer una búsqueda en 1D de las (etiquetas de) las filas del patrón en el orden correcto en una columna en la salida del paso 1, usando KMP say. Todo esto lleva tiempo lineal.

Con el mismo método, puede reducir el problema de coincidencia exacta de cualquier dimensión d a un problema de dimensión d-1. De esta manera obtienes una solución de tiempo lineal para cualquier dimensión fija d.

Rafael
fuente
9

Es posible resolverlo en un tiempo lineal casi (hasta el factor polylog) usando técnicas FFT. Puede consultar el documento: http://www.cs.tau.ac.il/~klim/papers/CEPR08.pdf donde utilizamos técnicas FFT para la coincidencia de patrones unidimensionales. Si desea resolver la coincidencia de patrones multidimensionales, solo necesita usar FFT de alta dimensión.

Klim
fuente
Dado que el documento es de 2008, supongo que aún no se conocen algoritmos de tiempo lineal.
Chao Xu
Lo di solo como un ejemplo de técnica que podría usarse para resolver su problema. La ventaja de este enfoque es que también le permite resolver el problema con desajustes y no le importa. Pero en cuanto a la coincidencia exacta de patrones dimensionales existe un tiempo lineal alg. así puede ser conocido por multidimensional.
Klim
1
Creo que el resultado básico en la coincidencia de patrones con comodines es de Fischer y Paterson 1974 y luego se modificó y simplificó continuamente hasta cs.bris.ac.uk/Publications/pub_master.jsp?id=2000602 (disculpas por la auto cita). Sin embargo, puede ser un poco excesivo para el problema que el OP preguntó dado el método de coincidencia exacta más antiguo que menciono a continuación.
Raphael