Comment la durée d'exécution de l'algorithme d'Ukkonen dépend-elle de la taille de l'alphabet?

Je m'intéresse à la question du temps d'exécution asymptotique de l'algorithme d'Ukkonen , peut-être l'algorithme le plus populaire pour construire des arbres de suffixes en temps linéaire (?).

Voici une citation du livre "Algorithmes sur les chaînes, les arbres et les séquences" de Dan Gusfield (section 6.5.1):

"... les algorithmes Aho-Corasick, Weiner, Ukkonen et McCreight nécessitent tous deux un espace de , ou la limite de temps doit être remplacée par le minimum de et ".$\Theta(m|\Sigma|)$$O(m)$$O(m \log m)$$O(m \log|\Sigma|)$

[ est la longueur de la chaîne et est la taille de l'alphabet]$m$$\Sigma$

Je ne comprends pas pourquoi c'est vrai.

• Espace: eh bien, dans le cas où nous représentons des branches hors des nœuds en utilisant des tableaux de taille , alors, en fait, nous nous retrouvons avec l' utilisation de l'espace . Cependant, pour autant que je puisse voir, il est également possible de stocker les branches à l'aide de tables de hachage (par exemple, des dictionnaires en Python). Nous n'aurions alors que des pointeurs stockés dans toutes les tables de hachage (car il y a des bords dans l'arborescence), tout en étant en mesure d'accéder aux nœuds enfants en temps , aussi rapidement comme lors de l'utilisation de tableaux.$\Theta(|\Sigma|)$$\Theta(m|\Sigma|)$$\Theta(m)$$\Theta(m)$$O(1)$
• Temps : comme mentionné ci-dessus, l'utilisation de tables de hachage nous permet d'accéder aux branches sortantes de n'importe quel nœud en temps . Étant donné que l'algorithme d'Ukkonen nécessite des opérations (y compris l'accès aux nœuds enfants), le temps d'exécution global serait alors également .$O(1)$$O(m)$$O(m)$

Je vous serais très reconnaissant de savoir pourquoi je me trompe dans mes conclusions et pourquoi Gusfield a raison sur la dépendance de l'algorithme d'Ukkonen vis-à-vis de l'alphabet.

Comme @jogojapan le mentionne dans les commentaires, le hachage n'est généralement amorti que , donc vous n'obtiendrez que des limites amorties pour l'algorithme. Cependant, je pense que vous ne les obtenez même pas: pour obtenir un hachage O ( 1 ) amorti , les tables de hachage doivent être de taille Ω ( Σ ) , vous avez donc encore un espace Θ ( m Σ ) (et en même temps condition d'initialisation).$O(1)$$O(1)$$\Omega(\Sigma)$$\Theta(m\Sigma)$

De plus, en pratique, le temps de configuration de toutes ces tables de hachage sera beaucoup plus long que le temps de configuration des tableaux.

Vous pourriez vous en sortir mieux avec une table de hachage globale indexée avec des paires (nœud, caractère), mais au moins l'argument "uniquement amorti" restera.