A greedy algorithm for building an optimal prefix-free binary code for a set of symbols given their frequencies, assigning shorter codes to more frequent symbols; a foundational technique behind many lossless data-compression formats.
Facts
Core PrincipleA lossless data compression method that assigns shorter variable-length codes to more frequent symbols and longer codes to rarer ones, derived from each symbol's estimated probability, producing an optimal prefix code among methods that encode symbols separately. 1 Connections
Associated With
Verified en.wikipedia.org/wiki/DEFLATE: "Deflate ... is a lossless data compression algorithm that uses a combination of LZ77 and Huffman coding."
In Field
Sources
1. Wikipedia: Huffman coding
Wikimedia FoundationLead section, first paragraph
an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".
Lead section, second paragraph
more common symbols are generally represented using fewer bits than less common symbols.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.