Constructions d'arborescence de suffixes linéaires conceptuellement simples

13

En 1973, Weiner a donné la première construction en temps linéaire d'arbres suffixes. L'algorithme a été simplifié en 1976 par McCreight et en 1995 par Ukkonen. Néanmoins, je trouve l'algorithme d'Ukkonen relativement impliqué conceptuellement.

Y a-t-il eu des simplifications de l'algorithme d'Ukkonen depuis 1995?

ds.algorithms Randomblue
la source
4
Farach et el 1998. Je pense que c'est un bon endroit pour commencer à lire: scholar.google.co.uk/…
Radu GRIGore

Réponses:

9

Je ne sais pas s'il y a eu de nouveaux résultats simplifiant directement la construction d'arbres de suffixes. Cependant, il y a eu au moins un résultat donnant un algorithme très simple pour construire des tableaux de suffixes en temps linéaire.

Notez qu'il y a plus qu'une équivalence conceptuelle entre ces deux structures de données, car vous pouvez utiliser un tableau de suffixes (avec pour interroger le préfixe commun le plus long) pour créer un arbre de suffixes équivalent. Cela devrait être un exercice relativement simple, mais je peux donner plus de détails si nécessaire.O(1)

O(nlg⁡n)

zotachidil
la source
1
Pourriez-vous donner un pointeur sur la façon la plus simple de créer des tableaux de suffixes en temps O (N lg N)?
Randomblue
1
Étiquetez tous les suffixes de longueur 2 ^ k avec un entier tel que les étiquettes correspondent à la relation d'ordre entre les suffixes. La première étape (k = 0) est évidente. Pour calculer les étiquettes à l'étape k, utilisez les étiquettes de l'étape k-1 et effectuez un tri radix. Ce document doit être facile à comprendre: webglimpse.net/pubs/suffix.pdf
zotachidil
7

En plus de ce qui a été mentionné ( Kärkkäinen & Sanders, 2003 ), je pense que vous apprécierez la version "plus récente" de Kärkkäinen, Sanders et Burkhard, 2006 . L'algorithme suit essentiellement la structure de l'algorithme de Farach. Il est sans doute conceptuellement plus simple, mais le véritable avantage est qu'ils fournissent au lecteur une implémentation de l'algorithme. Il ne s'agit que d'environ 50 lignes de C ++, donc il n'y a en effet aucun détail caché.

Juho
la source