Algoritmo de árvore de sufixos de Ukkonen em inglês comum

Eu me sinto um pouco grossa neste momento. Passei dias tentando entender completamente a construção de árvores com sufixos, mas como não tenho formação matemática, muitas das explicações me iludem quando começam a fazer uso excessivo da simbologia matemática. A mais próxima de uma boa explicação que encontrei é a Pesquisa Rápida de Cordas com Árvores de Sufixo , mas ele encobre vários pontos e alguns aspectos do algoritmo permanecem obscuros.

Uma explicação passo a passo desse 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

Meu entendimento básico, até agora:

• Eu preciso percorrer cada prefixo P de uma determinada string T
• Eu preciso percorrer cada sufixo S no prefixo P e adicioná-lo à árvore
• Para adicionar o sufixo S à árvore, preciso percorrer cada caractere em S, com as iterações consistindo em percorrer um ramo existente que começa com o mesmo conjunto de caracteres C em S e potencialmente dividir uma borda em nós descendentes quando I alcance um caractere diferente no sufixo, OU se não houver uma borda correspondente para descer. Quando nenhuma borda correspondente é encontrada para descer para C, uma nova borda da folha é criada para C.

O algoritmo básico parece ser O (n ² ), como é indicado na maioria das explicações, pois precisamos percorrer todos os prefixos e, em seguida, percorrer cada um dos sufixos de cada prefixo. O algoritmo de Ukkonen é aparentemente único por causa da técnica de ponteiro de sufixo que ele usa, embora eu ache que é isso que estou tendo problemas para entender.

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 eu vi precisam "consertar" variáveis ​​delimitadoras que elas estão usando

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

https://gist.github.com/2373868

Atualização 2017-11-04

Depois de muitos anos, encontrei um novo uso para árvores de sufixo e implementei o algoritmo em JavaScript . A essência está abaixo. Deve estar livre de erros. Coloque-o em um arquivo js, npm install chalkno mesmo local e execute com o node.js para ver uma saída colorida. Há uma versão simplificada no mesmo Gist, sem nenhum código de depuração.

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

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

Primeiro, algumas declarações preliminares.

1. O que estamos construindo é basicamente como um trie de pesquisa. Portanto, há um nó raiz, arestas saindo dele levando a novos nós, e outras arestas saindo deles, e assim por diante

2. Mas : diferentemente de uma pesquisa, os rótulos de borda não são caracteres únicos. Em vez disso, cada extremidade é rotulada usando um par de números inteiros [from,to]. Estes são indicadores para o texto. Nesse sentido, cada aresta carrega uma etiqueta de comprimento arbitrário, mas ocupa apenas O (1) de espaço (dois ponteiros).

Principio básico

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

abc

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

Assim, começamos da esquerda e primeiro inserimos apenas o caractere único a, criando uma aresta 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 significar o final atual , que está na posição 1 (logo após a).

Portanto, temos uma árvore inicial, que se parece com isso:

E o que isso significa é o seguinte:

Agora, avançamos 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

• expandindo a amargem existente paraab
• inserir uma nova aresta para b

Em nossa representação, isso parece

E o que isso significa é:

Observamos duas coisas:

• A representação borda para abé a mesma , uma vez que usada para estar na árvore inicial: [0,#]. Seu significado mudou automaticamente porque atualizamos a posição atual #de 1 para 2.
• Cada borda consome 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 ca 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 é o sufixo correto até a posição atual após cada etapa
• Existem tantas etapas quanto caracteres no texto
• A quantidade de trabalho em cada etapa é O (1), porque todas as arestas existentes são atualizadas automaticamente incrementando #e a inserção de uma nova aresta para o caractere final pode ser feita em O (1). Portanto, para uma sequência de comprimento n, apenas o tempo O (n) é necessário.

Primeira extensão: repetições simples

É claro que isso funciona tão bem apenas porque nossa string não contém repetições. Agora, olhamos para uma sequência mais realista:

abcabxabcd

Começa com abccomo no exemplo anterior, depois abé repetido e seguido por xe, em seguida, abcé repetido seguido por d.

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

Etapa 4: passamos #para a posição 4. Isso atualiza implicitamente todas as arestas existentes para isso:

e precisamos inserir o sufixo final da etapa atual,, ana raiz.

Antes de fazer isso, apresentamos mais duas variáveis (além de #), que obviamente estão lá o tempo todo, mas ainda não as usamos:

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

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

• No abcexemplo simples , o ponto ativo era sempre (root,'\0x',0), ou seja, active_nodeera o nó raiz, active_edgeera especificado como o caractere nulo '\0x'e active_lengthera zero. O efeito disso foi que a única nova borda que inserimos em todas as etapas foi inserida no nó raiz como uma nova borda criada. Veremos em breve por que um triplo é necessário para representar essa informação.
• O remaindersempre foi definido como 1 no início de cada etapa. O significado disso era 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 inserir o caractere final atual ana raiz, notamos que já existe uma extremidade de saída começando com a, especificamente: abca. Aqui está o que fazemos nesse caso:

• Nós não inserir uma borda fresca [4,#]no nó raiz. Em vez disso, simplesmente notamos que o sufixo ajá está em nossa árvore. Termina no meio de uma borda mais longa, mas não nos incomodamos com isso. Apenas deixamos as coisas do jeito que são.
• Definimos o ponto ativo como (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 a, especificamente, após a posição 1 nessa borda. Percebemos que a aresta é especificada simplesmente por seu primeiro caractere a. Isso é suficiente, pois só pode haver uma aresta começando com qualquer caractere em particular (confirme se isso é verdade depois de ler toda a descrição).
• Também incrementamos remainder, portanto, no início 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 (atualizamos apenas o ponto ativo e 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 aestá implicitamente contido ). Portanto, além de atualizar as variáveis ​​(todas com comprimento fixo, portanto é O (1)), não houve trabalho realizado nesta etapa.

Etapa 5: atualizamos a posição atual #para 5. Isso atualiza automaticamente a árvore para isso:

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

• O asufixo da etapa anterior nunca foi inserido corretamente. Portanto, permaneceu e, desde que avançamos um passo, passou de apara ab.
• E precisamos inserir a nova aresta final b.

Na prática, isso significa que vamos ao ponto ativo (que aponta atrás do aque agora é a abcabaresta) e inserimos o caractere final atual b. Mas: Novamente, acontece que btambém já está presente nessa mesma extremidade.

Então, novamente, não mudamos a árvore. Simplesmente:

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

Para ficar claro: tivemos que inserir abe bna etapa atual, mas como abjá foi encontrado, atualizamos o ponto ativo e nem tentamos inserir b. Por quê? Porque se abestá na árvore, todo sufixo (inclusive b) deve estar na árvore também. Talvez apenas implicitamente , mas deve estar lá, devido à maneira como construímos a árvore até agora.

Prosseguimos para a etapa 6 incrementando #. A árvore é atualizada automaticamente para:

Porque remainderé de 3 , temos que inserir abx, bxe x. O ponto ativo nos diz onde abtermina, então precisamos apenas pular lá e inserir o x. Na verdade, xainda não existe, então dividimos a abcabxborda e inserimos um nó interno:

As representações de arestas ainda são ponteiros para o texto, portanto, a divisão e a inserção de um nó interno podem ser feitas no tempo O (1).

Então, lidamos com abxe diminuímos remainderpara 2. Agora precisamos inserir o próximo sufixo restante bx,. Mas antes de fazer isso, precisamos atualizar o ponto ativo. A regra para isso, depois de dividir e inserir uma aresta, será chamada Regra 1 abaixo e será aplicada sempre que active_nodefor raiz (aprenderemos a regra 3 para outros casos mais adiante). 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

Portanto, o novo ponto triplo ativo (root,'b',1)indica que a próxima inserção deve ser feita na bcabxborda, atrás de 1 caractere, ou seja, atrás b. Podemos identificar o ponto de inserção no tempo O (1) e verificar se xjá está presente ou não. Se estivesse presente, encerraríamos a etapa atual e deixaríamos tudo do jeito que está. Como x não está presente, inserimos-o dividindo a borda:

Novamente, isso levou tempo O (1) e atualizamos remainderpara 1 e o ponto ativo para a (root,'x',0)regra 1.

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, conectaremos o nó inserido anteriormente e o novo nó através de um ponteiro especial, um link de sufixo . Veremos depois por que isso é útil. Aqui está o que obtemos: o link do sufixo é representado como uma borda pontilhada:

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

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

Prosseguimos para a etapa 7 configurando #= 7, que anexa automaticamente o próximo caractere a, a todas as bordas das folhas, como sempre. Em seguida, tentamos inserir o novo caractere final no ponto ativo (a raiz) e descobrimos que ele já está lá. Portanto, finalizamos a etapa atual sem inserir nada e atualizamos o ponto ativo para (root,'a',1).

Na etapa 8 , #= 8, acrescentamos be, como visto anteriormente, isso significa apenas que atualizamos o ponto ativo (root,'a',2)e aumentamos remaindersem fazer mais nada, porque bjá está presente. No entanto, notamos (no tempo O (1)) que o ponto ativo está agora no final de uma aresta. Nós refletimos isso redefinindo-o para (node1,'\0x',0). Aqui, eu uso node1para me referir ao nó interno no qual a abborda termina.

Então, na etapa #= 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 é anexada cautomaticamente às bordas das folhas e vamos ao ponto ativo para ver se podemos inserir 'c'. Acontece que 'c' já existe nessa extremidade, portanto, definimos o ponto ativo como (node1,'c',1), incrementamos remaindere não fazemos mais nada.

Agora, na etapa #= 10 , remainderé 4 e, portanto, precisamos primeiro inserir abcd(o que resta de 3 etapas atrás) inserindo dno ponto ativo.

Tentar inserir dno ponto ativo causa uma divisão da aresta no tempo O (1):

A active_nodepartir da qual a divisão foi iniciada está marcada em vermelho acima. Aqui está a regra final, Regra 3:

Depois de dividir uma aresta de um active_nodeque não é o nó raiz, seguimos o link do sufixo saindo desse nó, se houver algum, e redefinimos o active_nodepara o nó para o qual ele aponta. Se não houver link de sufixo, configuramos o active_nodepara a raiz. active_edge e active_lengthpermanecer inalterado.

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

Como a inserção de abcdestá concluída, decrementamos remainderpara 3 e consideramos o próximo sufixo restante da etapa atual bcd,. A regra 3 definiu o ponto ativo como o nó e a aresta certos, para que a inserção bcdpossa ser feita simplesmente inserindo seu caractere final dno ponto ativo.

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: 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 o nó no rótulo abestá vinculado ao nó em b(seu sufixo) e o nó em abcestá vinculado bc.

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

Daí a próxima inserção ocorre na uma extremidade de saída do nó raiz cuja começa etiqueta com c: cabxabcd, atrás do primeiro caractere, ou seja, por trás 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 link de sufixo fez com que o ponto reorganizasse as arestas existentes; portanto, verifique cuidadosamente para confirmar que a única coisa que foi inserida acima é um novo link de sufixo.)

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

Essa foi a etapa final e estamos prontos. Há um número de observações finais , no entanto:

• Em cada passo, avançamos #uma posição. Isso atualiza automaticamente todos os nós folha no tempo O (1).

• Mas não lida com a) quaisquer sufixos restantes das etapas anteriores eb) com o único caractere final da etapa atual.

• remaindernos diz quantas inserções adicionais precisamos fazer. Essas inserções correspondem um a um aos sufixos finais da sequência 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ê? Como os outros caracteres estão contidos implicitamente (caso contrário, o ponto ativo não estaria onde está).

• Após cada inserção, decrementamos remaindere seguimos o link do sufixo, se houver algum. Caso contrário, vamos para a raiz (regra 3). Se já estamos na raiz, modificamos o ponto ativo usando a regra 1. De qualquer forma, leva apenas O (1) tempo.

• Se, durante uma dessas inserções, descobrirmos que o caractere que deseja inserir já existe, não fazemos nada e encerramos a etapa atual, mesmo que remainder> 0. O motivo é que todas as inserções restantes serão sufixos da que acabamos de tentar fazer. Portanto, eles estão todos implícitos na árvore atual. O fato de que remainder> 0 garante que lidemos com os sufixos restantes posteriormente.

• E se no final do algoritmo remainder> 0? Este será o caso sempre que o final do texto for uma substring que ocorreu em algum lugar antes. Nesse caso, devemos acrescentar um caractere extra no final da string que não ocorreu 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 completa para procurar sufixos, devemos aceitar correspondências somente se elas terminarem em uma folha . Caso contrário, teríamos muitas correspondências falsas, porque existem muitas seqüências implicitamente contidas na árvore que não são sufixos reais da cadeia principal. Forçarremainderser 0 no final é essencialmente uma maneira de garantir que todos os sufixos terminem em um nó folha. No entanto, se queremos usar a árvore para procurar substrings 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, obviamente haverá n etapas (ou n + 1 se adicionarmos o cifrão). Em cada etapa, não fazemos nada (além de atualizar as variáveis) ou fazemos remainderinserções, cada uma levando tempo O (1). Como remainderindica quantas vezes não fizemos nada nas etapas anteriores e é diminuído 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 que sigamos um link de sufixo, atualizemos o ponto ativo e depois descubram que seu active_lengthcomponente 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 (red,'d',3), para que ele aponte para o local atrás fda defgborda. Agora suponha que fizemos as atualizações necessárias e agora siga o link do sufixo para atualizar o ponto ativo de acordo com a regra 3. O novo ponto ativo é (green,'d',3). No entanto, a dborda que sai do nó verde é de, portanto, possui apenas 2 caracteres. Para encontrar o ponto ativo correto, obviamente precisamos seguir essa borda até o nó azul e redefinir para (blue,'f',1).

Em um caso particularmente ruim, active_lengthpode ser tão grande quanto 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 pular um nó interno, mas talvez muitos, até n no pior caso. Isso significa que o algoritmo tem uma complexidade O (n ² ) oculta , porque em cada etapa remaindergeralmente é O (n), e os pós-ajustes no nó ativo após seguir um link de sufixo também podem ser O (n)?

Não. O motivo é que, se tivermos de ajustar o ponto ativo (por exemplo, de verde para azul como acima), isso nos leva a um novo nó que possui seu próprio link de sufixo e active_lengthserá reduzido. À medida que seguimos a cadeia de links de sufixos, fazemos as inserções restantes, active_lengthsó podemos diminuir e o número de ajustes de pontos ativos que podemos fazer no caminho não pode ser maior do que active_lengthem um determinado momento. Como active_lengthnunca pode ser maior que remainder, e remainder é O (n), não apenas em cada etapa, mas a soma total de incrementos já feitos ao remainderlongo de todo o processo é O (n) também, o número de ajustes de pontos ativos é também delimitada por O (n).

Tentei implementar a Árvore de Sufixo com a abordagem dada na resposta do jogojapan, mas não funcionou em alguns casos devido ao uso das regras. Além disso, mencionei que ninguém conseguiu implementar uma árvore de sufixos absolutamente correta usando essa abordagem. Abaixo, escreverei uma "visão geral" da resposta do jogojapan com algumas modificações nas regras. Também descreverei o caso em que esquecemos de criar links importantes de sufixos.

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 nossa palavra é 'abcaabca' e o restante = 3, significa que devemos processar três últimos sufixos: bca , ca e a .

Vamos usar o conceito de 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 pointe remainder).

Observação 2

Se, em algum momento, active_lengthfor maior ou igual ao comprimento da aresta atual ( edge_length), movemos nossa active pointseta para baixo até que edge_lengthseja estritamente maior que active_length.

Agora, vamos redefinir as regras:

Regra 1

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

1. nó ativo não é alterado
2. comprimento ativo é diminuído
3. a 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 criar um insersor a partir de um nó interno , e este não for o primeiro SUCH nó interno na etapa atual, vincularemos o nó SUCH anterior a ESTE através de um link de sufixo .

Essa definição de Rule 2é diferente de jogojapan ', pois aqui levamos em consideração não apenas os nós internos recém-criados , mas também os nós internos, 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 maneira, a borda ativa e o comprimento ativo permanecem inalterados.

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

E finalmente, observação 3:

Quando o símbolo que queremos adicionar à árvore já estiver no limite, de acordo com Observation 1, atualizamos apenas active pointe remainder, deixando a árvore inalterada. MAS, se houver um nó interno marcado como necessitando de link de sufixo , devemos conectar esse nó à nossa corrente active nodepor 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ão 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 :

   

2. Se nós FAZER conectar os nós através de um link 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, existem mais dois links de sufixo. Mas esses links de sufixo estão corretos , e um deles - do nó azul ao vermelho - é muito importante para a nossa abordagem com ponto ativo . O problema é que, se não colocarmos um link de sufixo aqui, mais tarde, quando adicionarmos novas letras à árvore, poderemos omitir a adição de alguns nós à árvore devido a Rule 3, porque, de acordo com ela, se não houver um link de sufixo, então devemos colocar o active_nodena 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 denominada 'c' ). Como houve uma inserção do nó azul, nós a marcamos como necessitando de um link de sufixo . Então, contando com a abordagem do ponto ativo , o valor active nodefoi definido no nó vermelho. Mas não fazemos uma inserção a partir do nó vermelho, pois 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 ao vermelho através de um link de sufixo. Por que isso está correto? Porque o ponto ativoEssa abordagem garante que chegamos ao lugar certo, ou seja, ao próximo local onde devemos processar uma inserção de um sufixo mais curto .

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

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 Árvore de Sufixo.

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

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

1. Terminar comRemainder > 0 Acontece que essa situação também pode acontecer durante a etapa de desenvolvimento , não apenas no final de todo o algoritmo. Quando isso acontece, podemos deixar inalterados o restante, o nó de atuação, o comprimento de ação e o comprimento de ato , encerrar a etapa atual de desdobramento e iniciar outra etapa, continuando a dobrar ou desdobrar, dependendo se o próximo caractere na sequência original estiver no caminho atual ou não.

2. Salto sobre nós: quando seguimos um link de sufixo, atualize o ponto ativo e, em seguida, descubra 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 a movimentação, o comprimento do ato e o comprimento da haste continuam mudando completamente; quando você precisa voltar para o nó raiz , o comprimento da haste e o comprimento do comprimento podem estar errados por causa desses movimentos. Precisamos de variáveis ​​adicionais para manter essas informações.

   

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

3. A divisão pode se deteriorar Ao tentar dividir uma aresta, em algum momento você encontrará a operação de divisão diretamente no 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.

4. Links de sufixo ocultos Há outro caso especial 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 avançarmos comparando a string restante e os rótulos dos caminhos. Nesse caso, o link do sufixo será negligenciado acidentalmente, se houver algum. Isso pode ser evitado lembrando-se do ponto certo ao avançar. O link do sufixo deve ser mantido se o nó de divisão já existir ou o problema 1 ocorrer durante uma etapa de desenvolvimento.

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

• Pitão

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

Desculpas se minha resposta parecer redundante, mas eu implementei o algoritmo de Ukkonen recentemente e me vi lutando com ele por dias; Eu tive que ler vários artigos sobre o assunto para entender o porquê e como de alguns aspectos centrais do algoritmo.

Achei a abordagem de 'regras' das respostas anteriores inútil para entender os motivos subjacentes ; por isso, escrevi tudo abaixo focando apenas na pragmática. Se você se esforçou para seguir outras explicações, assim como eu, talvez minha explicação suplementar faça com que ela seja um 'clique' para você.

Publiquei minha implementação em C # aqui: https://github.com/baratgabor/SuffixTree

Observe que eu não sou especialista neste assunto; portanto, as seções a seguir podem conter imprecisões (ou coisa pior). Se você encontrar algum, sinta-se à vontade para editar.

Pré-requisitos

O ponto de partida da explicação a seguir pressupõe que você esteja familiarizado com o conteúdo e o uso de árvores de sufixos e as características do algoritmo de Ukkonen, por exemplo, como você está estendendo o caractere da árvore de sufixos por caractere, do início ao fim. Basicamente, suponho que você já tenha lido algumas das outras explicações.

(No entanto, eu tive que adicionar uma narrativa básica para o fluxo, para que o começo possa parecer redundante.)

A parte mais interessante é a explicação sobre a diferença entre usar links de sufixo e redigitalizar a partir da raiz . Isso foi o que me deu muitos bugs e dores de cabeça na minha implementação.

Nós folha abertos e suas limitações

Tenho certeza que você já sabe que o 'truque' mais fundamental é perceber que podemos deixar o final dos sufixos 'aberto', ou seja, referenciar o comprimento atual da string em vez de definir o final para um valor estático. Dessa forma, quando adicionarmos caracteres adicionais, esses caracteres serão implicitamente adicionados a todos os rótulos de sufixo, sem a necessidade de visitar e atualizar todos eles.

Mas esse final aberto de sufixos - por razões óbvias - funciona apenas para nós que representam o final da string, ou seja, os nós das folhas na estrutura da árvore. As operações de ramificação que executamos na árvore (a adição de novos nós de ramificação e nós de folha) não se propagam automaticamente em todos os lugares que precisam.

Provavelmente é elementar, e não exigiria menção, que substrings repetidos não apareçam explicitamente na árvore, já que a árvore já os contém em virtude de serem repetições; no entanto, quando a substring repetitiva termina encontrando um caractere não repetitivo, precisamos criar uma ramificação nesse ponto para representar a divergência a partir desse ponto em diante.

Por exemplo, no caso da string 'ABCXABCY' (veja abaixo), uma ramificação para X e Y precisa ser adicionada a três sufixos diferentes, ABC , BC e C ; caso contrário, não seria uma árvore de sufixos válida e não poderíamos encontrar todas as substrings da string combinando caracteres da raiz para baixo.

Mais uma vez, para enfatizar - qualquer operação que executamos em um sufixo na árvore também precisa ser refletida por seus sufixos consecutivos (por exemplo, ABC> BC> C); caso contrário, eles simplesmente deixam de ser sufixos válidos.

Mas mesmo se aceitarmos que precisamos fazer essas atualizações manuais, como sabemos quantos sufixos precisam ser atualizados? Como, quando adicionamos o caractere repetido A (e o restante dos caracteres repetidos em sucessão), ainda não temos idéia de quando / onde precisamos dividir o sufixo em dois ramos. A necessidade de dividir é verificada apenas quando encontramos o primeiro caractere não repetitivo, neste caso, Y (em vez do X que já existe na árvore).

O que podemos fazer é corresponder à string mais longa repetida que pudermos e contar quantos sufixos precisamos atualizar posteriormente. É isso que significa "restante" .

O conceito de "restante" e "nova verificação"

A variável remaindernos diz quantos caracteres repetidos adicionamos implicitamente, sem ramificação; ou seja, quantos sufixos precisamos visitar para repetir a operação de ramificação depois que encontramos o primeiro caractere que não podemos corresponder. Isso é essencialmente igual a quantos caracteres 'profundos' estamos na árvore desde a raiz.

Portanto, permanecendo no exemplo anterior da sequência ABCXABCY , correspondemos a parte ABC repetida 'implicitamente', incrementando remaindercada vez, o que resulta no restante de 3. Em seguida, encontramos o caractere não repetitivo 'Y' . Aqui nós dividir o adicionado anteriormente ABCX em ABC -> X e ABC -> Y . Depois, diminuímos remainderde 3 para 2, porque já cuidamos da ramificação do ABC . Agora repetimos a operação combinando os dois últimos caracteres - BC - da raiz para chegar ao ponto em que precisamos dividir, e também dividimos o BCX em BC-> X e BC -> Y . Novamente, decrementamos remainderpara 1 e repetimos a operação; até que remainderseja 0. Por fim, precisamos adicionar o caractere atual ( Y ) à raiz também.

Essa operação, seguindo os sufixos consecutivos da raiz, simplesmente para chegar ao ponto em que precisamos realizar uma operação, é chamada de 'redigitalização' no algoritmo de Ukkonen, e normalmente essa é a parte mais cara do algoritmo. Imagine uma string mais longa, na qual você precisará 'redigitalizar' substrings longos, em várias dezenas de nós (discutiremos isso mais adiante), potencialmente milhares de vezes.

Como solução, apresentamos o que chamamos de 'links de sufixo' .

O conceito de 'links de sufixo'

Os links de sufixo apontam basicamente para as posições às quais normalmente teríamos que 'redigitalizar' , então, em vez da operação cara de digitalização, podemos simplesmente pular para a posição vinculada, fazer nosso trabalho, pular para a próxima posição vinculada e repetir - até não há mais posições para atualizar.

Obviamente, uma grande questão é como adicionar esses links. A resposta existente é que podemos adicionar os links quando inserimos novos nós de ramificação, utilizando o fato de que, em cada extensão da árvore, os nós de ramificação são naturalmente criados um após o outro na ordem exata em que precisamos vinculá-los . No entanto, precisamos vincular o último nó de ramificação criado (o sufixo mais longo) ao nó criado anteriormente, portanto, precisamos armazenar em cache o último que criamos, vincular esse ao próximo que criamos e armazenar em cache o recém-criado.

Uma conseqüência é que, na verdade, geralmente não temos links de sufixo a seguir, porque o nó de ramificação fornecido foi criado. Nesses casos, ainda temos que voltar à raiz da 'varredura' acima mencionada . É por isso que, após uma inserção, você é instruído a usar o link do sufixo ou ir para a raiz.

(Ou, alternativamente, se você estiver armazenando ponteiros pai nos nós, tente seguir os pais, verifique se eles têm um link e use-o. Descobri que isso é muito raramente mencionado, mas o uso do link com sufixo não é set em pedras. Existem várias abordagens possíveis, e se você entender o mecanismo subjacente que você pode implementar um que satisfaça suas necessidades o melhor.)

O conceito de 'ponto ativo'

Até agora, discutimos várias ferramentas eficientes para a construção da árvore e nos referimos vagamente a percorrer várias arestas e nós, mas ainda não exploramos as conseqüências e complexidades correspondentes.

O conceito explicado anteriormente de 'restante' é útil para acompanhar onde estamos na árvore, mas precisamos entender que ele não armazena informações suficientes.

Em primeiro lugar, sempre residimos em uma borda específica de um nó, portanto, precisamos armazenar as informações da borda. Vamos chamar isso de 'borda ativa' .

Em segundo lugar, mesmo depois de adicionar as informações da borda, ainda não temos como identificar uma posição mais abaixo na árvore e não diretamente conectada ao nó raiz . Portanto, precisamos armazenar o nó também. Vamos chamar esse 'nó ativo' .

Por fim, podemos notar que o 'restante' é inadequado para identificar uma posição em uma borda que não está diretamente conectada à raiz, porque 'restante' é o comprimento de toda a rota; e provavelmente não queremos nos preocupar em lembrar e subtrair o comprimento das arestas anteriores. Portanto, precisamos de uma representação que seja essencialmente o restante na borda atual . Isso é o que chamamos de "comprimento ativo" .

Isso leva ao que chamamos de 'ponto ativo' - um pacote de três variáveis ​​que contêm todas as informações que precisamos manter sobre nossa posição na árvore:

Active Point = (Active Node, Active Edge, Active Length)

Você pode observar na imagem a seguir como a rota correspondente do ABCABD consiste em 2 caracteres na borda AB (da raiz ) e mais 4 caracteres na borda CABDABCABD (do nó 4) - resultando em um 'restante' de 6 caracteres. Portanto, nossa posição atual pode ser identificada como Nó Ativo 4, Borda Ativa C, Comprimento Ativo 4 .

Outro papel importante do 'ponto ativo' é que ele fornece uma camada de abstração para o nosso algoritmo, o que significa que partes do nosso algoritmo podem fazer seu trabalho no 'ponto ativo' , independentemente de esse ponto ativo estar na raiz ou em qualquer outro lugar . Isso facilita a implementação do uso de links de sufixo em nosso algoritmo de maneira limpa e direta.

Diferenças entre redigitalização e uso de links de sufixo

Agora, a parte complicada, algo que - na minha experiência - pode causar muitos bugs e dores de cabeça, e é pouco explicado na maioria das fontes, é a diferença no processamento dos casos de link de sufixo versus os casos de nova varredura.

Considere o seguinte exemplo da cadeia 'AAAABAAAABAAC' :

Você pode observar acima como o 'restante' de 7 corresponde à soma total de caracteres da raiz, enquanto 'comprimento ativo' de 4 corresponde à soma de caracteres correspondentes da borda ativa do nó ativo.

Agora, após executar uma operação de ramificação no ponto ativo, nosso nó ativo pode ou não conter um link de sufixo.

Se um link de sufixo estiver presente: precisamos processar apenas a parte do 'comprimento ativo' . O 'restante' é irrelevante, porque o nó para o qual pulamos através do link do sufixo já codifica o 'restante' correto implicitamente , simplesmente por estar na árvore em que está.

Se um link de sufixo NÃO estiver presente: Precisamos 'digitalizar novamente' a partir de zero / raiz, o que significa processar todo o sufixo desde o início. Para esse fim, precisamos usar todo o "restante" como base para a nova verificação.

Exemplo de comparação de processamento com e sem um link de sufixo

Considere o que acontece na próxima etapa do exemplo acima. Vamos comparar como obter o mesmo resultado - ou seja, passar para o próximo sufixo a ser processado - com e sem um link de sufixo.

Usando 'link de sufixo'

Observe que, se usarmos um link de sufixo, estaremos automaticamente 'no lugar certo'. O que geralmente não é estritamente verdadeiro devido ao fato de que o 'comprimento ativo' pode ser 'incompatível' com a nova posição.

No caso acima, como o 'comprimento ativo' é 4, estamos trabalhando com o sufixo ' ABAA' , começando no Nó 4. vinculado. Mas depois de encontrar a borda que corresponde ao primeiro caractere do sufixo ( 'A' ), notamos que nosso 'comprimento ativo' ultrapassa essa borda em três caracteres. Então, pulamos a borda inteira, para o próximo nó, e diminuímos o 'comprimento ativo' pelos caracteres que consumimos com o salto.

Então, depois que encontramos a próxima aresta 'B' , correspondente ao sufixo decrescente 'BAA ', finalmente observamos que o comprimento da aresta é maior que o restante 'comprimento ativo' de 3, o que significa que encontramos o lugar certo.

Observe que parece que essa operação geralmente não é chamada de 'redigitalização', embora, para mim, pareça ser o equivalente direto da digitalização, apenas com um comprimento reduzido e um ponto inicial não raiz.

Usando 'redigitalizar'

Observe que, se usarmos uma operação tradicional de 'nova varredura' (aqui, fingindo que não tínhamos um link de sufixo), começamos no topo da árvore, na raiz e precisamos trabalhar novamente no lugar certo, seguindo ao longo de todo o comprimento do sufixo atual.

O tamanho desse sufixo é o 'restante' que discutimos anteriormente. Temos que consumir a totalidade desse restante, até chegar a zero. Isso pode (e geralmente inclui) pular através de vários nós, a cada salto diminuindo o restante pelo comprimento da borda pela qual pulamos. Finalmente, chegamos a um limite que é mais longo que o restante 'restante' ; aqui, definimos a aresta ativa para a aresta especificada, definimos 'comprimento ativo' para o restante 'restante ' e pronto.

Observe, no entanto, que a variável 'restante' real precisa ser preservada e decrementada apenas após a inserção de cada nó. Então, o que eu descrevi acima assumiu o uso de uma variável separada inicializada para 'restante' .

Notas sobre links de sufixo e rescansões

1) Observe que ambos os métodos levam ao mesmo resultado. O salto de link de sufixo é, no entanto, significativamente mais rápido na maioria dos casos; essa é toda a lógica por trás dos links de sufixo.

2) As implementações algorítmicas reais não precisam diferir. Como mencionei acima, mesmo no caso de usar o link do sufixo, o 'comprimento ativo' geralmente não é compatível com a posição vinculada, pois esse ramo da árvore pode conter ramificações adicionais. Então, basicamente, você só precisa usar 'comprimento ativo' em vez de 'restante' e executar a mesma lógica de redigitalização até encontrar uma borda menor do que o comprimento restante do sufixo.

3) Uma observação importante referente ao desempenho é que não há necessidade de verificar todos os caracteres durante a nova verificação. Devido à maneira como uma árvore de sufixos válida é criada, podemos assumir com segurança que os caracteres correspondem. Portanto, você está contando principalmente os comprimentos, e a única necessidade de verificação de equivalência de caracteres surge quando saltamos para uma nova aresta, já que as arestas são identificadas pelo primeiro caractere (que é sempre único no contexto de um determinado nó). Isso significa que a lógica de 'redigitalização' é diferente da lógica de correspondência completa de cadeias de caracteres (ou seja, procurando por uma subcadeia na árvore).

4) O link do sufixo original descrito aqui é apenas uma das abordagens possíveis . Por exemplo, NJ Larsson et al. nomeia essa abordagem como de cima para baixo orientada a nós e a compara com de baixo para cima e orientada a nós e duas variedades orientadas a arestas. As diferentes abordagens têm diferentes desempenhos, requisitos, limitações, etc. típicos e no pior caso, mas geralmente parece que as abordagens orientadas a borda são uma melhoria geral do original.

@jogojapan você trouxe explicações e visualizações incríveis. Mas como o @makagonov mencionou, faltam algumas regras em relação à configuração de links de sufixos. É visível de maneira agradável quando você segue 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á link de sufixo do nó 5 para o nó 2, mas o ponto ativo se move subitamente para lá.

@makagonov desde que moro no mundo Java, também tentei seguir sua implementação para entender o fluxo de trabalho de construção de ST, 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, 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);
        }
    });
  }
}

Minha intuição é a seguinte:

Após k iterações do loop principal, você construiu uma árvore de sufixos que contém todos os sufixos da cadeia completa iniciados nos primeiros k caracteres.

No início, isso significa que a árvore de sufixos contém um único nó raiz que representa toda a cadeia (este é o único sufixo que começa em 0).

Após as iterações len (string), você tem uma árvore 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 árvore de sufixos que corresponde a um sufixo adequado dos primeiros k caracteres da string. (Acho que adequado significa que o sufixo não pode ser a string inteira.)

Por exemplo, suponha que você tenha visto os caracteres 'abcabc'. O ponto ativo representaria o ponto na árvore correspondente ao sufixo 'abc'.

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

Ao adicionar um novo caractere, você olha para ver se o ponto ativo ainda está na árvore existente. Se for, então você está pronto. Caso contrário, você precisará adicionar um novo nó à árvore de sufixos no ponto ativo, fazer fallback para a próxima correspondência mais curta e verificar novamente.

Nota 1: Os ponteiros de sufixo fornecem um link para a próxima correspondência mais curta de cada nó.

Nota 2: Ao adicionar um novo nó e fallback, você adiciona um novo ponteiro de sufixo para o novo nó. O destino desse ponteiro de sufixo será o nó no ponto ativo reduzido. Esse nó já existe ou será criado na próxima iteração desse loop de fallback.

Nota 3: A parte da canonização economiza tempo na verificação do ponto ativo. Por exemplo, suponha que você sempre usou origin = 0 e apenas alterou o primeiro e o último. Para verificar o ponto ativo, é necessário seguir a árvore de sufixos toda vez em todos os nós intermediários. Faz sentido armazenar em cache o resultado de seguir esse caminho gravando apenas a distância do último nó.

Você pode dar um exemplo de código do que você quer dizer com "corrigir" variáveis ​​delimitadoras?

Aviso de integridade: também achei esse algoritmo particularmente difícil de entender; portanto, saiba que essa intuição provavelmente está incorreta em todos os detalhes importantes ...

Oi eu tentei implementar a implementação explicada acima em ruby, por favor, confira. parece funcionar bem.

a única diferença na implementação é que, tentei usar o objeto edge em vez de apenas usar símbolos.

também está presente em 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