हफ़मैन कैसे इष्टतम कोड बनाता है
हैमिंग हफ़मैन कोडिंग को एक लालची एल्गोरिदम के रूप में प्रस्तुत करता है जो न्यूनतम-औसत-लंबाई उपसर्ग-मुक्त कोड बनाता है। मुख्य विचार: पेड़ को नीचे से ऊपर बनाएं, हमेशा दो कम से कम संभावित प्रतीकों को मर्ज करते हुए।
आगे की पास (बिल्ड)
1. सभी प्रतीकों को संभावना के अनुसार, उच्चतम से निम्नतम तक क्रमबद्ध करें।
2. दो सबसे कम-संभावना वाले प्रतीकों को लें। उन्हें एक नए मेटा-प्रतीक में संयोजित करें जिसकी संभावना = दोनों का योग।
3. मेटा-प्रतीक को उसकी क्रमबद्ध स्थिति में डालें।
4. तब तक दोहराएं जब तक केवल दो प्रतीक न रह जाएं।
5. दोनों शेष प्रतीकों को 0 और 1 असाइन करें।
पिछली पास (कोड असाइन करना)
मर्ज को विपरीत क्रम में पूर्ववत करें: प्रत्येक विभाजन पर, जिन दो प्रतीकों को मर्ज किया गया था वे उनके संयुक्त मूल के समान उपसर्ग बिट्स प्राप्त करते हैं, साथ ही एक अतिरिक्त 0 (एक बच्चा) या 1 (अन्य बच्चा)। 0/1 असाइनमेंट मनमाना है — दोनों मान्य हैं।
यह इष्टतम क्यों है: यदि किसी अन्य कोड की छोटी औसत लंबाई L' होती, तो समान आगे की कटौती को लागू करने से अंततः दो प्रतीकों के साथ 1 बिट से कम औसत लंबाई प्राप्त होगी — एक 2-प्रतीक कोड के लिए असंभव। विरोधाभास।
एल्गोरिदम को ट्रेस करना
हैमिंग का उदाहरण: चार प्रतीक A, B, C, D जिनमें p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125।
आगे की पास:
चरण 1: क्रमबद्ध: A(0.5), B(0.25), C(0.125), D(0.125)। सबसे कम दो: C, D।
चरण 2: CD को p=0.25 के साथ मर्ज करें। नई सूची: A(0.5), B(0.25), CD(0.25)।
चरण 3: सबसे कम दो: B(0.25), CD(0.25)। BCD को p=0.5 के साथ मर्ज करें।
चरण 4: दो प्रतीक बचे: A(0.5), BCD(0.5)। A=0, BCD=1 असाइन करें।
पिछली पास:
BCD → B को 10 मिलता है, CD को 11 मिलता है। CD → C को 110 मिलता है, D को 111 मिलता है।
अंतिम कोड: A=0 (l=1), B=10 (l=2), C=110 (l=3), D=111 (l=3)।
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 बिट्स।
कई मान्य हफ़मैन कोड
हैमिंग दो गैर-विशिष्टता के स्रोतों को नोट करता है:
1. मनमाना 0/1 असाइनमेंट। प्रत्येक विभाजन पर, आप 0 को किसी भी बच्चे को दे सकते हैं। 0 और 1 को पूरी तरह स्वैप करने से एक अलग कोड मिलता है जिसमें समान L है।
2. टाई-ब्रेकिंग। जब दो नोड्स की समान संभावना होती है, तो या तो 'ऊपर' रखा जा सकता है (पहले संयोजित किया जा सकता है)। विभिन्न टाई-ब्रेकिंग विकल्प संरचनात्मक रूप से विभिन्न पेड़ — 'लंबे' बनाम 'झाड़ीदार' — उत्पादित कर सकते हैं जिनमें समान L लेकिन विभिन्न कोड-लंबाई वितरण हैं।
लंबा बनाम झाड़ीदार
लंबा पेड़ (तिरछा): प्रत्येक गहराई स्तर पर एक प्रतीक (फिबोनैचि-जैसी संरचना)। कोड लंबाई व्यापक रूप से भिन्न होती है: एक प्रतीक को एक छोटा कोड मिलता है, अन्य लंबे कोड में cascade होते हैं।
झाड़ीदार पेड़ (संतुलित): प्रतीक गहराई के स्तरों में समान रूप से फैले हुए हैं। कोड लंबाई औसत के पास क्लस्टर होती है। कम विचरण।
हैमिंग की सिफारिश: जब विकल्प दिया जाए, तो झाड़ीदार पेड़ को प्राथमिकता दें। समान L, लेकिन कोड लंबाई में कम विचरण → अधिक समान डिकोडिंग समय → वास्तविक समय अनुप्रयोगों में छोटे बफर आवश्यकताएं।
कोड-लंबाई विचरण की गणना
कोड लंबाई का विचरण: Var = E[l²] − (E[l])²
कोड {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3} के लिए p=[0.5, 0.25, 0.125, 0.125] के साथ:
E[l] = L = 1.75
E[l²] = 0.5·1² + 0.25·2² + 0.125·3² + 0.125·3² = 0.5 + 1.0 + 1.125 + 1.125 = 3.75
Var = 3.75 − 1.75² = 3.75 − 3.0625 = 0.6875
समान-संभावना वाले प्रतीकों के लिए एक वैकल्पिक झाड़ीदार कोड सभी लंबाई-2 कोड का उपयोग करता है: L=2, Var=0।
संपीड़न लाभ बनाम प्रतीक वितरण
हैमिंग का नियम: हफ़मैन कोडिंग तभी भुगतान करती है जब प्रतीक संभावनाएं काफी भिन्न हों।
समान संभावनाएं। यदि सभी 2^k प्रतीकों की समान संभावना 1/2^k है, तो हफ़मैन एक ब्लॉक कोड उत्पादित करता है: प्रत्येक प्रतीक को लंबाई k मिलती है। L = H = k। साधारण ब्लॉक कोड पर कोई लाभ नहीं।
तिरछी संभावनाएं। यदि एक प्रतीक प्रभावशाली है (p >> 1/2^k अन्य के लिए), तो हफ़मैन इसे बहुत छोटा कोड असाइन करता है (लंबाई 1 या 2), नाटकीय रूप से L को कम करते हुए।
अल्पविराम कोड (हैमिंग का शब्द)। जब प्रत्येक संभावना शेष कुल का 2/3 से अधिक हो, तो हफ़मैन स्वाभाविक रूप से उत्पादित करता है: p(s1)→0, p(s2)→10, p(s3)→110, ..., अंत तक दो समान-लंबाई कोड पर। यह एक 'अल्पविराम कोड' है: 1s के रन के बाद पिछला 0 अल्पविराम की तरह कार्य करता है।
हैमिंग नोट करता है: वास्तविक दुनिया के डेटा संपीड़न (बैकअप, फाइल आर्काइविंग) स्टोरेज को आधे से अधिक काटा जा सकता है जब स्रोत की तिरछी संभावनाएं हों — अंग्रेजी पाठ प्राथमिक उदाहरण है।
हफ़मैन बनाम ब्लॉक कोड: संख्यात्मक तुलना
हैमिंग का दूसरा उदाहरण: p(s1)=1/3, p(s2)=1/5, p(s3)=1/6, p(s4)=1/10, p(s5)=1/12, p(s6)=1/20, p(s7)=1/30, p(s8)=1/30।
ब्लॉक कोड: 8 प्रतीक → 3 बिट्स प्रत्येक → L_block = 3।
हैमिंग हफ़मैन कोड की गणना करता है और L_Huffman ≈ 2.58 बिट्स की रिपोर्ट करता है।
बचत: (3 − 2.58)/3 ≈ ब्लॉक कोडिंग पर 14% संपीड़न।
जब प्रतीक संभावनाएं बहुत भिन्न होती हैं (यहाँ 1/3 बनाम 1/30, 10:1 अनुपात), तो वेरिएबल-लंबाई कोडिंग पर्याप्त भुगतान करती है।
स्व-संकलन प्रोग्राम
हैमिंग अध्याय 11 को एक आकर्षक विचार के साथ समाप्त करता है: एक हफ़मैन एन्कोडर स्वयं को एन्कोड कर सकता है। डिकोडिंग ट्री (जो डिकोडर को बताता है कि संपीड़ित संदेश को कैसे पढ़ें) संपीड़ित डेटा के साथ प्रेषित किया जाता है। रिसीवर को कोड का कोई पूर्व ज्ञान नहीं चाहिए।
एन्कोडर: डेटा का नमूना लेता है, संभावनाओं का अनुमान लगाता है, हफ़मैन कोड का निर्माण करता है, डिकोडिंग ट्री को एक हेडर के रूप में एन्कोड करता है, फिर डेटा को एन्कोड करता है।
डिकोडर: हेडर को पढ़ता है और ट्री को पुनर्निर्माण करता है, फिर इसका उपयोग करके डेटा को डिकोड करता है।
हैमिंग का बिंदु: यह पूरी पाइपलाइन एक लाइब्रेरी फ़ंक्शन के रूप में चल सकती है जिसमें कोई मानव भागीदारी नहीं है। आप इसे कॉल करते हैं, यह स्वचालित रूप से संपीड़ित और विस्तारित करता है। आधुनिक आर्काइविंग प्रारूप (ZIP, gzip, bzip2) बिल्कुल यही पैटर्न लागू करते हैं।
गहरा सिद्धांत: बुद्धिमत्ता एल्गोरिदम में है, एक निश्चित कोड तालिका में नहीं। एल्गोरिदम जो भी डेटा प्राप्त करता है उसके अनुकूल होता है। यह पैटर्न है जो हैमिंग सभी महान इंजीनियरिंग सिस्टम में देखता है: अनुकूलन बनाया हुआ, बोल्ट किया हुआ नहीं।