performance - boyer - encontrar subcadenas repetidas largas en una cadena masiva

boyer moore algorithm

Question

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

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

Esta es la razón por la cual construir un trie de sufijo con conteo de datos es demasiado ineficiente en cuanto al espacio como para que funcione para mí. Para citar el árbol Sufijo de Wikipedia :

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 sufijo 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 esos fueron 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 de wikipedia para evitar que las personas los publiquen como la "respuesta": Algoritmos en cadenas y especialmente el problema de subcadena repetida más larga ;-))

Answer 1

¿Este texto contiene saltos 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 bocinazos, como por ejemplo secuencias bioinformáticas de ADN, entonces quieres construir algo así como tu 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 2

¿Puedes resolver tu problema construyendo una matriz de sufijos 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 3

La manera más fácil podría ser simplemente gastar $ 100 por 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

Podrías mirar los árboles de sufijo basados ​​en disco. Encontré esta biblioteca de implementación de árbol Suffix a través de Google, además de varios artículos que podrían ayudar a implementarlo usted mismo.

Answer 5

Podrías resolver esto usando divide y vencerás. Creo que esto debería ser la misma complejidad algorítmica que usar un trie, pero tal vez sea menos eficiente en la implementación

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, necesitaría crear una clase que implementara DiskBackedBuffer de modo que fuera una lista de números, y cuando el búfer alcanzara un cierto tamaño, se escribiría en el disco usando un archivo temporal y se recuperaría del disco cuando se leyera de.

Answer 6

Respondiendo mi propia pregunta:

Dado que un emparejamiento prolongado también es una coincidencia corta, puede intercambiar múltiples pases por RAM buscando primero coincidencias más cortas y luego viendo si puede ''crecer'' estas coincidencias.

El enfoque literal de esto es construir un trie (con recuentos en cada nodo) de todas las secuencias de cierta 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 sugirió usar 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 de la longitud de los datos para mantener los valores hash, puede hacer cosas interesantes, por ejemplo, para ver si una coincidencia es más larga que su paso fijo de datos, puede simplemente comparar las secuencias de hash en lugar de regenerar ellos. Etc.

Answer 7

Solo un pensamiento tardío que se me ocurrió ...

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

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

Answer 8

La forma efectiva de hacerlo es crear un índice de las subcadenas y ordenarlas. Esta es una operación O (n lg n).

La compresión BWT realiza este paso, por lo que es un problema bien entendido y existen implementaciones de clasificación radix y sufijo (claim O (n)) y para hacerlo lo más eficiente posible. Todavía lleva mucho tiempo, quizás varios segundos para textos grandes.

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

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

Answer 9

¿Qué tal un programa simple como este?

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)