Huffman coding: Difference between revisions

Revision as of 13:16, 13 January 2025

Revision as of 13:19, 13 January 2025

Line 163:

===Compression===

[[File:Huffman_coding_visualisation.svg|thumb|360pxupright=1.5|Visualisation of the use of Huffman coding to encode the message "A_DEAD_DAD_CEDED_A_BAD_BABE_A_BEADED_ABACA_A_DEAD_DAD_{{breakzwsp}}BEDCEDED_A_BAD_{{zwsp}}BABE_A_BEADED_{{zwsp}}ABACA_BED". In steps 2 to 6, the letters are sorted by increasing frequency, and the least frequent two at each step are combined and reinserted into the list, and a partial tree is constructed. The final tree in step 6 is traversed to generate the dictionary in step 7. Step 8 uses it to encode the message.]]

[[Image:Huffman coding example.svg|thumb|A source generates 4 different symbols <math>\{a_1 , a_2 , a_3 , a_4 \}</math> with probability <math>\{0.4 ; 0.35 ; 0.2 ; 0.05 \}</math>. A binary tree is generated from left to right taking the two least probable symbols and putting them together to form another equivalent symbol having a probability that equals the sum of the two symbols. The process is repeated until there is just one symbol. The tree can then be read backwards, from right to left, assigning different bits to different branches. The final Huffman code is: