Trabajando con árboles de sufijo en python

Question

Soy relativamente nuevo en python y estoy empezando a trabajar con árboles de sufijos. Puedo construirlos, pero me encuentro con un problema de memoria cuando la cadena se agranda. Sé que se pueden usar para trabajar con cadenas de ADN de tamaño 4^10 o 4^12, pero cada vez que trato de implementar un método, termino con un problema de memoria.

Aquí está mi código para generar la cadena y el árbol de sufijos.

import random 

def get_string(length): 
    string="" 
    for i in range(length): 
     string += random.choice("ATGC") 
    return string 

word=get_string(4**4)+"$" 

def suffixtree(string): 
    for i in xrange(len(string)): 
     if tree.has_key(string[i]): 
      tree[string[i]].append([string[i+1:]][0]) 
     else: 
      tree[string[i]]=[string[i+1:]] 
    return tree 

tree={} 
suffixtree(word) 

Cuando llego a 4 ** 8, me encuentro con problemas graves de memoria. Soy bastante nuevo en esto, así que estoy seguro de que me falta algo con el almacenamiento de estas cosas. Cualquier consejo sería muy apreciado.

Como nota: quiero hacer una búsqueda de cadenas para buscar cadenas coincidentes en una cadena muy grande. El tamaño de coincidencia de cadena de búsqueda es 16. Por lo tanto, esto buscaría una cadena de tamaño 16 dentro de una cadena grande, y luego pasar a la siguiente cadena y realizar otra búsqueda. Como haré una gran cantidad de búsquedas, se sugirió un árbol de sufijos.

Muchas gracias

Answer 1

Como ya han dicho otros, la estructura de datos que está creando no es un árbol de sufijos. Sin embargo, la memoria emite debido en gran parte al hecho de que su estructura de datos involucra muchas copias de cadenas explícitas . Una llamada como ésta

string[i+1:] 

crea una copia real (profundidad) de la subcadena a partir de las i+1.

Si aún está interesado en construir su estructura de datos original (cualquiera que sea su uso), una buena solución es usar buffers en lugar de cadenas de copias. Su algoritmo sería el siguiente aspecto:

def suffixtree(string): 
    N = len(string) 
    for i in xrange(N): 
     if tree.has_key(string[i]): 
      tree[string[i]].append(buffer(string,i+1,N)) 
     else: 
      tree[string[i]]=[buffer(string,i+1,N)] 
    return tree 

yo probamos este incrustado en el resto de su código, y confirmó que requiere significativamente menos de 1 GB de memoria principal, incluso en una longitud total de 8^11 caracteres.

Tenga en cuenta que esto probablemente sea relevante incluso si cambia a un árbol de sufijo real. Una implementación correcta del árbol de sufijos no almacenará copias (ni siquiera almacenamientos intermedios) en los bordes del árbol; sin embargo, durante la construcción del árbol, es posible que necesite muchas copias temporales de las cadenas. Usar el tipo buffer para estos es una muy buena idea para evitar poner una carga pesada en el recolector de basura para todas las copias innecesarias de cadenas explícitas.

Answer 2

Esto no se parece a un árbol para mí. Parece que está generando todos los sufijos posibles y almacenándolos en una tabla hash.

Es probable que obtenga un rendimiento de memoria mucho menor si utiliza un árbol real. Sugiero usar una implementación de biblioteca.

Answer 3

Si sus problemas de memoria se encuentran en la creación del árbol de sufijos, ¿está seguro de que necesita uno? Se podía encontrar todos los partidos en una sola cadena como esta:

word=get_string(4**12)+"$" 

def matcher(word, match_string): 
    positions = [-1] 
    while 1: 
     positions.append(word.find(match_string, positions[-1] + 1)) 
     if positions[-1] == -1: 
      return positions[1:-1] 

print matcher(word,'AAAAAAAAAAAA') 
[13331731, 13331732, 13331733] 
print matcher('AACTATAAATTTACCA','AT') 
[4, 8] 

Mi máquina es bastante viejo, y esto llevó 30 segundos para correr, con 4^12 cuerdas. Usé un objetivo de 12 dígitos, por lo que habría algunas coincidencias. Además, esta solución encontrará resultados superpuestos, en caso de haberlos.

Here es un módulo árbol de sufijos puede probar, como esto:

import suffixtree 
stree = suffixtree.SuffixTree(word) 
print stree.find_substring("AAAAAAAAAAAA") 

Unfortunetly, mi máquina es demasiado lento para probar esto correctamente con cadenas largas. Pero, presumiblemente, una vez que se construya el sufijoxtirector, las búsquedas serán muy rápidas, por lo que para grandes cantidades de búsquedas debería ser una buena decisión. Además, find_substring solo devuelve la primera coincidencia (no sé si esto es un problema, estoy seguro de que podrías adaptarlo fácilmente).

Actualización: dividir la cadena en sufijo árboles más pequeños, evitando así problemas de memoria

Así que si usted necesita para hacer 10 millones de búsquedas en 4^12 cadena de longitud, que claramente no quieren esperar a 9,5 años (búsqueda simple estándar, primero sugerí, en mi máquina lenta ...). Sin embargo, aún podemos usar árboles de sufijos (por lo tanto, es mucho más rápido), Y evitar los problemas de memoria. Divide la secuencia grande en fragmentos manejables (que sabemos que la memoria de la máquina puede manejar) y convierte un fragmento en un árbol de sufijos, búscalo 10 millones de veces, luego descarta ese trozo y pasa al siguiente. También debemos recordar buscar la superposición entre cada fragmento.Escribí un código para hacer esto (Se supone que la cadena grande que se buscará, word es un múltiplo de nuestra longitud de cadena máxima manejable, max_length, tendrá que ajustar el código para también verificar el resto al final, si esto es no es el caso):

def split_find(word,search_words,max_length): 
    number_sub_trees = len(word)/max_length 
    matches = {} 
    for i in xrange(0,number_sub_trees): 
     stree = suffixtree.SuffixTree(word[max_length*i:max_length*(i+1)]) 
     for search in search_words: 
      if search not in matches: 
       match = stree.find_substring(search) 
       if match > -1: 
        matches[search] = match + max_length*i,i 
      if i < number_sub_trees: 
       match = word[max_length*(i+1) - len(search):max_length*(i+1) + len(search)].find(search) 
       if match > -1: 
        matches[search] = match + max_length*i,i 
    return matches 

word=get_string(4**12) 
search_words = ['AAAAAAAAAAAAAAAA'] #list of all words to find matches for 
max_length = 4**10 #as large as your machine can cope with (multiple of word) 
print split_find(word,search_words,max_length) 

En este ejemplo I limitar la longitud árbol de sufijos max a la longitud 4^10, que necesita alrededor de 700 MB. Usando este código, para una cadena de 4^12 de longitud, 10 millones de búsquedas deberían tomar alrededor de 13 horas (búsquedas completas, con cero coincidencias, por lo que si hay coincidencias, será más rápido). Sin embargo, como parte de esto, necesitamos construir 100 árboles de sufijos, que tomarán aproximadamente.100 * 41 segundos = 1 hora.

Así que el tiempo total de ejecución es de alrededor de 14 horas, sin problemas de memoria ... Gran mejora en 9.5 años. Tenga en cuenta que estoy ejecutando esto en una CPU de 1.6GHz con 1GB de RAM, ¡así que debería poder hacerlo mucho mejor que esto!

Answer 4

La razón por la que tiene problemas de memoria es porque para la entrada 'banana' está generando {'b': ['anana$'], 'a': ['nana$', 'na$', '$'], 'n': ['ana$', 'a$']}. Esa no es una estructura de árbol. Tiene todos los sufijos posibles de la entrada creada y almacenada en una de las listas. Eso toma O (n^2) espacio de almacenamiento. Además, para que un árbol de sufijos funcione correctamente, desea que los nodos de hoja le den posiciones de índice.

El result you want to get es {'banana$': 0, 'a': {'$': 5, 'na': {'$': 3, 'na$': 1}}, 'na': {'$': 4, 'na$': 2}}. (Esta es una representación optimizada, un enfoque más simple nos limita a etiquetas de un solo carácter.)