Huffman coding - Revision history

FrozenBirdXD: Clean up/copyedit, improve readability

2025-04-19T17:13:40Z

Clean up/copyedit, improve readability

← Previous revision		Revision as of 17:13, 19 April 2025
Line 40:		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 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>{{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>		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]]. 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.		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 248:		Line 248:

	=== ''n''-ary Huffman coding ===		=== ''n''-ary Huffman coding ===
	The '''''n''-ary Huffman''' algorithm uses ~~the~~ {0, 1,..., ''n~~'' −~~ 1} ~~alphabet~~ to encode ~~message~~ and build an ''n''-ary tree. This approach was considered by Huffman in his original paper. The same algorithm applies as for binary (<math alt="''n'' equals 2">n = 2</math>) codes, ~~except that the ''n'' least probable symbols are taken together,~~ instead of ~~just~~ the 2 least ~~probable.~~ ~~Note that for ''n'' greater than 2~~, ~~not all sets of source words can properly form an ''n''-ary tree for Huffman coding. In these cases, additional 0-probability place holders must be added. This is because~~ the ~~tree must form an~~ ''n'' to 1 ~~contractor;{{clarify~~ ~~\|date=September~~ ~~2023}}~~ ~~for binary coding, this is a 2 to 1 contractor, and any sized set can form such a contractor~~. ~~If the number of source words is congruent to 1 modulo ''n'' − 1, then the set of source words will form a proper Huffman tree.~~		The '''''n''-ary Huffman''' algorithm uses an alphabet of size ''n'', typically {0, 1, ..., n-1}, to encode messages and build an ''n''-ary tree. This approach was considered by Huffman in his original paper. The same algorithm applies as for binary (<math alt="''n'' equals 2">n = 2</math>) codes, but instead of combining the two least likely symbols, the ''n'' least likely symbols are grouped together.

			Note that for ''n'' > 2, not all sets of source words can properly form a complete ''n''-ary tree for Huffman coding. In these cases, additional placeholder symbols with 0 probability may need to be added. This is because the structure of the tree needs to repeatedly join ''n'' branches into one - also known as an "''n'' to 1" combination. For binary coding, this is a "2 to 1" combination, which works with any number of symbols. For ''n''-ary coding, a complete tree is only possible when the total number of symbols (real + placeholders) leaves a remainder of 1 when divided by (n-1). <ref name=":0" />

	=== Adaptive Huffman coding ===		=== Adaptive Huffman coding ===

Eelmealdeal: Added mention of Hamming codes

2025-03-12T18:47:36Z

Added mention of Hamming codes

← Previous revision		Revision as of 18:47, 12 March 2025
Line 1:		Line 1:
			{{distinguish\|Hamming code}}
	{{Short description\|Technique to compress data}}		{{Short description\|Technique to compress data}}
	{{Use dmy dates\|date=May 2019\|cs1-dates=y}}		{{Use dmy dates\|date=May 2019\|cs1-dates=y}}

Citation bot: 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

2025-03-12T12:03:35Z

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

← Previous revision		Revision as of 12:03, 12 March 2025
Line 261:		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.		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/~~1057615?arnumber=~~1057615 \|journal=IRE Transactions on Information Theory \|publisher=IEEE \|publication-date=31 January 1961 \|volume=7 \|issue=1 \|pages=27–38 \|doi=10.1109/TIT.1961.1057615 \|url-access=subscription ~~\|via=IEEE~~}}</ref> whose solution has been refined for the case of integer costs by Mordecai J. Golin.<ref>{{Cite journal \|last=Golin \|first=Mordekai J. \|date=January 1998 \|publication-date=1 September 1998 \|title=A Dynamic Programming Algorithm for Constructing Optimal Prefix-Free Codes with Unequal Letter Costs \|url=https://page.mi.fu-berlin.de/rote/Papers/pdf/A+dynamic+programming+algorithm+for+constructing+optimal+prefix-free+codes+for+unequal+letter+costs.pdf \|access-date=10 September 2024 \|s2cid=2265146 \|doi=10.1109/18.705558 \|journal=IEEE Transactions on Information Theory \|volume=44 \|issue=5 \|pages=1770–1781}}</ref>		''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/1057615 \|journal=IRE Transactions on Information Theory \|publisher=IEEE \|publication-date=31 January 1961 \|volume=7 \|issue=1 \|pages=27–38 \|doi=10.1109/TIT.1961.1057615 \|url-access=subscription }}</ref> whose solution has been refined for the case of integer costs by Mordecai J. Golin.<ref>{{Cite journal \|last=Golin \|first=Mordekai J. \|date=January 1998 \|publication-date=1 September 1998 \|title=A Dynamic Programming Algorithm for Constructing Optimal Prefix-Free Codes with Unequal Letter Costs \|url=https://page.mi.fu-berlin.de/rote/Papers/pdf/A+dynamic+programming+algorithm+for+constructing+optimal+prefix-free+codes+for+unequal+letter+costs.pdf \|access-date=10 September 2024 \|s2cid=2265146 \|doi=10.1109/18.705558 \|journal=IEEE Transactions on Information Theory \|volume=44 \|issue=5 \|pages=1770–1781}}</ref>

	=== {{anchor\|Hu-Tucker coding\|Alphabetic Huffman coding\|Alphabetic Huffman tree}}Optimal alphabetic binary trees (Hu–Tucker coding) ===		=== {{anchor\|Hu-Tucker coding\|Alphabetic Huffman coding\|Alphabetic Huffman tree}}Optimal alphabetic binary trees (Hu–Tucker coding) ===

Thomas Meng: /* Informal description */ added problem description with citation

2025-01-26T03:42:26Z

Informal description: added problem description with citation

← Previous revision		Revision as of 03:42, 26 January 2025
Line 58:		Line 58:

	=== Informal description ===		=== Informal description ===
			;Given: A set of symbols <math>S</math> and for each symbol <math>x \in S</math>, the frequency <math>f_x</math> representing the fraction of symbols in the text that are equal to <math>x</math>.<ref name="kleinberg&Tardos">{{cite book \|last1=Kleinberg \|first1=Jon \|last2=Tardos \|first2=Eva \|title=Algorithm Design \|date=March 16, 2005 \|publisher=[[Pearson Education]] \|isbn=9780321295354 \|page=165 \|edition=1 \|url=https://www.pearson.com/en-us/subject-catalog/p/algorithm-design/P200000003259/9780137546350 \|access-date=26 January 2025}}</ref>
	;Given: A set of symbols and their weights (usually [[Proportionality (mathematics)\|proportional]] to probabilities).
	;Find: A [[Prefix code\|prefix-free binary code]] (a set of codewords) with minimum [[Expected value\|expected]] codeword length (equivalently, a tree with minimum [[weighted path length from the root]]).		;Find: A [[Prefix code\|prefix-free binary code]] (a set of codewords) with minimum [[Expected value\|expected]] codeword length (equivalently, a tree with minimum [[weighted path length from the root]]).

Belbury: /* Compression */ use {{zwsp}} in caption, MOS:UPRIGHT

2025-01-13T13:19:34Z

Compression: use {{zwsp}} in caption, MOS:UPRIGHT

← Previous revision		Revision as of 13:19, 13 January 2025
Line 163:		Line 163:

	===Compression===		===Compression===
	[[File:Huffman_coding_visualisation.svg\|thumb\|~~360px~~\|Visualisation of the use of Huffman coding to encode the message "~~A_DEAD_DAD_CEDED_A_BAD_BABE_A_BEADED_ABACA_~~{{~~break~~}}~~BED~~". In steps 2 to 6, the letters are sorted by increasing frequency, and the least frequent two at each step are combined and reinserted into the list, and a partial tree is constructed. The final tree in step 6 is traversed to generate the dictionary in step 7. Step 8 uses it to encode the message.]]		[[File:Huffman_coding_visualisation.svg\|thumb\|upright=1.5\|Visualisation of the use of Huffman coding to encode the message "A_DEAD_DAD_{{zwsp}}CEDED_A_BAD_{{zwsp}}BABE_A_BEADED_{{zwsp}}ABACA_BED". In steps 2 to 6, the letters are sorted by increasing frequency, and the least frequent two at each step are combined and reinserted into the list, and a partial tree is constructed. The final tree in step 6 is traversed to generate the dictionary in step 7. Step 8 uses it to encode the message.]]

	[[Image:Huffman coding example.svg\|thumb\|A source generates 4 different symbols <math>\{a_1 , a_2 , a_3 , a_4 \}</math> with probability <math>\{0.4 ; 0.35 ; 0.2 ; 0.05 \}</math>. A binary tree is generated from left to right taking the two least probable symbols and putting them together to form another equivalent symbol having a probability that equals the sum of the two symbols. The process is repeated until there is just one symbol. The tree can then be read backwards, from right to left, assigning different bits to different branches. The final Huffman code is:		[[Image:Huffman coding example.svg\|thumb\|A source generates 4 different symbols <math>\{a_1 , a_2 , a_3 , a_4 \}</math> with probability <math>\{0.4 ; 0.35 ; 0.2 ; 0.05 \}</math>. A binary tree is generated from left to right taking the two least probable symbols and putting them together to form another equivalent symbol having a probability that equals the sum of the two symbols. The process is repeated until there is just one symbol. The tree can then be read backwards, from right to left, assigning different bits to different branches. The final Huffman code is:

Belbury: Reverted good faith edits by 62.172.237.82 (talk): Punctuation

2025-01-13T13:16:31Z

Reverted good faith edits by 62.172.237.82 (talk): Punctuation

← Previous revision		Revision as of 13:16, 13 January 2025
Line 45:		Line 45:
	== History ==		== History ==

	In 1951, [[David A. Huffman]] and his [[MIT]] [[information theory]] classmates were given the choice of a term paper or a final [[exam]]. The professor, [[Robert M. Fano]], assigned a [[term paper]] on the problem of finding the most efficient binary code. Huffman, unable to prove any codes were the most efficient/ was about to give up and start studying for the final when he hit upon the idea of using a frequency-sorted [[binary tree]] and quickly proved this method the most efficient.<ref>{{Cite journal \| last1 = Huffman \| first1 = Ken \| title = Profile: David A. Huffman: Encoding the "Neatness" of Ones and Zeroes \| journal = [[Scientific American]] \| pages = 54–58 \| year = 1991 \| url = http://www.huffmancoding.com/my-uncle/scientific-american}}</ref>		In 1951, [[David A. Huffman]] and his [[MIT]] [[information theory]] classmates were given the choice of a term paper or a final [[exam]]. The professor, [[Robert M. Fano]], assigned a [[term paper]] on the problem of finding the most efficient binary code. Huffman, unable to prove any codes were the most efficient, was about to give up and start studying for the final when he hit upon the idea of using a frequency-sorted [[binary tree]] and quickly proved this method the most efficient.<ref>{{Cite journal \| last1 = Huffman \| first1 = Ken \| title = Profile: David A. Huffman: Encoding the "Neatness" of Ones and Zeroes \| journal = [[Scientific American]] \| pages = 54–58 \| year = 1991 \| url = http://www.huffmancoding.com/my-uncle/scientific-american}}</ref>

	In doing so, Huffman outdid Fano, who had worked with [[Claude Shannon]] to develop a similar code. Building the tree from the bottom up guaranteed optimality, unlike the top-down approach of [[Shannon–Fano coding]].		In doing so, Huffman outdid Fano, who had worked with [[Claude Shannon]] to develop a similar code. Building the tree from the bottom up guaranteed optimality, unlike the top-down approach of [[Shannon–Fano coding]].

62.172.237.82: /* History */

2025-01-13T13:11:01Z

History

← Previous revision		Revision as of 13:11, 13 January 2025
Line 45:		Line 45:
	== History ==		== History ==

	In 1951, [[David A. Huffman]] and his [[MIT]] [[information theory]] classmates were given the choice of a term paper or a final [[exam]]. The professor, [[Robert M. Fano]], assigned a [[term paper]] on the problem of finding the most efficient binary code. Huffman, unable to prove any codes were the most efficient, was about to give up and start studying for the final when he hit upon the idea of using a frequency-sorted [[binary tree]] and quickly proved this method the most efficient.<ref>{{Cite journal \| last1 = Huffman \| first1 = Ken \| title = Profile: David A. Huffman: Encoding the "Neatness" of Ones and Zeroes \| journal = [[Scientific American]] \| pages = 54–58 \| year = 1991 \| url = http://www.huffmancoding.com/my-uncle/scientific-american}}</ref>		In 1951, [[David A. Huffman]] and his [[MIT]] [[information theory]] classmates were given the choice of a term paper or a final [[exam]]. The professor, [[Robert M. Fano]], assigned a [[term paper]] on the problem of finding the most efficient binary code. Huffman, unable to prove any codes were the most efficient/ was about to give up and start studying for the final when he hit upon the idea of using a frequency-sorted [[binary tree]] and quickly proved this method the most efficient.<ref>{{Cite journal \| last1 = Huffman \| first1 = Ken \| title = Profile: David A. Huffman: Encoding the "Neatness" of Ones and Zeroes \| journal = [[Scientific American]] \| pages = 54–58 \| year = 1991 \| url = http://www.huffmancoding.com/my-uncle/scientific-american}}</ref>

	In doing so, Huffman outdid Fano, who had worked with [[Claude Shannon]] to develop a similar code. Building the tree from the bottom up guaranteed optimality, unlike the top-down approach of [[Shannon–Fano coding]].		In doing so, Huffman outdid Fano, who had worked with [[Claude Shannon]] to develop a similar code. Building the tree from the bottom up guaranteed optimality, unlike the top-down approach of [[Shannon–Fano coding]].

IznoRepeat: add WP:TEMPLATECAT to remove from template; genfixes

2024-12-06T00:48:18Z

add WP:TEMPLATECAT to remove from template; genfixes

← Previous revision		Revision as of 00:48, 6 December 2024
Line 1:		Line 1:
	{{Short description\|Technique to compress data}}{{Use dmy dates\|date=May 2019\|cs1-dates=y}}		{{Short description\|Technique to compress data}}
			{{Use dmy dates\|date=May 2019\|cs1-dates=y}}
	[[Image:Huffman tree 2.svg\|thumb\|Huffman tree generated from the exact frequencies of the text "this is an example of a huffman tree". Encoding the sentence with this code requires 135 (or 147) bits, as opposed to 288 (or 180) bits if 36 characters of 8 (or 5) bits were used (This assumes that the code tree structure is known to the decoder and thus does not need to be counted as part of the transmitted information). The frequencies and codes of each character are shown in the accompanying table.		[[Image:Huffman tree 2.svg\|thumb\|Huffman tree generated from the exact frequencies of the text "this is an example of a huffman tree". Encoding the sentence with this code requires 135 (or 147) bits, as opposed to 288 (or 180) bits if 36 characters of 8 (or 5) bits were used (This assumes that the code tree structure is known to the decoder and thus does not need to be counted as part of the transmitted information). The frequencies and codes of each character are shown in the accompanying table.

Line 246:		Line 247:

	=== ''n''-ary Huffman coding ===		=== ''n''-ary Huffman coding ===
	The '''''n''-ary Huffman''' algorithm uses the {0, 1,..., ''n'' − 1} alphabet to encode message and build an ''n''-ary tree. This approach was considered by Huffman in his original paper. The same algorithm applies as for binary (<math alt="''n'' equals 2">n = 2</math>) codes, except that the ''n'' least probable symbols are taken together, instead of just the 2 least probable. Note that for ''n'' greater than 2, not all sets of source words can properly form an ''n''-ary tree for Huffman coding. In these cases, additional 0-probability place holders must be added. This is because the tree must form an ''n'' to 1 contractor;{{~~what?~~ \|date=September 2023}} for binary coding, this is a 2 to 1 contractor, and any sized set can form such a contractor. If the number of source words is congruent to 1 modulo ''n'' − 1, then the set of source words will form a proper Huffman tree.		The '''''n''-ary Huffman''' algorithm uses the {0, 1,..., ''n'' − 1} alphabet to encode message and build an ''n''-ary tree. This approach was considered by Huffman in his original paper. The same algorithm applies as for binary (<math alt="''n'' equals 2">n = 2</math>) codes, except that the ''n'' least probable symbols are taken together, instead of just the 2 least probable. Note that for ''n'' greater than 2, not all sets of source words can properly form an ''n''-ary tree for Huffman coding. In these cases, additional 0-probability place holders must be added. This is because the tree must form an ''n'' to 1 contractor;{{clarify \|date=September 2023}} for binary coding, this is a 2 to 1 contractor, and any sized set can form such a contractor. If the number of source words is congruent to 1 modulo ''n'' − 1, then the set of source words will form a proper Huffman tree.

	=== Adaptive Huffman coding ===		=== Adaptive Huffman coding ===
Line 260:		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.		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/1057615?arnumber=1057615 \|journal=IRE Transactions on Information Theory \|publisher=IEEE \|publication-date=31 January 1961 \|volume=7 \|issue=1 \|pages=27–38 \|doi=10.1109/TIT.1961.1057615 \|url-access=subscription \|via=IEEE}}</ref> whose solution has been refined for the case of integer costs by Mordecai J. Golin.<ref>{{Cite journal \|last=Golin \|first=Mordekai J. \|date=January 1998 \|publication-date=1 September 1998 \|title=A Dynamic Programming Algorithm for Constructing Optimal Prefix-Free Codes with Unequal Letter Costs \|url=https://page.mi.fu-berlin.de/rote/Papers/pdf/A+dynamic+programming+algorithm+for+constructing+optimal+prefix-free+codes+for+unequal+letter+costs.pdf \|access-date=10 September 2024 \|s2cid=2265146 \|doi=10.1109/18.705558 \|journal=IEEE Transactions on Information Theory \|volume=44 \|issue=5 \|pages=~~1770-1781~~}}</ref>		''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/1057615?arnumber=1057615 \|journal=IRE Transactions on Information Theory \|publisher=IEEE \|publication-date=31 January 1961 \|volume=7 \|issue=1 \|pages=27–38 \|doi=10.1109/TIT.1961.1057615 \|url-access=subscription \|via=IEEE}}</ref> whose solution has been refined for the case of integer costs by Mordecai J. Golin.<ref>{{Cite journal \|last=Golin \|first=Mordekai J. \|date=January 1998 \|publication-date=1 September 1998 \|title=A Dynamic Programming Algorithm for Constructing Optimal Prefix-Free Codes with Unequal Letter Costs \|url=https://page.mi.fu-berlin.de/rote/Papers/pdf/A+dynamic+programming+algorithm+for+constructing+optimal+prefix-free+codes+for+unequal+letter+costs.pdf \|access-date=10 September 2024 \|s2cid=2265146 \|doi=10.1109/18.705558 \|journal=IEEE Transactions on Information Theory \|volume=44 \|issue=5 \|pages=1770–1781}}</ref>

	=== {{anchor\|Hu-Tucker coding\|Alphabetic Huffman coding\|Alphabetic Huffman tree}}Optimal alphabetic binary trees (Hu–Tucker coding) ===		=== {{anchor\|Hu-Tucker coding\|Alphabetic Huffman coding\|Alphabetic Huffman tree}}Optimal alphabetic binary trees (Hu–Tucker coding) ===
Line 300:		Line 301:
	[[Category:Lossless compression algorithms]]		[[Category:Lossless compression algorithms]]
	[[Category:Binary trees]]		[[Category:Binary trees]]
			[[Category:Data compression]]

Michael Hardy: /* Problem definition */

2024-11-28T02:31:15Z

Problem definition

← Previous revision		Revision as of 02:31, 28 November 2024
Line 54:		Line 54:
	== Problem definition ==		== Problem definition ==
	{{More citations needed\|date=December 2021}}		{{More citations needed\|date=December 2021}}
	[[File:HuffmanCodeAlg.png\|thumb\|Constructing a Huffman ~~Tree~~]]		[[File:HuffmanCodeAlg.png\|thumb\|Constructing a Huffman tree]]

	=== Informal description ===		=== Informal description ===

Michael Hardy: /* Example */ Someone put a hyphen where a minus sign belongs. Also, I'm making the lower-case italicized ells cursive.

2024-11-28T02:30:33Z

Example: Someone put a hyphen where a minus sign belongs. Also, I'm making the lower-case italicized ells cursive.

← Previous revision		Revision as of 02:30, 28 November 2024
Line 102:		Line 102:
	\|rowspan="2"\|		\|rowspan="2"\|
	\|-		\|-
	!style="background:#efefef;font-weight:normal"\| Codeword length (in bits)<br />({{math\|''l''<sub>''i''</sub>}})		!style="background:#efefef;font-weight:normal"\| Codeword length (in bits)<br />({{math\|''ℓ''<sub>''i''</sub>}})
	\|align="center"\| 3		\|align="center"\| 3
	\|align="center"\| 3		\|align="center"\| 3
Line 109:		Line 109:
	\|align="center"\| 2		\|align="center"\| 2
	\|-		\|-
	!style="background:#efefef;font-weight:normal"\| Contribution to weighted path length<br />({{math\|''l''<sub>''i''</sub>}} {{math\|''w''<sub>''i''</sub>}} )		!style="background:#efefef;font-weight:normal"\| Contribution to weighted path length<br />({{math\|''ℓ''<sub>''i''</sub>}} {{math\|''w''<sub>''i''</sub>}} )
	\|align="center"\| 0.30		\|align="center"\| 0.30
	\|align="center"\| 0.45		\|align="center"\| 0.45
Line 118:		Line 118:
	\|-		\|-
	!rowspan="3" style="background:#efefef"\| Optimality		!rowspan="3" style="background:#efefef"\| Optimality
	!style="background:#efefef;font-weight:normal"\| Probability budget<br />({{math\|2<sup>−''l''<sub>''i''</sub></sup>}})		!style="background:#efefef;font-weight:normal"\| Probability budget<br />({{math\|2<sup>−''ℓ''<sub>''i''</sub></sup>}})
	\| align="center" \| 1/8		\| align="center" \| 1/8
	\| align="center" \| 1/8		\| align="center" \| 1/8
Line 134:		Line 134:
	\|align="center"\|		\|align="center"\|
	\|-		\|-
	! style="background: #efefef; font-weight: normal;" \| Contribution to entropy<br />({{math\|-''w''<sub>''i''</sub> log<sub>2</sub> ''w''<sub>''i''</sub>}})		! style="background: #efefef; font-weight: normal;" \| Contribution to entropy<br />({{math\|−''w''<sub>''i''</sub> log<sub>2</sub> ''w''<sub>''i''</sub>}})
	\|align="center"\| 0.332		\|align="center"\| 0.332
	\|align="center"\| 0.411		\|align="center"\| 0.411

← Previous revision		Revision as of 18:47, 12 March 2025
Line 1:		Line 1:
			{{distinguish\|Hamming code}}
	{{Short description\|Technique to compress data}}		{{Short description\|Technique to compress data}}
	{{Use dmy dates\|date=May 2019\|cs1-dates=y}}		{{Use dmy dates\|date=May 2019\|cs1-dates=y}}

← Previous revision		Revision as of 02:30, 28 November 2024
Line 102:		Line 102:
	\|rowspan="2"\|		\|rowspan="2"\|
	\|-		\|-
	!style="background:#efefef;font-weight:normal"\| Codeword length (in bits)<br />({{math\|''l''<sub>''i''</sub>}})		!style="background:#efefef;font-weight:normal"\| Codeword length (in bits)<br />({{math\|''ℓ''<sub>''i''</sub>}})
	\|align="center"\| 3		\|align="center"\| 3
	\|align="center"\| 3		\|align="center"\| 3
Line 109:		Line 109:
	\|align="center"\| 2		\|align="center"\| 2
	\|-		\|-
	!style="background:#efefef;font-weight:normal"\| Contribution to weighted path length<br />({{math\|''l''<sub>''i''</sub>}} {{math\|''w''<sub>''i''</sub>}} )		!style="background:#efefef;font-weight:normal"\| Contribution to weighted path length<br />({{math\|''ℓ''<sub>''i''</sub>}} {{math\|''w''<sub>''i''</sub>}} )
	\|align="center"\| 0.30		\|align="center"\| 0.30
	\|align="center"\| 0.45		\|align="center"\| 0.45
Line 118:		Line 118:
	\|-		\|-
	!rowspan="3" style="background:#efefef"\| Optimality		!rowspan="3" style="background:#efefef"\| Optimality
	!style="background:#efefef;font-weight:normal"\| Probability budget<br />({{math\|2<sup>−''l''<sub>''i''</sub></sup>}})		!style="background:#efefef;font-weight:normal"\| Probability budget<br />({{math\|2<sup>−''ℓ''<sub>''i''</sub></sup>}})
	\| align="center" \| 1/8		\| align="center" \| 1/8
	\| align="center" \| 1/8		\| align="center" \| 1/8
Line 134:		Line 134:
	\|align="center"\|		\|align="center"\|
	\|-		\|-
	! style="background: #efefef; font-weight: normal;" \| Contribution to entropy<br />({{math\|-''w''<sub>''i''</sub> log<sub>2</sub> ''w''<sub>''i''</sub>}})		! style="background: #efefef; font-weight: normal;" \| Contribution to entropy<br />({{math\|−''w''<sub>''i''</sub> log<sub>2</sub> ''w''<sub>''i''</sub>}})
	\|align="center"\| 0.332		\|align="center"\| 0.332
	\|align="center"\| 0.411		\|align="center"\| 0.411