Lossless Compression Using Binary Necklace Classes and Multiple Huffman Trees
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 2001
- Accession Number
- ADA397592
Entities
People
- William L. Crowley Jr
Organizations
- Naval Postgraduate School