Algoritmo de tree de sufixos de Ukkonen em inglês claro

Eu me sinto um pouco grosso neste momento. Eu passei dias tentando envolver minha mente com a construção de tree 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 diversos 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 à tree
  • Para adicionar o sufixo S à tree, 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, apesar de eu achar 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 variables ​​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 trees 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 debugging.

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

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 outras bordas saindo delas, e assim por diante

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

Principio básico

Gostaria de demonstrar primeiro como criar a tree 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).

Então, começamos a partir da esquerda , e primeiro inserimos apenas o caractere único 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 subcadeia 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 tree 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 objective 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

insira a descrição da imagem aqui

E o que isso significa é:

Nós observamos duas coisas:

  • A representação de borda para ab é a mesma que costumava estar na tree 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 pointers no texto, independentemente de quantos caracteres ele representa.

Em seguida, incrementamos a posição novamente e atualizamos a tree 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 tree é a tree 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 tree 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 variables (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 tree. 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 tree , a tree em si não é alterada (apenas atualizamos o ponto ativo e o remainder ). A tree não é mais uma representação precisa da tree 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 variables ​​(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 tree 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 tree. 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 tree, todo sufixo dele (incluindo b ) deve estar na tree também. Talvez apenas implicitamente , mas deve estar lá, por causa da maneira como construímos a tree até agora.

Continuamos para o passo 6 incrementando # . A tree é 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 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 label 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 label 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 charts. O novo sufixo link fez com que o ponto reorganizasse as bordas existentes, portanto, verifique cuidadosamente 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 e b) com o caractere 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 tree 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 tree de sufixos concluída para procurar por sufixos, devemos aceitar as correspondências apenas se elas terminarem em uma folha . Caso contrário, obteríamos muitas correspondências espúrias, porque há muitas cadeias implicitamente contidas na tree 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 tree 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 sumrmos o cifrão). Em cada passo nós não fazemos nada (além de atualizar as variables), 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 nós 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 tree. 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 ajustes posteriores ao nó ativo após seguir um sufixo podem ser O (n) também?

Não. A razão é 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 sufixo link, 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 sum 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 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 tree 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 tree, a tree 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 à tree já está na borda, nós, de acordo com a Observation 1 , atualizamos apenas active point e o remainder , deixando a tree 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 tree 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 à tree, poderíamos omitir a adição de alguns nós à tree 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 à tree, 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. Esse 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 variables ​​adicionais para manter essa informação.

    insira a descrição da imagem aqui

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 labels 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:

  • Python

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

Minha intuição é a seguinte:

Depois de k iterações do loop principal, você construiu uma tree de sufixos que contém todos os sufixos da string completa que começa nos primeiros caracteres k.

No início, isso significa que a tree de sufixos contém um único nó raiz que representa a cadeia inteira (esse é o único sufixo que inicia em 0).

Após as iterações do len (string) você tem uma tree de sufixos que contém todos os sufixos.

Durante o loop, a chave é o ponto ativo. Meu palpite é que isso representa o ponto mais profundo da tree de sufixos que corresponde a um sufixo apropriado dos primeiros caracteres k da string. (Eu acho que apropriado significa que o sufixo não pode ser a string inteira.)

Por exemplo, suponha que você tenha visto caracteres ‘abcabc’. O ponto ativo representaria o ponto na tree correspondente ao sufixo ‘abc’.

O ponto ativo é representado por (origem, primeiro, último). Isso significa que você está atualmente no ponto da tree que você começa, iniciando na origem do nó e, em seguida, alimentando os caracteres em string [first: last]

Quando você adiciona um novo caractere, procura ver se o ponto ativo ainda está na tree existente. Se é então você está feito. Otherwise you need to add a new node to the suffix tree at the active point, fallback to the next shortest match, and check again.

Note 1: The suffix pointers give a link to the next shortest match for each node.

Note 2: When you add a new node and fallback you add a new suffix pointer for the new node. The destination for this suffix pointer will be the node at the shortened active point. This node will either already exist, or be created on the next iteration of this fallback loop.

Note 3: The canonization part simply saves time in checking the active point. For example, suppose you always used origin=0, and just changed first and last. To check the active point you would have to follow the suffix tree each time along all the intermediate nodes. It makes sense to cache the result of following this path by recording just the distance from the last node.

Can you give a code example of what you mean by “fix” bounding variables?

Health warning: I also found this algorithm particularly hard to understand so please realise that this intuition is likely to be incorrect in all important details…

Hi i have tried to implement the above explained implementation in ruby , please check it out. it seems to work fine.

the only difference in the implementation is that , i have tried to use the edge object instead of just using symbols.

its also present at https://gist.github.com/suchitpuri/9304856

  require 'pry' class Edge attr_accessor :data , :edges , :suffix_link def initialize data @data = data @edges = [] @suffix_link = nil end def find_edge element self.edges.each do |edge| return edge if edge.data.start_with? element end return nil end end class SuffixTrees attr_accessor :root , :active_point , :remainder , :pending_prefixes , :last_split_edge , :remainder def initialize @root = Edge.new nil @active_point = { active_node: @root , active_edge: nil , active_length: 0} @remainder = 0 @pending_prefixes = [] @last_split_edge = nil @remainder = 1 end def build string string.split("").each_with_index do |element , index| add_to_edges @root , element update_pending_prefix element add_pending_elements_to_tree element active_length = @active_point[:active_length] # if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data[0..active_length-1] == @active_point[:active_edge].data[active_length..@active_point[:active_edge].data.length-1]) # @active_point[:active_edge].data = @active_point[:active_edge].data[0..active_length-1] # @active_point[:active_edge].edges << Edge.new(@active_point[:active_edge].data) # end if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data.length == @active_point[:active_length] ) @active_point[:active_node] = @active_point[:active_edge] @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) @active_point[:active_length] = 0 end end end def add_pending_elements_to_tree element to_be_deleted = [] update_active_length = false # binding.pry if( @active_point[:active_node].find_edge(element[0]) != nil) @active_point[:active_length] = @active_point[:active_length] + 1 @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) if @active_point[:active_edge] == nil @remainder = @remainder + 1 return end @pending_prefixes.each_with_index do |pending_prefix , index| # binding.pry if @active_point[:active_edge] == nil and @active_point[:active_node].find_edge(element[0]) == nil @active_point[:active_node].edges << Edge.new(element) else @active_point[:active_edge] = node.find_edge(element[0]) if @active_point[:active_edge] == nil data = @active_point[:active_edge].data data = data.split("") location = @active_point[:active_length] # binding.pry if(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element) != nil ) else #tree split split_edge data , index , element end end end end def update_pending_prefix element if @active_point[:active_edge] == nil @pending_prefixes = [element] return end @pending_prefixes = [] length = @active_point[:active_edge].data.length data = @active_point[:active_edge].data @remainder.times do |ctr| @pending_prefixes << data[-(ctr+1)..data.length-1] end @pending_prefixes.reverse! end def split_edge data , index , element location = @active_point[:active_length] old_edges = [] internal_node = (@active_point[:active_edge].edges != nil) if (internal_node) old_edges = @active_point[:active_edge].edges @active_point[:active_edge].edges = [] end @active_point[:active_edge].data = data[0..location-1].join @active_point[:active_edge].edges << Edge.new(data[location..data.size].join) if internal_node @active_point[:active_edge].edges << Edge.new(element) else @active_point[:active_edge].edges << Edge.new(data.last) end if internal_node @active_point[:active_edge].edges[0].edges = old_edges end #setup the suffix link if @last_split_edge != nil and @last_split_edge.data.end_with?@active_point[:active_edge].data @last_split_edge.suffix_link = @active_point[:active_edge] end @last_split_edge = @active_point[:active_edge] update_active_point index end def update_active_point index if(@active_point[:active_node] == @root) @active_point[:active_length] = @active_point[:active_length] - 1 @remainder = @remainder - 1 @active_point[:active_edge] = @active_point[:active_node].find_edge(@pending_prefixes.first[index+1]) else if @active_point[:active_node].suffix_link != nil @active_point[:active_node] = @active_point[:active_node].suffix_link else @active_point[:active_node] = @root end @active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0]) @remainder = @remainder - 1 end end def add_to_edges root , element return if root == nil root.data = root.data + element if(root.data and root.edges.size == 0) root.edges.each do |edge| add_to_edges edge , element end end end suffix_tree = SuffixTrees.new suffix_tree.build("abcabxabcd") binding.pry 

@jogojapan you brought awesome explanation and visualisation. But as @makagonov mentioned it’s missing some rules regarding setting suffix links. It’s visible in nice way when going step by step on http://brenden.github.io/ukkonen-animation/ through word ‘aabaaabb’. When you go from step 10 to step 11, there is no suffix link from node 5 to node 2 but active point suddenly moves there.

@makagonov since I live in Java world I also tried to follow your implementation to grasp ST building workflow but it was hard to me because of:

  • combining edges with nodes
  • using index pointers instead of references
  • breaks statements;
  • continue statements;

So I ended up with such implementation in Java which I hope reflects all steps in clearer way and will reduce learning time for other Java people:

 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 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 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 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); } }); } }