Burrows-Wheeler trasforma la ricerca all'indietro: come trovare l'indice del suffisso?

Question

Burrows-Wheeler trasforma la ricerca all'indietro: come trovare l'indice del suffisso?

#1 da (1 voti)
#2 da (0 voti)

3

L'algoritmo di ricerca all'indietro di BWT è piuttosto semplice se abbiamo solo bisogno della molteplicità di un modello. Tuttavia ho anche bisogno di trovare gli indici del suffisso (cioè posizioni nella stringa di riferimento dove si verifica un pattern). ad es., data stringa banana e modello an , si verifica due volte nelle posizioni 1 e 3.

Potrei calcolare tutti i suffissi e ordinarli, ma ciò aumenterebbe la complessità del tempo in O (nlogn), n essendo la lunghezza della stringa di riferimento. C'è un modo per farlo e mantenere ancora la complessità del tempo O (lunghezza del pattern)?

algorithms complexity strings search string-matching

posta user798275 22.11.2015 - 02:57

fonte

2 risposte

Leggi altre domande sui tag algorithms complexity strings search string-matching

Riduzione del tempo di blocco (applicazione multithread) Posso automatizzare completamente la distribuzione Docker di un CoreCLR .Net su un server CI senza installare Visual Studio?

score 1 · Answer 1

L'algoritmo che stai cercando è l'albero dei suffissi di Ukkonen . Funziona in O (n) .

L'algoritmo che descrivi non è O (n log n) . Ha quel numero di confronti tra stringhe. Nel caso estremo, dove la stringa è "verylong_verylong_", i confronti prendono O (n) , portando il tuo algoritmo alla complessità quadratica.

score 0 · Answer 2

BW Il testo trasformato ha operazioni come un elenco collegato, in cui è possibile attraversare avanti e indietro da ogni voce per recuperare i caratteri adiacenti, ma trovare il loro offset dall'inizio o alla fine richiede attraversare l'intera distanza, o allegare informazioni ad alcuni o tutti i nodi per aiutare a determinare i loro offset.

Qualsiasi schema che funzioni per etichettare gli indici di una lista collegata funzionerà anche per la BWT. Ad esempio, etichettando ogni nodo k-esimo o i nodi di etichettatura di un certo tipo (ad es. Tutte le n nel testo).

Puoi anche etichettare ciascun nodo con un bit da un codice di autofornitura. Un esempio è la codifica Zeckendorf, che non ha mai due 1 bit di fila, ad eccezione dei confini della parola di codice. Dato un nodo casuale, si attraversa avanti o indietro finché non si trova un limite di parola, quindi si legge il limite successivo della parola e si decodificano i bit in mezzo per ottenere l'offset.