Content deleted Content added
Thomas Meng (talk | contribs) →Informal description: added problem description with citation |
Citation bot (talk | contribs) Altered url. URLs might have been anonymized. Removed parameters. | Use this bot. Report bugs. | Suggested by Dominic3203 | Linked from User:Jim.belk/Most_viewed_math_articles_(2010) | #UCB_webform_linked 434/998 |
||
Line 261:
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 |url=https://ieeexplore.ieee.org/document/
=== {{anchor|Hu-Tucker coding|Alphabetic Huffman coding|Alphabetic Huffman tree}}Optimal alphabetic binary trees (Hu–Tucker coding) ===
| |||