Arbre des suffixes et Tries. Quelle est la différence ?

Question

Je suis en train de lire sur Tries communément appelés "arbres à préfixes" et Suffix Trees .
Bien que j'aie trouvé du code pour un Trie Je ne trouve pas d'exemple pour un Suffix Tree . De plus, j'ai l'impression que le code qui construit une Trie est le même que celui d'un Suffix Tree avec la seule différence que dans le premier cas, on stocke les préfixes et dans le second les suffixes.
C'est vrai ? Quelqu'un peut-il m'aider à éclaircir ce point dans ma tête ? Un exemple de code serait d'une grande aide !

Answer 1

Un arbre de suffixes peut être considéré comme une structure de données construite au-dessus d'un trie où, au lieu d'ajouter la chaîne elle-même dans le trie, vous ajouteriez également tous les suffixes possibles de cette chaîne. Par exemple, si vous souhaitez indexer la chaîne de caractères banane dans un arbre de suffixes, vous construiriez un trie avec les chaînes suivantes :

banana
anana
nana
ana
na
a

Une fois que c'est fait, vous pouvez rechercher n'importe quel n-gramme et voir s'il est présent dans votre chaîne indexée. En d'autres termes, la recherche par n-gram est une recherche par préfixe de tous les suffixes possibles de votre chaîne.

C'est la façon la plus simple et la plus lente de construire un arbre de suffixes. Il s'avère qu'il existe de nombreuses variantes plus sophistiquées de cette structure de données qui améliorent l'espace et le temps de construction, ou les deux. Je ne suis pas assez versé dans ce domaine pour en donner une vue d'ensemble, mais vous pouvez commencer par vous intéresser à tableaux de suffixes ou cette classe structures de données avancées (lecture 16 et 18).

Ce site réponse explique également très bien une variante de cette structure de données.

Answer 2

Si vous imaginez un Trie dans lequel vous placez les suffixes d'un mot, vous pourrez très facilement l'interroger pour connaître les sous-chaînes de la chaîne. C'est l'idée principale de l'arbre des suffixes, c'est en fait un "Trie des suffixes".

Mais en utilisant cette approche naïve, la construction de cet arbre pour une chaîne de taille n serait O(n^2) et prendrait beaucoup de mémoire.

Comme toutes les entrées de cet arbre sont des suffixes de la même chaîne, elles partagent beaucoup d'informations. Il existe donc des algorithmes optimisés qui permettent de les créer plus efficacement. L'algorithme d'Ukkonen, par exemple, permet de créer un arbre de suffixes en ligne en un temps de complexité O(n).

Answer 3

La différence est très simple. Un arbre de suffixes a moins de nœuds "factices" que la trie de suffixes. Ces nœuds fictifs sont des caractères uniques qui augmentent l'opération de recherche dans l'arbre.

Answer 4

Les nœuds de Trie ont des liens vers des contextes plus courts, ce qui n'est pas le cas de "Tree". Si les nœuds de l'arbre ont un lien vers un contexte plus court, il devient un Trie ;o)

Answer 5

L'arbre des suffixes d'un texte donné est un tableau comprimé de tous les suffixes de ce texte.

Réf : https://www.geeksforgeeks.org/pattern-searching-using-suffix-tree/