I've already done some research on this topic, but it still isn't quite clear to me.

According to this post patricia trees are radix trees with $r = 2$. Every patricia tree I've seen so far is used to store alphanumeric symbols. Assuming that there are used 8 bits to represent one symbol, $r$ is the number of bits compared and the radix of a radix tree is $2^r$ shouldn't the radix of a patricia tree be $2^8 = 256$?

If you have a look at a PATRICIA Tree with the following inputs (in this order):

  • smile
  • smiled
  • smiles

According to the linked post a Patricia tree should then look like this:

smile - - - smiled - - - smiles

But intuitively (by the alphanumeric representation) it should look like this

  • $\begingroup$ Not necessarily. If you know that the data is alphanumeric, you can use a smaller radix. $\endgroup$ Dec 6 '17 at 15:31
  • $\begingroup$ I understand the referenced post differently. A symbol may have 8 bits, but in Patricia trees you can split at any one of these bits, thus each split still has only at most two children. If you store all 256 permutations of a single symbol, your tree is 8 levels deep and 128 node wide. $\endgroup$
    – TilmannZ
    Dec 7 '17 at 20:25
  • $\begingroup$ @YuvalFilmus if you have another look at the post, there is an example of a patricia tree. This tree is correct for the binary representation but not for the raw alphanumeric. Any ideas how to explain this? $\endgroup$
    – Ian Fako
    Dec 8 '17 at 11:06
  • $\begingroup$ A Patricia tree has radix 2. It treats its input as a stream of bits. $\endgroup$ Dec 8 '17 at 11:09
  • $\begingroup$ @YuvalFilmus I updated my post to explain what I don't understand $\endgroup$
    – Ian Fako
    Dec 8 '17 at 11:25

Quoting Wikipedia:

PATRICIA trees are radix trees with radix equals 2, which means that each bit of the key is compared individually and each node is a two-way (i.e., left versus right) branch.

According to Wikipedia, Patricia is just a "brand name" coined by Donald R. Morrison, standing for Practical Algorithm To Retrieve Information Coded In Alphanumeric.

Patricia trees thus accept their input in the form of binary strings. If the input is a word, then it is first encoded in binary.

As for the smile/smiled/smiles example, it is explained in the linked post – each of these words is encoded as a binary string, and this is what the Patricia tree sees. It is completely unaware of the semantic interpretation of the bitstring as an alphanumeric word.

  • $\begingroup$ Does that mean a radix tree with r = 256 (as described in my question) would represent a tree in the correct form for alphanumeric? (assuming a symbol need 8 bits) $\endgroup$
    – Ian Fako
    Dec 8 '17 at 15:12
  • $\begingroup$ A radix tree with radix $r \neq 2$ is not a Patricia tree, since a Patricia tree has radix 2. $\endgroup$ Dec 8 '17 at 15:13
  • $\begingroup$ I mean a radix tree with r = 256 should be the right thing I'm looking for? $\endgroup$
    – Ian Fako
    Dec 8 '17 at 15:15
  • $\begingroup$ Only you know what you're looking for. $\endgroup$ Dec 8 '17 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.