Uma tabela de sufixo (às vezes chamada de tabela de sufixo, em inglês : array de sufixos ) é uma estrutura de dados usada em ciência da computação e, mais particularmente, em combinatória de palavras e em bioinformática . Para uma determinada palavra, a tabela contém uma lista de inteiros que correspondem às posições iniciais dos sufixos da palavra, quando classificados em ordem lexicográfica.
O objetivo da tabela é fornecer os mesmos recursos de pesquisa que uma árvore de sufixo , reduzindo o tamanho da memória usada. A estrutura foi introduzida em 1990 por Manber e Myers e redescoberta em 1992.
Let Ser um alfabeto de tamanho finito e uma ordem lexicográfica neste alfabeto.
Que haja uma palavra no alfabeto . Esta palavra de comprimento tem sufixos. Esses sufixos podem ser ordenados de forma crescente de acordo com a ordem lexicográfica. Cada sufixo corresponde a uma posição inicial na palavra ; por exemplo, o sufixo na posição 0 é a própria palavra . Uma vez que os sufixos são ordenados, suas posições iniciais correspondentes formam a tabela de sufixos .
Tome a palavra = abracadabra. Esta palavra , de comprimento 11, tem os 11 sufixos abracadabra, bracadabra, racadabra, ..., a. Cada um desses 11 sufixos pode ser organizado em ordem crescente em ordem lexicográfica. Na tabela abaixo, os sufixos estão listados em ordem crescente. A segunda coluna indica a posição inicial do sufixo na palavra:
Sufixo | Posição inicial |
---|---|
no | 10 |
um sutiã | 7 |
abracadabra | 0 |
acadabra | 3 |
Adabra | 5 |
sutiã | 8 |
bracadabra | 1 |
cadabra | 4 |
dabra | 6 |
ra | 9 |
racadabra | 2 |
A tabela de sufixos T formada a partir da palavra w é composta pelas posições iniciais dos 11 sufixos dispostos em ordem lexicográfica crescente, ou seja,
T = {10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2}.A tabela de sufixos é usada como índice para pesquisar padrões em um texto. Encontrar um padrão em um texto é equivalente a encontrar o padrão como um prefixo de sufixos de texto.
A tabela é construída a partir do texto. A tabela contém as posições iniciais dos sufixos de texto. No entanto, esses sufixos são dispostos em ordem lexicográfica durante a construção da tabela, portanto, os sufixos que começam com o padrão pesquisado têm suas posições em caixas consecutivas da tabela. No entanto, inicialmente não é possível saber em qual seção da tabela se encontra esse conjunto de posições buscadas. O algoritmo usará, portanto, uma busca dicotômica para identificar esse cluster.
Devem ser consideradas duas complexidades: a relativa à ordenação dos sufixos pela ordem lexicográfica (durante a construção da tabela) e a relativa à procura de um padrão por dicotomia.
A classificação de sufixo é um algoritmo que ingenuamente leva as comparações médias (onde é o comprimento da palavra) e onde cada comparação de sufixo leva o pior cenário . Portanto, classificar sufixos ingenuamente leva muito tempo no pior dos casos. Vários algoritmos melhoram esse limite, oferecendo complexidades da ordem de ou até .
( Li, Li e Huo 2016 ) deram o primeiro algoritmo de construção de matriz de sufixo de complexidade que é ideal tanto no tempo quanto no local, onde "no lugar" significa que o algoritmo só precisa de espaço adicional além da string de entrada e da matriz de sufixo de saída. Outro algoritmo linear é fornecido em 2016 por Uwe Baier. De acordo com a monografia Construção de Estruturas de Dados Fundamentais para Strings , o algoritmo de ( Li, Li e Huo 2016 ) é consecutivo a dois algoritmos de Nong et al. em 2009 (denominado SAIS) e Nong em 2013 (denominado SACA-K) que também são lineares. Um algoritmo Keisuke Goto tem a mesma complexidade ótima (no tempo e no lugar).
Para reduzir o espaço ocupado por uma matriz de sufixo, dois tipos de estruturas de dados compactados foram criados: matrizes de sufixo compactadas (en) e o índice FM (baseado na transformação de Burrows-Wheeler ).