## Thursday, December 10, 2015

### Compressed Trie - Patricia/Radix tries

TODO

http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Text/trie02.html
A radix tree (also patricia trie or radix trie or compact prefix tree) is a space-optimized trie data structure where each node with only one child is merged with its child.
compressed trie is a trie with one additional rule:
 Each internal node has   ≥ 2   children
Such compacted trie is als known as:
Converting a standard trie to a compressed tree
• Redundant node:
• An internal node v is redundant if
 Node v is not the root node,       and          Node v has 1 child node
Redundant chain of edges:
• chain of edges:
(v0,v1), (v1,v2), ..., (vk−1,vk)
is redundant if:

 Nodes   v1, v2, ..., vk−1   are redundant Nodes   v0   and   vk   are not redundant
Compression algorithm:
• Replace:
 a redundant chain or edges   (v0,v1), (v1,v2), ..., (vk−1,vk)
by one edge:

 (v0 ,vk)

• Replace:
 the label vk
by the label:

 v1 v2 ... vk
• Before compression:

• After compression:
Compressed trie is a trie with only one addition rule such that, every internal node must have≥ 2 children Compressed trie is also known as Radix trie (or) Patricia trie.
Trie shown in above figure converted to compressed trie like below.

https://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/tries.htm
http://www.sanfoundry.com/java-program-patricia-trie/
https://github.com/mlarocca/Algorithms/blob/master/PatriciaTrie.java
https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/trie/PatriciaTrie.html
http://grepcode.com/file/repo1.maven.org/maven2/com.groupbyinc/common-utils/23/org/apache/commons/collections4/trie/AbstractPatriciaTrie.java#AbstractPatriciaTrie