Lossless compression using binary necklace classes and multiple huffman trees
Download
Author
Crowley, William L.
Date
2001-06Advisor
Fredricksen, Harold M.
Metadata
Show full item recordAbstract
In this thesis, we present two lossless compression approaches. Our Rotational Tree Approach (RTA) is based upon mathematics developed by Fredricksen. RTA uses the rotations associated with binary necklace classes to disperse source bit strings to a forest of Huffinan encoding trees. Our Indexed Tree Approach (ITA) also uses a Huffman forest, but disperses bit strings via a simpler mechanism based upon the first few bits of each string. For text compression, we find RTA to be competitive with standard Huffman encoding while ITA is generally superior by a small margin of 1% - 3%. Both approaches owe their (limited) success to decreased modeling overhead as compared to standard Huffman encoding. Compression results against the Canterbury Corpus test suit and complete Java implementation code are included as appendices. Index Tree.