Radix/Patricia Trie的STLish lower_bound函数

最近，我一直在研究Patricia尝试，并使用一个非常好的C++ implementation，它可以用作STL排序关联容器。帕特里夏尝试不同于普通的二叉树，因为叶节点具有指向内部节点的后指针。但是，如果仅通过叶节点后向指针访问内部节点，则可以通过按顺序遍历来按字母顺序遍历Patricia trie。Radix/Patricia Trie的STLish lower_bound函数

这引出了一个问题：是否可以使用Patricia trie实现STL lower_bound和upper_bound函数？我使用的实现确实是实现这些功能，但是它们不能按预期工作。

例如：

typedef uxn::patl::trie_set<std::string> trie; 
trie ts; 
ts.insert("LR"); 
ts.insert("BLQ"); 
ts.insert("HCDA"); 

trie::iterator it = ts.lower_bound("GG"); 
std::cout << *it << std::endl;

此输出BLQ，当我期望它输出HCDA。（例如，一个std::set，肯定会在这里输出HCDA。）

我通过电子邮件发送了制作此库的开发人员，但从未得到回复。无论如何，我觉得我对Patricia如何尝试工作有很好的理解，而且我无法弄清楚lower_bound是甚么可能的。问题在于lower_bound似乎依赖于按字典顺序比较两个字符串的能力。由于树中不存在“GG”，因此我们需要找出哪个元素> =到GG。但Radix/Patricia尝试不使用字典比较来从节点移动到节点;而是每个节点存储一个比特索引，该比特索引用于对搜索关键字执行比特比较。位比较的结果告诉你是否向左或向右移动。这使得在树中很容易找到特定的前缀。但是，如果前缀不存在于树中（例如我的搜索“GG”），似乎没有任何方法可以获得lower_bound，而不用进行字典比较。

我正在使用的C++实现似乎没有实现lower_bound的事实，证实了我怀疑它可能不可行。尽管如此，你可以按字母顺序遍历树，这让我觉得可能有办法做到这一点。

有没有人有这方面的经验，或知道是否有可能与Patricia Trie实现lower_bound功能？

来源

2010-09-20 Channel72

只要容器实际上是分类的，这当然是可能的。在最坏的情况下，你可以：trie :: iterator it = ts.begin（）; while（it！= ts.end（）&& * it <“GG”）++ it;你是否可以更有效地做到这一点是另一个问题。如果使用实际的trie结构不可能做得更好，我会感到惊讶，但我不太了解这些尝试从浏览中发现代码中的错误。 – aschepler 2010-09-28 15:44:12

是的，这是可能的。我已经实现了一个这样做的变体，而D.J.Bernstein的页面将其描述为快速操作之一。

http://cr.yp.to/critbit.html

原则上，你继续匹配的前缀，直到你无法比拟的更多，然后你去到下一个值，并且有你之后的节点。

来源

2010-10-10 05:02:51 janm

Radix/Patricia Trie的STLish lower_bound函数

回答

相关问题