Talk:Package-merge algorithm

From Wikipedia, the free encyclopedia

I was in the process of adding several related topics. I kept this one short and then added the others. When I came back, there was this notice. I am going to add the information now. :) Sorry, Oravec 06:13, 7 November 2006 (UTC)

I will add the details within 48 hours. I wish to verify the information before adding it. Oravec 06:22, 7 November 2006 (UTC)

Although some references need to be added, the algorithm is now described. Faster algorithms for the length-limited Huffman coding problem exist, but they are too complicated for practical applications. Vegasprof 12:06, 7 November 2006 (UTC)

This page has come a long way. I've added a link from the Huffman coding page, particularly the Length-limited Huffman coding section. Hopefully the links will draw others to help put the final touches on this page. Oravec 15:00, 7 November 2006 (UTC)

[edit] Improvements since 1990

Someone needs to add a section on improvements and extensions to the algorithm that have been developed since 1990. For example, it is now known how to execute the package-merge algorithm using O(n) space. I would prefer that someone else, hopefully someone who is more of an expert in these latest developments, volunteer for this task. Vegasprof 03:11, 8 November 2006 (UTC)

Done; the appropriate sources are various Moffat/Turpin sources (so hopefully Managing Gigabytes should be good enough) and:

author = "L. L. Larmore and T. M. Przytycka",

title = "A Fast Algorithm for Optimal Height-Limited Alphabetic Binary-Trees",

journal = SICOMP,

volume = "23",

number = "6",

month = dec,

year = 1994,

pages = "1283-1312",

If anyone wants to add the refs appropriately and/or use math tags, they're welcome to do so. If not, hopefully I'll get around to it soon.... Calbaer 03:52, 8 November 2006 (UTC)

[edit] Ok Now, I Think

Shouldn't "importance" and "verify" be removed now? They were put up there some time ago, before the page was expanded to include so much detail and so many references. Vegasprof 10:09, 13 November 2006 (UTC)