13-07-2012, 02:58 PM
Huffman Encoding
huffman.ppt (Size: 97.5 KB / Downloads: 208)
Entropy
Entropy is a measure of information content: the number of bits actually required to store data.
Entropy is sometimes called a measure of surprise
A highly predictable sequence contains little actual information
Example: 11011011011011011011011011 (what’s next?)
Example: I didn’t win the lottery this week
A completely unpredictable sequence of n bits contains n bits of information
Example: 01000001110110011010010000 (what’s next?)
Example: I just won $10 million in the lottery!!!!
Note that nothing says the information has to have any “meaning” (whatever that is)
Fixed and variable bit widths
To encode English text, we need 26 lower case letters, 26 upper case letters, and a handful of punctuation
We can get by with 64 characters (6 bits) in all
Each character is therefore 6 bits wide
We can do better, provided:
Some characters are more frequent than others
Characters may be different bit widths, so that for example, e use only one or two bits, while x uses several
We have a way of decoding the bit stream
Must tell where each character begins and ends
Creating a Huffman encoding
For each encoding unit (letter, in this example), associate a frequency (number of times it occurs)
You can also use a percentage or a probability
Create a binary tree whose children are the encoding units with the smallest frequencies
The frequency of the root is the sum of the frequencies of the leaves
Repeat this procedure until all the encoding units are in the binary tree
Practical considerations
It is not practical to create a Huffman encoding for a single short string, such as ABRACADABRA
To decode it, you would need the code table
If you include the code table in the entire message, the whole thing is bigger than just the ASCII message
Huffman encoding is practical if:
The encoded string is large relative to the code table, OR
We agree on the code table beforehand
For example, it’s easy to find a table of letter frequencies for English (or any other alphabet-based language)