Content deleted Content added
FrozenBirdXD (talk | contribs) Clean up/copyedit, improve readability |
ReidMoffat (talk | contribs) m Link fix |
||
| (5 intermediate revisions by 5 users not shown) | |||
Line 40:
|}
]]
In [[computer science]] and [[information theory]], a '''Huffman code''' is a particular type of optimal [[prefix code]] that is commonly used for [[Lossless compression|lossless data compression]]. The process of finding or using such a code is '''Huffman coding''', an algorithm developed by [[David A. Huffman]] while he was a [[Doctor of Science|Sc.D.]] student at [[Massachusetts Institute of Technology|MIT]], and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".<ref name=":0">{{Cite journal | last1 = Huffman | first1 = D. |author-link1=David A. Huffman| title = A Method for the Construction of Minimum-Redundancy Codes | doi = 10.1109/JRPROC.1952.273898 | journal = [[Proceedings of the IRE]]| volume = 40 | issue = 9 | pages = 1098–1101 | year = 1952 | url = http://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf}}</ref>
The output from Huffman's algorithm can be viewed as a [[variable-length code]] table for encoding a source symbol (such as a character in a file). The algorithm derives this table from the estimated probability or frequency of occurrence (''weight'') for each possible value of the source symbol. As in other [[entropy encoding]] methods, more common symbols are generally represented using fewer bits than less common symbols. Huffman's method can be efficiently implemented, finding a code in time [[linear time|linear]] to the number of input weights if these weights are sorted.<ref>{{cite journal | first = Jan | last = Van Leeuwen | author-link = Jan van Leeuwen | url = http://www.staff.science.uu.nl/~leeuw112/huffman.pdf | title = On the construction of Huffman trees | journal = ICALP | year =1976 | pages = 382–410 | access-date = 20 February 2014}}</ref> However, although optimal among methods encoding symbols separately, Huffman coding [[#Optimality|is not always optimal]] among all compression methods – it is replaced with [[arithmetic coding]]<ref name="LiDrew2014">{{cite book|author1=Ze-Nian Li|author2=Mark S. Drew|author3=Jiangchuan Liu|title=Fundamentals of Multimedia|url=https://books.google.com/books?id=R6vBBAAAQBAJ|date=9 April 2014|publisher=Springer Science & Business Media|isbn=978-3-319-05290-8}}</ref> or [[asymmetric numeral systems]]<ref name=PCS2015>[https://ieeexplore.ieee.org/document/7170048 J. Duda, K. Tahboub, N. J. Gadil, E. J. Delp, ''The use of asymmetric numeral systems as an accurate replacement for Huffman coding''], Picture Coding Symposium, 2015.</ref> if a better compression ratio is required.
Line 253 ⟶ 254:
=== Adaptive Huffman coding ===
A variation called '''[[adaptive Huffman coding]]''' involves calculating the probabilities dynamically based on recent actual frequencies in the sequence of source symbols, and changing the coding tree structure to match the updated probability estimates. It is used rarely in practice, since the cost of updating the tree makes it slower than optimized [[Arithmetic coding#Adaptive arithmetic coding|adaptive arithmetic coding]], which is more flexible and has better compression.{{citation needed|date=June 2025}}
=== Huffman template algorithm ===
Line 264 ⟶ 265:
In the standard Huffman coding problem, it is assumed that each symbol in the set that the code words are constructed from has an equal cost to transmit: a code word whose length is ''N'' digits will always have a cost of ''N'', no matter how many of those digits are 0s, how many are 1s, etc. When working under this assumption, minimizing the total cost of the message and minimizing the total number of digits are the same thing.
''Huffman coding with unequal letter costs'' is the generalization without this assumption: the letters of the encoding alphabet may have non-uniform lengths, due to characteristics of the transmission medium. An example is the encoding alphabet of [[Morse code]], where a 'dash' takes longer to send than a 'dot', and therefore the cost of a dash in transmission time is higher. The goal is still to minimize the weighted average codeword length, but it is no longer sufficient just to minimize the number of symbols used by the message. No algorithm is known to solve this in the same manner or with the same efficiency as conventional Huffman coding, though it has been solved by [[Richard M. Karp]]<ref>{{Cite journal |last=Karp |first=Richard M. |author-link=Richard M. Karp |title=Minimum-redundancy coding for the discrete noiseless channel
=== {{anchor|Hu-Tucker coding|Alphabetic Huffman coding|Alphabetic Huffman tree}}Optimal alphabetic binary trees (Hu–Tucker coding) ===
| |||