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函數

回答

相關問題