Sinto-me um pouco grosso 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. O mais próximo de uma boa explicação que eu encontrei éesquisa Rápida em String com Árvores de Sufi, mas ele encobre vários pontos e alguns aspectos do algoritmo permanecem obscuro

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

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

Meu entendimento básico, até agora:

Eu preciso percorrer cada prefixo P de uma determinada string TPreciso percorrer cada sufixo S no prefixo P e adicioná-lo à árvorePara adicionar o sufixo S à árvore, eu 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 aresta em nós descendentes quando Eu alcanço um caractere diferente no sufixo, OU se não houver uma borda correspondente para descer. Quando não é encontrada nenhuma aresta correspondente em C, uma nova aresta da folha é criada para C.

O algoritmo básico parece ser O (n2), como é indicado na maioria das explicações, como precisamos percorrer todos os prefixos, precisamos 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 quenaquel é o 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 que está acontecendo com o aspecto de canonização do algoritPor que as implementações que eu vi precisam "consertar" variáveis delimitadoras que estão usando

Aqui está o C # Código fonte. 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/237386

Update 2017-11-04

epois 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 chalk do mesmo local e, em seguida, execute o node.js para ver uma saída colorida. Há uma versão simplificada na mesma lista, sem nenhum código de depuraçã

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