Package-merge algorithm
पैकेज-विलय एल्गोरिथ्म आकार एन के दिए गए वर्णमाला पर दिए गए वितरण के लिए एक इष्टतम लंबाई-सीमित हफमैन कोड खोजने के लिए एक ओ (एनएल)-समय एल्गोरिथ्म है, जहां कोई भी कोड शब्द एल से लंबा नहीं है। पैकेज-विलय द्विआधारी सिक्का संग्राहक की समस्या के लिए कोड निर्माण समस्या को कम करके काम करता है। सिक्का संग्राहक की समस्या मान लीजिए कि एक सिक्का संग्राहक के पास विभिन्न मूल्यवर्ग के कई सिक्के हैं, जिनमें से प्रत्येक का एक मुद्राशास्त्रीय मूल्य है जो इसके मूल्यवर्ग से असंबंधित है। सिक्का संग्राहक के पास पैसे खत्म हो गए हैं और उसे अपने सिक्के के संग्रह में से कुछ का उपयोग एन मूल्य का कुछ खरीदने के लिए करना पड़ता है। वह अपने न्यूनतम मुद्रा मूल्य के संग्रह से सिक्कों के एक उपसमुच्चय का चयन करना चाहता है जिसके मूल्यवर्ग कुल एन हैं। इस समस्या का द्विआधारी संस्करण यह है कि सभी मूल्यवर्ग 2 की शक्तियाँ हैं, यानी 1,1/2,1/4, आदि। डॉलर। पैकेज-विलय एल्गोरिथम का विवरण मान लीजिए कि सबसे बड़ा मूल्यवर्ग 1 डॉलर है, और एन एक पूर्णांक है। (एल्गोरिथ्म काम करता है भले ही ये धारणाएं मामूली संशोधनों द्वारा नहीं होती हैं।) सिक्का संग्राहक पहले अपने सिक्कों को सूचियों में अलग करता है, प्रत्येक मूल्यवर्ग के लिए एक, मुद्रा मूल्य द्वारा क्रमबद्ध। फिर वह सबसे छोटे मूल्यवर्ग के सिक्कों को जोड़े में पैक करता है, जो सबसे छोटे कुल मुद्रा मूल्य की जोड़ी से शुरू होता है। यदि एक सिक्का बचा है, तो यह उस मूल्यवर्ग का उच्चतम मुद्रा मूल्य का सिक्का होगा, और इसे अलग रखा जाता है और अब से इसे नजरअंदाज कर दिया जाता है। इन पैकेजों को फिर से मुद्रा मूल्य के क्रम में अगले सबसे छोटे मूल्यवर्ग के सिक्कों की सूची में मिला दिया जाता है। उस सूची में वस्तुओं को फिर जोड़े में पैक किया जाता है, और अगली सबसे छोटी सूची में विलय कर दिया जाता है, और इसी तरह आगे। अंत में, वस्तुओं की एक सूची होती है, जिनमें से प्रत्येक 1 डॉलर का सिक्का या एक पैकेज होता है जिसमें दो या दो से अधिक छोटे सिक्के होते हैं जिनके मूल्यवर्ग कुल 1 डॉलर होते हैं। उन्हें मुद्रा मूल्य के क्रम में भी क्रमबद्ध किया जाता है। सिक्का संग्राहक तब उनमें से सबसे कम मूल्य एन का चयन करता है। ध्यान दें कि एल्गोरिथ्म का समय सिक्कों की संख्या में रैखिक है। सिक्का संग्राहक की समस्या के लिए लंबाई-सीमित हफमैन कोडिंग को कम करना मान लीजिए कि किसी भी कोड शब्द की अधिकतम लंबाई L होनी चाहिए। मान लीजिए कि p1,., pn कूटबद्ध किए जाने वाले वर्णमाला के प्रतीकों की आवृत्तियाँ हैं। हम पहले प्रतीकों को क्रमबद्ध करते हैं ताकि पाई ≤ पाई + 1 हो। 2-1,., 2-L मूल्यवर्ग के प्रत्येक प्रतीक के लिए एल सिक्के बनाएँ, प्रत्येक मुद्रा मूल्य पाई के। न्यूनतम मुद्रा मूल्य के सिक्कों के समूह का चयन करने के लिए पैकेज-विलय एल्गोरिथ्म का उपयोग करें जिनके मूल्यवर्ग कुल n-1 हैं। मुद्राशास्त्रीय मूल्य पाई के चयनित सिक्कों की संख्या को हाय मान लीजिए। इष्टतम लंबाई-सीमित हफमैन कोड प्रतीक i को लंबाई हाय की एक बिट स्ट्रिंग के साथ कूटबद्ध करेगा। कैनोनिकल हफमैन कोड को आसानी से एक सरल बॉटम-अप लालची विधि द्वारा बनाया जा सकता है, यह देखते हुए कि हाय ज्ञात हैं, और यह तेज डेटा संपीड़न का आधार हो सकता है। प्रदर्शन में सुधार और सामान्यीकरण इस कमी के साथ, एल्गोरिथ्म ओ (एनएल)-समय और ओ (एनएल)-स्थान है। हालांकि, मूल पेपर, "इष्टतम लंबाई-सीमित हफमैन कोड के लिए एक तेज़ एल्गोरिथ्म", दिखाता है कि इसे ओ (एनएल)-समय और ओ (एन)-स्थान में कैसे सुधार किया जा सकता है। विचार यह है कि एल्गोरिथ्म को पहली बार चलाया जाए, केवल दो समतुल्य उप-समस्याओं को निर्धारित करने में सक्षम होने के लिए पर्याप्त डेटा रखा जाए जो मूल समस्या के आधे आकार का योग है। यह पुनरावर्ती रूप से किया जाता है, जिसके परिणामस्वरूप एक एल्गोरिथ्म होता है जिसमें लगभग दोगुना समय लगता है लेकिन केवल रैखिक स्थान की आवश्यकता होती है। गुणक स्थिरांक को कम करने और विशेष मामलों में इसे तेजी से बनाने के लिए पैकेज-विलय एल्गोरिथ्म में कई अन्य सुधार किए गए हैं, जैसे कि उन समस्याओं में बार-बार पी. आई. एस. होना। पैकेज-विलय दृष्टिकोण को वर्णमाला कोडिंग जैसी संबंधित समस्याओं के लिए भी अनुकूलित किया गया है। ग्राफ सिद्धांत से जुड़ी विधियों में पैकेज-विलय एल्गोरिदम की तुलना में बेहतर एसिम्प्टोटिक स्पेस जटिलता दिखाई गई है, लेकिन इनमें उतना व्यावहारिक अनुप्रयोग नहीं देखा गया है। संदर्भ बाहरी लिंक पैकेज-विलय एल्गोरिदम का एक कार्यान्वयन "" एक तेज एन्ट्रापी कोडर जो पैकेज-विलय एल्गोरिदम का उपयोग करता है हानि रहित संपीड़न एल्गोरिदम कोडिंग सिद्धांत