búsqueda de subcadenas largas repetidas en una cadena masiva

Question

ingenuamente imaginé que podría construir un sufijo trie donde guardo una visita-recuento para cada nodo, y luego los nodos más profundos con recuentos mayores que uno son el conjunto de resultados que estoy buscando para.

Tengo una cadena muy larga (cientos de megabytes). Tengo alrededor de 1 GB de RAM.

Es por eso que construir un sufijo trie con conteo de datos es demasiado ineficiente en cuanto al espacio para que funcione. Para citar Wikipedia's Suffix tree:

el almacenamiento del árbol de sufijo de una cadena generalmente requiere mucho más espacio que el almacenamiento de la cadena.

La gran cantidad de información en cada borde y nodo hace que el árbol de sufijos sea muy costoso, consumiendo de diez a veinte veces el tamaño de la memoria del texto fuente en buenas implementaciones. El conjunto de sufijos reduce este requisito a un factor de cuatro, y los investigadores han seguido encontrando estructuras de indexación más pequeñas.

Y eso fue los comentarios de Wikipedia sobre el árbol, no trie.

¿Cómo puedo encontrar secuencias repetidas largas en una cantidad tan grande de datos, y en un tiempo razonable (por ejemplo, menos de una hora en una máquina de escritorio moderna)?

(Algunos enlaces Wikipedia para evitar la publicación de la gente como la 'respuesta': Algorithms on strings y especialmente Longest repeated substring problem ;-))

Answer 1

La manera más efectiva de hacer esto es crear un índice de las sub-cadenas, y ordenarlos. Esta es una operación O (n lg n).

BWT compresión hace este paso, así que es un problema bien entendido y hay radix y suffix (reivindicación O (n)) implementaciones ordenar y tal para que sea lo más eficiente posible. Todavía lleva mucho tiempo, quizás varios segundos para textos grandes.

Si desea utilizar el código de utilidad, C++ std::stable_sort() realiza mucho mejor que std::sort() de lenguaje natural (y mucho más rápido que C de qsort(), pero por razones diferentes).

Entonces visitar cada elemento para ver la longitud de su subcadena común con sus vecinos es O (n).

Answer 2

¿este texto con separaciones de palabras? Entonces sospecho que desea una variación de palabra clave en contexto: haga una copia de cada línea n veces para n palabras en una línea, dividiendo cada línea en cada palabra; ordenar alfa de todo el asunto; busca repeticiones

Si se trata de una secuencia larga de bocina, como por ejemplo secuencias bioinformáticas de ADN, entonces desea construir algo así como su trie en el disco; crear un registro para cada personaje con una compensación de disco para los siguientes nodos. Echaré un vistazo al Volumen 3 de Knuth, sección 5.4, "clasificación externa".

Answer 3

La manera más fácil podría ser plunk down the $100 para un montón más de RAM. De lo contrario, es probable que tenga que mirar las estructuras respaldadas por disco para mantener su árbol de sufijos.

Answer 4

Puede ver los árboles de sufijo basados ​​en disco. Encontré este Suffix tree implementation library a través de Google, además de un montón de artículos que podrían ayudarlo a implementarlo usted mismo.

Answer 5

¿Puedes resolver tu problema construyendo un suffix array en su lugar? De lo contrario, es probable que necesite usar uno de los árboles de sufijo basados ​​en disco mencionados en las otras respuestas.

Answer 6

Puede resolver esto usando divide y vencerás. Creo que esto debería ser la misma complejidad algorítmica como el uso de un trie, pero tal vez menos eficiente aplicación en cuanto

void LongSubstrings(string data, string prefix, IEnumerable<int> positions) 
{ 
    Dictionary<char, DiskBackedBuffer> buffers = new Dictionary<char, DiskBackedBuffer>(); 
    foreach (int position in positions) 
    { 
     char nextChar = data[position]; 
     buffers[nextChar].Add(position+1); 
    } 

    foreach (char c in buffers.Keys) 
    { 
     if (buffers[c].Count > 1) 
      LongSubstrings(data, prefix + c, buffers[c]); 
     else if (buffers[c].Count == 1) 
      Console.WriteLine("Unique sequence: {0}", prefix + c); 
    } 
} 

void LongSubstrings(string data) 
{ 
    LongSubstrings(data, "", Enumerable.Range(0, data.Length)); 
} 

Después de esto, se tendría que hacer una clase que implementa DiskBackedBuffer tal que era una lista de números, y cuando el búfer alcanzaba un cierto tamaño, se escribía en el disco usando un archivo temporal y se recuperaba del disco cuando se leía.

Answer 7

responder a mi propia pregunta:

Teniendo en cuenta que un partido largo es también un corto partido, usted puede operar múltiples pases para la memoria RAM encontrando primero partidos más cortos y luego ver si se puede 'crecer' estos partidos.

El enfoque literal a esta es la construcción de un trie (con recuentos en cada nodo) de todas las secuencias de algunos de longitud fija en los datos. Luego elimina todos los nodos que no coinciden con sus criterios (por ejemplo, la coincidencia más larga). Luego haga un pase posterior a través de los datos, construyendo el trie más profundo, pero no más amplio. Repita hasta que encuentre la (s) secuencia (s) repetida (s) más larga (s).

Un buen amigo le sugirió utilizar hash. Al mezclar la secuencia de caracteres de longitud fija comenzando en cada personaje, ahora tiene el problema de encontrar valores de hash duplicados (y verificar la duplicación, ya que la mezcla es con pérdida). Si asigna una matriz a la longitud de los datos para mantener los valores hash, puede hacer cosas interesantes, p. Ej. para ver si una coincidencia es más larga que su paso de longitud fija de los datos, puede simplemente comparar las secuencias de hashes en lugar de regenerarlos. Etc.

Answer 8

Sólo un pensamiento tardío de que se me ocurrió ...

Dependiendo de su sistema operativo/entorno. (Por ejemplo, punteros de 64 bits & mmap() disponible.)

Es posible que pueda crear un Suffix-tree muy grande en el disco a través de mmap(), y luego mantener un subconjunto de ese árbol en la caché más frecuentemente accedido memoria.

Answer 9

qué pasa con un programa sencillo como esto:

S = "ABAABBCCAAABBCCM" 

def findRepeat(S): 
    n = len(S) 
    #find the maxim lenth of repeated string first 
    msn = int(floor(n/2)) 
    #start with maximum length 
    for i in range(msn,1,-1): 
     substr = findFixedRepeat(S, i) 
     if substr: 
      return substr 
    print 'No repeated string' 
    return 0 

def findFixedRepeat(str, n): 
    l = len(str) 
    i = 0 
    while ((i + n -1) < l): 
     ss = S[i:i+n] 
     bb = S[i+n:] 
     try: 
      ff = bb.index(ss) 
     except: 
      ff = -1 

     if ff >= 0: 
      return ss; 
     i = i+1 
    return 0 
print findRepeat(S)