Algoritmo de Ukkonen - Ukkonen's algorithm
Na ciência da computação , o algoritmo de Ukkonen é um algoritmo online de tempo linear para construir árvores de sufixo , proposto por Esko Ukkonen em 1995. O algoritmo começa com uma árvore de sufixo implícita contendo o primeiro caractere da string. Em seguida, ele percorre a string, adicionando caracteres sucessivos até que a árvore esteja completa. Esta ordem de adição de caracteres dá ao algoritmo de Ukkonen sua propriedade "on-line". O algoritmo original apresentado por Peter Weiner retrocedeu do último caractere para o primeiro, do sufixo mais curto para o mais longo. Um algoritmo mais simples foi encontrado por Edward M. McCreight , indo do sufixo mais longo para o mais curto.
Árvore de sufixo implícita
Ao gerar a árvore de sufixo usando o algoritmo de Ukkonen, veremos a árvore de sufixo implícita em etapas intermediárias dependendo dos caracteres na string S. Em árvores de sufixo implícitas, não haverá borda com $ (ou qualquer outro caractere de terminação) rótulo e nenhum nó interno com apenas uma vantagem saindo dele.
Descrição de alto nível do algoritmo de Ukkonen
O algoritmo de Ukkonen constrói uma árvore de sufixos implícita T i para cada prefixo S [l ... i] de S (S sendo a string de comprimento n). Ele primeiro constrói T 1 usando 1 st personagem, então T 2 usando 2 nd personagem, então T 3 usando 3 rd caráter, ..., T n usando o n º personagem. Você pode encontrar as seguintes características em uma árvore de sufixo que usa o algoritmo de Ukkonen:
- A árvore de sufixo implícita T i +1 é construída no topo da árvore de sufixo implícita T i .
- A qualquer momento, o algoritmo de Ukkonen constrói a árvore de sufixos para os personagens vistos até agora e, portanto, possui propriedade on-line , permitindo que o algoritmo tenha um tempo de execução de O (n).
- O algoritmo de Ukkonen é dividido em n fases (uma fase para cada caractere na string com comprimento n).
- Cada fase i + 1 é subdividida em extensões i + 1, uma para cada um dos sufixos i + 1 de S [1 ... i + 1].
A extensão de sufixo trata de adicionar o próximo caractere na árvore de sufixos construída até agora. Na extensão j da fase i + 1, o algoritmo encontra o final de S [j ... i] (que já está na árvore devido à fase i anterior) e então estende S [j ... i] para ter certeza o sufixo S [j ... i + 1] está na árvore. Existem três regras de extensão:
- Se o caminho da raiz rotulada S [j ... i] termina na borda da folha (ou seja, S [i] é o último caractere na borda da folha), então o caractere S [i + 1] é apenas adicionado ao final da etiqueta na borda da folha.
- se o caminho da raiz rotulada S [j ... i] termina na borda não folha (ou seja, há mais caracteres após S [i] no caminho) e o próximo caractere não é S [i + 1], então um novo borda da folha com rótulo S [i + 1] e número j é criado a partir do caractere S [i + 1]. Um novo nó interno também será criado se S [1 ... i] terminar dentro (no meio) de uma aresta que não seja folha.
- Se o caminho da raiz rotulada S [j..i] termina na borda não-folha (ou seja, há mais caracteres após S [i] no caminho) e o próximo caractere é s [i + 1] (já na árvore), fazer nada.
Um ponto importante a se notar é que a partir de um determinado nó (raiz ou interno), haverá uma e apenas uma aresta começando com um caractere. Não haverá mais de uma aresta saindo de qualquer nó, começando com o mesmo caractere.
Tempo de execução
A implementação ingênua para gerar uma árvore de sufixo no futuro requer complexidade de tempo O ( n 2 ) ou mesmo O ( n 3 ) na notação grande O , onde n é o comprimento da string. Explorando uma série de técnicas algorítmicas, Ukkonen reduziu isso para o tempo O ( n ) (linear), para alfabetos de tamanho constante, e O ( n log n ) em geral, correspondendo ao desempenho do tempo de execução dos dois algoritmos anteriores.
Exemplo de algoritmo de Ukkonen
Para ilustrar melhor como uma árvore de sufixo usando o algoritmo de Ukkonen é construída, podemos usar o seguinte exemplo:
S = xabxac
- Comece com um nó raiz vazio.
- Construa T 1 para S [1] adicionando o primeiro caractere da string. A regra 2 se aplica, o que cria um novo nó folha.
- Construa T 2 para S [1 ... 2] adicionando sufixos de xa (xa e a). A regra 1 se aplica, que estende o rótulo do caminho na borda da folha existente. A regra 2 se aplica, o que cria um novo nó folha.
- Construa T 3 para S [1 ... 3] adicionando sufixos de xab (xab, ab e b). A regra 1 se aplica, que estende o rótulo do caminho na borda da folha existente. A regra 2 se aplica, o que cria um novo nó folha.
- Construa T 4 para S [1 ... 4] adicionando sufixos de xabx (xabx, abx, bx e x). A regra 1 se aplica, que estende o rótulo do caminho na borda da folha existente. A regra 3 se aplica, não faça nada.
- Constrói T 5 para S [1 ... 5] adicionando sufixos de xabxa (xabxa, abxa, bxa, xa e x). A regra 1 se aplica, que estende o rótulo do caminho na borda da folha existente. A regra 3 se aplica, não faça nada.
- Constrói T 6 para S [1 ... 6] adicionando sufixos de xabxac (xabxac, abxac, bxac, xac, ac e c). A regra 1 se aplica, que estende o rótulo do caminho na borda da folha existente. A regra 2 se aplica, o que cria um novo nó folha (neste caso, três novas bordas de ataque e dois novos nós internos são criados).
Referências
- ^ Ukkonen, E. (1995). "Construção on-line de árvores de sufixo" (PDF) . Algorithmica . 14 (3): 249–260. CiteSeerX 10.1.1.10.751 . doi : 10.1007 / BF01206331 . S2CID 6027556 .
- ^ Weiner, Peter (1973). "Algoritmos de correspondência de padrões lineares" (PDF) . 14º Simpósio Anual sobre Teoria de Comutação e Autômatos (SWAT 1973) . pp. 1–11. CiteSeerX 10.1.1.474.9582 . doi : 10.1109 / SWAT.1973.13 .
- ^ McCreight, Edward Meyers (1976). "Um algoritmo de construção de árvore de sufixo com economia de espaço". Jornal do ACM . 23 (2): 262–272. CiteSeerX 10.1.1.130.8022 . doi : 10.1145 / 321941.321946 . S2CID 9250303 .
links externos
- Explicação detalhada em inglês simples
- Pesquisa rápida de strings com árvores de sufixo Tutorial de Mark Nelson. Possui um exemplo de implementação escrito em C ++.
- Implementação em C com explicação detalhada
- Slides de palestras de Guy Blelloch
- Página inicial de Ukkonen
- Projeto de indexação de texto (construção de árvores de sufixo em tempo linear de Ukkonen)
- Implementação em C Parte 1 Parte 2 Parte 3 Parte 4 Parte 5 Parte 6