Algoritmo rápido de coincidencia de cadenas k no coinciden

10

Estoy buscando un algoritmo rápido de coincidencia de cadenas k-incompatibilidad. Dada una cadena de patrón P de longitud m, y una cadena de texto T de longitud n, necesito un algoritmo rápido (tiempo lineal) para encontrar todas las posiciones donde P coincida con una subcadena de T con a lo sumo k desajustes. Esto es diferente del problema de k-diferencias (distancia de edición). Una falta de coincidencia implica que la subcadena y el patrón tienen una letra diferente en la mayoría de las k posiciones. Realmente solo necesito k = 1 (como máximo 1 falta de coincidencia), por lo que un algoritmo rápido para el caso específico de k = 1 también será suficiente. El tamaño del alfabeto es 26 (texto en inglés que no distingue entre mayúsculas y minúsculas), por lo que el requisito de espacio no debería crecer demasiado rápido con el tamaño del alfabeto (por ejemplo, el algoritmo FAAST, creo, ocupa un espacio exponencial en el tamaño del alfabeto, y así es adecuado solo para secuencias de proteínas y genes).

Un enfoque basado en programación dinámica tenderá a ser O (mn) en el peor de los casos, lo que será demasiado lento. Creo que hay modificaciones del algoritmo de Boyer-Moore para esto, pero no puedo tener en mis manos esos documentos. No tengo suscripción para acceder a revistas o publicaciones académicas, por lo que cualquier referencia tendrá que ser de dominio público.

Agradecería mucho cualquier puntero, o referencia a documentos disponibles gratuitamente, o el algoritmo en sí para este problema.

Paresh
fuente
2
Si el patrón es fijo (pero el texto para que coincida varía), podría crear un autómata finito y ejecutar el texto a través de él. También hay algoritmos que usan árboles de sufijos (generalmente buenos si el texto es constante y el patrón varía, pero también aplicable si ambos varían), es posible que pueda encontrar algunas referencias en la web. (Todavía no agrego una respuesta ya que no estoy muy seguro de los algoritmos basados ​​en el árbol de sufijos, si alguien lo sabe, no dude en ignorar este comentario).
Aryabhata
@Aryabhata ¡Gracias! Tanto el patrón como el texto cambian. En ese contexto, construir un autómata finito sería demasiado costoso, especialmente cuando se incluye el alcance para 1 falta de coincidencia. En cuanto a los árboles de sufijos / matrices de sufijos, nunca los he usado, y sé poco sobre ellos, pero tenía la impresión de que son lentos de construir y eficientes principalmente para la coincidencia exacta. Pero exploraré esta opción más a fondo. ¡Cualquier puntero en esta dirección, o en cualquier otra dirección sería muy útil!
Paresh
1
No, los árboles de sufijos también se pueden usar para coincidencias aproximadas. Al menos la wiki dice que sí: en.wikipedia.org/wiki/Suffix_tree
Aryabhata

Respuestas:

5

Se pueden utilizar matrices de sufijos para este problema. Contienen las posiciones iniciales de cada sufijo de la cadena ordenada en orden lexicográfico. Aunque pueden construirse ingenuamente en complejidad , existen métodos para construirlos en complejidad Θ ( n ) . Ver por ejemplo esto y esto . Llamemos a este sufijo array SA.O(nlogn)Θ(n)

Una vez que se ha construido la matriz de sufijos, necesitamos construir una matriz de prefijo común más largo (LCP) para la matriz de sufijos. La matriz LCP almacena la longitud del prefijo común más largo entre dos prefijos consecutivos en la matriz de sufijos (sufijos lexicográficos consecutivos). Por lo tanto, LCP [i] contiene la longitud del prefijo común más largo entre SA [i] y SA [i + 1]. Esta matriz también se puede construir en tiempo lineal: vea aquí , aquí y aquí para algunas buenas referencias.

Ahora, para calcular la longitud del prefijo más largo común a cualquiera de los dos sufijos en el árbol de sufijos (en lugar de sufijos consecutivos), necesitamos usar alguna estructura de datos RMQ . Se ha mostrado en las referencias anteriores (y se puede ver fácilmente si la matriz se visualiza como un árbol de sufijos), que la longitud del prefijo común más largo entre dos sufijos que tienen posiciones y v ( u < v ) en la matriz de sufijos , se puede obtener como m i n u < = k < = v - 1 L C P [ k ]uvu<vminu<=k<=v1LCP[k]. Un buen RMQ puede preprocesar la matriz en el tiempo O ( n ) u O ( n log n ) y responder a las consultas de la forma L C P [ u , v ] en el tiempo O ( 1 ) . Vea aquí un breve algoritmo RMQ, y aquí un buen tutorial sobre RMQ y la relación (y reducciones) entre LCA y RMQ. Esto tiene otro buen enfoque alternativo.LCPAGSO(norte)O(norteIniciar sesiónnorte)LCPAGS[tu,v]O(1)

Con esta información, construimos la matriz de sufijos y las matrices asociadas (como se describió anteriormente) para la concatenación de las dos cadenas con un delimitador en el medio (como T # P, donde '#' no aparece en ninguna de las cadenas). Entonces, podemos realizar k coincidencia de cadenas de desajuste utilizando el método "canguro". Esto y esto explican el método canguro en el contexto de los árboles de sufijos, pero también se pueden aplicar directamente a las matrices de sufijos. Para cada índice del texto T , encuentre el L C P del sufijo de T que comienza en i y el sufijo de PyoTLCPAGSTyoPAGScomenzando en 0. Esto proporciona la ubicación después de la cual se produce la primera falta de coincidencia al hacer coincidir con T [ i ] . Deje que esta longitud sea l 0 . Omita el carácter no coincidente en T y P e intente hacer coincidir las cadenas restantes. Es decir, nuevamente encuentre el L C P de T [ i + l 0 + 1 ] y P [ l 0 + 1 ] . Repita esto hasta obtener k discrepancias, o cualquiera de las cadenas termina. CadaPAGST[yo]l0 0TPAGSLCPAGST[yo+l0 0+1]PAGS[l0 0+1]k es O ( 1 ) . Hay O ( k ) L C P 's para cada índice i de T , lo que da una complejidad total de O ( n k ) .LCPAGSO(1)O(k) LCPAGSyoTO(nortek)

Utilicé un RMQ más fácil de implementar que daba una complejidad total de u O ( n k + n log nO(nortek+(norte+metro)Iniciar sesión(norte+metro)) si m = O ( n ) , pero también se puede hacer en O ( n k ) como se describió anteriormente. Puede haber otros métodos directos para este problema, pero este es un enfoque poderoso y genérico que se puede aplicar a muchos problemas similares.O(nortek+norteIniciar sesiónnorte)metro=O(norte)O(nortek)

Paresh
fuente
¡Excelente! Tengo algo de lectura en mi lista TODO ahora :-)
Aryabhata
El enlace siam.org en el segundo párrafo está roto, pero el documento enlazado se puede encontrar aquí epubs.siam.org/doi/pdf/10.1137/1.9781611972917.3
leecbaker
4

A continuación se muestra un algoritmo esperado de (que se puede extender a otros k , lo que lo haceO(n+m)k ). (Sin embargo, no he hecho los cálculos para demostrar que es así).O(nortek+metro)

La idea es similar al algoritmo de hash rodante Rabin-Karp para coincidencias exactas de subcadenas.

La idea es separar cada cadena de longitud en bloques de 2 k de m / 2 kmetro2kmetro/ /2k tamaño cada uno y calcular el hash de laminación para cada bloque (dando valores hash) y comparar estas 2 k valores hash contra el uno del patrón.2k2k

Permitimos a lo sumo desajustes en esos valores.k

Si se producen más de desajustes, rechazamos y seguimos adelante. De lo contrario, intentamos confirmar una coincidencia aproximada.k

Espero (advertencia: no lo he intentado yo mismo) esto probablemente será más rápido en la práctica, y quizás más fácil de codificar / mantener, que usar un enfoque basado en un árbol de sufijos.

Aryabhata
fuente
Solo necesito una aclaración. Por "... separe cada cadena de longitud m en bloques de 2k de tamaño m / 2k cada ...", quiere decir que separa cada subcadena de longitud m en T (de longitud n) en bloques de 2k. Y este hash se puede calcular en O (n) mediante el método de hash rodante. Luego, la cadena del patrón también se dividirá en 2k bloques, y se compararán los hashes correspondientes, dando lugar a que no coincidan casi k bloques. Si es así, podríamos descartar potencialmente todos los casos en que el número de desajustes sea mayor que k. ¿Lo entendí bien?
Paresh
@Paresh: Sí, lo entendiste bien, excepto porque hay hashes, es Ω ( n k ) , en lugar de O ( n ) . kΩ(nortek)O(norte)
Aryabhata
Me gusta este enfoque! Sin embargo, este enfoque es rápido en general, pero se degrada a O (mnk) si el número de coincidencias es alto (O (n) coincide). Teniendo esto en cuenta, mantuve dos hashes rodantes, bajo el supuesto de que ambos no pueden tener una colisión por la misma entrada (no lo hice matemáticamente porque quería ver la velocidad). De esta manera, no tenemos que verificar una coincidencia char-by-char si los dos hashes están de acuerdo. Esto es bastante rápido en general, pero también es lento si el número de coincidencias es grande. Con esto y con la forma en que sugirió, fue lento para partidos grandes.
Paresh
Esto podría hacerse más rápido en el peor de los casos si dividimos el texto en bloques de tamaño en lugar dem/2kbloques. El patrón también se dividirá enmetrometro/ /2k (+1 si no es un cuadrado perfecto) bloques, y comparamos cada uno de los bloques. Esto será más lento que su enfoque si el número de desajustes es pequeño, pero creo que solo debería serO(nkmetroen el peor de los casos (aunque no he comprobado esto correctamente). No he intentado esto, pero primero exploraré los árboles / matrices de sufijos como sugirió. Parecen ofrecer buenos límites. ¡Gracias! O(nortekmetro)
Paresh
@Paresh: No puedes verlo (en el historial de revisiones), pero inicialmente tuve el metrometro/ /2k2kk+1k+CΩ(nortemetro)metrometro/ /2k