blocks|key|1307073|text|如果你正在寻找一个ANSI实现，你可以从FreeBSD那里“偷走”它。您要查找的文件名为radix.c。它用于管理内核中的路由数据。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1307074|entityMap|0|LINK|mutability|MUTABLE|url|http://bxr.su/f/sys/net/radix.c^0|18|7|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

if you are looking for an ANSI C implementation you can "steal" it from FreeBSD. The file you are looking for is called <a href="http://bxr.su/f/sys/net/radix.c" rel="noreferrer">radix.c</a>. It's used for managing routing data in kernel.

blocks|key|1522230|text|我知道这个问题是关于现成的实现，但作为参考...|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1522231|在你攻击朱迪之前，你应该先读一读"A+Performance+Comparison+of+Judy+to+Hash+Tables“。然后，在谷歌上搜索这个标题可能会让你一生都在讨论和反驳。|offset|length|1522232|我所知道的一个显式缓存敏感的trie是HAT-trie。|1522233|HAT-trie，当正确实现时，是非常酷的。但是，对于前缀搜索，您需要在散列存储桶上执行排序步骤，这与前缀结构的概念有些冲突。|1522234|一个更简单的trie是burst-trie，它本质上给出了某种标准树(如BST)和trie之间的插值。我喜欢它的概念，它更容易实现。|1522235|entityMap|0|LINK|mutability|MUTABLE|url|http://www.nothings.org/computer/judy/|1|http://crpit.com/confpapers/CRPITV62Askitis.pdf|2|http://www.cs.rmit.edu.au/~jz/fulltext/acmtois02.pdf^0|0|H|1B|0|0|J|8|1|0|0|B|A|2|0^^$0|@$1|2|3|4|5|6|7|X|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Y|8|@]|9|@$D|Z|E|10|1|11]]|A|$]]|$1|F|3|G|5|6|7|12|8|@]|9|@$D|13|E|14|1|15]]|A|$]]|$1|H|3|I|5|6|7|16|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|17|8|@]|9|@$D|18|E|19|1|1A]]|A|$]]|$1|L|3|-4|5|6|7|1B|8|@]|9|@]|A|$]]]|M|$N|$5|O|P|Q|A|$R|S]]|T|$5|O|P|Q|A|$R|U]]|V|$5|O|P|Q|A|$R|W]]]]

I realize the question was about ready implementations, but for reference...

Before you jump on Judy you should have read "<a href="http://www.nothings.org/computer/judy/" rel="nofollow noreferrer">A Performance Comparison of Judy to Hash Tables</a>". Then googling the title will likely give you a lifetime of discussion and rebutals to read.

The one explicitly cache-conscious trie I know of is the <a href="http://crpit.com/confpapers/CRPITV62Askitis.pdf" rel="nofollow noreferrer">HAT-trie</a>. 

The HAT-trie, when implemented correctly, is very cool. However, for prefix search you need a sorting step on the hash buckets, which somewhat clashes with the idea of a prefix structure.

A somewhat simpler trie is the <a href="http://www.cs.rmit.edu.au/~jz/fulltext/acmtois02.pdf" rel="nofollow noreferrer">burst-trie</a> which essentially gives you an interpolation between a standard tree of some sort (like a BST) and a trie. I like it conceptually and it's much easier to implement.

blocks|key|1307053|text|我和libTrie在一起很走运。它可能没有专门针对缓存进行优化，但对于我的应用程序来说，它的性能总是不错的。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1307054|entityMap|0|LINK|mutability|MUTABLE|url|http://wikipedia-clustering.speedblue.org/trie.php^0|2|7|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

I've had good luck with <a href="http://wikipedia-clustering.speedblue.org/trie.php" rel="noreferrer">libTrie</a>. It may not be specifically cache optimized but the performance has always been decent for my applications.

blocks|key|1522329|text|作为其“基于策略的数据结构”的一部分，GCC附带了一些数据结构。这包括一些trie实现。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1522330|http://gcc.gnu.org/onlinedocs/libstdc%2B%2B/ext/pb_ds/trie_based_containers.html|offset|length|1522331|entityMap|0|LINK|mutability|MUTABLE|url|http://gcc.gnu.org/onlinedocs/libstdc%2B%2B/ext/pb_ds/trie_based_containers.html^0|0|0|24|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

GCC ships with a handful of data structures as part of its "Policy-based data structures". This includes a few trie implementations. 

<a href="http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/trie_based_containers.html" rel="noreferrer">http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/trie_based_containers.html</a>

blocks|key|1522198|text|Judy+arrays：非常快速且节省内存的有序稀疏动态数组，用于位、整数和字符串。Judy数组比任何二进制搜索树都更快，内存效率更高。avl和红黑树)。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1522199|entityMap|0|LINK|mutability|MUTABLE|url|http://judy.sourceforge.net/^0|0|B|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

<a href="http://judy.sourceforge.net/" rel="nofollow noreferrer">Judy arrays</a>: Very fast and memory efficient ordered sparse dynamic arrays for bits, integers and strings. Judy arrays are faster and more memory efficient than any binary-search-tree (incl. avl &amp; red-black-trees).

blocks|key|1522441|text|Cedar、HAT-Trie和JudyArray非常棒，你可以找到基准测试here。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1522442|​|1522443|📷|atomic|1522444|1522445|entityMap|0|LINK|mutability|MUTABLE|url|http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/#perf|1|https://github.com/luikore/hat-trie|2|https://github.com/mpictor/judy-template|3|http://kokizzu.blogspot.com/2015/02/string-associative-array-benchmark.html|4|IMAGE|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/6ba99ad9af252eae310d5ba7bf9ff654.png|imageAlt^0|0|5|0|6|8|1|F|9|2|11|4|3|0|0|0|1|4|0|0^^$0|@$1|2|3|4|5|6|7|13|8|@]|9|@$A|14|B|15|1|16]|$A|17|B|18|1|19]|$A|1A|B|1B|1|1C]|$A|1D|B|1E|1|1F]]|C|$]]|$1|D|3|E|5|6|7|1G|8|@]|9|@]|C|$]]|$1|F|3|G|5|H|7|1H|8|@]|9|@$A|1I|B|1J|1|1K]]|C|$]]|$1|I|3|E|5|6|7|1L|8|@]|9|@]|C|$]]|$1|J|3|-4|5|6|7|1M|8|@]|9|@]|C|$]]]|K|$L|$5|M|N|O|C|$P|Q]]|R|$5|M|N|O|C|$P|S]]|T|$5|M|N|O|C|$P|U]]|V|$5|M|N|O|C|$P|W]]|X|$5|Y|N|Z|C|$10|11|12|-4]]]]

<a href="http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/#perf" rel="nofollow noreferrer">Cedar</a>, <a href="https://github.com/luikore/hat-trie" rel="nofollow noreferrer">HAT-Trie</a>, and <a href="https://github.com/mpictor/judy-template" rel="nofollow noreferrer">JudyArray</a> is quite awesome, you can find the benchmark <a href="http://kokizzu.blogspot.com/2015/02/string-associative-array-benchmark.html" rel="nofollow noreferrer">here</a>.

<img src="https://i.stack.imgur.com/mBZbh.png" alt="benchmark result">

blocks|key|1307254|text|您也可以在http://tommyds.sourceforge.net/上试用TommyDS|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1307255|请参阅网站上的基准测试页面，以获得与nedtries和judy的速度比较。|1307256|entityMap|0|LINK|mutability|MUTABLE|url|http://tommyds.sourceforge.net/^0|5|V|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]]|C|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]]]

You can also try TommyDS at <a href="http://tommyds.sourceforge.net/" rel="nofollow">http://tommyds.sourceforge.net/</a>

See the benchmarks page on the site for a speed comparison with nedtries and judy.

blocks|key|1307115|text|缓存优化是您可能不得不做的事情，因为您必须将数据放入单个缓存行中，该缓存行通常约为64字节(如果您开始组合数据，例如指针，这可能会起作用)。但这很棘手:-)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1307116|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Cache optimizations are something you'll probably are going to have to do, because you'll have to fit the data into a single cacheline which generally is something like 64 bytes (which will probably work if you start combining data, such as pointers). But it's tricky :-)

blocks|key|1522391|text|Burst+Trie's似乎更节省空间。我不确定你能从任何索引中获得多大的缓存效率，因为CPU缓存是如此的小。然而，这种trie足够紧凑，可以将大型数据集保存在RAM中(而常规Trie不会)。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1522392|我编写了一个burst+trie的Scala实现，它还结合了一些我在GWT的预输入实现中发现的节省空间的技术。|1522393|https://github.com/nbauernfeind/scala-burst-trie|1522394|entityMap|0|LINK|mutability|MUTABLE|url|http://goanna.cs.rmit.edu.au/~jz/fulltext/acmtois02.pdf|1^0|0|C|0|0|0|0|1C|1|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@$A|R|B|S|1|T]]|C|$]]|$1|D|3|E|5|6|7|U|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|V|8|@]|9|@$A|W|B|X|1|Y]]|C|$]]|$1|H|3|-4|5|6|7|Z|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]|P|$5|K|L|M|C|$N|G]]]]

<a href="http://goanna.cs.rmit.edu.au/~jz/fulltext/acmtois02.pdf" rel="nofollow">Burst Trie's</a> seem to be a bit more space efficient. I'm not sure how much cache-efficiency you can get out of any index since CPU-caches are so tiny. However, this kind of trie is plenty compact enough to keep large data sets in RAM (where a regular Trie would not).

I wrote a Scala implementation of a burst trie that also incorporates some space-saving techniques that I found in GWT's type-ahead implementation.

<a href="https://github.com/nbauernfeind/scala-burst-trie" rel="nofollow">https://github.com/nbauernfeind/scala-burst-trie</a>

blocks|key|1307493|text|与我的数据集中提到的几个TRIE实现相比，我使用marisa-trie获得了非常好的结果(在性能和大小之间取得了很好的平衡)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1307494|https://github.com/s-yata/marisa-trie/tree/master|offset|length|1307495|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|1D|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@$D|O|E|P|1|Q]]|A|$]]|$1|F|3|-4|5|6|7|R|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|C]]]]

I've had very good results (very good balance between performance and size) with marisa-trie compared to several TRIE implementations mentioned with my data set. 

<a href="https://github.com/s-yata/marisa-trie/tree/master" rel="nofollow">https://github.com/s-yata/marisa-trie/tree/master</a>

blocks|key|1522554|text|分享我的Trie的“快速”实现，仅在基本场景中测试：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1522555|#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;+%2B%2Bi)+{
++++++++++++++++if(sons[i]+!=+NULL)
++++++++++++++++++++cout+<<+"+"+<<+(char)('a'%2Bi);
++++++++++++}
++++++++++++cout+<<+endl;
++++++++++++cout+<<+"strsInBranch+=+"+<<+strsInBranch+<<+endl;
++++++++++++cout+<<+"isEndOfStr+=+"+<<+isEndOfStr+<<+endl;
++++++++++++for(int+i=0;+i<ENG_LET;+%2B%2Bi)+{
++++++++++++++++if(sons[i]+!=+NULL)
++++++++++++++++++++sons[i]->print();
++++++++++++}

++++++++}
++++++++TrieNode(bool+_isEndOfStr+=+false):isEndOfStr(_isEndOfStr),+strsInBranch(0)+{
++++++++++++for(int+i=0;+i<ENG_LET;+%2B%2Bi)+{
++++++++++++++++sons[i]+=+NULL;
++++++++++++}
++++++++}
++++++++~TrieNode()+{
++++++++++++for(int+i=0;+i<ENG_LET;+%2B%2Bi)+{
++++++++++++++++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();+%2B%2Bi)+{
++++++++++++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();+%2B%2Bi)+{
++++++++++++int+letIdx+=+s[i]-'a';
++++++++++++if(curr->sons[letIdx]+==+NULL)+{
++++++++++++++++curr->sons[letIdx]+=+new+TrieNode();++++
++++++++++++}
++++++++++++%2B%2Bcurr->strsInBranch;
++++++++++++curr+=+curr->sons[letIdx];
++++++++}
++++++++%2B%2Bcurr->strsInBranch;
++++++++curr->isEndOfStr+=+true;
++++}
++++void+removeString(const+string&+s)+{
++++++++if(!isExists(s))
++++++++++++return;
++++++++TrieNode*+curr+=+head;
++++++++for(int+i=0;+i<s.size();+%2B%2Bi)+{
++++++++++++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;+%2B%2Bi)+{
++++++++++++delete+head->sons[i];
++++++++++++head->sons[i]+=+NULL;
++++++++}
++++}

};|code-block|syntax|javascript|1522556|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Sharing my "fast" implementation for Trie, tested just in basic scenario:

<pre><code>#define ENG_LET 26

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

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

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

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

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

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

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

};
</code></pre>

Is there any speed- and cache-efficient implementations of trie in C/C++?
I know what a trie is, but I don't want reinvent the wheel, implementing it myself.

Trie implementation

数据结构

FreeBSD

路由

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

问Trie实现
EN

回答 11

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Trie实现EN

回答 11

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Trie实现
EN