radix trie with rank/select operations

algorithm

Solution

To be able to insert words and calculate rank quickly, you could store a value representing the number of words in the subtree on each node. Then when querying the rank you could travel up from the leaf node `x` to the root accumulating the value for the `rank(x)`

So for example you could have a radix trie like (number in paren is number of words in subtree) of words "a", "bcd", "bg" and "def"

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

To find the `rank()` of word "bg". You start at node `g(1)` and you go up:

- At node `b(2)` you you accumulate the values of all subtrees left of `g(1)`. Set rank(bg) = size(cd)

- At node `root` you you accumulate the values of all subtrees left of `b(2)`. So rank(bg) = size(cd) + size(a) = 1 + 1 = 2

To find the `rank()` of word "def"

- At node `root` you you accumulate the values of all subtrees left of `def(1)`. So rank(def) = size(a) + size(b) = 2 + 1 = 3

As far as runtime is concerned: For string `x` you may go through trough `len(x)` parent nodes. And at each node there can be at most `|A|` children, where `A` is your alphabet. So the runtime would be `O(len(x) * |A|)`

Problem

Now I am implementing a radix trie (also called patricia trie) to index sorted character strings. So I need a rank() operation to know how many nodes are existed in left of the matched node. More formally, ``` 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. ``` For example, there are three keys such that ``` key set = {"abc", "def", "ghi"}, and index is 0, 1, 2. ``` So the patricia trie stores these like below: ``` root / | \ abc def ghi ``` and the rank() function should return 1 if key is "def", and 0 if key is "abc". My question is that how can implement the rank() operation efficiently? I think a recalculation of rank of the node after each insertion is inefficient. The exposition of radix trie is as below: http://en.wikipedia.org/wiki/Radix_tree Thanks~

Original source