Implementazione Trie

Question

Esiste implementazioni di trie in C/C++ efficienti in termini di velocità e cache? So cos'è un trie, ma non voglio reinventare la ruota, implementandola da sola.

Answer 1

se siete alla ricerca di un'implementazione ANSI C si può "rubare" da FreeBSD. il file che si sta cercando si chiama 012.. È usato per gestire i dati di routing nel kernel.

Answer 2

Ho avuto fortuna con libTrie. Potrebbe non essere specificamente ottimizzato per la cache, ma le prestazioni sono sempre state decenti per le mie applicazioni.

Answer 3

Riferimenti,

• A Double-Array Trie implementation articolo (include una C implementazione)
• TRASH - A LC-trie e dei dati di hash struttura dinamica - (un riferimento 2006 PDF che descrive un LC-trie dinamica utilizzata in il kernel Linux per implementare ricerca di indirizzi nella tabella di routing IP

Answer 4

Le ottimizzazioni della cache sono qualcosa che probabilmente dovresti fare, perché dovrai inserire i dati in una singola cacheline che generalmente è qualcosa come 64 byte (che probabilmente funzionerà se inizi a combinare i dati, come puntatori). Ma è difficile :-)

Answer 5

Judy arrays: Array dinamici sparsi ordinati molto veloci e con memoria per bit, interi e stringhe. Gli array Judy sono più veloci e più efficienti in termini di memoria rispetto a qualsiasi albero di ricerca binaria (compresi gli alberi rossi-neri avl &).

Answer 6

mi rendo conto la questione era di circa implementazioni pronti, ma per riferimento ...

Prima di saltare su Judy dovreste leggere "A Performance Comparison of Judy to Hash Tables". Quindi googling il titolo probabilmente ti darà una vita di discussione e rebutal da leggere.

L'unico trio esplicitamente attento alla cache che conosco è lo HAT-trie.

HAT-trie, se implementato correttamente, è molto interessante. Tuttavia, per la ricerca del prefisso è necessario un passaggio di ordinamento sui bucket hash, che si scontra in qualche modo con l'idea di una struttura di prefisso.

Un trie un po 'più semplice è il burst-trie che essenzialmente ti dà un'interpolazione tra un albero standard di qualche tipo (come un BST) e un trie. Mi piace concettualmente ed è molto più facile da implementare.

Answer 7

Si può anche provare a TommyDS http://tommyds.sourceforge.net/

Si veda la pagina di riferimento sul sito per un confronto di velocità con nedtries e Judy.

Answer 8

GCC viene fornito con una manciata di strutture di dati come parte delle sue "strutture dati basate su criteri". Ciò include alcune implementazioni trie.

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

Answer 9

Burst Trie's sembrano essere un po 'più efficiente dello spazio. Non sono sicuro di quanta efficienza della cache si possa ottenere da un indice dato che le cache della CPU sono così piccole. Tuttavia, questo tipo di trie è abbastanza compatto da contenere grandi set di dati nella RAM (dove un normale Trie non lo farebbe).

Ho scritto un'implementazione Scala di un burst trie che incorpora anche alcune tecniche di risparmio di spazio che ho trovato nell'implementazione di tipo-avanti di GWT.

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

Answer 10

Cedar, HAT-Trie, e JudyArray è abbastanza impressionante, è possibile trovare il punto di riferimento here.

Answer 11

che ho avuto risultati molto buoni (ottimo equilibrio tra prestazioni e dimensioni) con marisa-trie rispetto a diverse implementazioni TRIE citati con il mio set di dati.

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

Answer 12

Condividere la mia realizzazione "veloce" per Trie, testato solo nello scenario di 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; 
     } 
    } 

};