Trie vs suffixe arbre vs suffixe tableau

La structure qui fournit les meilleurs résultats de performance; trie (préfixe de l'arbre), le suffixe arbre ou un suffixe tableau? 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.

  • De meilleures performances pour quelles opérations?
InformationsquelleAutor David Campos | 2010-03-21
  1. 56

    La trie a été la première structure de données de ce type découvert.

    Le suffixe de l'arbre est une amélioration par rapport à la trie (il a le suffixe des liens qui permettent d'erreur linéaire de recherche, le suffixe arbre garnitures inutiles branches de la trie par conséquent, il n'a pas besoin d'autant d'espace).

    Le suffixe tableau est une dépouillé structure de données basée sur le suffixe de l'arbre (pas de suffixe de liens (lent erreur matches), mais le filtrage est très rapide).

    La trie n'est pas pour une utilisation dans le monde réel, car elle consomme trop d'espace.

    Le suffixe de l'arbre est plus léger et plus rapide que le trie et est utilisée pour l'indexation de l'ADN ou à l'optimisation de certains grands moteurs de recherche web.

    Le suffixe tableau est plus lente dans certains modèle de recherche que le suffixe arbre, mais utilise moins d'espace et est plus largement utilisé que le Suffixe de l'arbre.

    Dans la même famille de structures de données:

    Il existe d'autres implémentations, le CST est une implémentation du suffixe de l'arbre à l'aide d'un suffixe tableau et quelques autres structures de données pour obtenir le suffixe de l'arbre de capacités de recherche.

    La FCST va encore plus loin, il met en place un échantillonnage de suffixe de l'arbre avec un suffixe tableau.

    La DFCST est une version dynamique de la FCST.

    Expansion:

    Les deux facteurs importants sont l'utilisation de l'espace et de l'exploitation de l'exécution. Vous pourriez penser que la modernité des machines, ce n'est pas pertinente, mais à l'indice de l'ADN d'un être humain aurait besoin de 40 giga-octets de mémoire (à l'aide d'un non compressé et unoptimized suffixe de l'arbre). Et pour construire un de ces indices au cours de cette quantité de données peut prendre des jours. Imaginez Google, il y a beaucoup de données consultables, ils ont besoin d'un grand indice au-dessus de toutes les données du web et ils ne changent pas à chaque fois que quelqu'un construit une page web. Ils ont une certaine forme de mise en cache pour que. Toutefois, le principal indice est probablement statique. Et toutes les deux semaines afin qu'ils rassemblent tous les nouveaux sites web et les données et de construire un nouvel indice, en remplacement de l'ancien avec le nouveau, c'est fini. Je ne sais pas qui l'algorithme qu'ils utilisent à l'index, mais c'est probablement un suffixe tableau avec le suffixe de l'arbre des propriétés sur une base de données partitionnées.

    Le CST utilise 8 gigaoctets, cependant le suffixe de l'arbre des opérations de vitesse sont fortement réduites.

    Le suffixe tableau peut faire la même chose dans quelques 700 megas à 2 Gigas. Cependant, vous ne trouverez pas d'erreurs génétiques dans l'ADN avec un suffixe de tableau (ce qui signifie: la recherche d'un modèle avec un caractère générique est d'autant plus faible).

    La FCST (complètement compressé suffixe arbre) peut créer un suffixe arbre de 800 à 1,5 gigas. Avec une petite vitesse de détérioration de la direction de la CST.

    La DFCST utilise 20% d'espace en plus que la FCST, et perd de la vitesse à la statique de la mise en œuvre de la FCST (cependant un index dynamique est très important).

    Il n'y a pas beaucoup de viable (espace sage) implémentations de le suffixe de l'arbre parce qu'il est très difficile de rendre les opérations de boost de vitesse de compenser les structures de données de la RAM coût de l'espace.

    Cela dit, le suffixe de l'arbre est très intéressant, les résultats de la recherche pour le modèle d'appariement 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.

    • Ce qui est "linéaire" recherche d'erreur"?
    • Linéaire de recherche d'erreur est une erreur de recherche qui renvoie d'erreur possible matches en un temps linéaire. Par exemple, un texte a les mots "Maison", "Housa", "Hotse" quelque part. Une erreur constante match serait le retour de toutes les erreurs en une seule opération. Erreur linéaire match retourne toutes les erreurs (matches) dans le COMTE(matches). Dans ce cas-2. Certains pourraient interpréter cela comme une recherche linéaire sur la taille du texte (texte d'analyse de l'erreur), et par conséquent, le coût serait égale à la taille du texte. Ce qui est le cas de presque toutes les erreurs des algorithmes de recherche, cependant ce n'est pas le cas pour le suffixe de l'arbre.
    • L'avantage de suffixe tableau est utilise moins d'espace que le suffixe de l'arbre. Mais comment pouvons-nous savoir ? Est-il une preuve mathématique ou l'on se base sur les expériences pratiques ?
    • Elle est basée sur la démonstration mathématique et expériences pratiques. Le comprimé suffixe arbre proposé par Sadakane en 2007 utilise nHk + 6n + o(n) de l'espace, où la nHk est le suffixe de tableau. Vous bénéficiez donc d'un point de vue de parent d'utilisation de l'espace, où SA est en fait une partie de la mise en œuvre de la ST. Il existe plusieurs implémentations qui s'avèrent réels d'utilisation de l'espace ainsi. Vous pouvez voir sa proposition ou la mienne. Et Sadakane ici: Kunihiko Sadakane.Theor. Comp. Sys., 41(4):589-607, 2007. La mienne : Une mise en œuvre de la dynamique complètement compressé suffixe arbres. Par Miguel Figueiredo hdl.handle.net/10362/4328
    InformationsquelleAutor Miguel Figueiredo
  2. 4

    Quelles sont les opérations que prévoyez-vous faire? libdivsufsort était à la fois la meilleure suffixe de la matrice de mise en œuvre de C.

    • Qu'est-ce que la technique de la réalisation que de l'efficacité pour le suffixe de la matrice de la construction?
    • En temps opportun question. AmpLab vient de sortir une version parallèle en profondeur explication, amplab.cs.berkeley.edu/publication/...
    InformationsquelleAutor Chad Brewbaker
  3. 2

    À l'aide du Suffixe Arbres, vous pouvez écrire quelque chose qui va correspondre à votre dictionnaire à votre texte en O(n+m+k) le temps où n est lettres dans votre dictionnaire, m est les lettres de votre texte, et k est le nombre de matchs. Tente sont beaucoup plus lents pour cela. Je ne suis pas sûr de ce qu'un Suffixe Tableau, alors je ne peux pas commenter sur ce point.

    Cela dit, il est non-trivial de code et je n'arrive pas à savoir de toutes les bibliothèques Java qui fournissent les fonctions nécessaires.

    • À propos de Suffixe Tableaux: en.wikipedia.org/wiki/Suffix_array
    • Ouais, j'ai lu sur le Suffixe Tableaux. Tour des ils ont la même asymptotique de la vitesse comme le Suffixe arbres, mais sont plus efficace de l'espace. Ils sont certainement une option.
    InformationsquelleAutor swestrup
  4. 1

    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 sonne comme une application pour les Aho-Corasick algorithme: 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 temps linéaire).

    (La description dans ces notes de cours, accessible à partir de l' "liens Externes" de la section de la page de Wikipedia, c'est beaucoup plus facile à lire que la description sur la page elle-même.)

    InformationsquelleAutor Matthew Slattery
  5. 1

    Trie vs Suffixe arbre

    à la fois la structure de données d'assurer une très rapide regarder vers le haut, le temps de recherche est proportionnelle à la longueur du mot de requête, la complexité en temps O(m) où m est la longueur du mot de requête.

    c'est dire si nous avons mot de requête qui en ont 10 caractères, donc nous avons besoin d'au plus 10 étapes pour les trouver.

    Trie : Un arbre pour stocker des chaînes de caractères dans laquelle il y a un nœud pour chaque préfixe commun. Les chaînes de caractères sont stockées dans la feuille supplémentaire nœuds.

    le suffixe de l'arbre: Une représentation compacte d'un trie correspondant pour les suffixes d'une chaîne où tous les nœuds avec un enfant sont fusionnées avec leurs parents.

    def sont de :
    Dictionnaire des Algorithmes et Structures de Données

    généralement Trie utilisé pour indexer les mots du dictionnaire (lexique) ou tous les ensembles de chaînes de caractères
    exemple D={abcd, abcdd, bxcdf,.....,zzzz }

    un suffixe de l'arbre utilisée pour l'indexation de texte en utilisant la même structure de données "Trie" sur tous les suffixes de notre texte
    T=abcdabcg
    tous les suffixes de T = {abcdabcg , abcdabc , abcdab, abcda, abcd abc , ab, a}

    maintenant il ressemble à un des groupes de chaînes.
    nous construisons un Trie de plus de plus de ce groupes de chaînes de caractères (tous les suffixes de T).

    la construction de la structure de données est linéaire, il O(n) dans le temps et dans l'espace.

    en cas de dicionary (un ensemble de chaînes de caractères): n = la somme des caractères de tous les mots.
    dans le texte : n = longueur du texte.

    suffixe tableau : c'est une technique pour représenter un suffixe arbre en comprimé space, c'est un tableau de toutes les positions de départ des suffixes d'une chaîne de caractères.

    il est plus lent que le suffixe de l'arbre à la recherche de temps.

    pour plus d'informations allez sur wikipedia , il y a un bon article de parler sur ce sujet.

    InformationsquelleAutor ibra
  6. 1

    Je préfère le Suffixe de la Machine Automatique.
    Vous pouvez trouver plus de détails par le biais de mon site:
    http://www.fogsail.net/2019/03/06/20190306/

    entrez la description de l'image ici

    tout d'abord, Si vous avez utilisé la normale de la construction, il prend O(n^2) de voyager tout le suffixe

    Nous utilisons radix-trier pour trier le suffixe Tableau en premier caractère.

    Mais, si nous avons en quelque sorte le premier caractère, nous pouvons utiliser ces informations.

    Détails sont montré par les images (négligence Chinois)

    On trie un tableau par la première clé, le résultat est présenté par le rectangle rouge

    ,,....-->,,....

    entrez la description de l'image ici

    #include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1001 * 100 + 10;
struct suffixArray {
int str[maxn], sa[maxn], rank[maxn], lcp[maxn];
int c[maxn], t1[maxn], t2[maxn];
int n;
void init() { n = 0; memset(sa, 0, sizeof(sa)); }
void buildSa(int Rdx) {
int i, *x = t1, *y = t2;
for(i = 0; i < Rdx; i++) c[i] = 0;
for(i = 0; i < n; i++) c[x[i] = str[i]]++;
for(i = 1; i < Rdx; i++) c[i] += c[i-1];
for(i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;
for(int offset = 1; offset <= n; offset <<= 1) {
int p = 0;
for(i = n-offset; i < n; i++) y[p++] = i;
for(i = 0; i < n; i++) if(sa[i] >= offset) y[p++] = sa[i] - offset;
//radix sort
for(i = 0; i < Rdx; i++) c[i] = 0;
for(i = 0; i < n; i++) c[x[y[i]]]++;
for(i = 1; i < Rdx; i++) c[i] += c[i-1];
for(i = n-1; i >= 0; i--) { sa[--c[x[y[i]]]] = y[i]; y[i] = 0; }
//rebuild x and y
swap(x, y); x[sa[0]] = 0; p = 1;
for(i = 1; i < n; i++)
x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+offset] == y[sa[i]+offset] ? p-1 : p++;
if(p >= n) break;
Rdx = p;
}
}
    InformationsquelleAutor Fogsail Chen
  7. 0

    Cette mise en œuvre de l'induite par l'algorithme de tri (appelé isc) a une version de Java pour la construction de suffixe tableaux.

    InformationsquelleAutor hexcoder