Arranjo de sufixos

Array de sufixos
Tipe	Array
Inventado por	Predefinição:Harvtxt
Complexidade de tempo em Notação Grande-O
	Média	Pior caso
Espaço	$𝒪(n)$	$𝒪(n)$
Construção	$𝒪(n)$	$𝒪(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.Predefinição:Sfn

Arrays de sufixos foram introduzidos por Predefinição:Harvtxt como uma alternativa simples e eficiente em termos de espaço a árvore de sufixos. Eles foram descobertos independentemente por Predefinição:Harvtxt 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\le n$: $S[A[i-1],n]<S[A[i],n]$.

Exemplo

Considere o texto Predefinição:Mvar=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 Predefinição:Mvar 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 Predefinição:Mvar, que é o sufixo ana$.

Referências

• Predefinição:Citar periódico
• Predefinição:Citar conferência
• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico