Article Preview
Buy Now
| Print: | |
| PDF: |
Feature
Huffman Compression
An application of binary trees
Issue: 3.3 (January/February 2005)
Author: Thomas Reed
Author Bio: Thomas Reed has been programming as a hobbyist for more than 20 years, and fell in love with the Mac in 1984.
Article Description: No description available.
Article Length (in bytes): 7,220
Starting Page Number: 34
RBD Number: 3316
Resource File(s): None
Related Link(s): None
Known Limitations: None
Excerpt of article text...
In the last issue, this column discussed binary trees as a searching tool. This month, let's look at another application of binary trees. Huffman compression, described in a paper by David Huffman in 1952, is a general purpose compression algorithm. Huffman compression is, in fact, so useful that even modern compression formats such as JPEG and MP3 employ the Huffman algorithm as a part of their specification.
The Huffman algorithm employs a method of compression that involves replacing bytes from the input string with codes having a shorter bit length. The most frequently occurring bytes should have the shortest codes, often as few as one or two bits long. A binary tree is an integral part of this process. It is used in the compression process to generate these codes, as well as the expansion process, where it helps to convert the codes back into the original bytes.
Let's take a look at a very simple example. The string "apple" could be compressed using the codes p=0, a=10, l=110, e=111. Replacing the letters with these codes results in the binary string 1000110111. That's only ten bits, compared with 40 in the original string, which means the compressed data is only a quarter the size of the original. This is an impressive savings!
...End of Excerpt. Please purchase the magazine to read the full article.
Article copyrighted by REALbasic Developer magazine. All rights reserved.
|
