[Verse 1]
Data compression is the name of the game
When file sizes got you feeling shame
Fixed-length codes waste precious space
Variable-length brings us saving grace
Start with frequencies, count each letter
Common symbols coded better
Build a tree from bottom up
Priority queue fills your cup
[Chorus]
Huffman coding saves the day
Frequent symbols shorter way
Less frequent get longer strings
Binary tree optimization brings
Left is zero, right is one
Greedy algorithm gets it done
Optimal prefix codes we make
Data compression for goodness sake
[Verse 2]
Two smallest frequencies combine
Create internal nodes every time
Parent holds the sum of both
Children sworn by sacred oath
No code word is prefix of another
That's the rule we can't ignore brother
Unique decoding guaranteed
Self-synchronizing is what we need
[Chorus]
Huffman coding saves the day
Frequent symbols shorter way
Less frequent get longer strings
Binary tree optimization brings
Left is zero, right is one
Greedy algorithm gets it done
Optimal prefix codes we make
Data compression for goodness sake
[Bridge]
Start with leaves at the bottom floor
Merge the smallest two or more
Until one root remains standing tall
That's the tree that rules them all
Read the path from root to leaf
Compression ratio brings relief
Forty percent or more you'll save
When Huffman's algorithm you crave
[Verse 3]
ASCII uses eight bits flat
But English text ain't balanced like that
Letter E appears the most
Gets the shortest code to boast
Letter Z shows up real rare
Longer code is only fair
Adaptive versions change on the fly
As new statistics pass on by
[Chorus]
Huffman coding saves the day
Frequent symbols shorter way
Less frequent get longer strings
Binary tree optimization brings
Left is zero, right is one
Greedy algorithm gets it done
Optimal prefix codes we make
Data compression for goodness sake
[Outro]
From JPEG to zip files too
Huffman's legacy shines through
Lossless compression at its best
Put your data to the test