Content deleted Content added
m Open access bot: doi updated in citation with #oabot. |
m Disambiguating links to Code word (link changed to Code word (communication)) using DisamAssist. |
||
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 (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==
| |||