Trie vs suffixe arbre vs suffixe tableau
quelle structure fournit les meilleurs résultats de performance; trie (arbre du préfixe), arbre du suffixe ou tableau du suffixe? Il existe d'autres structures similaires? Quelles sont les bonnes implémentations Java de ces structures?
Edit: dans ce cas, je veux faire de la chaîne de mise en correspondance entre un grand dictionnaire de noms et un vaste ensemble de textes en langue naturelle, afin d'identifier les noms des dictionnaire sur les textes.
6 réponses
la trie fut la première structure de données de ce type découverte.
l'arbre de suffixe est une amélioration par rapport au trie (il a des liens de suffixe qui permettent une recherche d'erreur linéaire, l'arbre de suffixe coupe les branches inutiles du trie donc il ne nécessite pas autant d'espace).
le tableau de suffixe est une structure de données dépouillée basée sur l'arbre de suffixe (pas de liens de suffixe (correspondances d'erreurs lentes), mais l'appariement des motifs est très rapide).
La trie n'est pas pour utilisation dans le monde réel, car elle consomme trop d'espace.
le suffixe est plus léger et plus rapide que le trie et sert à indexer L'ADN ou à optimiser certains gros moteurs de recherche sur le web.
le tableau de suffixe est plus lent dans certaines recherches de motif que l'arbre de suffixe mais utilise moins d'espace, et est plus largement utilisé que l'arbre de suffixe.
Dans la même famille de structures de données:
il y a d'autres implémentations, le CST est une implémentation de l'arbre de suffixe utiliser un tableau de suffixe et quelques structures de données supplémentaires pour obtenir certaines des capacités de recherche d'arbre de suffixe.
le FCST va plus loin, il implémente un arbre de suffixe échantillonné avec un tableau de suffixe.
le DFCST est une version dynamique du FCST.
Expansion:
les deux facteurs importants sont l'utilisation de l'espace et le temps d'exécution des opérations. Vous pourriez penser qu'avec les machines modernes ce n'est pas pertinent mais d'indexer L'ADN d'un seul être humain nécessiterait 40 gigaoctets de mémoire (en utilisant un arbre de suffixe non compressé et non optimisé). Et construire un de ces indices sur autant de données peut prendre des jours. Imaginez Google, il a beaucoup de données consultables, ils ont besoin d'un grand index sur toutes les données web et ils ne le changent pas chaque fois que quelqu'un construit une page web. Ils ont une forme de cache pour ça. Toutefois, l'indice principal est probablement statique. Et toutes les deux semaines environ, ils rassemblent tous les nouveaux sites Web et données et construisent un nouvel index., remplacer l'ancien quand le nouveau est terminé. Je ne sais pas quel algorithme ils utilisent pour indexer, mais c'est probablement un tableau de suffixe avec des propriétés d'arbre de suffixe sur une base de données partitionnée.
le CST utilise 8 gigaoctets, mais la vitesse des opérations des arbres de suffixe est fortement réduite.
le tableau de suffixe peut faire la même chose dans quelque 700 mégas à 2 Gigas. Cependant, vous ne trouverez pas d'erreurs génétiques dans L'ADN avec un tableau de suffixe (ce qui signifie: la recherche d'un motif avec une Joker est beaucoup beaucoup plus lent).
le FCST (arbre de suffixe entièrement comprimé) peut créer un arbre de Suffixe de 800 à 1,5 gigas. Avec une détérioration assez faible de la vitesse vers le Gend.
le DFCST utilise 20% plus d'espace que le FCST, et perd de la vitesse par rapport à L'implémentation statique du FCST (cependant un index dynamique est très important).
il n'y a pas beaucoup d'implémentations viables (du point de vue de l'espace) de l'arbre de suffixe car il est très difficile de faire compenser l'augmentation de la vitesse des opérations les structures de données RAM coût de l'espace.
ceci dit, l'arbre de suffixe a des résultats de recherche très intéressants pour la correspondance des motifs avec des erreurs. L'aho corasick n'est pas aussi rapide (mais presque aussi rapide pour certaines opérations, pas d'erreur correspondant) et le boyer moore est laissé dans la poussière.
quelles opérations prévoyez-vous faire? libdivsufsort était à un moment donné la meilleure implémentation de tableau de suffixe dans C.
en utilisant des arbres de suffixe, vous pouvez écrire quelque chose qui correspondra à votre dictionnaire dans O(n+m+k) time où n est lettres dans votre dictionnaire, m est lettres dans votre texte, et k est le nombre de correspondances. Tente sont beaucoup plus lents pour cela. Je ne suis pas sûr de ce qu'est un tableau de suffixe, donc je ne peux pas le commenter.
cela dit, il est non-trivial de coder et je ne connais pas de bibliothèques Java qui fournissent les fonctions nécessaires.
EDIT: Dans ce cas, je veux faire de la chaîne de mise en correspondance entre un grand dictionnaire de noms et un vaste ensemble d' le langage naturel textes, afin d'identifier les noms des dictionnaire sur les textes.
cela ressemble à une application pour le algorithme Aho-Corasick: construire un automate à partir du dictionnaire (en temps linéaire), qui peut ensuite être utilisé pour trouver toutes les occurrences de tous les mots du dictionnaire dans plusieurs textes (aussi dans le linéaire temps.)
(La description ces notes de cours, lié à partir de la section "Liens externes" de la page Wikipedia, est beaucoup plus facile à lire que la description sur la page elle-même.)
Trie vs Suffixe arbre
les deux structures de données assurent une recherche très rapide, le temps de recherche est proportionnel à la longueur du mot d'interrogation, le temps de complexité O(m) où m est la longueur du mot d'interrogation.
c'est Moyen si nous avons le mot de requête qui a 10 caractères, donc nous avons besoin au plus 10 étapes pour le trouver.
Trie: un arbre pour stocker les chaînes dans lesquelles il y a un noeud pour chaque préfixe commun. Les cordes sont stockées dans des feuilles supplémentaires nœud.
suffix tree: une représentation compacte d'une règle correspondant aux suffixes d'une chaîne donnée où tous les noeuds avec un enfant sont fusionnés avec leurs parents.
les Déf sont de : Dictionnaire des Algorithmes et Structures de Données
généralement utilisé pour indexer les mots du dictionnaire (lexique) ou tout ensemble de chaînes exemple D = {abcd, abcdd, bxcdf,.....,zzzz }
un arbre de suffixe utilisé pour indexer le texte en utilisant la même structure de données "Tri" sur tous les suffixes de notre texte T = abcdabcg tous les suffixes de T = {abcdabcg, abcdabc , abcdab, abcda, abcd, abc, ab, a}
maintenant ça ressemble à un groupe de cordes. nous construisons un tri sur ces groupes de chaînes (tous les suffixes de T).
la construction des deux structures de données est linéaire, elle prend O (n) dans le temps et l'espace.
dans le cas de dicionary (un ensemble de chaînes): n = la somme des caractères de tous les mots. dans le texte : n = longueur du texte.
tableau de suffixe: est une technique pour représenter un arbre de suffixe dans sapce compressé, c'est un tableau de toutes les positions de départ des suffixes d'une chaîne.
il est plus lent que l'arbre de suffixe dans le temps de recherche.
pour plus d'informations allez sur wikipedia , il y a un bon article qui parle de ce sujet.
implémentation de l'algorithme de tri induit (appelé sais) a une version Java pour construire des tableaux de suffix.