67

在 C/C++ 中是否有任何速度和缓存高效的 trie 实现？我知道 trie 是什么，但我不想重新发明轮子，自己实现它。

4

12 回答 12

38

如果您正在寻找 ANSI C 实现，您可以从 FreeBSD 中“窃取”它。您要查找的文件名为radix.c。它用于管理内核中的路由数据。

于 2009-06-24T09:35:33.277 回答
19

我意识到问题是关于现成的实现，但仅供参考......

在你开始讨论 Judy 之前，你应该阅读“ A Performance Comparison of Judy to Hash Tables ”。然后谷歌搜索标题可能会给你一生的讨论和反驳阅读。

我所知道的一个明确的缓存意识 trie 是HAT-trie。

HAT-trie 在正确实施时非常酷。但是，对于前缀搜索，您需要对哈希桶进行排序，这与前缀结构的想法有些冲突。

一个更简单的 trie 是Burst-trie，它本质上为您提供了某种标准树（如 BST）和 trie 之间的插值。我在概念上喜欢它，而且它更容易实现。

于 2009-08-14T23:38:17.730 回答
7

我在libTrie上运气不错。它可能没有经过专门的缓存优化，但对于我的应用程序来说性能一直不错。

于 2009-06-24T05:21:55.210 回答
5

GCC 附带了一些数据结构作为其“基于策略的数据结构”的一部分。这包括一些 trie 实现。

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

于 2011-05-17T19:20:45.567 回答
4

参考，

  • Double-Array Trie 实现文章（包括C实现）
  • TRASH - A dynamic LC-trie and hash data structure --（2006 PDF 参考，描述了在 Linux 内核中用于实现 IP 路由表中地址查找的动态 LC-trie
于 2009-06-24T05:28:45.920 回答
4

Judy 数组：非常快速且内存高效的有序稀疏动态数组，用于位、整数和字符串。Judy 数组比任何二叉搜索树（包括 avl 和红黑树）都更快且内存效率更高。

于 2009-06-24T11:33:50.447 回答
3

Cedar、HAT-Trie和JudyArray非常棒，你可以在这里找到基准。

基准测试结果

于 2015-02-27T05:44:20.743 回答
2

您也可以在http://tommyds.sourceforge.net/尝试 TommyDS

有关与 nedtries 和 judy 的速度比较，请参阅网站上的基准页面。

于 2011-01-10T20:02:48.280 回答
1

缓存优化是您可能必须要做的事情，因为您必须将数据放入单个缓存行中，该缓存行通常约为 64 字节（如果您开始组合数据，例如指针，这可能会起作用） . 但这很棘手:-)

于 2009-06-24T10:09:25.313 回答
0

Burst Trie似乎更节省空间。我不确定您可以从任何索引中获得多少缓存效率，因为 CPU 缓存非常小。但是，这种 trie 足够紧凑，可以将大型数据集保存在 RAM 中（常规 Trie 不会）。

我编写了一个 Burst trie 的 Scala 实现，它还结合了我在 GWT 的 type-ahead 实现中发现的一些节省空间的技术。

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

于 2014-04-29T18:48:36.723 回答
0

与我的数据集提到的几个 TRIE 实现相比，我使用 marisa-trie 获得了非常好的结果（性能和大小之间的非常好的平衡）。

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

于 2016-10-25T10:02:35.867 回答
0

分享我对 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;
        }
    }

};
于 2017-04-15T22:50:12.163 回答