Implémentation de Trie

Question

Y a-t-il des implémentations de trie en C/C++ efficaces en termes de vitesse et de cache? Je sais ce que c'est, mais je ne veux pas réinventer la roue, la mettre en œuvre moi-même.

Answer 1

si vous êtes à la recherche d'une implémentation ANSI C, vous pouvez « voler » avec FreeBSD. le fichier que vous recherchez est appelé radix.c. Il est utilisé pour gérer les données de routage dans le noyau.

Answer 2

J'ai eu de la bonne chance avec libTrie. Il peut ne pas être spécifiquement optimisé en cache, mais les performances ont toujours été décentes pour mes applications.

Answer 3

Références,

• Un Double-Array Trie implementation article (comprend une C mise en œuvre)
• TRASH - Une LC-Trie dynamique et la structure des données de hachage - (référence 2006 PDF décrivant une LC-Trie dynamique utilisé dans le noyau Linux pour mettre en œuvre la recherche d'adresse dans la table de routage IP

Answer 4

Les optimisations de cache sont quelque chose que vous allez probablement devoir faire, parce que vous devrez adapter les données dans une seule cacheline qui est généralement quelque chose comme 64 octets (qui fonctionnera probablement si vous commencez à combiner des données, tels que les pointeurs). Mais c'est difficile :-)

Answer 5

Judy arrays: Très rapide et efficace en mémoire ordonnée des tableaux dynamiques clairsemés pour les bits, entiers et chaînes. Les tableaux de Judy sont plus rapides et plus efficaces en mémoire que n'importe quel arbre de recherche binaire (y compris avl & red-black-trees).

Answer 6

Je me rends compte que la question était sur les implémentations prêts, mais pour référence ...

Avant de sauter sur Judy vous devez avoir lu « A Performance Comparison of Judy to Hash Tables ». Ensuite, googler le titre vous donnera probablement une vie de discussion et de réfutations à lire.

Celui dont je connais le cache explicitement est le HAT-trie.

Le HAT-trie, lorsqu'il est implémenté correctement, est très cool. Cependant, pour la recherche de préfixes, vous avez besoin d'une étape de tri sur les compartiments de hachage, ce qui heurte quelque peu l'idée d'une structure de préfixe.

Un peu plus simple est le burst-trie qui vous donne essentiellement une interpolation entre un arbre standard de quelque sorte (comme un BST) et un trie. Je l'aime conceptuellement et c'est beaucoup plus facile à mettre en œuvre.

Answer 7

Vous pouvez également essayer TommyDS à http://tommyds.sourceforge.net/

Voir la page de référence sur le site pour une comparaison de vitesse avec nedtries et judy.

Answer 8

GCC est livré avec une poignée de structures de données dans le cadre de ses «structures de données basées sur des règles». Cela inclut quelques implémentations.

http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/trie_based_containers.html

Answer 9

Burst Trie's semblent être un peu plus efficace de l'espace. Je ne suis pas certain de l'efficacité du cache que vous pouvez tirer d'un index, car les caches CPU sont si petits. Cependant, ce type de trie est suffisamment compact pour garder de grands ensembles de données en RAM (où un Trie ordinaire ne le ferait pas).

J'ai écrit une implémentation Scala d'une rafale qui incorpore également des techniques peu encombrantes que j'ai trouvées dans l'implémentation de type GWT.

https://github.com/nbauernfeind/scala-burst-trie

Answer 10

Cedar, HAT-Trie et JudyArray est tout à fait impressionnant, vous pouvez trouver la référence here.

Answer 11

J'ai eu de très bons résultats (très bon équilibre entre la performance et la taille) avec marisa-Trie par rapport à plusieurs implémentations de TRIE mentionnées avec mon ensemble de données.

https://github.com/s-yata/marisa-trie/tree/master

Answer 12

Partage ma mise en œuvre "rapide" pour Trie, testé juste dans le scénario de base:

#define ENG_LET 26 

class Trie { 
    class TrieNode { 
    public: 
     TrieNode* sons[ENG_LET]; 
     int strsInBranch; 
     bool isEndOfStr; 

     void print() { 
      cout << "----------------" << endl; 
      cout << "sons.."; 
      for(int i=0; i<ENG_LET; ++i) { 
       if(sons[i] != NULL) 
        cout << " " << (char)('a'+i); 
      } 
      cout << endl; 
      cout << "strsInBranch = " << strsInBranch << endl; 
      cout << "isEndOfStr = " << isEndOfStr << endl; 
      for(int i=0; i<ENG_LET; ++i) { 
       if(sons[i] != NULL) 
        sons[i]->print(); 
      } 

     } 
     TrieNode(bool _isEndOfStr = false):isEndOfStr(_isEndOfStr), strsInBranch(0) { 
      for(int i=0; i<ENG_LET; ++i) { 
       sons[i] = NULL; 
      } 
     } 
     ~TrieNode() { 
      for(int i=0; i<ENG_LET; ++i) { 
       delete sons[i]; 
       sons[i] = NULL; 
      } 
     } 
    }; 

    TrieNode* head; 
public: 
    Trie() { head = new TrieNode();} 
    ~Trie() { delete head; } 
    void print() { 
     cout << "Preorder Print : " << endl; 
     head->print(); 
    } 
    bool isExists(const string s) { 
     TrieNode* curr = head; 
     for(int i=0; i<s.size(); ++i) { 
      int letIdx = s[i]-'a'; 
      if(curr->sons[letIdx] == NULL) { 
       return false; 
      } 
      curr = curr->sons[letIdx]; 
     } 

     return curr->isEndOfStr; 
    } 
    void addString(const string& s) { 
     if(isExists(s)) 
      return; 
     TrieNode* curr = head; 
     for(int i=0; i<s.size(); ++i) { 
      int letIdx = s[i]-'a'; 
      if(curr->sons[letIdx] == NULL) { 
       curr->sons[letIdx] = new TrieNode();  
      } 
      ++curr->strsInBranch; 
      curr = curr->sons[letIdx]; 
     } 
     ++curr->strsInBranch; 
     curr->isEndOfStr = true; 
    } 
    void removeString(const string& s) { 
     if(!isExists(s)) 
      return; 
     TrieNode* curr = head; 
     for(int i=0; i<s.size(); ++i) { 
      int letIdx = s[i]-'a'; 

      if(curr->sons[letIdx] == NULL) { 
       assert(false); 
       return; //string not exists, will not reach here 
      } 
      if(curr->strsInBranch==1) { //just 1 str that we want remove, remove the whole branch 
       delete curr; 
       return; 
      } 
      //more than 1 son 
      --curr->strsInBranch; 
      curr = curr->sons[letIdx]; 
     } 
     curr->isEndOfStr = false; 
    } 

    void clear() { 
     for(int i=0; i<ENG_LET; ++i) { 
      delete head->sons[i]; 
      head->sons[i] = NULL; 
     } 
    } 

};