Perl 前缀树实现
前缀树,用来处理大量字符串的查找、排序,也称为字典树,可以代替hash table。
http://en.wikipedia.org/wiki/Trie
以下翻译自Wikipedia:
The following are the main advantages of tries over binary search trees (BSTs):
相对二叉搜索树的优点:
1. 搜索更快。搜索一个长度为m 的字串最坏情况下需要O(m),而二叉树取决与树的深度,最坏情况需要O(m log n)的时间。
2. Trie 树在存储空间上更加高效。由于相同的前缀,他们会共享前缀节点.
3. Trie 可以用来完成最大前缀字符串匹配。
4. 从跟节点到叶节点的节点数与搜索字符串长度相同。
The following are the main advantages of tries over hash tables:
As mentioned, a trie has a number of advantages over binary search trees.[4] A trie can also be used to replace a hash table, over which it has the following advantages:
Tries do have some drawbacks as well:
Perl代码:
a => 1and => 1is => 1just => 1testing => 2this => 1