Paketsammanfogningsalgoritm

Paketsammanslagningsalgoritmen är en O (nL) -tidsalgoritm för att hitta en optimal längdbegränsad Huffman-kod för en given distribution på ett givet alfabet av storlek n , där inget kodord är längre än L . Det är en girig algoritm och en generalisering av Huffmans ursprungliga algoritm . Package-merge fungerar genom att reducera kodkonstruktionsproblemet till det binära myntsamlarproblemet .

Myntsamlarens problem

Anta att en myntsamlare har ett antal mynt av olika valörer, som vart och ett har ett numismatiskt värde som inte är relaterat till dess valör. Myntsamlaren har slut på pengar och behöver använda en del av sin myntsamling för att köpa något till kostnad N . Han vill välja en delmängd av mynt från sin samling med minsta numismatiska värde vars valörer totalt N .

Den binära versionen av detta problem är att alla valörer är potenser av 2, det vill säga 1, 1/2, 1/4, etc. dollar.

Beskrivning av paketsammanslagningsalgoritmen

Antag att den största valören är 1 dollar och att N är ett heltal. (Algorithmen fungerar även om dessa antaganden inte håller, genom triviala modifieringar.) Myntsamlaren delar först upp sina mynt i listor, en för varje valör, sorterade efter numismatiskt värde. Han paketerar sedan de minsta valörerna i par, med start från paret med minsta totala numismatiska värde. Om det finns ett mynt över, kommer det att vara myntet med högsta numismatiska värde för valören, och det läggs åt sidan och ignoreras hädanefter. Dessa paket slås sedan samman i listan över mynt med näst minsta valör, återigen i ordning efter numismatiskt värde. Objekten i den listan paketeras sedan i par och slås samman till den näst minsta listan, och så vidare.

Slutligen finns det en lista över föremål, som var och en är ett 1 dollarmynt eller ett paket bestående av två eller flera mindre mynt vars valörer totalt 1 dollar. De är också sorterade i ordning efter numismatiskt värde. Myntsamlaren väljer sedan det lägsta värdet N av dem.

Observera att tiden för algoritmen är linjär i antalet mynt.

Minskning av längdbegränsad Huffman-kodning till myntsamlarens problem

Låt L vara den maximala längden som ett kodord får ha. Låt p ₁ , …, p _n vara frekvenserna för symbolerna i alfabetet som ska kodas. Vi sorterar först symbolerna så att p _i ≤ p _{i +1} . Skapa L mynt för varje symbol med valörerna 2 ⁻¹ , …, 2 ^{− L} , var och en med numismatiskt värde p _i . Använd paketsammanslagningsalgoritmen för att välja uppsättningen mynt med minsta numismatiska värde vars valörer totalt n − 1. Låt h _i vara antalet mynt med numismatiskt värde p _i valda. Den optimala längdbegränsade Huffman-koden kommer att koda symbolen i med en bitsträng med längden h _i . Den kanoniska Huffman-koden kan enkelt konstrueras med en enkel nedifrån och upp girig metod, givet att h i _är kända, och detta kan vara grunden för snabb datakomprimering .

Prestandaförbättringar och generaliseringar

Med denna reduktion är algoritmen O(nL) -tid och O(nL) -rymd. Den ursprungliga uppsatsen, " En snabb algoritm för optimala längdbegränsade Huffman-koder ", visar hur detta kan förbättras till O(nL) -tid och O(n) -mellanrum. Tanken är att köra algoritmen en första gång, bara behålla tillräckligt med data för att kunna fastställa två ekvivalenta delproblem som är hälften så stora som det ursprungliga problemet. Detta görs rekursivt, vilket resulterar i en algoritm som tar ungefär dubbelt så lång tid men som bara kräver linjärt utrymme.

Många andra förbättringar har gjorts av paketsammanslagningsalgoritmen för att reducera den multiplikativa konstanten och för att göra den snabbare i speciella fall, såsom de problem som har upprepade p _i :er. Metoden för sammanslagning av paket har också anpassats till relaterade problem som alfabetisk kodning .

Metoder som involverar grafteori har visat sig ha bättre asymptotisk rymdkomplexitet än paketsammanslagningsalgoritmen, men dessa har inte haft så mycket praktisk tillämpning.

^ ^a ^b Larmore, Lawrence L. ; Hirschberg, Daniel S. (1990). "En snabb algoritm för optimala längdbegränsade Huffman-koder". Journal of the Association for Computing Machinery . 37 (3): 464–473. doi : 10.1145/79147.79150 . S2CID 11696729 .
^ Moffat, Alistair; Turpin, Andrew (okt 1997). "Om implementering av minimiredundansprefixkoder". IEEE-transaktioner på kommunikation . 45 (10): 1200–1207. doi : 10.1109/26.634683 .
^ Witten, Ian H. ; Moffat, Alistair; Bell, Timothy Clinton (1999). Hantera Gigabyte: Komprimering och indexering av dokument och bilder (2 uppl.). Morgan Kaufmann förlag . ISBN 978-1-55860-570-1 . 1558605703.
^ Larmore, Lawrence L. ; Przytycka, Teresa M. (1994). "En snabb algoritm för optimala höjdbegränsade alfabetiska binära träd". SIAM Journal on Computing . 23 (6): 1283–1312. doi : 10.1137/s0097539792231167 .

externa länkar

Baer, Michael B. (2006). "Tjugo (eller så) frågor: D -ary Length-Bounded Prefix Coding". arXiv : cs.IT/0602085 .
Moffat, Alistair; Turpin, Andrew; Katajainen, Jyrki (mars 1995). Utrymmeseffektiv konstruktion av optimala prefixkoder . IEEE Data Compression Conference. Snowbird, Utah, USA. doi : 10.1109/DCC.1995.515509 .
En implementering av paketsammanslagningsalgoritmen " [1] "
En snabb entropikodare som använder paketsammanslagningsalgoritm [2]

[LaHi-1] Larmore, Lawrence L. ; Hirschberg, Daniel S. (1990). "En snabb algoritm för optimala längdbegränsade Huffman-koder". Journal of the Association for Computing Machinery . 37 (3): 464–473. doi : 10.1145/79147.79150 . S2CID 11696729 .

[MoTu-2] Moffat, Alistair; Turpin, Andrew (okt 1997). "Om implementering av minimiredundansprefixkoder". IEEE-transaktioner på kommunikation . 45 (10): 1200–1207. doi : 10.1109/26.634683 .

[MG-3] Witten, Ian H. ; Moffat, Alistair; Bell, Timothy Clinton (1999). Hantera Gigabyte: Komprimering och indexering av dokument och bilder (2 uppl.). Morgan Kaufmann förlag . ISBN 978-1-55860-570-1 . 1558605703.

[LaPr-4] Larmore, Lawrence L. ; Przytycka, Teresa M. (1994). "En snabb algoritm för optimala höjdbegränsade alfabetiska binära träd". SIAM Journal on Computing . 23 (6): 1283–1312. doi : 10.1137/s0097539792231167 .