Definição – o que significa árvore de sufixo?
Uma árvore de sufixo é uma ferramenta freqüentemente usada para analisar strings de texto. É um tipo de árvore digital que usa métodos algorítmicos para revelar a estrutura de uma string e seus subconjuntos. É um tipo de árvore Patricia, uma estrutura que serve para armazenar um conjunto de strings.
Definirtec explica Suffix Tree
As árvores de sufixo podem ser usadas para muitas coisas. Geralmente, essas árvores contêm todos os subconjuntos de uma determinada string de texto. Com isso em mente, outras sequências de texto podem ser comparadas com a árvore de sufixos para descobrir se estão incluídas na entrada da sequência inicial.
A árvore de sufixos foi desenvolvida ao longo do tempo por figuras como Weiner e McCreight na década de 1970 e Ukkonen na década de 1990. As adaptações visuais de uma árvore de sufixo mostram como os subconjuntos da string de texto são tratados pelo algoritmo. Como alternativa, uma árvore de sufixo pode ser compartilhada em notação matemática.
Árvores de sufixo geralmente são usadas para localizar subpadrões específicos em um conjunto maior de strings. Os programadores usam a pesquisa em árvore de sufixo para tornar as pesquisas eficientes, para encontrar cada instância onde uma determinada substring é representada na estrutura de dados. As pesquisas em árvore de sufixo podem ser usadas para encontrar sequências de DNA, coordenadas de pesquisa ou qualquer outro tipo de dados de sequência.