انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

Huffman

This is an important and widely-used example of a statistical compression algorithm. As with all such algorithms the basic idea is to identify those data items (symbols) that appear most frequently and give them the shortest codes.

This is achieved by first creating a binary tree as follows...

1. Rank the symbols by their frequency (which should sum

      to 1) and create a node for each symbol.

2. Create a new node by joining the two lowest ranked

     nodes and summing their rankings together.

3. Continue until all nodes on the tree are joined to create

     a single node of rank 1.

Binary tree example:

Having obtained the binary tree it is now possible to

calculate the Huffman code for each symbol...

1. Starting at the root assign 0 to the branch with the

     higher value and 1 to the branch with the lower value.

2. Once the tree is traversed the code for each symbol

    may be obtained by following the path from the root to

     that symbol.

This ensures that that the highest frequency symbols have

the shortest codes and that a continuous stream of

encoded bits may be uniquely decoded.

To illustrate how codes are assigned:

Decoding

Decoding a Huffman code is very easy. For example

decode

0110010001110100010011

when

A = 1

B = 000

C = 010

D = 011

E = 0010

F = 0011

Efficiency

It is possible to calculate the average number of bits per

character by multiplying the length of each character code

by its frequency and then taking the sum...

In the previous example this yields the following average

number of bits per character:

1 x 0.40 = 0.40

3 x 0.20 = 0.60

3 x 0.13 = 0.39

3 x 0.12 = 0.36

4 x 0.08 = 0.32

4 x 0.07 = 0.28

                 2.35