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	${\mathcal {O}}(n)$	${\mathcal {O}}(n)$
Construção	${\mathcal {O}}(n)$	${\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.

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}$ uma cadeia de caracteres e seja $S[i,j]$ a subcadeia de $S$ que vai de $i$ até $j$.

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

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 
• 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 
• 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 
• 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 
• 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 
• 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 
• 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 
• 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