FILE COMPRESSION

FILE COMPRESSION: 

FILE COMPRESSION USING HUFFMAN ALGORITHM

Compression: 

Compression The process of coding that will effectively reduce the total number of bits needed to represent certain information.

PowerPoint Presentation: 

There are two main categories: Lossless Lossy Compression ratio:

Information Theory: 

Information Theory We define the entropy  of an information source with alphabet S = { s 1 , s 2 , …, s n } as p i - probability that s i occurs in the source and log 2 1/ p i is amount of information in s i .

PowerPoint Presentation: 

The entropy  gives a lower bound on the average number of bits needed to code a symbol in the alphabet.   l where l is the average bit length of the code words produced by the encoder assuming a memoryless source .

TYPES OF CODING:: 

TYPES OF CODING: RUN-LENGTH CODING VARIABLE LENGTH CODING HUFFMAN CODING PIXEL REPLACEMENT CODING

Huffman Coding:: 

Huffman Coding: Huffman coding constructs a binary tree starting with the probabilities of each symbol in the alphabet The tree is built in a bottom-up manner The tree is then used to find the codeword for each symbol An algorithm for finding the Huffman code for a given alphabet with associated probabilities .

PURPOSE OF HUFFMAN CODING:: 

PURPOSE OF HUFFMAN CODING: Proposed by Dr. David A. Huffman in 1952. “A Method for the Construction of Minimum Redundancy Codes” Applicable to many forms of data transmission - text files Huffman coding is a technique used to compress files for transmission

Representing binary tree:: 

Representing binary tree: 1.Insertion of a node in a binary tree 2.Deletion of some element from binary search tree a)deletion of leaf node b)deletion of a node having one child c)deletion of a node having two children 3.Searching of an element in the binary tree. 4.Display of binary tree.

HUFFMAN CODING:: 

HUFFMAN CODING:

Huffman Code: Example : 

Huffman Code: Example The following example bases on a data source using a set of five different symbols. The symbol's frequencies are: Symbol Frequency A 24 B 12 C 10 D 8 E 8 ----> total 186 bit (with 3 bit per code word)

PowerPoint Presentation: 

The two rarest symbols 'E' and 'D' are connected first, followed by 'C' and 'D'. The new parent nodes have the frequency 16 and 22 respectively and are brought together in the next step. The resulting node and the remaining symbol 'A' are subordinated to the root node that is created in a final step.

Code Tree according to Huffman: : 

Code Tree according to Huffman:

PowerPoint Presentation: 

symbol frequency code Code length Total length A 24 0 1 24 B 12 100 3 36 C 10 101 3 30 D 8 110 3 24 E 8 111 3 24

Representation:: 

Representation: The Huffman algorithm is based on statistical coding, which means that the probability of a symbol has a direct bearing on the length of its representation. The more probable the occurrence of a symbol is, the shorter will be its bit -size representation.

PowerPoint Presentation: 

In any file, certain characters are used more than others. Using binary representation, the number of bits required to represent each character depends upon the number of characters that have to be represented. Using one bit we can represent two characters, i.e., 0 represents the first character and 1 represents the second character. Using two bits we can represent four characters, and so on.

REAL TIME IMPLEMENTATION:: 

REAL TIME IMPLEMENTATION: The file compresseion concept will be evoluated in the field of data transaction. The vast amount data are shrinked using this compression algorithm. Now a days we can compress the data using zip and convert rar file formats when mail transation .

MAINTAINING;: 

MAINTAINING; Using this huffman method we can save the memory space or size of the storage source in our system. Huffman coding was very efficient and quality one for best data transaction process. We all keep this methodology to save our cost of transaction, convenience and efficiency.

PowerPoint Presentation: 

THANK YOU!