Matrice di suffissi

In informatica, un array di suffissi è un array che specifica i suffissi di una stringa di caratteri in ordine lessicografico .

esempio

Considera la stringa = di lunghezza 11. Poiché la stringa vuota è anche un suffisso valido, aggiungiamo il marcatore di fine alla fine di per poter esprimere la stringa vuota o la fine di . La stringa con le posizioni associate dei suoi caratteri è quindi: ${\ displaystyle S}$abracadabra${\ displaystyle S}$$${\ displaystyle S}$

io	1	2	3	4 °	5	6 °	7 °	8 °	9	10	11	12 °
${\ displaystyle S [i]}$	un	b	r	un	c	un	d	un	b	r	un	$

Questa stringa ha dodici suffissi, che possono essere descritti anche dalla loro posizione iniziale iin : ${\ displaystyle S}$

La stringa vuota è lessicograficamente più piccola di qualsiasi suffisso di . Pertanto, per convenzione , il marcatore di fine è anche lessicograficamente più piccolo di qualsiasi altro carattere nella stringa. Pertanto, tutti i suffissi possono essere ordinati lessicograficamente: ${\ displaystyle S}$$

Rappresentato come risultati di matrice {$, a$, abra$, …}.

Se la stringa originale è nota, ogni suffisso può essere specificato utilizzando l'indice del suo primo carattere per risparmiare spazio. L'array dei suffissi è un array di questi indici in ordine lessicografico. L' abracadabra$array di suffissi per la stringa è quindi = : Il suffisso "a" o "a $" inizia con l'undicesimo carattere, "abra" con l'ottavo carattere e così via. ${\ displaystyle A}${12,11,8,1,4,6,9,2,5,7,10,3}

Il marcatore di fine $è utile quando si combinano più stringhe. Ad esempio, in = è subito chiaro che il testo è composto dalle due stringhe e . Se viene considerata solo una stringa, questo suffisso può essere ignorato: poiché la stringa vuota viene sempre ordinata lessicograficamente prima di tutte le altre, in questo caso nessuna informazione viene persa. ${\ displaystyle S '}$abracadabra$mississippi$abracadabramississippi

Algoritmi

Esistono numerosi algoritmi per costruire un array di suffissi da un dato testo di lunghezza n . I metodi usati per l'ordinamento dei suffissi possono essere approssimativamente suddivisi in tre classi: ordinamento iterativo, ricorsivo e indotto.

Ordinamento parziale iterativo

Il modo più semplice è utilizzare un efficiente algoritmo di ordinamento basato sul confronto che richiede al massimo confronti. Poiché il confronto di due suffissi richiede tempo, il tempo di esecuzione completo di questa procedura è . Algoritmi ulteriormente sviluppati migliorano questo utilizzando i risultati di confronti parziali ed evitando così confronti ridondanti. ${\ displaystyle O (n \ log n)}$${\ displaystyle O (n)}$${\ displaystyle O (n ^ {2} \ log n)}$${\ displaystyle O (n \ log n)}$

A tal fine, viene considerata solo la prima lettera di ciascun suffisso e da questa viene costruito un array di suffissi preliminare, che non ha ancora ordinato i suffissi con la stessa prima lettera tra loro. Tuttavia, i suffissi con lettere iniziali diverse sono già inclusi nell'ordine corretto. In una seconda fase, ogni gruppo di suffissi con la stessa lettera iniziale viene ordinato in modo che siano ordinati correttamente rispetto alle prime due lettere iniziali. Il terzo passaggio ordina tutti i gruppi di suffissi con due prime lettere identiche in modo che siano ordinati correttamente rispetto alle prime quattro, il quarto passaggio in modo che siano ordinati correttamente rispetto alle prime otto e così via. Dopo i passaggi, ogni suffisso viene ordinato in modo completamente corretto e l'array di suffissi è completamente costruito. Ogni passaggio parziale è possibile nel tempo , in modo che risulti il tempo di esecuzione totale .${\ displaystyle \ log _ {2} n}$${\ displaystyle O (n)}$${\ displaystyle O (n \ log n)}$

Questa classe include il classico algoritmo di array di suffissi di Manber e Myers, nonché l'algoritmo di Larsson e Sadakane, che è molto più efficiente nella pratica.

Algoritmi ricorsivi

Questa classe di algoritmi è stata studiata solo dal 2003. I caratteri della stringa sono divisi in due stringhe di caratteri x e y . L'algoritmo viene quindi chiamato ricorsivamente su x . Con la matrice di suffissi di x così calcolata , la matrice di suffissi di y può essere calcolata in modo efficiente ("indotto"). Poiché la divisione in x e y è nota, l'array di suffissi di può essere letto da esso. ${\ displaystyle S}$${\ displaystyle S}$

Scegliendo abilmente x e y , la maggior parte di questi algoritmi ha un tempo di esecuzione di . Tuttavia, poiché in pratica la ricorsione è costosa, non è sempre preferibile.${\ displaystyle O (n)}$

Smistamento indotto

Anche qui, con un array di suffissi già calcolato di una stringa di caratteri x, l'array di suffissi di una stringa di caratteri y viene calcolato (indotto) in modo efficiente. Invece di un metodo di lavoro ricorsivo, la stringa può essere eseguita più volte in direzioni diverse. I caratteri sono classificati in x o y , parzialmente ordinati e ulteriormente ordinati in una fase successiva sulla base di altri risultati parziali. Gli algoritmi in questa classe sono molto diversi. Quasi tutti hanno in comune, tuttavia, il fatto che sono solitamente più veloci degli algoritmi ricorsivi nella pratica, nonostante il runtime del caso peggiore spesso scarso . Inoltre generalmente richiedono molto meno spazio di archiviazione rispetto ad altri algoritmi.${\ displaystyle S}$${\ displaystyle O (n ^ {2} \ log n)}$

L'algoritmo attualmente più veloce in questa classe è l' algoritmo di ordinamento indotto dall'array di suffissi (SAIS in breve) di Nong, Zhang e Chan. Ha solo bisogno di un runtime in . L'algoritmo SAIS si rivela anche molto veloce nella pratica quando vari effetti come B. Gli errori nella cache vengono presi in considerazione.${\ displaystyle O (n)}$

Applicazioni

Una volta costruito, l'array di suffissi può essere utilizzato come indice del testo per eseguire in modo efficiente le operazioni successive. Queste operazioni includono query di ricerca e metodi di compressione.

Query di ricerca esatte (corrispondenza delle stringhe)

Una query di ricerca esatta è costituita da un modello di ricerca che deve essere cercato in un testo . Un passaggio di testo conta solo come un'occorrenza esatta se ogni carattere nel passaggio di testo corrisponde. In questo modo, queste query differiscono dalle query imprecise, in cui è consentito un numero specificato di caratteri divergenti. E 'a esattamente query di ricerca tra le richieste di decisione ( "Venite a prima?"), Numero di richieste ( "Quante volte in fronte?") E le richieste di enumerazione ( "in quali punti è di fronte?"), A seconda di dove le richieste di decisione , se necessario utilizzando le richieste di numero e le richieste di numero possono essere risposte con domande di enumerazione. ${\ displaystyle P}$${\ displaystyle T}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle T}$${\ displaystyle P}$${\ displaystyle T}$${\ displaystyle P}$${\ displaystyle T}$

Per determinare il numero di occorrenze esatte di , è necessario cercare tutti i suffissi che iniziano con nell'array dei suffissi . Poiché l'array di suffissi è ordinato, questi suffissi sono tutti direttamente uno dietro l'altro e formano un blocco. È quindi sufficiente determinare il suffisso lessicograficamente più piccolo e lessicograficamente più grande che iniziano con . Con l'aiuto della ricerca binaria, questi possono essere trovati in, dove nel seguito sta per la lunghezza di e per la lunghezza di . Il numero di occorrenze di è quindi uguale al numero di suffissi in questo blocco. Ciò consente di determinare il numero totale di occorrenze in . Se, inoltre, è richiesta l'output delle posizioni iniziali di tutte le occorrenze esatte, devono essere restituiti i valori dell'array di suffissi nel blocco. Il runtime per questo è , dove sta per il numero di occorrenze di in . ${\ displaystyle P}$${\ displaystyle T}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle O (m \ cdot \ log n)}$${\ displaystyle m}$${\ displaystyle P}$${\ displaystyle n}$${\ displaystyle T}$${\ displaystyle P}$${\ displaystyle O (m \ cdot \ log n)}$${\ displaystyle O (m \ cdot \ log n + \ vert O_ {P} \ vert)}$${\ Displaystyle \ vert O_ {P} \ vert}$${\ displaystyle P}$${\ displaystyle T}$

Metodi raffinati possono ottenere tempi di esecuzione migliori con l'aiuto di strutture di dati aggiuntive. Se è stato determinato il cosiddetto array LCP (prefisso comune più lungo inglese ) ed è stata costruita una struttura dati RMQ adeguata (query minima intervallo inglese) per l'array LCP, è possibile rispondere alle query di decisione e numero in e alle query di enumerazione in . ${\ displaystyle T}$${\ displaystyle O (m)}$${\ displaystyle O (m + \ vert O_ {P} \ vert)}$

Costruzione di un albero dei suffissi

L'array di suffissi di un testo viene spesso utilizzato come passaggio intermedio per costruire l' albero dei suffissi associato in tempo lineare. L'albero dei suffissi può quindi essere utilizzato anche come indice per rispondere alle query di ricerca. ${\ displaystyle T}$

compressione

Vari metodi di compressione possono essere implementati in modo efficiente utilizzando l'array di suffissi. In questo modo, la fattorizzazione della compressione LZ77 può essere implementata in tempo lineare. Inoltre, la trasformazione Burrows-Wheeler del testo può essere calcolata da un array di suffissi esistente con uno sforzo minimo . Per fare ciò, per ogni suffisso della matrice di suffissi, il carattere che si trova esattamente una posizione prima del suffisso nel testo viene determinato e memorizzato in una matrice. L'array risultante è quindi identico alla trasformazione Burrows-Wheeler del testo e può essere utilizzato, ad esempio, per il metodo di compressione bzip2 .

storia

Gli array di suffissi sono stati originariamente sviluppati da Gene Myers e Udi Manber nel 1990 per ridurre il consumo di memoria rispetto agli alberi dei suffissi . Dopo alcuni anni senza risultati significativi, gli array di suffissi sono stati un argomento di ricerca popolare dal 2000 circa. Da allora, è stata sviluppata una varietà di algoritmi di progettazione che hanno numerose proprietà desiderabili.

Gli algoritmi esistono dal 1999 che sono più veloci degli algoritmi del tempo lineare esistenti nella maggior parte delle applicazioni, ma nel peggiore dei casi richiedono un tempo compreso tra . I primi algoritmi di tempo lineare garantito (cioè quelli con runtime nel caso peggiore ) sono noti solo dal 2003. È noto dal 2004 che gli array di suffissi possono risolvere qualsiasi problema con la stessa complessità temporale degli alberi di suffissi . Da allora, al più tardi, gli array di suffissi sono stati il ​​metodo di scelta per quasi tutte le attività di ordinamento dei suffissi e delle stringhe. ${\ displaystyle O (n \ log n)}$${\ displaystyle O (n ^ {2} \ log n)}$${\ displaystyle O (n)}$

Dal 2005, oltre alla progettazione è stata considerata anche l'archiviazione efficiente degli array di suffissi. Oltre agli array di suffissi puri, ora è possibile creare e utilizzare in modo efficiente anche array di suffissi compressi. Sono utili anche per gli indici full-text compressi basati sulla trasformazione Burrows-Wheeler .

letteratura

• Udi Manber, Gene Myers: Suffix array: un nuovo metodo per le ricerche di stringhe in linea . In: SIAM Journal on Computing , Volume 22, Issue 5, October 1993, pp. 935-948.
• Pang Ko, Srinivas Aluru: Costruzione in tempo lineare efficiente in termini di spazio di array di suffissi . In: Combinatorial Pattern Matching (CPM 03) . LNCS 2676, Springer, 2003, pagg. 203-210.
• Juha Kärkkäinen, Peter Sanders: Semplice costruzione lineare di array di suffissi . (PDF; 193 kB) In: Proc. 30th International Colloquium on Automata, Languages ​​and Programming (ICALP '03) . LNCS 2719, Springer, 2003, pagg. 943-955.
• Enno Ohlebusch: Algoritmi bioinformatici: analisi della sequenza, riarrangiamenti del genoma e ricostruzione filogenetica . Oldenbusch, Brema 2013, uni-ulm.de
• Klaus-Bernd Schürmann, Jens Stoye: un algoritmo incompleto per la costruzione veloce di array di suffissi . (PDF; 204 kB) In: Atti di ALENEX , 2005.

link internet

• Esempio di utilizzo di array di suffissi per cercare parole in un dizionario

Prove individuali

1. ↑ ^{a b c} Simon J. Puglisi, WF Smyth, Andrew H. Turpin: A Taxonomy of Suffix Array Construction Algorithms . In: ACM Computing Surveys (CSUR) 39.2 (2007)
2. ↑ ^{a b} U. Manber, GW Myers: Suffix array: un nuovo metodo per le ricerche di stringhe in linea . In Atti del 1 ° Simposio ACM-SIAM sugli algoritmi discreti (1990)
3. ↑ ^{a b} J.N. Larsson, K. Sadakane: ordinamento dei suffissi più veloce . In rappresentante tecnico. LU-CS-TR: 99-214 , Dep. of Computer Science, Lund University, Svezia (1999)
4. ^ Nong Ge, Sen Zhang, Wai Hong Chan: T wo Efficient Algorithms for Linear Time Suffix Array Construction . In: IEEE Transactions on Computers 60 , n. 10 (ottobre 2011), pp. 1471-1484.
5. ↑ Nataliya Timoshevskaya, Wu-chun Feng: SAIS-OPT: Sulla caratterizzazione e ottimizzazione dell'algoritmo SA-IS per la costruzione di array di suffissi . In: 2014 IEEE 4th International Conference on Computational Advances in Bio and Medical Sciences (ICCABS) , 2014.
6. ↑ Enno Ohlebusch: Algoritmi di bioinformatica. Analisi di sequenza, riarrangiamenti del genoma e ricostruzione filogenetica. Oldenbusch Verlag, Brema 2013, ISBN 978-3-00-041316-2 , p. 116.
7. ↑ Enno Ohlebusch: Algoritmi di bioinformatica. Analisi di sequenza, riarrangiamenti genomici e ricostruzione filogenetica. Oldenbusch Verlag, Brema 2013, ISBN 978-3-00-041316-2 , pagg. 120-125.
8. ↑ Enno Ohlebusch: Algoritmi di bioinformatica. Analisi di sequenza, riarrangiamenti genomici e ricostruzione filogenetica. Oldenbusch Verlag, Brema 2013, ISBN 978-3-00-041316-2 , pagg. 117-118.
9. ↑ Enno Ohlebusch: Algoritmi di bioinformatica. Analisi di sequenza, riarrangiamenti genomici e ricostruzione filogenetica. Oldenbusch Verlag, Brema 2013, ISBN 978-3-00-041316-2 , pagg. 113-114.
10. ↑ Enno Ohlebusch: Algoritmi di bioinformatica. Analisi di sequenza, riarrangiamenti del genoma e ricostruzione filogenetica. Oldenbusch Verlag, Brema 2013, ISBN 978-3-00-041316-2 , p. 130.
11. ↑ Juha Kärkkäinen: BWT veloce in poco spazio grazie all'ordinamento dei suffissi a blocchi. In: Informatica teorica. Volume 387, n. 3, 2007, pagina 251 ( PDF; 227KB )
12. ↑ S. Burkhardt, J. Kärkkäinen: Costruzione e controllo di array di suffissi veloci e leggeri . In: Atti del 14th Annual Symposium CPM 2003
13. ↑ P. Ko, S. Aluru: Costruzione tempo lineare efficiente in termini di spazio di array di suffissi . In: Atti del 14th Annual Symposium CPM 2003
14. ↑ Juha Kärkkäinen, Peter Sanders: Semplice costruzione lineare di array di suffissi . (PDF; 193 kB) In_ Proc. 30th International Colloquium on Automata, Languages ​​and Programming (ICALP '03) . LNCS 2719, Springer, 2003, pagg. 943-955
15. ↑ MI Abouelhoda, S. Kurtz, E. Ohlebusch: Sostituzione degli alberi dei suffissi con array di suffissi . In J. Disc. Algor. 2 , 1, 2004, pagg. 53-86
16. ^ R. Grossi, J. Vitter: array di suffissi compressi e alberi di suffissi con applicazioni per l'indicizzazione del testo e la corrispondenza delle stringhe . In SIAM J. Comput. 35.2, 2005, pagg. 378-407
17. ^ G. Navarro, V. Mäkinen: indici full-text compressi . In_ ACM Comput. Serv. , 39, 1.2, 2007