Algoritmo de Ukkonen

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em ciência da computação, o algoritmo de Ukkonen é um algoritmo online de tempo linear para construção de árvores de sufixos, proposto por Esko Ukkonen em 1995.[1]

O algoritmo inicia com uma árvore de sufixos implícita contendo o primeiro caracter da string. Então ele prossegue através da string adicionando caracteres sucessivos até que a árvore esteja completa. Esta ordem de adição dos caracteres dá ao algoritmo de Ukkonen a sua propriedade "online". Anteriormente, os algoritmos procediam de forma inversa, do último caractere ao primeiro, seja do maior ao menor sufixo[2] ou do menor ao maior sufixo.[3] A implementação ingênua para a geração de uma árvore de sufixos requer tempo O(n²) ou mesmo O(n3), aonde n é o tamanho da string. Ao explorar um número de técnicas algorítmicas, Ukkonen reduziu para um tempo O(n) (linear), para alfabetos de tamanho constante, e O(n log n) em geral.

Referências

  1. doi:10.1007/BF01206331
    Esta citação será automaticamente completada em poucos minutos. Você pode furar a fila ou completar manualmente
  2. doi:10.1145/321941.321946
    Esta citação será automaticamente completada em poucos minutos. Você pode furar a fila ou completar manualmente
  3. doi:10.1109/SWAT.1973.13
    Esta citação será automaticamente completada em poucos minutos. Você pode furar a fila ou completar manualmente

Ligações externas[editar | editar código-fonte]