Le suffixe de l'arbre et Tente. Quelle est la différence?
Je lis à propos de Tries
communément connu comme Préfixe arbres et Suffix Trees
.
Bien que j'ai trouvé le code pour un Trie
je ne peux pas trouver un exemple pour un Suffix Tree
. Aussi, j'ai l'impression que le code qui construit un Trie
est le même que pour un Suffix Tree
avec la seule différence que dans le premier cas, nous stockons des préfixes, mais dans la dernière suffixes.
Est-ce vrai? Quelqu'un peut-il m'aider à effacer ce dans ma tête? Un exemple de code d'une grande aide!
- TL;DR Le suffixe arbre d'une chaîne de caractères est une patricia trie de toutes ses suffixes. La seule chose, c'est que le bord des étiquettes sont des sous-chaînes de la chaîne d'origine, de sorte qu'ils peuvent être représentés comme une paire d'indices et de ne prendre que la constante de l'espace. C'est aussi pourquoi il peut être construit en temps linéaire.
Vous devez vous connecter pour publier un commentaire.
Un suffixe arbre peut être considéré comme une structure de données construite sur le toit d'un trie où, au lieu de simplement ajouter la chaîne elle-même dans la trie, vous aussi, vous ajoutez tous les possibles suffixe de cette chaîne. Par exemple, si vous voulais de l'indice de la chaîne banane dans un suffixe de l'arbre, vous serait de construire un trie avec les chaînes suivantes:
Une fois que c'est fait, vous pouvez rechercher un n-gramme et de voir si il est présent dans votre indexé chaîne. En d'autres termes, le n-gramme de recherche est un préfixe de recherche de toutes les suffixes de votre chaîne.
C'est le plus simple et le plus lent façon de construire un suffixe de l'arbre. Il s'avère qu'il y a beaucoup d'amateur de variantes sur cette structure de données qui permettent d'améliorer un ou l'autre ou les deux de l'espace et du temps de compilation. Je ne suis pas très versé assez dans ce domaine pour donner un aperçu, mais vous pouvez commencer par la recherche dans les suffixe des tableaux ou de cette classe avancée structures de données (cours 16 et 18).
Ce réponse aussi fait un superbe travail en expliquant une variante de cette structure de données.
Si vous imaginez un Trie dans lequel vous mettez un mot de suffixes, vous seriez en mesure de faire des requêtes pour la chaîne de sous-chaînes très facilement. C'est l'idée principale derrière le suffixe de l'arbre, c'est essentiellement un "suffixe trie".
Mais en utilisant cette approche naïve, la construction de cet arbre pour une chaîne de caractères de taille n serait en O(n^2) et de prendre beaucoup de mémoire.
Depuis toutes les entrées de cet arbre sont des suffixes de la même chaîne, ils partagent un grand nombre d'informations, il y a donc des algorithmes optimisés qui vous permet de créer plus efficacement. L'algorithme d'Ukkonen, par exemple, permet de créer un suffixe arbre en ligne en O(n) le temps de la complexité.
La différence est très simple. Un suffixe arbre a moins de "dummy" de nœuds que le suffixe trie. Ces factice nœuds sont les caractères uniques qui augmentent l'opération de recherche à l'arbre