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.
In Group: String Matching and Compression Algorithms, Lead
In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression.
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.