string - ternaria - trie tst




Algoritmo de árvore de sufixos de Ukkonen em inglês claro (4)

A seguir, é apresentada uma tentativa de descrever o algoritmo Ukkonen mostrando primeiro o que ele faz quando a cadeia é simples (ou seja, não contém caracteres repetidos) e, em seguida, estendendo-a ao algoritmo completo.

Primeiro, algumas declarações preliminares.

  1. O que estamos construindo é basicamente como uma pesquisa. Portanto, há um nó raiz, com as bordas saindo dele, levando a novos nós, e bordas adicionais saindo delas, e assim por diante

  2. Mas : ao contrário de uma pesquisa, os rótulos de borda não são caracteres únicos. Em vez disso, cada borda é rotulada usando um par de inteiros [from,to] . Estes são ponteiros no texto. Nesse sentido, cada borda carrega um rótulo de seqüência de comprimento arbitrário, mas ocupa apenas O (1) espaço (dois ponteiros).

Principio básico

Gostaria de demonstrar primeiro como criar a árvore de sufixos de uma string particularmente simples, uma string sem caracteres repetidos:

abc

O algoritmo funciona em etapas, da esquerda para a direita . Há um passo para cada caractere da string . Cada passo pode envolver mais de uma operação individual, mas veremos (veja as observações finais no final) que o número total de operações é O (n).

Assim, começamos a partir da esquerda e primeiro inserimos apenas o caractere a , criando uma aresta a partir do nó raiz (à esquerda) para uma folha, e rotulando-a como [0,#] , o que significa que a aresta representa a subseqüência começando na posição 0 e terminando no final atual . Eu uso o símbolo # para indicar o fim atual , que está na posição 1 (logo após a ).

Então nós temos uma árvore inicial, que se parece com isso:

E o que isso significa é isto:

Agora nós progredimos para a posição 2 (logo após b ). Nosso objetivo em cada etapa é inserir todos os sufixos até a posição atual . Fazemos isso por

  • expandindo o já existente para ab
  • inserindo uma nova borda para b

Em nossa representação, isso parece

E o que isso significa é:

Nós observamos duas coisas:

  • A representação de borda para ab é a mesma que costumava estar na árvore inicial: [0,#] . Seu significado mudou automaticamente porque atualizamos a posição atual de 1 para 2.
  • Cada borda consome o espaço O (1), porque consiste em apenas dois ponteiros no texto, independentemente de quantos caracteres ele representa.

Em seguida, incrementamos a posição novamente e atualizamos a árvore anexando a c a todas as arestas existentes e inserindo uma nova aresta para o novo sufixo c .

Em nossa representação, isso parece

E o que isso significa é:

Nós observamos:

  • A árvore é a árvore de sufixos correta até a posição atual após cada etapa
  • Existem tantos passos quantos os caracteres no texto
  • A quantidade de trabalho em cada etapa é O (1), porque todas as arestas existentes são atualizadas automaticamente pelo incremento # , e a inserção da nova aresta para o caractere final pode ser feita no tempo O (1). Portanto, para uma cadeia de comprimento n, apenas O (n) tempo é necessário.

Primeira extensão: repetições simples

Claro que isso funciona tão bem apenas porque a nossa string não contém repetições. Agora olhamos para uma string mais realista:

abcabxabcd

Ele começa com abc como no exemplo anterior, depois ab é repetido e seguido por x e, em seguida, abc é repetido seguido por d .

Etapas 1 a 3: Após as 3 primeiras etapas, temos a árvore do exemplo anterior:

Passo 4: Nós movemos # para a posição 4. Isso implicitamente atualiza todas as arestas existentes para isso:

e precisamos inserir o sufixo final do passo atual, a , na raiz.

Antes de fazermos isso, introduzimos mais duas variáveis (além de # ), que, é claro, estão lá o tempo todo, mas não as usamos até agora:

  • O ponto ativo , que é um triplo (active_node,active_edge,active_length)
  • O remainder , que é um inteiro indicando quantos novos sufixos precisamos inserir

O significado exato destes dois ficará claro em breve, mas por enquanto vamos apenas dizer:

  • No exemplo simples do abc , o ponto ativo era sempre (root,'\0x',0) , isto é, active_node era o nó raiz, active_edge era especificado como o caractere nulo '\0x' e active_length era zero. O efeito disso foi que a nova borda que inserimos em cada etapa foi inserida no nó raiz como uma borda recém criada. Veremos em breve porque é necessário um triplo para representar essa informação.
  • O remainder foi sempre definido como 1 no início de cada etapa. O significado disso foi que o número de sufixos que tivemos que inserir ativamente no final de cada etapa era 1 (sempre apenas o caractere final).

Agora isso vai mudar. Quando inserimos o caractere final atual a na raiz, notamos que já existe uma borda de saída começando com a , especificamente: abca . Aqui está o que fazemos em tal caso:

  • Nós não inserimos uma borda nova [4,#] no nó raiz. Em vez disso, simplesmente notamos que o sufixo a já está em nossa árvore. Ele termina no meio de uma borda mais longa, mas não nos incomodamos com isso. Nós apenas deixamos as coisas do jeito que são.
  • Nós definimos o ponto ativo para (root,'a',1) . Isso significa que o ponto ativo está agora em algum lugar no meio da borda de saída do nó raiz que começa com, especificamente, após a posição 1 nessa aresta. Percebemos que a borda é especificada simplesmente pelo primeiro caractere a . Isso é suficiente porque pode haver apenas uma borda começando com qualquer caractere específico (confirme se isso é verdade depois de ler toda a descrição).
  • Nós também incrementamos o remainder , então no começo da próxima etapa será 2.

Observação: Quando o sufixo final que precisamos inserir já existe na árvore , a árvore em si não é alterada (apenas atualizamos o ponto ativo e o remainder ). A árvore não é mais uma representação precisa da árvore de sufixos até a posição atual , mas contém todos os sufixos (porque o sufixo final a é contido implicitamente ). Portanto, além de atualizar as variáveis ​​(que são todas de tamanho fixo, portanto, isso é O (1)), não houve nenhum trabalho nessa etapa.

Passo 5: Atualizamos a posição atual # para 5. Isso atualiza automaticamente a árvore para isto:

E como o remainder é 2 , precisamos inserir dois sufixos finais da posição atual: ab e b . Isso é basicamente porque:

  • O sufixo do passo anterior nunca foi inserido corretamente. Assim, permaneceu e, como progredimos um passo, ele agora cresceu de a para ab .
  • E precisamos inserir a nova borda final b .

Na prática, isso significa que vamos para o ponto ativo (que aponta para o a na borda agora abcab ) e insira o caractere final atual b . Mas: Novamente, verifica-se que b também já está presente na mesma borda.

Então, novamente, nós não mudamos a árvore. Nós simplesmente:

  • Atualize o ponto ativo para (root,'a',2) (mesmo nó e aresta como antes, mas agora apontamos para trás do b )
  • Incrementar o remainder para 3 porque ainda não inserimos corretamente a borda final da etapa anterior e também não inserimos a borda final atual.

Para ser claro: Tínhamos que inserir ab e b na etapa atual, mas como ab já havia sido encontrado, atualizamos o ponto ativo e nem tentamos inserir b . Por quê? Porque se ab está na árvore, todo sufixo dele (incluindo b ) deve estar na árvore também. Talvez apenas implicitamente , mas deve estar lá, por causa da maneira como construímos a árvore até agora.

Continuamos para o passo 6 incrementando # . A árvore é atualizada automaticamente para:

Porque o remainder é 3 , temos que inserir abx , bx e x . O ponto ativo nos diz onde ab termina, então só precisamos pular lá e inserir o x . De fato, x ainda não existe, então dividimos a borda do abcabx e inserimos um nó interno:

As representações de borda ainda são apontadas para o texto, portanto, dividir e inserir um nó interno pode ser feito no tempo O (1).

Então, nós lidamos com abx e decrementamos o remainder para 2. Agora precisamos inserir o próximo sufixo restante, bx . Mas antes de fazermos isso, precisamos atualizar o ponto ativo. A regra para isso, depois de dividir e inserir uma aresta, será chamada Regra 1 abaixo, e se aplica sempre que o active_node for root (aprenderemos a regra 3 para outros casos mais abaixo). Aqui está a regra 1:

Após uma inserção da raiz,

  • active_node permanece raiz
  • active_edge é definido como o primeiro caractere do novo sufixo que precisamos inserir, ou seja, b
  • active_length é reduzido em 1

Assim, o novo triplo de ponto ativo (root,'b',1) indica que a próxima inserção deve ser feita na borda do bcabx , atrás de 1 caractere, ou seja, atrás de b . Podemos identificar o ponto de inserção no tempo O (1) e verificar se o x já está presente ou não. Se estivesse presente, terminaríamos o passo atual e deixaríamos tudo como está. Mas x não está presente, então nós o inserimos dividindo a borda:

Novamente, isso levou O (1) tempo e nós atualizamos o remainder para 1 e o ponto ativo para (root,'x',0) como regra 1 indica.

Mas há mais uma coisa que precisamos fazer. Vamos chamar isso de Regra 2:

Se dividirmos uma aresta e inserirmos um novo nó, e se esse não for o primeiro nó criado durante a etapa atual, conectamos o nó inserido anteriormente e o novo nó por meio de um ponteiro especial, um link de sufixo . Mais tarde veremos porque isso é útil. Aqui está o que temos, o link do sufixo é representado como uma borda pontilhada:

Ainda precisamos inserir o sufixo final do passo atual, x . Como o componente active_length do nó ativo caiu para 0, a inserção final é feita diretamente na raiz. Como não há borda de saída no nó raiz começando com x , inserimos uma nova borda:

Como podemos ver, na etapa atual todas as inserções restantes foram feitas.

Passamos para o passo 7 definindo # = 7, que automaticamente anexa o próximo caractere, a , a todas as bordas da folha, como sempre. Em seguida, tentamos inserir o novo caractere final no ponto ativo (a raiz) e descobrir que ele já está lá. Então, terminamos a etapa atual sem inserir nada e atualizar o ponto ativo para (root,'a',1) .

Na etapa 8 , # = 8, anexamos b e, como visto anteriormente, isso significa apenas que atualizamos o ponto ativo para (root,'a',2) e incrementamos o remainder sem fazer mais nada, porque b já está presente. No entanto, notamos (no tempo O (1)) que o ponto ativo está agora no final de uma aresta. Nós refletimos isso reajustando-o para (node1,'\0x',0) . Aqui, eu uso node1 para me referir ao nó interno no qual a borda ab termina.

Então, no passo # = 9 , precisamos inserir 'c' e isso nos ajudará a entender o truque final:

Segunda extensão: usando links de sufixo

Como sempre, a atualização # anexa c automaticamente às bordas da folha e vamos ao ponto ativo para ver se podemos inserir 'c'. Acontece que 'c' já existe nessa borda, então definimos o ponto ativo como (node1,'c',1) , incrementamos o remainder e não fazemos mais nada.

Agora, no passo # = 10 , o remainder is 4 , e então primeiro precisamos inserir abcd (que permanece a partir de 3 passos atrás) inserindo d no ponto ativo.

Tentar inserir d no ponto ativo causa uma divisão de borda no tempo O (1):

O active_node , do qual a divisão foi iniciada, é marcado em vermelho acima. Aqui está a regra final, Regra 3:

Depois de dividir uma aresta a partir de um active_node que não seja o nó raiz, seguimos o link do sufixo saindo desse nó, se houver algum, e reconfigure o active_node para o nó para o qual ele aponta. Se não houver um link de sufixo, definimos o active_node para a raiz. active_edge e active_length permanecem inalterados.

Portanto, o ponto ativo é agora (node2,'c',1) e node2 está marcado em vermelho abaixo:

Como a inserção de abcd está completa, decrementamos o remainder para 3 e consideramos o próximo sufixo restante do passo atual, bcd . A regra 3 definiu o ponto ativo para apenas o nó e a borda corretos, de modo que inserir o bcd pode ser feito simplesmente inserindo seu caractere final d no ponto ativo.

Fazer isso causa outra divisão de borda e, devido à regra 2 , devemos criar um link de sufixo do nó inserido anteriormente para o novo:

Observamos: Os links de sufixo nos permitem redefinir o ponto ativo para que possamos fazer a próxima inserção restante no esforço O (1). Observe o gráfico acima para confirmar que, de fato, o nó no rótulo ab está vinculado ao nó em b (seu sufixo) e o nó em abc está vinculado a bc .

A etapa atual ainda não está concluída. remainder agora é 2 e precisamos seguir a regra 3 para redefinir o ponto ativo novamente. Como o atual active_node (vermelho acima) não possui um link de sufixo, redefinimos para root. O ponto ativo é agora (root,'c',1) .

Portanto, a próxima inserção ocorre na única borda de saída do nó raiz cujo rótulo começa com c : cabxabcd , atrás do primeiro caractere, ou seja, atrás de c . Isso causa outra divisão:

E como isso envolve a criação de um novo nó interno, seguimos a regra 2 e definimos um novo link de sufixo a partir do nó interno criado anteriormente:

(Estou usando o Graphviz Dot para esses pequenos gráficos. O novo sufixo link fez com que o ponto reorganizasse as bordas existentes, portanto, verifique cuidadosamente para confirmar se a única coisa inserida acima é um novo sufixo.)

Com isso, o remainder pode ser definido como 1 e como o active_node é root, usamos a regra 1 para atualizar o ponto ativo para (root,'d',0) . Isso significa que a inserção final da etapa atual é inserir um único d na raiz:

Esse foi o passo final e estamos prontos. Há um número de observações finais , no entanto:

  • Em cada passo nós nos movemos para frente em 1 posição. Isso atualiza automaticamente todos os nós da folha no tempo O (1).

  • Mas não se trata de a) quaisquer sufixos remanescentes das etapas anteriores eb) com o caracter final da etapa atual.

  • remainder nos diz quantas inserções adicionais precisamos fazer. Essas inserções correspondem um a um aos sufixos finais da string que termina na posição atual # . Consideramos um após o outro e fazemos a inserção. Importante: Cada inserção é feita no tempo O (1) desde que o ponto ativo nos diz exatamente para onde ir, e precisamos adicionar apenas um único caractere no ponto ativo. Por quê? Porque os outros caracteres estão contidos implicitamente (caso contrário, o ponto ativo não estaria onde está).

  • Após cada inserção, decrementamos o remainder e seguimos o link do sufixo, se houver algum. Se não vamos para a raiz (regra 3). Se já estamos na raiz, modificamos o ponto ativo usando a regra 1. Em qualquer caso, leva apenas o tempo O (1).

  • Se, durante uma dessas inserções, descobrirmos que o caractere que queremos inserir já está lá, não faremos nada e terminaremos a etapa atual, mesmo que seja remainder > 0. A razão é que quaisquer inserções que restarem serão sufixos do que acabamos de tentar fazer. Portanto, estão todos implícitos na árvore atual. O fato de que remainder > 0 garante que lidamos com os sufixos restantes mais tarde.

  • E se no final do algoritmo remainder > 0? Este será o caso sempre que o final do texto for uma subseqüência que ocorreu em algum lugar antes. Nesse caso, devemos acrescentar um caractere extra no final da string que não tenha ocorrido antes. Na literatura, geralmente o cifrão $ é usado como um símbolo para isso. Por que isso importa? -> Se mais tarde usarmos a árvore de sufixos concluída para procurar por sufixos, devemos aceitar as correspondências somente se elas terminarem em uma folha . Caso contrário, obteríamos muitas correspondências espúrias, porque há muitas cadeias implicitamente contidas na árvore que não são sufixos reais da cadeia principal. Forçar o remainder a ser 0 no final é essencialmente uma maneira de garantir que todos os sufixos terminem em um nó folha. No entanto, se quisermos usar a árvore para procurar subseqüências gerais , não apenas sufixos da string principal, essa etapa final não é necessária, como sugerido pelo comentário do OP abaixo.

  • Então, qual é a complexidade de todo o algoritmo? Se o texto tiver n caracteres, existem obviamente n passos (ou n + 1 se somarmos o cifrão). Em cada passo, não fazemos nada (além de atualizar as variáveis), ou fazemos inserções de remainder , cada uma tomando O (1) hora. Como o remainder indica quantas vezes não fizemos nada nas etapas anteriores e é decrementado para cada inserção que fazemos agora, o número total de vezes que fazemos algo é exatamente n (ou n + 1). Portanto, a complexidade total é O (n).

  • No entanto, há uma pequena coisa que não expliquei corretamente: pode acontecer de seguirmos um link de sufixo, atualizar o ponto ativo e, em seguida, descobrir que seu componente active_length não funciona bem com o novo active_node . Por exemplo, considere uma situação como esta:

(As linhas tracejadas indicam o restante da árvore. A linha pontilhada é um link de sufixo.)

Agora, deixe o ponto ativo ser (red,'d',3) , então ele aponta para o lugar atrás do f na borda do defg . Agora, suponhamos que fizemos as atualizações necessárias e agora sigamos o link do sufixo para atualizar o ponto ativo de acordo com a regra 3. O novo ponto ativo é (green,'d',3) . No entanto, o d -edge que sai do nó verde é de , portanto, ele tem apenas dois caracteres. Para encontrar o ponto ativo correto, obviamente precisamos seguir essa aresta até o nó azul e redefinir para (blue,'f',1) .

Em um caso particularmente ruim, o active_length pode ser tão grande quanto o remainder , que pode ser tão grande quanto n. E pode muito bem acontecer que para encontrar o ponto ativo correto, precisamos não apenas saltar sobre um nó interno, mas talvez muitos, até n no pior dos casos. Isso significa que o algoritmo tem uma complexidade O (n 2 ) oculta, porque em cada passo o remainder é geralmente O (n), e os pós-ajustes no nó ativo após seguir um sufixo podem ser O (n) também?

Não. O motivo é que, se realmente tivermos que ajustar o ponto ativo (por exemplo, de verde para azul como acima), isso nos leva a um novo nó que tem seu próprio link de sufixo, e active_length será reduzido. À medida que seguimos a cadeia de links de sufixo, fazemos as inserções restantes, o active_length só pode diminuir e o número de ajustes de ponto ativo que podemos fazer no caminho não pode ser maior do que o active_length a qualquer momento. Já que active_length nunca pode ser maior que remainder , e remainder é O (n) não apenas em cada passo, mas a soma total de incrementos feitos para o remainder no decorrer de todo o processo é O (n) também, o número de ajustes de pontos ativos também são limitados por O (n).

Eu me sinto um pouco grosso neste momento. Eu passei dias tentando envolver minha mente com a construção de árvore com sufixo, mas como não tenho conhecimento em matemática, muitas das explicações me escapam à medida que começam a usar excessivamente a simbologia matemática. O mais próximo de uma boa explicação que encontrei é o Fast String Searching With Suffix Trees , mas ele encobre vários pontos e alguns aspectos do algoritmo permanecem obscuros.

Uma explicação passo-a-passo deste algoritmo aqui no Stack Overflow seria inestimável para muitos outros além de mim, tenho certeza.

Para referência, aqui está o artigo de Ukkonen sobre o algoritmo: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Minha compreensão básica, até agora:

  • Eu preciso iterar através de cada prefixo P de uma dada string T
  • Eu preciso percorrer cada sufixo S no prefixo P e adicioná-lo à árvore
  • Para adicionar o sufixo S à árvore, preciso fazer uma iteração em cada caractere em S, com as iterações consistindo em percorrer uma ramificação existente que comece com o mesmo conjunto de caracteres C em S e dividir potencialmente uma aresta em nós descendentes quando alcançar um caractere diferente no sufixo OU se não houver borda correspondente para descer. Quando nenhuma borda correspondente é encontrada para descer por C, uma nova aresta de folha é criada para C.

O algoritmo básico parece ser O (n 2 ), como é apontado na maioria das explicações, já que precisamos percorrer todos os prefixos, então precisamos passar por cada um dos sufixos para cada prefixo. O algoritmo de Ukkonen é aparentemente único por causa da técnica de ponteiro de sufixo que ele usa, embora eu pense que é isso que estou tendo dificuldade em entender.

Eu também estou tendo problemas para entender:

  • exatamente quando e como o "ponto ativo" é atribuído, usado e alterado
  • o que está acontecendo com o aspecto de canonização do algoritmo
  • Por que as implementações que vi precisam "consertar" as variáveis ​​de delimitação que estão usando

Aqui está o código-fonte C # completo. Ele não só funciona corretamente, mas suporta canonização automática e renderiza um gráfico de texto mais bonito da saída. O código fonte e a saída de amostra estão em:

https://gist.github.com/2373868

Atualização 2017-11-04

Depois de muitos anos, encontrei um novo uso para árvores de sufixos e implementei o algoritmo em JavaScript . A essência está abaixo. Deve estar livre de bugs. Despeje-o em um arquivo js, npm install chalk do mesmo local e, em seguida, execute o node.js para ver alguma saída colorida. Há uma versão simplificada no mesmo Gist, sem qualquer código de depuração.

https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6


Eu tentei implementar a Suffix Tree com a abordagem dada na resposta do jogojapan, mas não funcionou em alguns casos devido à formulação usada para as regras. Além disso, mencionei que ninguém conseguiu implementar uma árvore de sufixos absolutamente correta usando essa abordagem. Abaixo vou escrever uma "visão geral" da resposta do jogojapan com algumas modificações nas regras. Também descreverei o caso quando nos esquecemos de criar links importantes para o sufixo.

Variáveis ​​adicionais usadas

  1. ponto ativo - um triplo (active_node; active_edge; active_length), mostrando de onde devemos começar a inserir um novo sufixo.
  2. restante - mostra o número de sufixos que devemos adicionar explicitamente . Por exemplo, se a nossa palavra for 'abcaabca' e resto = 3, significa que devemos processar 3 últimos sufixos: bca , ca e a .

Vamos usar um conceito de um nó interno - todos os nós, exceto a raiz e as folhas são nós internos .

Observação 1

Quando o sufixo final que precisamos inserir já existe na árvore, a árvore em si não é alterada (apenas atualizamos o active point e o remainder ).

Observação 2

Se em algum ponto o active_length for maior ou igual ao comprimento da borda atual ( edge_length ), moveremos nosso active point para baixo até que edge_length seja estritamente maior que active_length .

Agora, vamos redefinir as regras:

Regra 1

Se após uma inserção do nó ativo = root , o comprimento ativo for maior que 0, então:

  1. nó ativo não é alterado
  2. comprimento ativo é diminuído
  3. borda ativa é deslocada para a direita (para o primeiro caractere do próximo sufixo, devemos inserir)

Regra 2

Se criarmos um novo nó interno OU fizermos um inserter a partir de um nó interno , e este não for o primeiro nó interno do SUCH na etapa atual, então vinculamos o nó do SUCH anterior com ESTE através de um link de sufixo .

Esta definição da Rule 2 é diferente do jogojapan ', pois aqui levamos em conta não apenas os nós internos recém-criados , mas também os nós internos, a partir dos quais fazemos uma inserção.

Regra 3

Após uma inserção do nó ativo que não é o nó raiz , devemos seguir o link do sufixo e definir o nó ativo para o nó para o qual ele aponta. Se não houver um link de sufixo, configure o nó ativo para o nó raiz . De qualquer forma, a borda ativa e o comprimento ativo permanecem inalterados.

Nesta definição da Rule 3 , também consideramos as inserções de nós de folha (não apenas nós divididos).

E finalmente, Observação 3:

Quando o símbolo que queremos adicionar à árvore já está na borda, nós, de acordo com a Observation 1 , atualizamos apenas active point e o remainder , deixando a árvore inalterada. MAS se houver um nó interno marcado como precisando de um link de sufixo , devemos conectar esse nó com nosso active node atual por meio de um link de sufixo.

Vejamos o exemplo de uma árvore de sufixos para cdddcdc se adicionarmos um link de sufixo nesse caso e se não o fizermos:

  1. Se nós não conectar os nós através de um link de sufixo:

    • antes de adicionar a última letra c :

    • depois de adicionar a última letra c :

  2. Se nós conectarmos os nós através de um link de sufixo:

    • antes de adicionar a última letra c :

    • depois de adicionar a última letra c :

Parece que não há diferença significativa: no segundo caso, há mais dois links de sufixos. Mas esses links de sufixo estão corretos e um deles - do nó azul ao vermelho - é muito importante para nossa abordagem com ponto ativo . O problema é que, se não colocarmos um sufixo link aqui, mais tarde, quando adicionarmos algumas novas letras à árvore, poderemos omitir a adição de alguns nós à árvore devido à Rule 3 , porque, de acordo com ela, se houver não há um link de sufixo, então devemos colocar o active_node na raiz.

Quando estávamos adicionando a última letra à árvore, o nó vermelho já existia antes de fazermos uma inserção a partir do nó azul (a borda era 'c' ). Como havia uma inserção do nó azul, marcamos como precisando de um link de sufixo . Então, contando com a abordagem de ponto ativo , o active node foi definido para o nó vermelho. Mas nós não fazemos uma inserção a partir do nó vermelho, já que a letra 'c' já está no limite. Isso significa que o nó azul deve ser deixado sem um link de sufixo? Não, devemos conectar o nó azul com o vermelho por meio de um link de sufixo. Por que isso está correto? Porque a abordagem do ponto ativo garante que chegamos ao lugar certo, ou seja, ao próximo local onde devemos processar uma inserção de um sufixo menor .

Finalmente, aqui estão minhas implementações da Suffix Tree:

  1. Java
  2. C++

Espero que esta "visão geral" combinada com a resposta detalhada do jogojapan ajude alguém a implementar sua própria Suffix Tree.


Obrigado pelo tutorial bem explicado por @jogojapan , eu implementei o algoritmo em Python.

Alguns pequenos problemas mencionados pelo @jogojapan são mais sofisticados do que eu esperava, e precisam ser tratados com muito cuidado. Custou-me vários dias para que minha implementação fosse suficientemente robusta (suponho). Problemas e soluções estão listados abaixo:

  1. Terminar com Remainder > 0 Acontece que esta situação também pode acontecer durante a etapa de desdobramento , não apenas no final de todo o algoritmo. Quando isso acontece, podemos deixar o restante, actnode, acgedge e actlength inalterados , terminar a etapa de desdobramento atual e iniciar outra etapa mantendo ou desdobrando, dependendo se o próximo caractere na cadeia original estiver no caminho atual ou não.

  2. Leap Over Nodes: quando seguimos um link de sufixo, atualizamos o ponto ativo e depois descobrimos que seu componente active_length não funciona bem com o novo active_node. Temos que avançar para o lugar certo para dividir ou inserir uma folha. Este processo pode não ser tão simples, porque durante o movimento, o comprimento de ação e a ação continuam mudando completamente, quando você tem que voltar para o nó raiz , a ação e o comprimento de ação podem estar errados por causa desses movimentos. Precisamos de variáveis ​​adicionais para manter essa informação.

Os outros dois problemas foram apontados de alguma forma pelo @managonov

  1. Dividir Poderia Degenerar Ao tentar dividir uma borda, em algum momento você encontrará a operação de divisão está certo em um nó. Nesse caso, precisamos apenas adicionar uma nova folha a esse nó, tomá-la como uma operação de divisão de borda padrão, o que significa que os links de sufixo, se houver algum, devem ser mantidos correspondentemente.

  2. Hidden Suffix Links Existe outro caso especial que é incorrido pelo problema 1 e pelo problema 2 . Às vezes precisamos pular vários nós para o ponto certo para dividir, podemos ultrapassar o ponto certo se nos movermos comparando a string remanescente e os rótulos de caminho. Nesse caso, o link do sufixo será negligenciado sem intenção, se houver algum. Isso poderia ser evitado lembrando-se do ponto certo ao seguir em frente. O link de sufixo deve ser mantido se o nó de divisão já existir ou até mesmo o problema 1 ocorrer durante uma etapa de desdobramento.

Finalmente, minha implementação em Python é a seguinte:

Dicas: Inclui uma função de impressão de árvore ingênua no código acima, que é muito importante durante a depuração . Isso me poupou muito tempo e é conveniente para localizar casos especiais.


@jogojapan você trouxe uma explicação e visualização impressionantes. Mas como @makagonov mencionou que faltam algumas regras sobre a configuração de links de sufixo. É visível no bom caminho quando passo passo a passo em http://brenden.github.io/ukkonen-animation/ através da palavra 'aabaaabb'. Quando você passa da etapa 10 para a etapa 11, não há um link de sufixo do nó 5 para o nó 2, mas o ponto ativo se desloca de repente para lá.

@makagonov desde que eu vivo no mundo de Java Eu também tentei seguir sua implementação para entender o fluxo de trabalho do ST building, mas foi difícil para mim por causa de:

  • combinando arestas com nós
  • usando ponteiros de índice em vez de referências
  • quebra declarações;
  • continuar instruções;

Então acabei com essa implementação em Java, que espero que reflita todas as etapas de maneira mais clara e reduza o tempo de aprendizado para outras pessoas em Java:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class ST {

  public class Node {
    private final int id;
    private final Map<Character, Edge> edges;
    private Node slink;

    public Node(final int id) {
        this.id = id;
        this.edges = new HashMap<>();
    }

    public void setSlink(final Node slink) {
        this.slink = slink;
    }

    public Map<Character, Edge> getEdges() {
        return this.edges;
    }

    public Node getSlink() {
        return this.slink;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"id\"")
                .append(":")
                .append(this.id)
                .append(",")
                .append("\"slink\"")
                .append(":")
                .append(this.slink != null ? this.slink.id : null)
                .append(",")
                .append("\"edges\"")
                .append(":")
                .append(edgesToString(word))
                .append("}")
                .toString();
    }

    private StringBuilder edgesToString(final String word) {
        final StringBuilder edgesStringBuilder = new StringBuilder();
        edgesStringBuilder.append("{");
        for(final Map.Entry<Character, Edge> entry : this.edges.entrySet()) {
            edgesStringBuilder.append("\"")
                    .append(entry.getKey())
                    .append("\"")
                    .append(":")
                    .append(entry.getValue().toString(word))
                    .append(",");
        }
        if(!this.edges.isEmpty()) {
            edgesStringBuilder.deleteCharAt(edgesStringBuilder.length() - 1);
        }
        edgesStringBuilder.append("}");
        return edgesStringBuilder;
    }

    public boolean contains(final String word, final String suffix) {
        return !suffix.isEmpty()
                && this.edges.containsKey(suffix.charAt(0))
                && this.edges.get(suffix.charAt(0)).contains(word, suffix);
    }
  }

  public class Edge {
    private final int from;
    private final int to;
    private final Node next;

    public Edge(final int from, final int to, final Node next) {
        this.from = from;
        this.to = to;
        this.next = next;
    }

    public int getFrom() {
        return this.from;
    }

    public int getTo() {
        return this.to;
    }

    public Node getNext() {
        return this.next;
    }

    public int getLength() {
        return this.to - this.from;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"content\"")
                .append(":")
                .append("\"")
                .append(word.substring(this.from, this.to))
                .append("\"")
                .append(",")
                .append("\"next\"")
                .append(":")
                .append(this.next != null ? this.next.toString(word) : null)
                .append("}")
                .toString();
    }

    public boolean contains(final String word, final String suffix) {
        if(this.next == null) {
            return word.substring(this.from, this.to).equals(suffix);
        }
        return suffix.startsWith(word.substring(this.from,
                this.to)) && this.next.contains(word, suffix.substring(this.to - this.from));
    }
  }

  public class ActivePoint {
    private final Node activeNode;
    private final Character activeEdgeFirstCharacter;
    private final int activeLength;

    public ActivePoint(final Node activeNode,
                       final Character activeEdgeFirstCharacter,
                       final int activeLength) {
        this.activeNode = activeNode;
        this.activeEdgeFirstCharacter = activeEdgeFirstCharacter;
        this.activeLength = activeLength;
    }

    private Edge getActiveEdge() {
        return this.activeNode.getEdges().get(this.activeEdgeFirstCharacter);
    }

    public boolean pointsToActiveNode() {
        return this.activeLength == 0;
    }

    public boolean activeNodeIs(final Node node) {
        return this.activeNode == node;
    }

    public boolean activeNodeHasEdgeStartingWith(final char character) {
        return this.activeNode.getEdges().containsKey(character);
    }

    public boolean activeNodeHasSlink() {
        return this.activeNode.getSlink() != null;
    }

    public boolean pointsToOnActiveEdge(final String word, final char character) {
        return word.charAt(this.getActiveEdge().getFrom() + this.activeLength) == character;
    }

    public boolean pointsToTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() == this.activeLength;
    }

    public boolean pointsAfterTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() < this.activeLength;
    }

    public ActivePoint moveToEdgeStartingWithAndByOne(final char character) {
        return new ActivePoint(this.activeNode, character, 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge() {
        return new ActivePoint(this.getActiveEdge().getNext(), null, 0);
    }

    public ActivePoint moveToSlink() {
        return new ActivePoint(this.activeNode.getSlink(),
                this.activeEdgeFirstCharacter,
                this.activeLength);
    }

    public ActivePoint moveTo(final Node node) {
        return new ActivePoint(node, this.activeEdgeFirstCharacter, this.activeLength);
    }

    public ActivePoint moveByOneCharacter() {
        return new ActivePoint(this.activeNode,
                this.activeEdgeFirstCharacter,
                this.activeLength + 1);
    }

    public ActivePoint moveToEdgeStartingWithAndByActiveLengthMinusOne(final Node node,
                                                                       final char character) {
        return new ActivePoint(node, character, this.activeLength - 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge(final String word, final int index) {
        return new ActivePoint(this.getActiveEdge().getNext(),
                word.charAt(index - this.activeLength + this.getActiveEdge().getLength()),
                this.activeLength - this.getActiveEdge().getLength());
    }

    public void addEdgeToActiveNode(final char character, final Edge edge) {
        this.activeNode.getEdges().put(character, edge);
    }

    public void splitActiveEdge(final String word,
                                final Node nodeToAdd,
                                final int index,
                                final char character) {
        final Edge activeEdgeToSplit = this.getActiveEdge();
        final Edge splittedEdge = new Edge(activeEdgeToSplit.getFrom(),
                activeEdgeToSplit.getFrom() + this.activeLength,
                nodeToAdd);
        nodeToAdd.getEdges().put(word.charAt(activeEdgeToSplit.getFrom() + this.activeLength),
                new Edge(activeEdgeToSplit.getFrom() + this.activeLength,
                        activeEdgeToSplit.getTo(),
                        activeEdgeToSplit.getNext()));
        nodeToAdd.getEdges().put(character, new Edge(index, word.length(), null));
        this.activeNode.getEdges().put(this.activeEdgeFirstCharacter, splittedEdge);
    }

    public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode,
                           final Node node) {
        if(previouslyAddedNodeOrAddedEdgeNode != null) {
            previouslyAddedNodeOrAddedEdgeNode.setSlink(node);
        }
        return node;
    }

    public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) {
        return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode);
    }
  }

  private static int idGenerator;

  private final String word;
  private final Node root;
  private ActivePoint activePoint;
  private int remainder;

  public ST(final String word) {
    this.word = word;
    this.root = new Node(idGenerator++);
    this.activePoint = new ActivePoint(this.root, null, 0);
    this.remainder = 0;
    build();
  }

  private void build() {
    for(int i = 0; i < this.word.length(); i++) {
        add(i, this.word.charAt(i));
    }
  }

  private void add(final int index, final char character) {
    this.remainder++;
    boolean characterFoundInTheTree = false;
    Node previouslyAddedNodeOrAddedEdgeNode = null;
    while(!characterFoundInTheTree && this.remainder > 0) {
        if(this.activePoint.pointsToActiveNode()) {
            if(this.activePoint.activeNodeHasEdgeStartingWith(character)) {
                activeNodeHasEdgeStartingWithCharacter(character, previouslyAddedNodeOrAddedEdgeNode);
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    rootNodeHasNotEdgeStartingWithCharacter(index, character);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithCharacter(index,
                            character, previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
        else {
            if(this.activePoint.pointsToOnActiveEdge(this.word, character)) {
                activeEdgeHasCharacter();
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
    }
  }

  private void activeNodeHasEdgeStartingWithCharacter(final char character,
                                                    final Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(character);
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private void rootNodeHasNotEdgeStartingWithCharacter(final int index, final char character) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    this.activePoint = this.activePoint.moveTo(this.root);
    this.remainder--;
    assert this.remainder == 0;
  }

  private Node internalNodeHasNotEdgeStartingWithCharacter(final int index,
                                                         final char character,
                                                         Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private void activeEdgeHasCharacter() {
    this.activePoint = this.activePoint.moveByOneCharacter();
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private Node edgeFromRootNodeHasNotCharacter(final int index,
                                             final char character,
                                             Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByActiveLengthMinusOne(this.root,
            this.word.charAt(index - this.remainder + 2));
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private Node edgeFromInternalNodeHasNotCharacter(final int index,
                                                 final char character,
                                                 Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private ActivePoint walkDown(final int index) {
    while(!this.activePoint.pointsToActiveNode()
            && (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) {
        if(this.activePoint.pointsAfterTheEndOfActiveEdge()) {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.word, index);
        }
        else {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
        }
    }
    return this.activePoint;
  }

  public String toString(final String word) {
    return this.root.toString(word);
  }

  public boolean contains(final String suffix) {
    return this.root.contains(this.word, suffix);
  }

  public static void main(final String[] args) {
    final String[] words = {
            "abcabcabc$",
            "abc$",
            "abcabxabcd$",
            "abcabxabda$",
            "abcabxad$",
            "aabaaabb$",
            "aababcabcd$",
            "ababcabcd$",
            "abccba$",
            "mississipi$",
            "abacabadabacabae$",
            "abcabcd$",
            "00132220$"
    };
    Arrays.stream(words).forEach(word -> {
        System.out.println("Building suffix tree for word: " + word);
        final ST suffixTree = new ST(word);
        System.out.println("Suffix tree: " + suffixTree.toString(word));
        for(int i = 0; i < word.length() - 1; i++) {
            assert suffixTree.contains(word.substring(i)) : word.substring(i);
        }
    });
  }
}




suffix-tree