हफमान कैसे ऑप्टिमल कोड बनाता है
हैमिंग हफमान कोडिंग को एक लालची एल्गोरिदम के रूप में प्रस्तुत करता है जो एक न्यूनतम औसत लंबाई वाले प्रीफ्री कोड को निर्मित करता है। कुंजी विचार: झाड़ को नीचे से निर्मित करें, हमेशा सबसे कम संभावना सिंबल को मिलाएं।
अग्रिम पास (निर्माण)
1. सभी सिंबलों को संभावन के अनुसार क्रमबद्ध करें, सबसे ऊंचा सबसे नीचे।
2. सबसे कम संभावना सिंबल को लें। उन्हें एक नया मेटा-सिंबल के साथ जोड़ें। इसकी संभावना = दो संभावनों की गिनती।
3. इसे सॉर्टेड स्थान में डालें।
4. जब तक केवल दो सिंबल बचते हैं, ऐसा करते रहें।
5. दो शेष सिंबलों को 0 और 1 आवंटित करें।
वापसी पास (कोड आवंटित करें)
प्रत्यावर्तित करते हुए: प्रत्येक विभाजन पर, जो दो सिंबल थे जो मिलाए गए थे, उनके को अपने संयुक्त माता-पिता के समान प्रीफिक्स बिट्स प्राप्त करते हैं, साथ में एक अतिरिक्त 0 (एक बच्चा) या 1 (दूसरा बच्चा)। 0/1 आवंटन का विकल्प उपलब्ध है - कोई भी वैध है।
ऑप्टिमल क्यों है: यदि किसी अन्य कोड की औसत लंबाई एल' थी, तो उसी अग्रिम कमी को लागू करने पर अंततः दो सिंबलों के औसत लंबाई का 1 बिट से कम होना संभव होगा - एक 2-सिंबल कोड के लिए असंभव। विरोधाभास।
एल्गोरिदम को ट्रेस करें
हैमिंग के उदाहरण: चार सिंबल ए, बी, सी, डी के साथ p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125।
अग्रिम पास:
चरण 1: सॉर्टेड: ए(0.5), ब(0.25), सी(0.125), डी(0.125)। सबसे नीचे दो: सी, डी।
चरण 2: एमर्ज सीडी के साथ प=0.25। नई सूची: ए(0.5), ब(0.25), सीडी(0.25)।
चरण 3: सबसे कम दो: ब(0.25), सीडी(0.25)। बीसीडी को प=0.5 के साथ मिलाएं।
चरण 4: दो सिंबल बचते हैं: ए(0.5), बीसीडी(0.5)। आवंटित करते हैं: ए=0, बीसीडी=1।
वापसी पास:
बीसीडी → ब को 10 मिलता है, सीडी को 11 मिलता है। सीडी → सी को 110 मिलता है, डी को 111 मिलता है।
अंतिम कोड: ए=0 (l=1), ब=10 (l=2), सी=110 (l=3), डी=111 (l=3)।
एल = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 बिट्स।
वैध हफमेन कोडों की अनन्याता
हैमिंग दो स्रोतों की अनन्याता को नोट करते हैं:
1. निर्भरता 0/1 की अनार्द्धय। प्रत्येक विभाजन में, आप बच्चे को 0 दे सकते हैं। 0 और 1 को पूरी तरह से बदलने से एक अलग कोड प्राप्त होता है जिसके साथ समान एल।
2. बराबरी टाई-ब्रेकिंग। जब दो नोड्स की समान संभावना होती है, तो किसी को भी 'ऊपर' रखा जा सकता है (प्रथम मिलान किया जाए)। अलग-अलग टाई-ब्रेकिंग चयन संरचना में समान एल वाले 'लंबे' और 'बुशी' वृक्ष पैदा कर सकते हैं, लेकिन भिन्न कोड-लंबाई वितरण होते हैं।
लंबे व बुशी
लंबे वृक्ष (विचलित): प्रत्येक गहराई स्तर पर एक सिंबल (फाइबोनैकी जैसी संरचना)। कोड लंबाई विस्तृत रूप से भिन्न होती है: एक सिंबल को छोटा कोड मिलता है, अन्य को लंबे कोड की ओर गिरते हैं।
बुशी वृक्ष (संतुलित): सिंबल्स को समान रूप से गहराई स्तर पर फैला दिया जाता है। कोड लंबाई क्लस्टर करीब औसत के पास होती है। निम्न वैरिएंस।
हैमिंग का सुझाव: जब विकल्प मिले, तो बुशी वृक्ष का विकल्प चुनें। समान एल, लेकिन कोड लंबाई में छोटे वैरिएंस → समानान्तर अनुप्रयोगों में डिकोडिंग समय में अधिक संतोषजनक → वास्तविक समय आवेदनों के लिए छोटे बफर आवश्यकता।
कोड-लंबाई वैरिएंस की गणना
कोड-लंबाई का वैरिएंस: 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.
कम्प्रेशन के लाभ vs चिह्न वितरण
हम्मिंग का नियम: हफमेन कोडिंग केवल तब लाभदायक होती है जब चिह्नों की संभावनों में काफी अंतर हो।
समान संभावनाएँ। अगर सभी 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, ..., अंत में दो बराबर लंबाई के कोड तक पहुंचता है। यह एक 'कॉमा कोड' है: एक रन के बाद 1 के बाद प्रतीक्षा करने वाला 0 एक कोमा की तरह काम करता है।
हम्मिंग नोट करते हैं: वास्तविक दुनिया की डेटा संपीड़न (बैकअप, फ़ाइल आर्काइविंग) जब स्रोत में असमान संभावना होती है - अंग्रेजी टेक्स्ट एक प्रमुख उदाहरण है - तब स्टोरेज को आधे से अधिक कम कर सकता है।
हफमेन vs ब्लॉक कोड: संख्यात्मक तुलना
हम्मिंग का दूसरा उदाहरण: 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 vs 1/30, एक 10:1 अनुपात), तो वैरिएबल-लेंथ कोडिंग का काफी हद तक लाभ होता है।
स्वयं-कंपाइलिंग प्रोग्राम
हैमिंग के 11वें अध्याय का अंतिम विचार: हफमन एन्कोडर स्वयं को एन्कोड कर सकता है। डिकोडिंग ट्री (जो डिकोडर को कॉम्प्रेस्ड मैसेज को पढ़ने के लिए बताती है) कॉम्प्रेस्ड डेटा के साथ साथ भेजा जाता है। प्राप्तकर्ता को कोड के बारे में पूर्वानुमान नहीं होने की आवश्यकता है।
एन्कोडर: डेटा को सैंपल करता है, संभावनाओं को अनुमान लगाता है, हफमन कोड को बनाता है, एक हेडर के रूप में डिकोडिंग ट्री को एन्कोड करता है, फिर डेटा को एन्कोड करता है।
डिकोडर: हेडर को पढ़कर ट्री को पुनर्निर्माण करता है, फिर इसे उपयोग करता है।
हैमिंग का निर्देश: इस पाइपलाइन को पूरी तरह से लाइब्रेरी फंक्शन के रूप में चल सकता है जिसमें कोई मानव सहभागिता नहीं होती है। आप इसे कॉल करते हैं, यह संपीड़ित और विस्तृत करता है। आधुनिक आर्काइविंग फॉर्मेट्स (ZIP, gzip, bzip2) इसी पैटर्न को लागू करते हैं।
गहरा सिद्धांत: एल्गोरिदम की बुद्धिमत्ता है, नहीं कि एक स्थिर कोड टेबल में। एल्गोरिदम को वह डेटा प्राप्त होता है। यही पैटर्न हैमिंग देखता है सभी महान इंजीनियरिंग प्रणालियों में: अनुक्षमता बनाई जाती है, नहीं कि बांधा जाता है।