Array de sufixos

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido (desde fevereiro de 2014). Ajude e colabore com a tradução.
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.[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 nome array PAT.

Definição[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

[[Category:Estruturas de dados]]-->