User:Ss020/sandbox

SC205 PROJECT

Motivation

• Many digital data streams contain a lot of redundant information. For example, a file may contain more zeros than ones: 0, 0, 0, 0, 1, 0 ,0 , 1, 0, 0, 0, 1, 1.

• Uncompressed data can take up a lot of space, which is not optimal for storing data on a fixed hard drive space and transferring data over fixed bandwidth.

• Example: One minute of uncompressed HD video can be over 1 GB. How can we fit a 2-3 hour HD film on a 1-2 GB disc ?

• We want to minimize the original data to reduce superfluous information.

• There are two points we need to take care of:

1. A good algorithm to achieve maximum data compression.
2. Maximum data compression that can be achieved without losing any data and can be recovered to exact bit sequence after decompression.

Approach

Huffman Coding

• It is a lossless data compression algorithm. The main idea is to assign variable-length codes to input characters.
• Lengths of the assigned codes are based on the frequencies of corresponding characters. The most frequent character gets the smallest code and the least frequent character gets the largest code.
• Here variable-length codes assigned to input characters are prefix codes, meaning the codes are assigned in such a way that the code assigned to one character is not the prefix of code assigned to any other character.
• This makes sure that there is no ambiguity while decompressing.

Formulate the Mathematics

1. Calculate the frequency of each character in the code.
2. Sort the characters in descending order of the frequency. These are stored in a priority queue (Q) using a binary heap.
3. Create an empty node *. Assign the minimum frequency (last element of Q)  to the left child of z and assign the second minimum frequency (second last element of Q) to the right child of *. Set the value of the * as the sum of the above two minimum frequencies (* denote the internal nodes).
4. Remove these two minimum frequencies from Q and add the sum into the list of frequencies .
5. Insert node * into Q.
6. Repeat steps 2 to 5 for all the characters.
7. For each non-leaf node, assign 0 to the left edge and 1 to the right edge.

Solve the Mathematics

Let's look for the original code -  “ABACCADCDACDACC”

1. Counting frequency of each character in code

   

2. Sorting character according to their frequency

   

3. Creating empty node for Huffman Tree

   

   

4. Repeating steps 2 to 5 of algorithm

   

   

5. Repeating steps 2 to 5 of algorithm

   

   

6. Assigning Huffman codes to each character

   

Solve the Mathematics

For decoding the code, we can take the code and traverse through the tree to find the character.

Let 101 is to be decoded, we can traverse from the root as in the figure below.

Interpretation and significance of the solution for application

After performing Huffman coding on the original code, we arrived at the following encoded result: “ABACCADCDACDACC”.

Comparing general encoded bits with Huffman encoded bits:

General code   - 000100101000111011001011001010 (30 bits)

Huffman code - 1110011001110101011101011100 (28 bits)

Compressed ratio  is  0.93 %

The compression ratio appears to be quite little. However, as the size of our input code grows, so does the performance of Huffman coding.

Bibliography

Huffman coding

https://mathworld.wolfram.com/HuffmanCoding.html

https://www.geeksforgeeks.org/huffman-coding-greedy-algo-3/

https://ocw.mit.edu/courses/mathematics/18-310-principles-of-discrete-applied-mathematics-fall-2013/lecture-notes/MIT18_310F13_Ch19.pdf

Wikipedia

https://youtu.be/eJ1lbXKjDfA

Recorded presentation

https://youtu.be/2m60HT3OMOI