CODEWITHSUNDEEP
stringalgorithmdata-structuresbit-manipulationtrie
user1516425
user1516425

Reputation: 1571

Compressed trie implementation?

I am going through a Udacity course and in one of the lectures (https://www.youtube.com/watch?v=gPQ-g8xkIAQ&feature=player_embedded), the professor gives the function high_common_bits which (taken verbatim from the lecture) looks like this in pseudocode:

function high_common_bits(a,b):
   return:
     - high order bits that a+b in common
     - highest differing bit set
     - all remaining bits clear

As an example:

a = 10101
b = 10011
high_common_bits(a,b) => 10100

He then says that this function is used in highly-optimized implementations of tries. Does anyone happen to know which exact implementation he's referring to?

Upvotes: 1

Views: 5095

Answers (3)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 86146

He was talking about Succinct Tries, tries in which each node requires only two bits to store (the theoretical minimum).

Steve Hanov wrote a very approachable blog post on Succinct Tries here. You can also read the original paper by Guy Jacobson (written as recently as 1989) which introduced them here.

Upvotes: 1

Jerry Coffin
Jerry Coffin

Reputation: 490653

A compressed trie stores a prefix in one node, then branches from that node to each possible item that's been seen that starts with that prefix.

In this case he's apparently doing a bit-wise trie, so it's storing a prefix of bits -- i.e., the bits at the beginning that the items have in common go in one node, then there are two branches from that node, one to a node for the next bit being a 0, and the other for the next bit being a 1. Presumably those nodes will be compressed as well, so they won't just store the next single bit, but instead store a number of bits that all matched in the items inserted into the trie so far.

In fact, the next bit following a given node may not be stored in the following nodes at all. That bit can be implicit in the link that's followed, so the next nodes store only bits after that.

Upvotes: 0

Justin
Justin

Reputation: 4216

If you are looking for a highly optimized bitwise compressed trie (aka Radix Tree). The BSD routing table uses one in it's implementation. The code is not easy to read though.

Upvotes: 5

Related Questions