¿Qué algoritmo usar para obtener la coincidencia de cadena más larga en dos grandes matrices?

El problema es fácil de explicar: tenemos dos grandes matrices (valores enteros de 32 bits) y tenemos que encontrar todas las secuencias comunes por encima de un número dado de posición consecutiva (n).¿Qué algoritmo usar para obtener la coincidencia de cadena más larga en dos grandes matrices?

Por ejemplo, si n = 3 y matrices para comparar son:

a = [1, 3, 5, 7, 3, 2, 7, 4, 6, 7, 2, 1, 0, 4, 6] 
b = [2, 5, 7, 3, 2, 3, 4, 5, 6, 3, 2, 7, 4, 6, 0]

El algoritmh debería volver, dos matrices:

r0 = [5, 7, 3, 2] 
r1 = [3, 2, 7, 4, 6]

(o mejor, sus posiciones relativas a primera matriz y la cantidad de bytes consecutivos coincidentes).

Creo que un buen punto para comenzar es el Longest Common Substring Algorithm, pero quizás alguien conozca un algoritmo que se adapte mejor o más exactamente a mi problema.

Fuente

2011-07-17 Ivan

Creo que esto pertenece a [Math.stackexchange] (http://math.stackexchange.com/) – genesis

Este es un problema de investigación abierto, a menudo estudiado en el contexto de la coincidencia/alineación de secuencias de ADN. Es posible que tenga un poco de suerte investigando cómo la gente está haciendo esto con el ADN, o incluso encontrar algunas bibliotecas disponibles. –

@Mark: ¿Cómo es este un problema de investigación abierto? –

creo que el algoritmo para encontrar LCS usando árbol de sufijos es un ajuste perfecto. Construyes el árbol de sufijos de la misma manera, pero en la fase final, no estás buscando el nodo más profundo que tenga descendientes para ambas cadenas. Está buscando todos los nodos con una profundidad de más de n que tienen descendientes para ambas cadenas.

Fuente

2011-07-17 13:43:07 svick

Esta es la respuesta. –

-1

Si he entendido bien y N es el tamaño mínimo de una secuencia, entonces I'de usar una variación en el algoritmo de búsqueda de Boyer-Moor (http://en.wikipedia.org/wiki/Boyer_moore)

Fuente

2011-07-17 12:29:43 sternr

¿Pero el algoritmo BM no es para búsqueda de cadenas? Mi problema es encontrar todas las subcadenas entre dos cadenas grandes – Ivan

una cadena es inherentemente una secuencia de dígitos de un dominio por lo que básicamente no importa. Puede simplemente configurar la subcadena para buscar como cualquier secuencia de array/tamaño posible (desde la posición i a i + n, desde i + 1 a i + 1 + n ...) y hacer BM. (Si existe una secuencia idéntica más grande, encontrará la secuencia inicial n-size y podría continuar probando un sufijo más grande) – sternr

no, BM se usa para buscar una subcadena dentro de una cadena. – woliveirajr

Creo que los algoritmos en la página de wikipedia a la que hace referencia hacen casi exactamente lo que usted desea. Solo necesita modificarlos para mantener todas las respuestas en un cierto tamaño en lugar de solo mantener la respuesta más larga. Por ejemplo, la solución de programación dinámica en esa página podría modificarse de la siguiente manera:

function LCSubstr(S[1..m], T[1..n], min_size) 
    L := array(1..m, 1..n) 
    ret := {} 
    for i := 1..m 
     for j := 1..n 
      if S[i] = T[j] 
       if i = 1 or j = 1 
        L[i,j] := 1 
       else 
        L[i,j] := L[i-1,j-1] + 1 
       if L[i,j] >= min_size 
        ret := ret ∪ {S[i-z+1..z]} 
    return

Como está escrito esto incluirá prefijos, así como partidos más largos. Esos datos se pueden filtrar rastreando qué cadena se encontró en L y quitando un prefijo del conjunto de resultados cuando descubrimos que tiene una extensión.

Fuente

2011-07-17 13:49:49 jacobm

+1, pero quisiera enfatizar que realmente quiere la solución de árbol de sufijo generalizado O (m + n) en lugar de la solución O (mn) DP si m y n son grandes, como OP dice que son. –

¿Qué algoritmo usar para obtener la coincidencia de cadena más larga en dos grandes matrices?

Respuesta

Cuestiones relacionadas