Package-merge algorithm - Revision history

Onel5969: Disambiguating links to Code word (link changed to Code word (communication)) using DisamAssist.

2023-10-24T01:40:18Z

Disambiguating links to Code word (link changed to Code word (communication)) using DisamAssist.

← Previous revision		Revision as of 01:40, 24 October 2023
Line 1:		Line 1:
	The '''package-merge algorithm''' is an ''[[Big O notation\|O]](nL)''-time algorithm for finding an optimal [[length-limited Huffman code]] for a given distribution on a given alphabet of size ''n'', where no [[code word]] is longer than ''L''. It is a [[greedy algorithm]], and a generalization of [[Huffman coding\|Huffman's original algorithm]]. Package-merge works by reducing the code construction problem to the binary ''[[Coupon collector's problem\|coin collector's problem]]''.<ref name="LaHi">{{cite journal \|first1=Lawrence L. \|last1=Larmore \|author-link1=Lawrence L. Larmore \|first2=Daniel S. \|last2=Hirschberg \|author-link2=Daniel S. Hirschberg \|title=A fast algorithm for optimal length-limited Huffman codes \|journal=[[Journal of the Association for Computing Machinery]] \|volume=37 \|number=3 \|pages=464–473 \|date=1990 \|doi=10.1145/79147.79150\|s2cid=11696729 \|doi-access=free }}</ref>		The '''package-merge algorithm''' is an ''[[Big O notation\|O]](nL)''-time algorithm for finding an optimal [[length-limited Huffman code]] for a given distribution on a given alphabet of size ''n'', where no [[Code word (communication)\|code word]] is longer than ''L''. It is a [[greedy algorithm]], and a generalization of [[Huffman coding\|Huffman's original algorithm]]. Package-merge works by reducing the code construction problem to the binary ''[[Coupon collector's problem\|coin collector's problem]]''.<ref name="LaHi">{{cite journal \|first1=Lawrence L. \|last1=Larmore \|author-link1=Lawrence L. Larmore \|first2=Daniel S. \|last2=Hirschberg \|author-link2=Daniel S. Hirschberg \|title=A fast algorithm for optimal length-limited Huffman codes \|journal=[[Journal of the Association for Computing Machinery]] \|volume=37 \|number=3 \|pages=464–473 \|date=1990 \|doi=10.1145/79147.79150\|s2cid=11696729 \|doi-access=free }}</ref>

	==The coin collector's problem==		==The coin collector's problem==

OAbot: Open access bot: doi updated in citation with #oabot.

2023-08-14T05:56:19Z

Open access bot: doi updated in citation with #oabot.

← Previous revision		Revision as of 05:56, 14 August 2023
Line 1:		Line 1:
	The '''package-merge algorithm''' is an ''[[Big O notation\|O]](nL)''-time algorithm for finding an optimal [[length-limited Huffman code]] for a given distribution on a given alphabet of size ''n'', where no [[code word]] is longer than ''L''. It is a [[greedy algorithm]], and a generalization of [[Huffman coding\|Huffman's original algorithm]]. Package-merge works by reducing the code construction problem to the binary ''[[Coupon collector's problem\|coin collector's problem]]''.<ref name="LaHi">{{cite journal \|first1=Lawrence L. \|last1=Larmore \|author-link1=Lawrence L. Larmore \|first2=Daniel S. \|last2=Hirschberg \|author-link2=Daniel S. Hirschberg \|title=A fast algorithm for optimal length-limited Huffman codes \|journal=[[Journal of the Association for Computing Machinery]] \|volume=37 \|number=3 \|pages=464–473 \|date=1990 \|doi=10.1145/79147.79150\|s2cid=11696729 }}</ref>		The '''package-merge algorithm''' is an ''[[Big O notation\|O]](nL)''-time algorithm for finding an optimal [[length-limited Huffman code]] for a given distribution on a given alphabet of size ''n'', where no [[code word]] is longer than ''L''. It is a [[greedy algorithm]], and a generalization of [[Huffman coding\|Huffman's original algorithm]]. Package-merge works by reducing the code construction problem to the binary ''[[Coupon collector's problem\|coin collector's problem]]''.<ref name="LaHi">{{cite journal \|first1=Lawrence L. \|last1=Larmore \|author-link1=Lawrence L. Larmore \|first2=Daniel S. \|last2=Hirschberg \|author-link2=Daniel S. Hirschberg \|title=A fast algorithm for optimal length-limited Huffman codes \|journal=[[Journal of the Association for Computing Machinery]] \|volume=37 \|number=3 \|pages=464–473 \|date=1990 \|doi=10.1145/79147.79150\|s2cid=11696729 \|doi-access=free }}</ref>

	==The coin collector's problem==		==The coin collector's problem==

Citation bot: Alter: template type. Add: s2cid. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 437/1682

2022-01-30T09:47:23Z

Alter: template type. Add: s2cid. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 437/1682

← Previous revision		Revision as of 09:47, 30 January 2022
Line 1:		Line 1:
	The '''package-merge algorithm''' is an ''[[Big O notation\|O]](nL)''-time algorithm for finding an optimal [[length-limited Huffman code]] for a given distribution on a given alphabet of size ''n'', where no [[code word]] is longer than ''L''. It is a [[greedy algorithm]], and a generalization of [[Huffman coding\|Huffman's original algorithm]]. Package-merge works by reducing the code construction problem to the binary ''[[Coupon collector's problem\|coin collector's problem]]''.<ref name="LaHi">{{cite journal \|first1=Lawrence L. \|last1=Larmore \|author-link1=Lawrence L. Larmore \|first2=Daniel S. \|last2=Hirschberg \|author-link2=Daniel S. Hirschberg \|title=A fast algorithm for optimal length-limited Huffman codes \|journal=[[Journal of the Association for Computing Machinery]] \|volume=37 \|number=3 \|pages=464–473 \|date=1990 \|doi=10.1145/79147.79150}}</ref>		The '''package-merge algorithm''' is an ''[[Big O notation\|O]](nL)''-time algorithm for finding an optimal [[length-limited Huffman code]] for a given distribution on a given alphabet of size ''n'', where no [[code word]] is longer than ''L''. It is a [[greedy algorithm]], and a generalization of [[Huffman coding\|Huffman's original algorithm]]. Package-merge works by reducing the code construction problem to the binary ''[[Coupon collector's problem\|coin collector's problem]]''.<ref name="LaHi">{{cite journal \|first1=Lawrence L. \|last1=Larmore \|author-link1=Lawrence L. Larmore \|first2=Daniel S. \|last2=Hirschberg \|author-link2=Daniel S. Hirschberg \|title=A fast algorithm for optimal length-limited Huffman codes \|journal=[[Journal of the Association for Computing Machinery]] \|volume=37 \|number=3 \|pages=464–473 \|date=1990 \|doi=10.1145/79147.79150\|s2cid=11696729 }}</ref>

	==The coin collector's problem==		==The coin collector's problem==
Line 30:		Line 30:

	==External links==		==External links==
	* {{cite ~~arxiv~~ \|first=Michael B. \|last=Baer \|eprint=cs.IT/0602085 \|title=Twenty (or so) Questions: ''D''-ary Length-Bounded Prefix Coding\|year=2006 }}<!-- Please do not add as a reference; it has not yet been peer-reviewed, but it does survey and expand upon the techniques and literature on this subject -->		* {{cite arXiv \|first=Michael B. \|last=Baer \|eprint=cs.IT/0602085 \|title=Twenty (or so) Questions: ''D''-ary Length-Bounded Prefix Coding\|year=2006 }}<!-- Please do not add as a reference; it has not yet been peer-reviewed, but it does survey and expand upon the techniques and literature on this subject -->
	* {{cite conference \|first1=Alistair \|last1=Moffat \|first2=Andrew \|author-link1=Alistair Moffat (computer scientist) \|last2=Turpin \|first3=Jyrki \|last3=Katajainen \|title=Space-Efficient Construction of Optimal Prefix Codes \|conference=IEEE Data Compression Conference \|date=March 1995 \|location=Snowbird, Utah, USA \|doi=10.1109/DCC.1995.515509}}		* {{cite conference \|first1=Alistair \|last1=Moffat \|first2=Andrew \|author-link1=Alistair Moffat (computer scientist) \|last2=Turpin \|first3=Jyrki \|last3=Katajainen \|title=Space-Efficient Construction of Optimal Prefix Codes \|conference=IEEE Data Compression Conference \|date=March 1995 \|location=Snowbird, Utah, USA \|doi=10.1109/DCC.1995.515509}}
	* An implementation of the package-merge algorithm "[http://sourceforge.net/p/tpabbrevia/code/26/tree/trunk/source/AbDfPkMg.pas]"		* An implementation of the package-merge algorithm "[http://sourceforge.net/p/tpabbrevia/code/26/tree/trunk/source/AbDfPkMg.pas]"

David Eppstein: Teresa Przytycka

2021-12-12T20:26:27Z

Teresa Przytycka

← Previous revision		Revision as of 20:26, 12 December 2021
Line 22:		Line 22:
	With this reduction, the algorithm is ''O(nL)''-time and ''O(nL)''-space. However, the original paper, "''A fast algorithm for optimal length-limited Huffman codes''", shows how this can be improved to ''O(nL)''-time and ''O(n)''-space. The idea is to run the algorithm a first time, only keeping enough data to be able to determine two equivalent subproblems that sum to half the size of the original problem. This is done recursively, resulting in an algorithm that takes about twice as long but requires only linear space.<ref name="LaHi"/>		With this reduction, the algorithm is ''O(nL)''-time and ''O(nL)''-space. However, the original paper, "''A fast algorithm for optimal length-limited Huffman codes''", shows how this can be improved to ''O(nL)''-time and ''O(n)''-space. The idea is to run the algorithm a first time, only keeping enough data to be able to determine two equivalent subproblems that sum to half the size of the original problem. This is done recursively, resulting in an algorithm that takes about twice as long but requires only linear space.<ref name="LaHi"/>

	Many other improvements have been made to the package-merge algorithm to reduce the [[Big O notation\|multiplicative constant]] and to make it faster in special cases, such as those problems having repeated ''p<sub>i</sub>''s.<ref name="MG">{{cite book \|first1=Ian H. \|last1=Witten \|author-link1=Ian H. Witten \| first2=Alistair \|last2=Moffat \|author-link2=Alistair Moffat (computer scientist) \|first3=Timothy Clinton \|last3=Bell \|author-link3=Timothy Clinton Bell \|title=Managing Gigabytes: Compressing and indexing documents and images \|edition=2 \|publisher=[[Morgan Kaufmann Publishers]] \|date=1999 \|isbn=978-1-55860-570-1 \|id=1558605703}}</ref> The package-merge approach has also been adapted to related problems such as [[alphabetic Huffman coding\|alphabetic coding]].<ref name="LaPr">{{cite journal \|first1=Lawrence L. \|last1=Larmore \|author-link1=Lawrence L. Larmore \|first2=Teresa M. \|last2=Przytycka \|title=A Fast Algorithm for Optimal Height-Limited Alphabetic Binary-Trees \|journal=[[SIAM Journal on Computing]] \|volume=23 \|number=6 \|pages=1283–1312 \|date=1994 \|doi=10.1137/s0097539792231167}}</ref>		Many other improvements have been made to the package-merge algorithm to reduce the [[Big O notation\|multiplicative constant]] and to make it faster in special cases, such as those problems having repeated ''p<sub>i</sub>''s.<ref name="MG">{{cite book \|first1=Ian H. \|last1=Witten \|author-link1=Ian H. Witten \| first2=Alistair \|last2=Moffat \|author-link2=Alistair Moffat (computer scientist) \|first3=Timothy Clinton \|last3=Bell \|author-link3=Timothy Clinton Bell \|title=Managing Gigabytes: Compressing and indexing documents and images \|edition=2 \|publisher=[[Morgan Kaufmann Publishers]] \|date=1999 \|isbn=978-1-55860-570-1 \|id=1558605703}}</ref> The package-merge approach has also been adapted to related problems such as [[alphabetic Huffman coding\|alphabetic coding]].<ref name="LaPr">{{cite journal \|first1=Lawrence L. \|last1=Larmore \|author-link1=Lawrence L. Larmore \|first2=Teresa M. \|last2=Przytycka\|author2-link=Teresa Przytycka \|title=A Fast Algorithm for Optimal Height-Limited Alphabetic Binary-Trees \|journal=[[SIAM Journal on Computing]] \|volume=23 \|number=6 \|pages=1283–1312 \|date=1994 \|doi=10.1137/s0097539792231167}}</ref>

	Methods involving [[graph theory]] have been shown to have better asymptotic space complexity than the package-merge algorithm, but these have not seen as much practical application.		Methods involving [[graph theory]] have been shown to have better asymptotic space complexity than the package-merge algorithm, but these have not seen as much practical application.

DabbleE: Updated link text to reflect cross-page title change.

2021-09-06T21:35:17Z

Updated link text to reflect cross-page title change.

← Previous revision		Revision as of 21:35, 6 September 2021
Line 1:		Line 1:
	The '''package-merge algorithm''' is an ''[[Big O notation\|O]](nL)''-time algorithm for finding an optimal [[length-limited Huffman code]] for a given distribution on a given alphabet of size ''n'', where no [[code word]] is longer than ''L''. It is a [[greedy algorithm]], and a generalization of [[Huffman coding\|Huffman's original algorithm]]. Package-merge works by reducing the code construction problem to the binary ''[[coin collector's problem]]''.<ref name="LaHi">{{cite journal \|first1=Lawrence L. \|last1=Larmore \|author-link1=Lawrence L. Larmore \|first2=Daniel S. \|last2=Hirschberg \|author-link2=Daniel S. Hirschberg \|title=A fast algorithm for optimal length-limited Huffman codes \|journal=[[Journal of the Association for Computing Machinery]] \|volume=37 \|number=3 \|pages=464–473 \|date=1990 \|doi=10.1145/79147.79150}}</ref>		The '''package-merge algorithm''' is an ''[[Big O notation\|O]](nL)''-time algorithm for finding an optimal [[length-limited Huffman code]] for a given distribution on a given alphabet of size ''n'', where no [[code word]] is longer than ''L''. It is a [[greedy algorithm]], and a generalization of [[Huffman coding\|Huffman's original algorithm]]. Package-merge works by reducing the code construction problem to the binary ''[[Coupon collector's problem\|coin collector's problem]]''.<ref name="LaHi">{{cite journal \|first1=Lawrence L. \|last1=Larmore \|author-link1=Lawrence L. Larmore \|first2=Daniel S. \|last2=Hirschberg \|author-link2=Daniel S. Hirschberg \|title=A fast algorithm for optimal length-limited Huffman codes \|journal=[[Journal of the Association for Computing Machinery]] \|volume=37 \|number=3 \|pages=464–473 \|date=1990 \|doi=10.1145/79147.79150}}</ref>

	==The coin collector's problem==		==The coin collector's problem==

Botaki: /* External links */

2019-12-30T10:56:53Z

External links

← Previous revision		Revision as of 10:56, 30 December 2019
Line 33:		Line 33:
	* {{cite conference \|first1=Alistair \|last1=Moffat \|first2=Andrew \|author-link1=Alistair Moffat (computer scientist) \|last2=Turpin \|first3=Jyrki \|last3=Katajainen \|title=Space-Efficient Construction of Optimal Prefix Codes \|conference=IEEE Data Compression Conference \|date=March 1995 \|location=Snowbird, Utah, USA \|doi=10.1109/DCC.1995.515509}}		* {{cite conference \|first1=Alistair \|last1=Moffat \|first2=Andrew \|author-link1=Alistair Moffat (computer scientist) \|last2=Turpin \|first3=Jyrki \|last3=Katajainen \|title=Space-Efficient Construction of Optimal Prefix Codes \|conference=IEEE Data Compression Conference \|date=March 1995 \|location=Snowbird, Utah, USA \|doi=10.1109/DCC.1995.515509}}
	* An implementation of the package-merge algorithm "[http://sourceforge.net/p/tpabbrevia/code/26/tree/trunk/source/AbDfPkMg.pas]"		* An implementation of the package-merge algorithm "[http://sourceforge.net/p/tpabbrevia/code/26/tree/trunk/source/AbDfPkMg.pas]"
			* A fast entropy coder that uses package-merge algorithm [https://github.com/algorithm314/FPC]

	[[Category:Lossless compression algorithms]]		[[Category:Lossless compression algorithms]]

Citation bot: Removed URL that duplicated unique identifier. | You can use this bot yourself. Report bugs here.| Activated by User:Headbomb

2019-07-15T23:40:32Z

Removed URL that duplicated unique identifier. | You can use this bot yourself. Report bugs here.| Activated by User:Headbomb

← Previous revision		Revision as of 23:40, 15 July 2019
Line 17:		Line 17:
	Let ''p''<sub>1</sub>, …, ''p<sub>n</sub>'' be the frequencies of the		Let ''p''<sub>1</sub>, …, ''p<sub>n</sub>'' be the frequencies of the
	symbols of the alphabet to be encoded. We first sort the symbols so that ''p''<sub>''i''</sub> ≤ ''p''<sub>''i''+1</sub>. Create ''L'' coins for each symbol, of denominations 2<sup>−1</sup>, …, 2<sup>−''L''</sup>, each of numismatic value ''p<sub>i</sub>''. Use the package-merge algorithm to select the set of coins of minimum numismatic value whose denominations total ''n'' − 1. Let ''h<sub>i</sub>'' be the number of coins of numismatic value ''p<sub>i</sub>'' selected.		symbols of the alphabet to be encoded. We first sort the symbols so that ''p''<sub>''i''</sub> ≤ ''p''<sub>''i''+1</sub>. Create ''L'' coins for each symbol, of denominations 2<sup>−1</sup>, …, 2<sup>−''L''</sup>, each of numismatic value ''p<sub>i</sub>''. Use the package-merge algorithm to select the set of coins of minimum numismatic value whose denominations total ''n'' − 1. Let ''h<sub>i</sub>'' be the number of coins of numismatic value ''p<sub>i</sub>'' selected.
	The optimal length-limited Huffman code will encode symbol ''i'' with a bit string of length ''h<sub>i</sub>''. The [[canonical Huffman code]] can easily be constructed by a simple bottom-up greedy method, given that the ''h<sub>i</sub>'' are known, and this can be the basis for fast [[data compression]].<ref name="MoTu">{{cite journal \|first1=Alistair \|last1=Moffat \|author-link1=Alistair Moffat (computer scientist) \|first2=Andrew \|last2=Turpin \|title=On the implementation of minimum redundancy prefix codes \|journal=[[IEEE Transactions on Communications]] \|volume=45 \|number=10 \|pages=1200–1207 \|date=Oct 1997 ~~\|url=http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=634683~~ \|doi=10.1109/26.634683}}</ref>		The optimal length-limited Huffman code will encode symbol ''i'' with a bit string of length ''h<sub>i</sub>''. The [[canonical Huffman code]] can easily be constructed by a simple bottom-up greedy method, given that the ''h<sub>i</sub>'' are known, and this can be the basis for fast [[data compression]].<ref name="MoTu">{{cite journal \|first1=Alistair \|last1=Moffat \|author-link1=Alistair Moffat (computer scientist) \|first2=Andrew \|last2=Turpin \|title=On the implementation of minimum redundancy prefix codes \|journal=[[IEEE Transactions on Communications]] \|volume=45 \|number=10 \|pages=1200–1207 \|date=Oct 1997 \|doi=10.1109/26.634683}}</ref>

	==Performance improvements and generalizations==		==Performance improvements and generalizations==

Citation bot: Add: year, eprint. Removed parameters. | You can use this bot yourself. Report bugs here. | User-activated.

2019-03-15T04:30:19Z

Add: year, eprint. Removed parameters. | You can use this bot yourself. Report bugs here. | User-activated.

← Previous revision		Revision as of 04:30, 15 March 2019
Line 30:		Line 30:

	==External links==		==External links==
	* {{cite arxiv \|first=Michael B. \|last=Baer \|~~arxiv~~=cs.IT/0602085 \|title=Twenty (or so) Questions: ''D''-ary Length-Bounded Prefix Coding}}<!-- Please do not add as a reference; it has not yet been peer-reviewed, but it does survey and expand upon the techniques and literature on this subject -->		* {{cite arxiv \|first=Michael B. \|last=Baer \|eprint=cs.IT/0602085 \|title=Twenty (or so) Questions: ''D''-ary Length-Bounded Prefix Coding\|year=2006 }}<!-- Please do not add as a reference; it has not yet been peer-reviewed, but it does survey and expand upon the techniques and literature on this subject -->
	* {{cite conference \|first1=Alistair \|last1=Moffat \|first2=Andrew \|author-link1=Alistair Moffat (computer scientist) \|last2=Turpin \|first3=Jyrki \|last3=Katajainen \|title=Space-Efficient Construction of Optimal Prefix Codes \|conference=IEEE Data Compression Conference \|date=March 1995 \|location=Snowbird, Utah, USA \|doi=10.1109/DCC.1995.515509}}		* {{cite conference \|first1=Alistair \|last1=Moffat \|first2=Andrew \|author-link1=Alistair Moffat (computer scientist) \|last2=Turpin \|first3=Jyrki \|last3=Katajainen \|title=Space-Efficient Construction of Optimal Prefix Codes \|conference=IEEE Data Compression Conference \|date=March 1995 \|location=Snowbird, Utah, USA \|doi=10.1109/DCC.1995.515509}}
	* An implementation of the package-merge algorithm "[http://sourceforge.net/p/tpabbrevia/code/26/tree/trunk/source/AbDfPkMg.pas]"		* An implementation of the package-merge algorithm "[http://sourceforge.net/p/tpabbrevia/code/26/tree/trunk/source/AbDfPkMg.pas]"

Rjwilmsi: Journal cites, Added 3 dois to journal cites using AWB (12066)

2016-08-06T09:17:04Z

Journal cites, Added 3 dois to journal cites using AWB (12066)

← Previous revision		Revision as of 09:17, 6 August 2016
Line 1:		Line 1:
	The '''package-merge algorithm''' is an ''[[Big O notation\|O]](nL)''-time algorithm for finding an optimal [[length-limited Huffman code]] for a given distribution on a given alphabet of size ''n'', where no [[code word]] is longer than ''L''. It is a [[greedy algorithm]], and a generalization of [[Huffman coding\|Huffman's original algorithm]]. Package-merge works by reducing the code construction problem to the binary ''[[coin collector's problem]]''.<ref name="LaHi">{{cite journal \|first1=Lawrence L. \|last1=Larmore \|author-link1=Lawrence L. Larmore \|first2=Daniel S. \|last2=Hirschberg \|author-link2=Daniel S. Hirschberg \|title=A fast algorithm for optimal length-limited Huffman codes \|journal=[[Journal of the Association for Computing Machinery]] \|volume=37 \|number=3 \|pages=~~464--473~~ \|date=1990}}</ref>		The '''package-merge algorithm''' is an ''[[Big O notation\|O]](nL)''-time algorithm for finding an optimal [[length-limited Huffman code]] for a given distribution on a given alphabet of size ''n'', where no [[code word]] is longer than ''L''. It is a [[greedy algorithm]], and a generalization of [[Huffman coding\|Huffman's original algorithm]]. Package-merge works by reducing the code construction problem to the binary ''[[coin collector's problem]]''.<ref name="LaHi">{{cite journal \|first1=Lawrence L. \|last1=Larmore \|author-link1=Lawrence L. Larmore \|first2=Daniel S. \|last2=Hirschberg \|author-link2=Daniel S. Hirschberg \|title=A fast algorithm for optimal length-limited Huffman codes \|journal=[[Journal of the Association for Computing Machinery]] \|volume=37 \|number=3 \|pages=464–473 \|date=1990 \|doi=10.1145/79147.79150}}</ref>

	==The coin collector's problem==		==The coin collector's problem==
Line 17:		Line 17:
	Let ''p''<sub>1</sub>, …, ''p<sub>n</sub>'' be the frequencies of the		Let ''p''<sub>1</sub>, …, ''p<sub>n</sub>'' be the frequencies of the
	symbols of the alphabet to be encoded. We first sort the symbols so that ''p''<sub>''i''</sub> ≤ ''p''<sub>''i''+1</sub>. Create ''L'' coins for each symbol, of denominations 2<sup>−1</sup>, …, 2<sup>−''L''</sup>, each of numismatic value ''p<sub>i</sub>''. Use the package-merge algorithm to select the set of coins of minimum numismatic value whose denominations total ''n'' − 1. Let ''h<sub>i</sub>'' be the number of coins of numismatic value ''p<sub>i</sub>'' selected.		symbols of the alphabet to be encoded. We first sort the symbols so that ''p''<sub>''i''</sub> ≤ ''p''<sub>''i''+1</sub>. Create ''L'' coins for each symbol, of denominations 2<sup>−1</sup>, …, 2<sup>−''L''</sup>, each of numismatic value ''p<sub>i</sub>''. Use the package-merge algorithm to select the set of coins of minimum numismatic value whose denominations total ''n'' − 1. Let ''h<sub>i</sub>'' be the number of coins of numismatic value ''p<sub>i</sub>'' selected.
	The optimal length-limited Huffman code will encode symbol ''i'' with a bit string of length ''h<sub>i</sub>''. The [[canonical Huffman code]] can easily be constructed by a simple bottom-up greedy method, given that the ''h<sub>i</sub>'' are known, and this can be the basis for fast [[data compression]].<ref name="MoTu">{{cite journal \|first1=Alistair \|last1=Moffat \|author-link1=Alistair Moffat (computer scientist) \|first2=Andrew \|last2=Turpin \|title=On the implementation of minimum redundancy prefix codes \|journal=[[IEEE Transactions on Communications]] \|volume=45 \|number=10 \|pages=~~1200-1207~~ \|date=Oct 1997 \|url=http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=634683}}</ref>		The optimal length-limited Huffman code will encode symbol ''i'' with a bit string of length ''h<sub>i</sub>''. The [[canonical Huffman code]] can easily be constructed by a simple bottom-up greedy method, given that the ''h<sub>i</sub>'' are known, and this can be the basis for fast [[data compression]].<ref name="MoTu">{{cite journal \|first1=Alistair \|last1=Moffat \|author-link1=Alistair Moffat (computer scientist) \|first2=Andrew \|last2=Turpin \|title=On the implementation of minimum redundancy prefix codes \|journal=[[IEEE Transactions on Communications]] \|volume=45 \|number=10 \|pages=1200–1207 \|date=Oct 1997 \|url=http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=634683 \|doi=10.1109/26.634683}}</ref>

	==Performance improvements and generalizations==		==Performance improvements and generalizations==
	With this reduction, the algorithm is ''O(nL)''-time and ''O(nL)''-space. However, the original paper, "''A fast algorithm for optimal length-limited Huffman codes''", shows how this can be improved to ''O(nL)''-time and ''O(n)''-space. The idea is to run the algorithm a first time, only keeping enough data to be able to determine two equivalent subproblems that sum to half the size of the original problem. This is done recursively, resulting in an algorithm that takes about twice as long but requires only linear space.<ref name="LaHi"/>		With this reduction, the algorithm is ''O(nL)''-time and ''O(nL)''-space. However, the original paper, "''A fast algorithm for optimal length-limited Huffman codes''", shows how this can be improved to ''O(nL)''-time and ''O(n)''-space. The idea is to run the algorithm a first time, only keeping enough data to be able to determine two equivalent subproblems that sum to half the size of the original problem. This is done recursively, resulting in an algorithm that takes about twice as long but requires only linear space.<ref name="LaHi"/>

	Many other improvements have been made to the package-merge algorithm to reduce the [[Big O notation\|multiplicative constant]] and to make it faster in special cases, such as those problems having repeated ''p<sub>i</sub>''s.<ref name="MG">{{cite book \|first1=Ian H. \|last1=Witten \|author-link1=Ian H. Witten \| first2=Alistair \|last2=Moffat \|author-link2=Alistair Moffat (computer scientist) \|first3=Timothy Clinton \|last3=Bell \|author-link3=Timothy Clinton Bell \|title=Managing Gigabytes: Compressing and indexing documents and images \|edition=2 \|publisher=[[Morgan Kaufmann Publishers]] \|date=1999 \|isbn=978-1-55860-570-1 \|id=1558605703}}</ref> The package-merge approach has also been adapted to related problems such as [[alphabetic Huffman coding\|alphabetic coding]].<ref name="LaPr">{{cite journal \|\|first1=Lawrence L. \|last1=Larmore \|author-link1=Lawrence L. Larmore \|first2=Teresa M. \|last2=Przytycka \|title=A Fast Algorithm for Optimal Height-Limited Alphabetic Binary-Trees \|journal=[[SIAM Journal on Computing]] \|volume=23 \|number=6 \|pages=~~1283--1312~~ \|date=1994}}</ref>		Many other improvements have been made to the package-merge algorithm to reduce the [[Big O notation\|multiplicative constant]] and to make it faster in special cases, such as those problems having repeated ''p<sub>i</sub>''s.<ref name="MG">{{cite book \|first1=Ian H. \|last1=Witten \|author-link1=Ian H. Witten \| first2=Alistair \|last2=Moffat \|author-link2=Alistair Moffat (computer scientist) \|first3=Timothy Clinton \|last3=Bell \|author-link3=Timothy Clinton Bell \|title=Managing Gigabytes: Compressing and indexing documents and images \|edition=2 \|publisher=[[Morgan Kaufmann Publishers]] \|date=1999 \|isbn=978-1-55860-570-1 \|id=1558605703}}</ref> The package-merge approach has also been adapted to related problems such as [[alphabetic Huffman coding\|alphabetic coding]].<ref name="LaPr">{{cite journal \|first1=Lawrence L. \|last1=Larmore \|author-link1=Lawrence L. Larmore \|first2=Teresa M. \|last2=Przytycka \|title=A Fast Algorithm for Optimal Height-Limited Alphabetic Binary-Trees \|journal=[[SIAM Journal on Computing]] \|volume=23 \|number=6 \|pages=1283–1312 \|date=1994 \|doi=10.1137/s0097539792231167}}</ref>

	Methods involving [[graph theory]] have been shown to have better asymptotic space complexity than the package-merge algorithm, but these have not seen as much practical application.		Methods involving [[graph theory]] have been shown to have better asymptotic space complexity than the package-merge algorithm, but these have not seen as much practical application.

Matthiaspaul: +red link

2016-02-10T19:34:07Z

+red link

← Previous revision		Revision as of 19:34, 10 February 2016
Line 1:		Line 1:
	The '''package-merge algorithm''' is an ''[[Big O notation\|O]](nL)''-time algorithm for finding an optimal [[length-limited Huffman code]] for a given distribution on a given alphabet of size ''n'', where no [[code word]] is longer than ''L''. It is a [[greedy algorithm]], and a generalization of [[Huffman coding\|Huffman's original algorithm]]. Package-merge works by reducing the code construction problem to the binary '''coin collector's problem'''.<ref name="LaHi">{{cite journal \|first1=Lawrence L. \|last1=Larmore \|author-link1=Lawrence L. Larmore \|first2=Daniel S. \|last2=Hirschberg \|author-link2=Daniel S. Hirschberg \|title=A fast algorithm for optimal length-limited Huffman codes \|journal=[[Journal of the Association for Computing Machinery]] \|volume=37 \|number=3 \|pages=464--473 \|date=1990}}</ref>		The '''package-merge algorithm''' is an ''[[Big O notation\|O]](nL)''-time algorithm for finding an optimal [[length-limited Huffman code]] for a given distribution on a given alphabet of size ''n'', where no [[code word]] is longer than ''L''. It is a [[greedy algorithm]], and a generalization of [[Huffman coding\|Huffman's original algorithm]]. Package-merge works by reducing the code construction problem to the binary ''[[coin collector's problem]]''.<ref name="LaHi">{{cite journal \|first1=Lawrence L. \|last1=Larmore \|author-link1=Lawrence L. Larmore \|first2=Daniel S. \|last2=Hirschberg \|author-link2=Daniel S. Hirschberg \|title=A fast algorithm for optimal length-limited Huffman codes \|journal=[[Journal of the Association for Computing Machinery]] \|volume=37 \|number=3 \|pages=464--473 \|date=1990}}</ref>

	==The coin collector's problem==		==The coin collector's problem==