Huffman Coding
Huffman Coding Algorithm is a lossless data compression algorithm. In lossless data compression, the original data can be perfectly reconstructed from the compressed data.
This algorithm is developed by David A. Huffman in 1952 while he was a Ph.D. student at MIT. This algorithm is widely used in mainstream compression formats such as JPEG, PNG, MP3, GZIP etc.
The steps of the Huffman Coding algorithm are as following -
Step 1: Sort given symbols according to their frequency.
Then we create a Binary Tree using following steps -
Step 2: From the frequency table, select two symbols S1 and S2
with least frequencies(say ‘f1’ and ‘f2’). Create nodes for S1 and S2.
Step 3: Combine S1 and S2 to create a new symbol S12
with frequency ‘f1’ + ‘f2’. Create node for S12.
Step 4: Remove S1 and S2, Insert S12 into the frequency table while keeping it sorted.
Step 5: Repeat steps 2-4 until there is only one symbol left
in the frequency table
Time Complexity: O(n)
Space Complexity: O(n)
Видео Huffman Coding канала IDeserve
This algorithm is developed by David A. Huffman in 1952 while he was a Ph.D. student at MIT. This algorithm is widely used in mainstream compression formats such as JPEG, PNG, MP3, GZIP etc.
The steps of the Huffman Coding algorithm are as following -
Step 1: Sort given symbols according to their frequency.
Then we create a Binary Tree using following steps -
Step 2: From the frequency table, select two symbols S1 and S2
with least frequencies(say ‘f1’ and ‘f2’). Create nodes for S1 and S2.
Step 3: Combine S1 and S2 to create a new symbol S12
with frequency ‘f1’ + ‘f2’. Create node for S12.
Step 4: Remove S1 and S2, Insert S12 into the frequency table while keeping it sorted.
Step 5: Repeat steps 2-4 until there is only one symbol left
in the frequency table
Time Complexity: O(n)
Space Complexity: O(n)
Видео Huffman Coding канала IDeserve
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
Huffman Codes: An Information Theory Perspective3.4 Huffman Coding - Greedy MethodHuffman CodingText Compression with Huffman CodingTree: Huffman Decoding||Hackerrank||C++||Day 20Building Bridges Dynamic ProgrammingHow Computers Compress Text: Huffman Coding and Huffman TreesHuffman EncodingHow Huffman Trees Work - ComputerphileARITHMETIC CODINGHuffman’s Algorithm With ExampleHuffman Coding (Lossless Compression Algorithm)Huffman Coding Technique for binary system.Hash Table - Data Structures & Algorithms Tutorials In Python #5Huffman Coding - Python Implementation and DemoIntroduction to Huffman CodingHuffman coding || Easy methodHuffman Codes Compression (2/3) [كود مصري]Huffman Encoding (Binary Tree Data Structure)