Lossless compression using binary necklace classes and multiple huffman trees
Loading...
Authors
Crowley, William L.
Subjects
Advisors
Fredricksen, Harold M.
Date of Issue
2001-06
Date
June 2001
Publisher
Monterey, California. Naval Postgraduate School
Language
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.
Type
Thesis
Description
Series/Report No
Department
Applied Mathematics
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
x, 159 p. ; 28 cm.
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.