Quelle structure donne les meilleurs résultats en termes de performances : trie (arbre de préfixes), arbre de suffixes ou tableau de suffixes ? Existe-t-il d'autres structures similaires ? Quelles sont les bonnes implémentations Java de ces structures ?
Edit : dans ce cas je veux faire de la correspondance de chaîne entre un grand dictionnaire de noms et un grand ensemble de textes en langage naturel, afin d'identifier les noms du dictionnaire sur les textes.
Le TRIE a été la première structure de données de ce type découverte.
L'arbre des suffixes est une amélioration par rapport au TRIE (il possède des liens entre les suffixes qui permettent une recherche linéaire des erreurs, l'arbre des suffixes supprime les branches inutiles du TRIE et n'occupe donc pas autant d'espace).
Le tableau des suffixes est une structure de données dépouillée basée sur l'arbre des suffixes (pas de liens entre les suffixes (correspondance lente des erreurs), mais la correspondance des motifs est très rapide).
Le TRIE n'est pas destiné à une utilisation dans le monde réel car il consomme trop d'espace.
L'arbre des suffixes est plus léger et plus rapide que le Trie et est utilisé pour indexer l'ADN ou optimiser certains grands moteurs de recherche web.
Le tableau de suffixes est plus lent dans certaines recherches de motifs que l'arbre de suffixes, mais il utilise moins d'espace, et il est plus largement utilisé que l'arbre de suffixes.
Dans la même famille de structures de données :
Il existe d'autres implémentations, la CST est une implémentation de l'arbre des suffixes utilisant un tableau de suffixes et quelques structures de données supplémentaires pour obtenir certaines des capacités de recherche de l'arbre des suffixes.
Le FCST va plus loin, il implémente un arbre de suffixes échantillonné avec un tableau de suffixes.
Le DFCST est une version dynamique du FCST.
En 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, cela n'a pas d'importance, mais pour indexer l'ADN d'un seul être humain, il faudrait 40 gigaoctets de mémoire (en utilisant un arbre de suffixes non compressé et non optimisé). Et construire un de ces index sur une telle quantité de données peut prendre des jours. Imaginez Google, il a beaucoup de données interrogeables, il a besoin d'un grand index sur toutes les données web et il ne le change pas à chaque fois que quelqu'un construit une page web. Ils ont une certaine forme de cache pour cela. Cependant, l'index principal est probablement statique. Et toutes les deux semaines environ, ils rassemblent tous les nouveaux sites Web et toutes les nouvelles données et construisent un nouvel index, remplaçant l'ancien lorsque le nouveau est terminé. Je ne sais pas quel algorithme ils utilisent pour indexer, mais il s'agit probablement d'un tableau de suffixes avec des propriétés d'arbre de suffixes sur une base de données partitionnée.
La CST utilise 8 gigaoctets, mais la vitesse des opérations de l'arbre des suffixes est fortement réduite.
Le réseau Suffixe peut faire la même chose dans quelques 700 mégas à 2 gigas. Toutefois, vous ne trouverez pas d'erreurs génétiques dans l'ADN avec un tableau de suffixes (autrement dit, la recherche d'un motif avec un caractère de remplacement est beaucoup plus lente).
Le FCST (fully compressed suffix tree) peut créer un arbre de suffixes en 800 à 1,5 gigas. Avec une détérioration assez faible de la vitesse vers le FCST.
La DFCST utilise 20% d'espace en plus que la FCST, et perd en vitesse par rapport à l'implémentation statique de la FCST. (cependant un index dynamique est très important)
Il n'existe pas beaucoup d'implémentations viables (en termes d'espace) de l'arbre des suffixes, car il est très difficile de faire en sorte que l'augmentation de la vitesse des opérations compense le coût en espace des structures de données.
Ceci dit, l'arbre des suffixes a des résultats très intéressants pour la recherche de motifs avec des erreurs. L'aho corasick n'est pas aussi rapide (bien qu'il soit presque aussi rapide pour certaines opérations, mais pas pour la recherche d'erreurs) et le boyer moore est laissé dans la poussière.
Quelles opérations envisagez-vous de faire ? libdivsufsort était à un moment donné la meilleure implémentation de tableaux de suffixes en C.
En utilisant les Suffix Trees, vous pouvez écrire quelque chose qui fera correspondre votre dictionnaire à votre texte en O(n+m+k) temps où n est le nombre de lettres de votre dictionnaire, m le nombre de lettres de votre texte et k le nombre de correspondances. Les essais sont beaucoup plus lents pour cela. Je ne suis pas sûr de savoir ce qu'est un Suffix Array, donc je ne peux pas faire de commentaires à ce sujet.
Cela dit, ce n'est pas trivial à coder et je ne connais pas de bibliothèque Java qui fournisse les fonctions nécessaires.
EDIT : Dans ce cas, je veux faire une correspondance de chaînes de caractères entre un grand dictionnaire de noms et un grand ensemble de textes en langage naturel. textes en langage naturel, afin d'identifier les noms du dictionnaire sur les textes.
Cela ressemble à une demande pour le Algorithme d'Aho-Corasick : construire un automate à partir du dictionnaire (en temps linéaire), qui peut ensuite être utilisé pour trouver toutes les occurrences de l'un des mots du dictionnaire dans plusieurs textes (également en temps linéaire).
(La description dans ces notes de cours dont le lien se trouve dans la section "Liens externes" de la page Wikipédia, est beaucoup plus facile à lire que la description de la page elle-même).
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
