Trie Implementierung [geschlossen]

Question

Gibt es eine Drehzahl- und Cache-effiziente Implementierungen von Trie in C / C ++? Ich weiß, was ein Trie ist, aber ich will nicht das Rad neu erfinden, es selbst zu implementieren.

Answer 1

Wenn Sie eine ANSI-C-Implementierung suchen Sie „stehlen“ kann es von FreeBSD. Die Datei die Sie suchen, heißt radix.c . Es wird verwendet, um Routing-Daten im Kernel zu verwalten.

Answer 2

Ich weiß, die Frage nach bereit Implementierungen war, aber als Referenz ...

Bevor Sie Judy springen sollten Sie gelesen haben „ Ein Performance-Vergleich von Judy Tabellen bis Hash “. Dann den Titel googeln werden Sie wahrscheinlich eine Lebensdauer von Diskussion geben und rebutals zu lesen.

Der eine explizit Cache bewusste trie ich kenne ist die HAT-trie .

Die HAT-trie, wenn sie richtig umgesetzt wird, ist sehr cool. Doch für Präfixsuche benötigen Sie einen Sortierschritt auf dem Hash-Eimer, die etwas mit der Idee einer Vorsilbe Struktur kollidiert.

Eine etwas einfachere trie ist die Burst-trie , die Ihnen im wesentlichen zwischen einem Standard-Baum von einer Art (wie ein BST) und einem Trie eine Interpolation gibt. Ich mag es, konzeptionell und es ist viel einfacher zu implementieren.

Answer 3

Ich habe viel Glück gehabt mit libTrie . Es kann nicht optimiert-Cache, aber die Leistung ist für meine Anwendungen immer anständig gewesen.

Answer 4

GCC Schiffe mit einer Handvoll von Datenstrukturen im Rahmen der „richtlinienbasierte Datenstrukturen“. Dazu gehören ein paar Trie-Implementierungen.

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

Answer 5

Referenzen,

• Doppel-Array Trie Implementierung Artikel (enthält eine C Implementierung )
• TRASH - Eine dynamische LC-trie und Hash Datenstruktur - (a 2006 PDF Referenz eine dynamische LC-trie im Linux-Kernel verwendet, beschreibt Adressensuche in der IP-Routing-Tabelle
zu implementieren

Answer 6

Judy Arrays : Sehr schnell und speichereffiziente geordnete spärlich dynamische Arrays für Bits, Zahlen und Strings. Judy Arrays sind schneller und mehr Speicher effizienter als jede binäre Suchbaum (inkl. Avl & rot-schwarz-Bäume).

Answer 7

Sie können auch versuchen TommyDS unter http://tommyds.sourceforge.net/

Sehen Sie die Benchmarks Seite auf der Website für einen Geschwindigkeitsvergleich mit nedtries und judy.

Answer 8

Cedar , HAT-Trie und JudyArray ist ziemlich genial, können Sie die Benchmark finden hier .

Answer 9

Cache-Optimierungen sind etwas, das Sie wahrscheinlich tun, gehen zu müssen, weil Sie die Daten in eine einzige Cache-Zeile passen müssen werden in der Regel so etwas wie 64 Bytes ist (die, wenn Sie die Kombination von Daten beginnen werden wahrscheinlich funktionieren, wie als Zeiger). Aber es ist schwierig: -)

Answer 10

Burst Trie der scheint ein bisschen mehr Platz zu sein effizient. Ich bin mir nicht sicher, wie viel Cache-Effizienz, die Sie aus jedem Index erhalten können, da CPU-Caches so winzig sind. Allerdings ist diese Art von Trie ist viel kompakt genug, um große Datenmengen in RAM (wo eine regelmäßige Trie würde nicht) zu halten.

Ich schrieb eine Scala Implementierung eines Bursts trie, die auch einige platzsparende Techniken enthalten, die ich in GWT Type-Ahead-Implementierung gefunden.

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

Answer 11

Ich hätte sehr gute Ergebnisse (sehr gute Balance zwischen Leistung und Größe) mit marisa-trie im Vergleich zu mehreren TRIE-Implementierungen mit meinem Datensatz erwähnt.

https://github.com/s-yata/marisa-trie/ Baum / Master

Answer 12

Sharing meiner "schnelle" Umsetzung für Trie, getestet nur in Basisszenario:

#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;
        }
    }

};