Árvore de sufixos

Em ciência da computação, uma árvore de sufixos (também chamada árvore PAT ou, na forma anterior, árvore de posições) é uma trie comprimida, contendo todos os sufixos de um dado texto, assim como suas chaves e posições no texto como seus valores. Árvores de sufixo permitem uma implementação particularmente rápida de muitas operações importantes com strings.

Árvore de sufixo para o texto BANANA. Cada substring é terminada com um caractere especial $. Os seis caminhos da raiz até as folhas (mostradas como caixas) correspondem aos seis sufixos A$, NA$, ANA$, NANA$, ANANA$ e BANANA$. Os números nas folhas dão a posição inicial ao sufixo correspondente. Suffix links, desenhadas em potilhado, são usadas durante a construção

A construção de tal árvore para uma string $S$ leva tempo e espaço lineares no tamanho de $S$. Uma vez construída, muitas operações podem ser realizadas rapidamente, por exemplo, localizar uma substring em $S$, localizar uma substring se um certo número de erros for permitido, localizar acertos para uma expressão regular etc. Árvores de sufixo também proveem uma das primeiras soluções em tempo linear para o problema da maior substring comum. Estes ganhos de velocidade vem com um custo: armazenar uma árvore de sufixos de uma string tipicamente requer significativamente mais espaço do que armazenar a própria string.

Definição

Uma árvore de sufixos para a string $S$ de tamanho $n$ é definida como uma árvore tal que:

• A árvore possui exatamente n folhas numeradas de 1 a n.
• Exceto pela raiz, cada nó interno possui pelo menos dois filhos.
• Cada aresta é denominada com uma substring não vazia de S (rótulo-string).
• Não podem existir duas substrings a partir de um nó que possuam rótulos-strings iniciando com o mesmo caractere.
• A string obtida ao concatenar todas os rótulos-strings encontrados no caminho da raiz até a folha i resulta no sufixo S[i..n], para i de 1 a n.

Como tal árvore não existe para todas as strings, $S$ é customizado com um símbolo terminal não visto na string (usualmente denotado $). Isto assegura que nenhum sufixo é um prefixo de outro, e que haverá $n$ nós folhas, uma para cada os $n$ sufixos de $S$. Desde que todos os nós internos não-raís ramificam, deve haver no máximo n −  1 de tais nós, e n + (n − 1) + 1 = 2n nós no total (n folhas, n − 1 nós internos não-raízes, 1 raiz).

Suffix links são uma característica chave para algoritmos de construção em tempo linear mais antigos, apesar da maioria dos algoritmos mais novos, que são baseados no algoritmo de Farach, dispensarem suffix links. Em uma árvore de sufixos completa, todos os nós internos não-raízes possuem um para outro nó interno. Se o caminho da raiz até um nó resulta na string $\chi \alpha$, aonde $\chi$ é um caractere simples e $\alpha$ é uma string (possivelmente vazia), este caminho possui um suffix link para o nó interno representando $\alpha$. Veja o exemplo com o nó de ANA para o nó de NA na imagem acima. Suffix links também são usados em alguns algoritmos que executam sobre a árvore.