Array de sufixos Tipe Array Inventado por colspan="2" Complexidade de tempoem Notação Grande-O Média Pior caso Espaço Construção
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 como uma alternativa simples e eficiente em termos de espaço a árvore de sufixos. Eles foram descobertos independentemente por sob o noe array PAT.
Definição Seja uma cadeia de caracteres e seja a subcadeia de que vai de até .
O array de sufixos de é definido como sendo um array de inteiros que proveem as posições iniciais dos sufixos de em ordem lexicográfica. Isto significa que uma entrada contem a posição inicial do -ésimo menor sufixo em e, da mesma forma, para todo : .
Exemplo
Considere o texto =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 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 contém o valor 4, e por isso, se refere ao sufixo iniciando na posição 4 dentro de , que é o sufixo ana$.
Notas
Referências
Categoria:Estruturas de dados