Lavorare con gli alberi di suffisso in python

Question

Sono relativamente nuovo a Python e sto iniziando a lavorare con gli alberi di suffisso. Posso costruirli, ma sto incontrando un problema di memoria quando la stringa diventa grande. So che possono essere utilizzati per lavorare con stringhe di DNA di dimensione 4^10 o 4^12, ma ogni volta che cerco di implementare un metodo, finisco con un problema di memoria.

Ecco il mio codice per la generazione della stringa e dell'albero del suffisso.

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) 

Quando mi alzo a circa 4 ** 8, mi imbatto in problemi di memoria gravi. Sono piuttosto nuovo a questo quindi sono sicuro che mi manca qualcosa con la memorizzazione di queste cose. Qualsiasi consiglio sarebbe molto apprezzato.

Come nota: voglio eseguire una ricerca stringa per cercare stringhe corrispondenti in una stringa molto grande. La dimensione della corrispondenza della stringa di ricerca è 16. Quindi, questo cercherebbe una stringa di dimensione 16 all'interno di una stringa grande, quindi passerà alla stringa successiva ed eseguirà un'altra ricerca. Poiché eseguirò un numero molto elevato di ricerche, è stato suggerito un albero di suffisso.

Molte grazie

Answer 1

Come altri hanno già detto, la struttura dei dati si sta costruendo non è un albero suffisso. Tuttavia, i problemi di memoria derivano in gran parte dal fatto che la struttura dei dati coinvolge molte copie di stringa esplicite di . Una chiamata come questo

string[i+1:] 

crea una copia reale (profondità) della sottostringa a partire da i+1.

Se si è ancora interessati alla costruzione della struttura dati originale (qualunque sia il suo utilizzo), una buona soluzione è utilizzare i buffer anziché le stringhe. Il vostro algoritmo sarebbe quindi simile a questa:

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 

Ho provato questo incorporato nel resto del codice, e ha confermato che richiede significativamente meno di 1 GB di memoria principale, anche per una lunghezza totale di 8^11 caratteri.

Si noti che questo sarà probabilmente rilevanti anche se si passa ad un albero suffisso reale. Un'implementazione dell'albero dei suffissi corretta non memorizzerà copie (nemmeno i buffer) nei bordi dell'albero; tuttavia, durante la costruzione degli alberi potresti aver bisogno di molte copie temporanee delle stringhe. Utilizzare il tipo buffer per questi è un'ottima idea per evitare di gravare pesantemente sul garbage collector per tutte le copie di stringa esplicite non necessarie.

Answer 2

Questo non sembra un albero per me. Sembra che stiate generando tutti i suffissi possibili e li archiviamo in una tabella hash.

È probabile che si ottengano prestazioni di memoria molto più ridotte se si utilizza un albero reale. Suggerisco di utilizzare un'implementazione di libreria.

Answer 3

Se i problemi di memoria si trovano nella creazione dell'albero del suffisso, sei sicuro di averne bisogno? Si potrebbe trovare tutte le partite in una singola stringa come questa:

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] 

La mia macchina è piuttosto vecchio, e questo ci sono voluti 30 secondi per l'esecuzione, con 4^12 corde. Ho usato un bersaglio a 12 cifre, quindi ci sarebbero state alcune partite. Anche questa soluzione troverà risultati sovrapposti, se ce ne sono.

Here è un modulo albero suffisso si potrebbe provare, in questo modo:

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

Unfortunetly, la mia macchina è troppo lento per testare il tutto correttamente con stringhe lunghe. Ma presumibilmente una volta che il suffixtree è stato creato, le ricerche saranno molto veloci, quindi per grandi quantità di ricerche dovrebbe essere una buona chiamata. Inoltre find_substring restituisce solo la prima corrispondenza (non so se questo è un problema, sono sicuro che potresti adattarlo facilmente).

Aggiornamento: dividere la stringa in alberi di suffisso più piccoli, evitando così problemi di memoria

Quindi se avete bisogno di fare 10 milioni di ricerche su 4^12 stringa di lunghezza, abbiamo chiaramente non vuole aspettare per 9,5 anni (semplice ricerca standard, prima ho suggerito, sulla mia macchina lenta ...). Tuttavia, possiamo ancora usare gli alberi di suffisso (quindi essere molto più veloci), ed evitare i problemi di memoria. Dividi la grande stringa in blocchi gestibili (che sappiamo che la memoria della macchina può farcela) e trasforma un pezzo in un albero di suffisso, cercalo 10 milioni di volte, poi scarta quel pezzo e passa a quello successivo. Dobbiamo anche ricordare di cercare la sovrapposizione tra ogni blocco.Ho scritto qualche codice per fare questo (Assume la grande stringa da cercare, word è un multiplo della nostra lunghezza massima della stringa gestibile, max_length, dovrete modificare il codice per controllare anche il resto, alla fine, se questo è non è il 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) 

In questo esempio limita la massima lunghezza albero suffisso lunghezza 4^10, che necessita di circa 700 MB. Utilizzando questo codice, per una stringa di lunghezza 4^12, 10 milioni di ricerche dovrebbero richiedere circa 13 ore (ricerche complete, con corrispondenze zero, quindi se ci sono corrispondenze sarà più veloce). Tuttavia, come parte di questo, abbiamo bisogno di costruire 100 suffissi, che richiederanno circa. 00 * 41 secondi = 1 ora.

Quindi il tempo totale per l'esecuzione è di circa 14 ore, senza problemi di memoria ... grande miglioramento su 9,5 anni. Nota che lo sto usando su una CPU da 1.6GHz con 1GB di RAM, quindi dovresti essere in grado di fare meglio di così!

Answer 4

Il motivo per cui si verificano problemi di memoria è che per l'input 'banana' si genera {'b': ['anana$'], 'a': ['nana$', 'na$', '$'], 'n': ['ana$', 'a$']}. Quella non è una struttura ad albero. Hai tutto il suffisso possibile dell'input creato e memorizzato in uno degli elenchi. Ciò richiede O (n^2) spazio di archiviazione. Inoltre, affinché un albero di suffisso funzioni correttamente, si desidera che i nodi foglia forniscano posizioni di indice.

Il result you want to get è {'banana$': 0, 'a': {'$': 5, 'na': {'$': 3, 'na$': 1}}, 'na': {'$': 4, 'na$': 2}}. (Questa è una rappresentazione ottimizzata; un approccio più semplice ci limita alle etichette singolo carattere.)