Como o tempo de execução do algoritmo de Ukkonen depende do tamanho do alfabeto?

Estou preocupado com a questão do tempo de execução assintótico do algoritmo de Ukkonen , talvez o algoritmo mais popular para a construção de árvores de sufixo em tempo linear (?).

Aqui está uma citação do livro "Algoritmos sobre cordas, árvores e sequências" de Dan Gusfield (seção 6.5.1):

"... os algoritmos Aho-Corasick, Weiner, Ukkonen e McCreight exigem espaço ou o limite de tempo deve ser substituído pelo mínimo de e ". $\Theta(m|\Sigma|)$ $O(m)$ $O(m \log m)$ $O(m \log|\Sigma|)$

[ é o comprimento da string e é o tamanho do alfabeto] $m$ $\Sigma$

Não entendo por que isso é verdade.

Espaço: bem, caso representemos ramificações fora dos nós usando matrizes de tamanho , então, de fato, acabamos com o uso de espaço . No entanto, tanto quanto posso ver, também é possível armazenar os ramos usando tabelas de hash (por exemplo, dicionários em Python). Teríamos, então, apenas ponteiros armazenados em todas as tabelas de hash ao todo (uma vez que existem bordas na árvore), enquanto continuam sendo capazes de acessar os nós filhos em $\Theta(|\Sigma|)$ $\Theta(m|\Sigma|)$ $\Theta(m)$ $\Theta(m)$ $O(1)$ tempo, tão rápido quanto ao usar matrizes.
Tempo : como mencionado acima, o uso de tabelas de hash nos permite acessar as ramificações de saída de qualquer nó no tempo . Como o algoritmo de Ukkonen requer operações (incluindo o acesso a nós filhos), o tempo de execução geral também seria . $O(1)$ $O(m)$ $O(m)$

Ficaria muito grato a você por qualquer sugestão sobre por que estou errado em minhas conclusões e por que Gusfield está certo sobre a dependência do algoritmo de Ukkonen no alfabeto.

algorithms data-structures algorithm-analysis strings Mikhail Dubov
fonte

Não acho que exista prova de que seja impossível um limite de tempo / espaço independente do tamanho do alfabeto. Acredito que Gusfield fez a afirmação porque não existe um método conhecido para se livrar completamente do tempo limite. Para estabelecer uma, você teria que elaborar suas funções de hash com mais detalhes. Um verdadeiro período O (1) de pior caso vinculado à pesquisa de hash requer um hash perfeito. Não está claro para mim como fazer isso durante o algoritmo (porque as entradas de hash não são estáticas nesse ponto).

precisa saber é o seguinte

(continuação) Você poderia fazê-lo quando a árvore estiver concluída, mas o tempo limite para o algoritmo em si continuaria inalterado. (+1 para a pergunta).

jogojapan

Contexto útil: o algoritmo de Ukkonen explicou

FrankW

Como @jogojapan menciona nos comentários, geralmente, o hasing é apenas amortizado , portanto você só obteria limites amortizados para o algoritmo. No entanto, acho que você nem consegue: Para obter o hash amortizado , as tabelas de hash devem ser do tamanho , portanto, você ainda tem espaço (e ao mesmo tempo requisito para inicialização). $O(1)$ $O(1)$ $\Omega(\Sigma)$ $\Theta(m\Sigma)$

Além disso, na prática, o tempo para configurar todas essas tabelas de hash será muito maior do que o tempo para configurar matrizes.

Você pode se sair melhor usando uma tabela de hash global indexada com (nó, caractere) -pairs, mas pelo menos o argumento "somente amortizado" permanecerá.

FrankW
fonte

Como o tempo de execução do algoritmo de Ukkonen depende do tamanho do alfabeto?

Respostas: