Comprendre l'algorithme d'Ukkonen pour les arbres de suffixes

Je travaille avec l'algorithme d'Ukkonen pour construire des arbres de suffixes, mais je ne comprends pas certaines parties de l'explication de l'auteur pour sa complexité linéaire. J'ai appris l'algorithme et l'ai codé, mais le papier que j'utilise comme principale source d'information (lien ci-dessous) est assez confus à certains endroits, donc je ne comprends pas vraiment pourquoi l'algorithme est linéaire .Comprendre l'algorithme d'Ukkonen pour les arbres de suffixes

Une aide? Merci.

Lien vers l'article de Ukkonen: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Source

2009-08-20 Vinicius Pinto

Pour tous ceux qui trouvent cette question: Une similaire est apparue [ici] (http://stackoverflow.com/q/9452701/777186) et nous créons une description de l'algorithme en tant que réponse Stackoverflow [ici] (http://stackoverflow.com/a/9513423/777186). – jogojapan

Trouver une copie de Gusfield de string algorithms textbook. Il a la meilleure exposition de la construction de l'arbre suffixe que j'ai vu. La linéarité est une conséquence surprenante d'un certain nombre d'optimisations de l'algorithme de haut niveau.

Source

2009-08-29 15:18:45

Existe-t-il une version animée de cet algo ukkonen? Désolé, je ne pouvais pas comprendre la nature constante de la fonction "mise à jour". J'ai essayé gusfield, le papier d'ukkonen et google aussi: D – Seeker

J'aimerais regarder une animation pour construire un arbre de suffixe généralisé en temps linéaire. Généralement l'explication basée sur le texte ne correspond pas à mon esprit .. :) – Abhi

Le chapitre de Gusfields sur les arbres de suffixe a cette caractéristique ennuyante, qu'il emploie différentes chaînes pour illustrer les différentes étapes - ainsi vous perdez la grande image. – maasha

Comprendre l'algorithme d'Ukkonen pour les arbres de suffixes

Répondre

Questions connexes