What is the difference between trie and radix trie

问题:

Are the trie and radix trie data structures the same thing?

If they are same, then what is the meaning of radix trie (AKA Patricia trie)?

回答1:

A radix tree is a compressed version of a trie. In a trie, on each edge you write a single letter, while in a PATRICIA tree (or radix tree) you store whole words.

Now, assume you have the words hello, hat and have. To store them in a trie, it would look like:

    e - l - l - o
  /
h - a - t
      \
       v - e

And you need nine nodes. I have placed the letters in the nodes, but in fact they label the edges.

In a radix tree, you will have:

            *
           /
        (ello)
         /
* - h - * -(a) - * - (t) - *
                 \
                 (ve)
                   \
                    *

and you need only five nodes. In the picture above nodes are the asterisks.

So, overall, a radix tree takes less memory, but it is harder to implement. Otherwise the use case of both is pretty much the same.

回答2:

My question is whether Trie data structure and Radix Trie are the same thing?

In short, no. The category Radix Trie describes a particular category of Trie, but that doesn't mean that all tries are radix tries.

If they are[n't] same, then what is the meaning of Radix trie (aka Patricia Trie)?

I assume you meant to write aren't in your question, hence my correction.

Similarly, PATRICIA denotes a specific type of radix trie, but not all radix tries are PATRICIA tries.

---

What is a trie?

"Trie" describes a tree data structure suitable for use as an associative array, where branches or edges correspond to parts of a key. The definition of parts is rather vague, here, because different implementations of tries use different bit-lengths to correspond to edges. For example, a binary trie has two edges per node that correspond to a 0 or a 1, while a 16-way trie has sixteen edges per node that correspond to four bits (or a hexidecimal digit: 0x0 through to 0xf).

This diagram, retrieved from Wikipedia, seems to depict a trie with (at least) the keys 'A', 'to', 'tea', 'ted', 'ten' and 'inn' inserted:

If this trie were to store items for the keys 't', 'te', 'i' or 'in' there would need to be extra information present at each node to distinguish between nullary nodes and nodes with actual values.

---

What is a radix trie?

"Radix trie" seems to describe a form of trie that condenses common prefix parts, as Ivaylo Strandjev described in his answer. Consider that a 256-way trie which indexes the keys "smile", "smiled", "smiles" and "smiling" using the following static assignments:

root['s']['m']['i']['l']['e']['\0'] = smile_item;
root['s']['m']['i']['l']['e']['d']['\0'] = smiled_item;
root['s']['m']['i']['l']['e']['s']['\0'] = smiles_item;
root['s']['m']['i']['l']['i']['n']['g']['\0'] = smiling_item;

Each subscript accesses an internal node. That means to retrieve smile_item, you must access seven nodes. Eight node accesses correspond to smiled_item and smiles_item, and nine to smiling_item. For these four items, there are fourteen nodes in total. They all have the first four bytes (corresponding to the first four nodes) in common, however. By condensing those four bytes to create a root that corresponds to ['s']['m']['i']['l'], four node accesses have been optimised away. That means less memory and less node accesses, which is a very good indication. The optimisation can be applied recursively to reduce the need to access unnecessary suffix bytes. Eventually, you get to a point where you're only comparing differences between the search key and indexed keys at locations indexed by the trie. This is a radix trie.

root = smil_dummy;
root['e'] = smile_item;
root['e']['d'] = smiled_item;
root['e']['s'] = smiles_item;
root['i'] = smiling_item;

To retrieve items, each node needs a position. With a search key of "smiles" and a root.position of 4, we access root["smiles"[4]], which happens to be root['e']. We store this in a variable called current. current.position is 5, which is the location of the difference between "smiled" and "smiles", so the next access will be root["smiles"[5]]. This brings us to smiles_item, and the end of our string. Our search has terminated, and the item has been retrieved, with just three node accesses instead of eight.

---

What is a PATRICIA trie?

A PATRICIA trie is a variant of radix tries for which there should only ever be n nodes used to contain n items. In our crudely demonstrated radix trie pseudocode above, there are five nodes in total: root (which is a nullary node; it contains no actual value), root['e'], root['e']['d'], root['e']['s'] and root['i']. In a PATRICIA trie there should only be four. Let's take a look at how these prefixes might differ by looking at them in binary, since PATRICIA is a binary algorithm.

smile:   0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0000 0000  0000 0000
smiled:  0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0110 0100  0000 0000
smiles:  0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0111 0011  0000 0000
smiling: 0111 0011  0110 1101  0110 1001  0110 1100  0110 1001  0110 1110  0110 0111 ...

Let us consider that the nodes are added in the order they are presented above. smile_item is the root of this tree. The difference, bolded to make it slightly easier to spot, is in the last byte of "smile", at bit 36. Up until this point, all of our nodes have the same prefix. smiled_node belongs at smile_node[0]. The difference between "smiled" and "smiles" occurs at bit 43, where "smiles" has a '1' bit, so smiled_node[1] is smiles_node.

Rather than using NULL as branches and/or extra internal information to denote when a search terminates, the branches link back up the tree somewhere, so a search terminates when the offset to test decreases rather than increasing. Here's a simple diagram of such a tree (though PATRICIA really is more of a cyclic graph, than a tree, as you'll see), which was included in Sedgewick's book mentioned below:

A more complex PATRICIA algorithm involving keys of variant length is possible, though some of the technical properties of PATRICIA are lost in the process (namely that any node contains a common prefix with the node prior to it):

By branching like this, there are a number of benefits: Every node contains a value. That includes the root. As a result, the length and complexity of the code becomes a lot shorter and probably a bit faster in reality. At least one branch and at most k branches (where k is the number of bits in the search key) are followed to locate an item. The nodes are tiny, because they store only two branches each, which makes them fairly suitable for cache locality optimisation. These properties make PATRICIA my favourite algorithm so far...

I'm going to cut this description short here, in order to reduce the severity of my impending arthritis, but if you want to know more about PATRICIA you can consult books such as "The Art of Computer Programming, Volume 3" by Donald Knuth, or any of the "Algorithms in {your-favourite-language}, parts 1-4" by Sedgewick.

回答3:

TRIE:
We can have a search scheme where instead of comparing a whole search key with all existing keys (such as a hash scheme), we could also compare each character of the search key. Following this idea, we can build a structure (as shown below) which has three existing keys – “dad”, “dab”, and ”cab”.

         [root]
     ...// | \\...
           |  \
           c   d
           |    \
          [*]    [*]
      ...//|\.  ./|\\...        Fig-I
        a       a
       /       /
     [*]      [*]
 ...//|\..  ../|\\...
    /        /   \
   B        b     d
  /        /       \
 []       []       []

(cab)   (dab)     (dad)

This is essentially an M-ary tree with internal node, represented as [ * ] and leaf node, represented as [ ]. This structure is called a trie. The branching decision at each node can be kept equal to the number of unique symbols of the alphabet, say R. For lower case English alphabets a-z, R=26; for extended ASCII alphabets, R=256 and for binary digits/strings R=2.

Compact TRIE:
Typically, a node in a trie uses an array with size=R and thus causes waste of memory when each node has fewer edges. To circumvent the memory concern, various proposals were made. Based on those variations trie are also named as “compact trie” and “compressed trie”. While a consistent nomenclature is rare, a most common version of a compact trie is formed by grouping all edges when nodes have single edge. Using this concept, the above (Fig-I) trie with keys “dad”, “dab”, and ”cab” can take below form.

         [root]
     ...// | \\...
           |  \
          cab  da
           |    \
          [ ]   [*]                Fig-II
               ./|\\...
                 |  \
                 b   d
                 |    \
                []    []

Note that each of ‘c’, ‘a’, and ‘b’ is sole edge for its corresponding parent node and therefore, they are conglomerated into a single edge “cab”. Similarly, ‘d’ and a’ are merged into single edge labelled as “da”.

Radix Trie:
The term radix, in Mathematics, means a base of a number system, and it essentially indicates the number of unique symbols needed to represent any number in that system. For example, decimal system is radix ten,and binary system is radix two. Using the similar concept, when we’re interested in characterizing a data structure or an algorithm by the number of unique symbols of the underlying representational system, we tag the concept with the term “radix”. For example, “radix sort” for certain sorting algorithm. In the same line of logic, all variants of trie whose characteristics (such as depth, memory need, search miss/hit runtime, etc.) depend on radix of the underlying alphabets, we may call them radix “trie’s”. For example, an un-compacted as well as a compacted trie when uses alphabets a-z, we can call it a radix 26 trie. Any trie that uses only two symbols (traditionally ‘0’ and ‘1’) can be called a radix 2 trie. However, somehow many literatures restricted the use of the term “Radix Trie” only for the compacted trie.

Prelude to PATRICIA Tree/Trie:
It would be interesting to notice that even strings as keys can be represented using binary-alphabets. If we assume ASCII encoding, then a key “dad” can be written in binary form by writing the binary representation of each character in sequence, say as “011001000110000101100100” by writing binary forms of ‘d’, ‘a’, and ‘d’ sequentially. Using this concept, a trie (with Radix Two) can be formed. Below we depict this concept using a simplified assumption that the letters ‘a’,’b’,’c’, and’d’ are from a smaller alphabet instead of ASCII.

Note for Fig-III: As mentioned, to make the depiction easy, let’s assume an alphabet with only 4 letters {a,b,c,d} and their corresponding binary representations are “00”, “01”, “10” and “11” respectively. With this, our string keys “dad”, “dab”, and ”cab” become “110011”, “110001”, and “100001” respectively. The trie for this will be as shown below in Fig-III (bits are read from left to right just like strings are read from left to right).

          [root]
             \1               
              \
              [*]
             0/ \1               
             /   \
           [*]   [*]         
           0/     /               
           /     /0
         [*]    [*]      
        0/      /               
        /      /0
      [*]    [*]
     0/     0/ \1                Fig-III
     /      /   \
    [*]   [*]   [*]
     \1     \1    \1
      \      \     \
      []     []    []
    (cab)   (dab) (dad)

PATRICIA Trie/Tree:
If we compact the above binary trie (Fig-III) using single edge compaction, it would have much less nodes than shown above and yet, the nodes would still be more than the 3, the number of keys it contains. Donald R. Morrison found (in 1968) an innovative way to use binary trie to depict N keys using only N nodes and he named this data structure PATRICIA. His trie structure essentially got rid of single edges (one-way branching); and in doing so, he also got rid of the notion of two kinds of nodes – inner nodes (that don’t depict any key) and leaf nodes (that depict keys). Unlike the compaction logic explained above, his trie uses a different concept where each node includes an indication of how many bits of a key to be skipped for making a branching decision. Yet another characteristic of his PATRICIA trie is that it doesn’t store the keys – which means such data structure will not be suitable for answering questions like, list all keys that match a given prefix, but is good for finding if a key exists or not in the trie. Nonetheless, the term Patricia Tree or Patricia Trie has, since then, been used in many different but similar senses, such as, to indicate a compact trie [NIST], or to indicate a radix trie with radix two [as indicated in a subtle way in WIKI] and so on.

Trie that may not be a Radix Trie:
Ternary Search Trie (aka Ternary Search Tree) often abbreviated as TST is a data structure (proposed by J. Bentley and R. Sedgewick) which looks very similar to a trie with three-way branching. For such tree, each node has a characteristic alphabet ‘x’ so that branching decision is driven by whether a character of a key is less than, equal to or greater than ‘x’. Due to this fixed 3-way branching feature, it provides a memory-efficient alternative for trie, especially when R (radix) is very large such as for Unicode alphabets. Interestingly, the TST, unlike (R-way) trie, doesn’t have its characteristics influenced by R. For example, search miss for TST is ln(N) as opposed log_R(N) for R-way Trie. Memory requirements of TST, unlike R-way trie is NOT a function of R as well. So we should be careful to call a TST a radix-trie. I, personally, don’t think we should call it a radix-trie since none (as far as I know) of its characteristics are influenced by the radix,R, of its underlying alphabets.