基於排序/選擇操作的基數特里爾

現在我正在實現一個基數特里（也稱爲帕特里夏特里）來索引排序的字符串。所以我需要一個rank（）操作來知道匹配節點左邊有多少個節點。更正式，基於排序/選擇操作的基數特里爾

rankT(x) = |{t∈T | t < x}| for T⊆U and x∈U, where T is a radix trie and U is a universe of key. 
meaning that calculation of the number of left leaf nodes in the trie.

例如，有三個按鍵，使得

key set = {"abc", "def", "ghi"}, and index is 0, 1, 2.

所以帕特里夏線索將這些象下面這樣：

 root 
    /| \ 
    abc def ghi

和秩（）函數應該如果鍵是「def」則返回1;如果鍵是「abc」則返回0。

我的問題是如何有效地實現rank（）操作？我認爲在每次插入之後重新計算節點的排名是低效的。

基數特里的論述，是如下： http://en.wikipedia.org/wiki/Radix_tree

謝謝〜

來源

2014-01-06 Junho Suh

爲了能夠插入文字和快速計算排名，你可以存儲代表的單詞數子樹中的一個值每個節點。然後查詢等級時，你可以從葉子節點x行程達根積累的rank(x)

因此，例如，你可以有一個基數特里像值（括號數字是在樹字數）字「一」，「BCD」，「BG」和「高清」

root 
/| \ 
a(1) | def(1) 
    b(2) 
    / \ 
    cd(1) g(1)

要查找單詞「BG」的rank()。你開始在節點g(1)，你上去：

在節點b(2)你你積累離開的g(1)所有子樹的值。設置等級（bg）=大小（cd）
在節點root您可累積b(2)左側的所有子樹的值。所以等級（BG）=尺寸（CD）+尺寸（A）= 1 + 1 = 2

要查找單詞的rank() 「高清」

在節點root你你積累def(1)左側的所有子樹的值。所以秩（DEF）=尺寸（A）+尺寸（B）= 2 + 1 = 3

至於運行而言：對於字符串x你可能經過槽len(x)父節點。並且在每個節點處最多可以有|A|兒童，其中A是您的字母表。所以運行時將是O(len(x) * |A|)

來源

2014-01-06 13:08:34 cyon

如果我添加插入後排名2的「be」會怎樣？如何在插入密鑰時計算密鑰x的等級？ –

當你在插入節點的時候從根節點開始往下走時，你可以按照從已經插入的節點到根節點的方式來計算它的等級。但是，在插入時，您還必須增加存儲在您傳遞的每個節點上的數字。你這樣做是因爲這個數字代表以該節點爲根的子樹結尾的單詞。這意味着，在插入「be」時，您必須將節點「b」處的計數器從2增加到3。 – cyon

基於排序/選擇操作的基數特里爾

回答

相關問題