Question:

Published on: 12 October, 2024

What is a minimum spanning tree ? Describe Huffman’s Algorithm.

Answer:

A *spanning tree* of a graph is just a subgraph that contains all the vertices and is a tree. A graph may have many spanning trees; for instance the complete graph on four vertices

**Huffman Algorithm**

Huffman’s algorithm is a method for building an extended binary tree with a minimum weighted path length from a set of given weights.

Huffman coding is based on the frequency of occurance of a data item (pixel in images). The principle is to use a lower number of bits to encode the data that occurs more frequently. Codes are stored in a * Code Book* which may be constructed for each image or a set of images. In all cases the code book plus encoded data must be transmitted to enable decoding.

The Huffman algorithm is now briefly summarised:

· A bottom-up approach

1. Initialization: Put all nodes in an OPEN list, keep it sorted at all times (e.g., ABCDE).

2. Repeat until the OPEN list has only one node left:

(a) From OPEN pick two nodes having the lowest frequencies/probabilities, create a parent node of them.

(b) Assign the sum of the children's frequencies/probabilities to the parent node and insert it into OPEN.

(c) Assign code 0, 1 to the two branches of the tree, and delete the children from OPEN.

Symbol Count Code Subtotal (# of bits)

---------- ----- --------- --------------------

A 11 0 11

B 5 100 15

C 6 101 18

D 5 110 15

E 6 111 18

TOTAL (# of bits): 77

The following points are worth noting about the above algorithm:

Decoding for the above two algorithms is trivial as long as the coding table (the statistics) is sent before the data. (There is a bit overhead for sending this, negligible if the data file is big.)

**Unique Prefix Property**: no code is a prefix to any other code (all symbols are at the leaf nodes) -> great for decoder, unambiguous.

If prior statistics are available and accurate, then Huffman coding is very good.

In the above example:

Number of bits needed for Huffman Coding is: 77 / 33 = 2.3

Subjects

Trending

Random questions

**Write Short Note on Rapid Application Development**

12 October, 2024

How insertion sort and selection sorts are different?

23 January, 2022

12 October, 2024

12 October, 2024

**Discuss about SCHEDULING**

12 October, 2024