Arranjo de sufixos

Array de sufixos
Tipe Array
Inventado por Manber & Myers (1990)
Complexidade de tempo
em Notação Grande-O
Média Pior caso
Espaço O ( n ) {\displaystyle {\mathcal {O}}(n)} O ( n ) {\displaystyle {\mathcal {O}}(n)}
Construção O ( n ) {\displaystyle {\mathcal {O}}(n)} O ( n ) {\displaystyle {\mathcal {O}}(n)}

Em ciência da computação, um array de sufixos é um array ordenado de todos os sufixos de uma cadeia de caracteres. É uma estrutura de dados simples, porém poderosa que é usada, dentre outras, em índices de textos inteiros, algoritmos de compressão de dados e dentro do campo da bioinformática.[1]

Arrays de sufixos foram introduzidos por Manber & Myers (1990) como uma alternativa simples e eficiente em termos de espaço a árvore de sufixos. Eles foram descobertos independentemente por Gonnet, Baeza-Yates & Snider (1992) sob o noe array PAT.

Definição

Seja S = s 1 , s 2 , . . . , s n {\displaystyle S=s_{1},s_{2},...,s_{n}} uma cadeia de caracteres e seja S [ i , j ] {\displaystyle S[i,j]} a subcadeia de S {\displaystyle S} que vai de i {\displaystyle i} até j {\displaystyle j} .

O array de sufixos A {\displaystyle A} de S {\displaystyle S} é definido como sendo um array de inteiros que proveem as posições iniciais dos sufixos de S {\displaystyle S} em ordem lexicográfica. Isto significa que uma entrada A [ i ] {\displaystyle A[i]} contem a posição inicial do i {\displaystyle i} -ésimo menor sufixo em S {\displaystyle S} e, da mesma forma, para todo 1 < i ≤ n {\displaystyle 1<i\leq n} : S [ A [ i − 1 ] , n ] < S [ A [ i ] , n ] {\displaystyle S[A[i-1],n]<S[A[i],n]} .

Exemplo

Considere o texto S=banana$ a ser indexado:

i 1 2 3 4 5 6 7
S[i] b a n a n a $

O texto termina com a letra sentinela especial $, que é único e lexicograficamente menor do que qualquer outro caractere. O texto possui os seguintes sufixos:

Suffix i
banana$ 1
anana$ 2
nana$ 3
ana$ 4
na$ 5
a$ 6
$ 7

Estes sufixos podem ser ordenados:

Suffix i
$ 7
a$ 6
ana$ 4
anana$ 2
banana$ 1
na$ 5
nana$ 3

O array de sufixos A contém a posição inicial destes sufixos ordenados:

i 1 2 3 4 5 6 7
A[i] 7 6 4 2 1 5 3

Array completo com os próprios sufixos:

i 1 2 3 4 5 6 7
A[i] 7 6 4 2 1 5 3
1 $ a a a b n n
2 $ n n a a a
3 a a n $ n
4 $ n a a
5 a n $
6 $ a
7 $

Então por exemplo, A[3] contém o valor 4, e por isso, se refere ao sufixo iniciando na posição 4 dentro de S, que é o sufixo ana$.

Notas

Referências

  • Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2004). «Replacing suffix trees with enhanced suffix arrays». Journal of Discrete Algorithms. 2. 53 páginas. doi:10.1016/S1570-8667(03)00065-0 
  • Manber, Udi; Myers, Gene (1990). Suffix arrays: a new method for on-line string searches. First Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 319–327 
  • Manber, Udi; Myers, Gene (1993). «Suffix arrays: a new method for on-line string searches». SIAM Journal on Computing. 22: 935-948. doi:10.1137/0222058 
  • Gonnet, G.H; Baeza-Yates, R.A; Snider, T (1992). «New indices for text: PAT trees and PAT arrays». Information retrieval: data structures and algorithms 
  • Kurtz, S (1999). «Reducing the space requirement of suffix trees». Software-Practice and Experience. 29 (13). 1149 páginas. doi:10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O 
  • Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2002). «Algorithms in Bioinformatics». Lecture Notes in Computer Science. 2452. 449 páginas. ISBN 978-3-540-44211-0. doi:10.1007/3-540-45784-4_35  |capítulo= ignorado (ajuda)
  • Puglisi, Simon J.; Smyth, W. F.; Turpin, Andrew H. (2007). «A taxonomy of suffix array construction algorithms». ACM Computing Surveys. 39 (2). 4 páginas. doi:10.1145/1242471.1242472 
  • Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). «2009 Data Compression Conference». 193 páginas. ISBN 978-0-7695-3592-0. doi:10.1109/DCC.2009.42  |capítulo= ignorado (ajuda)
  • Fischer, Johannes (2011). «Algorithms and Data Structures». Lecture Notes in Computer Science. 6844. 374 páginas. ISBN 978-3-642-22299-3. doi:10.1007/978-3-642-22300-6_32  |capítulo= ignorado (ajuda)
  • Salson, M.; Lecroq, T.; Léonard, M.; Mouchard, L. (2010). «Dynamic extended suffix arrays». Journal of Discrete Algorithms. 8 (2). 241 páginas. doi:10.1016/j.jda.2009.02.007 
  • Burkhardt, Stefan; Kärkkäinen, Juha (2003). «Combinatorial Pattern Matching». Lecture Notes in Computer Science. 2676. 55 páginas. ISBN 978-3-540-40311-1. doi:10.1007/3-540-44888-8_5  |capítulo= ignorado (ajuda)
  • Karp, Richard M.; Miller, Raymond E.; Rosenberg, Arnold L. (1972). «Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72». 125 páginas. doi:10.1145/800152.804905  |capítulo= ignorado (ajuda)
  • Farach, M. (1997). «Proceedings 38th Annual Symposium on Foundations of Computer Science». 137 páginas. ISBN 0-8186-8197-7. doi:10.1109/SFCS.1997.646102  |capítulo= ignorado (ajuda)
  • Kärkkäinen, Juha; Sanders, Peter (2003). «Automata, Languages and Programming». Lecture Notes in Computer Science. 2719. 943 páginas. ISBN 978-3-540-40493-4. doi:10.1007/3-540-45061-0_73  |capítulo= ignorado (ajuda)
  • Dementiev, Roman; Kärkkäinen, Juha; Mehnert, Jens; Sanders, Peter (2008). «Better external memory suffix array construction». Journal of Experimental Algorithmics. 12. 1 páginas. doi:10.1145/1227161.1402296 
  • Kulla, Fabian; Sanders, Peter (2007). «Scalable parallel suffix array construction». Parallel Computing. 33 (9). 605 páginas. doi:10.1016/j.parco.2007.06.004