Реализация Trie

если вы ищете реализацию ANSI C, вы можете «украсть» ее у FreeBSD. Файл, который вы ищете, называется radix.c. Он используется для управления данными маршрутизации в ядре.

Я понимаю, что речь шла о готовых реализациях, но для справки ...

Прежде чем перейти к Джуди, вы должны прочитать «Сравнение производительности Джуди с хеш-таблицами» . Тогда поиск в Google заголовка, скорее всего, даст вам целую жизнь обсуждений и опровержений, которые нужно прочитать.

Я знаю одно явно ориентированное на кеширование дерево - это HAT-trie.

HAT-trie при правильной реализации - это очень круто. Однако для поиска по префиксу вам потребуется этап сортировки хэш-сегментов, что несколько противоречит идее структуры префикса.

Несколько более простое дерево - это burst-trie, которое по сути дает вам интерполяцию между каким-либо стандартным деревом (например, BST) и деревом. Мне нравится концептуально, и это намного проще реализовать.

Мне повезло с libTrie. Возможно, он не был специально оптимизирован для кеширования, но производительность для моих приложений всегда была достойной.

GCC поставляется с несколькими структурами данных как частью «структур данных на основе политик». Это включает в себя несколько реализаций trie.

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

Использованная литература,

• Статья о реализации двойного массива данных (включает C реализацию)
• TRASH - динамическая структура данных LC-дерева и хэша - - (справочник в формате PDF от 2006 г., описывающий динамическое дерево LC, используемое в ядре Linux для реализации поиска адресов в таблице IP-маршрутизации.

Массивы Джуди: очень быстрые и эффективные с точки зрения памяти упорядоченные разреженные динамические массивы для битов, целых чисел и строк. Массивы Judy быстрее и эффективнее с точки зрения памяти, чем любое дерево двоичного поиска (включая avl и красно-черные деревья).

кедр, HAT-Trie и JudyArray - это здорово, вы можете найти тест здесь.

Вы также можете попробовать TommyDS на http://tommyds.sourceforge.net/

См. Страницу тестов на сайте для сравнения скорости с nedtries и judy.

Оптимизация кеша - это то, что вам, вероятно, придется сделать, потому что вам нужно будет уместить данные в одну строку кеша, которая обычно составляет примерно 64 байта (что, вероятно, сработает, если вы начнете объединять данные, такие как указатели) . Но это сложно :-)

Burst Trie кажутся немного более компактными. Я не уверен, насколько эффективен кеш-память любого индекса, так как кеш-память ЦП настолько мала. Однако такой тип дерева достаточно компактен, чтобы хранить большие наборы данных в ОЗУ (в отличие от обычного дерева).

Я написал реализацию пакетного дерева на Scala, которая также включает в себя некоторые методы экономии места, которые я нашел в реализации GWT с опережающим вводом типов.

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

У меня были очень хорошие результаты (очень хороший баланс между производительностью и размером) с marisa-trie по сравнению с несколькими реализациями TRIE, упомянутыми в моем наборе данных.

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

Делюсь моей "быстрой" реализацией для Trie, протестированной только в базовом сценарии:

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

};