लालची रणनीति क्यों इष्टतम है
हफ़मैन एल्गोरिदम एक लालची एल्गोरिदम है: प्रत्येक चरण में, यह स्थानीय रूप से इष्टतम विकल्प बनाता है (दो सबसे सस्ते नोड्स को मिलाएं) आगे देखे बिना। लालची एल्गोरिदम हमेशा विश्व स्तर पर इष्टतम नहीं होते — लेकिन यहां वे हैं।
इष्टतमता तर्क
मान लीजिए कि एक कोड C में न्यूनतम औसत लंबाई L है। सबसे कम प्रायिकता वाले दो प्रतीकों पर विचार करें, मान लीजिए p_a और p_b। किसी भी इष्टतम कोड में, ये दोनों प्रतीक वृक्ष के सबसे गहरे स्तर पर भाई-बहन की पत्तियों के रूप में दिखाई देना चाहिए। क्यों?
यदि उन्होंने माता-पिता साझा नहीं किए, तो आप गहरे प्रतीक को छोटे कोड के साथ स्वैप कर सकते हैं — L को कम करते हुए। इसलिए सबसे गहरी पत्तियां सबसे कम संभावित प्रतीकें होनी चाहिए।
अब, यदि आप a और b को एक मेटा-प्रतीक ab (p_ab = p_a + p_b के साथ) में जोड़ते हैं, तो घटी हुई समस्या पर कोई भी इष्टतम कोड बिल्कुल घटी हुई समस्या पर हफ़मैन कोड है। आगमन तर्क को पूरा करता है।
ज्यामितीय दृश्य
हफ़मैन एल्गोरिदम द्विआधारी वृक्ष को नीचे से ऊपर तक निर्माण करता है, सबसे कम संभावित प्रतीकों को सबसे बड़ी गहराई पर रखते हुए। यह Σ p_i · depth(i) = L को कम करता है।
समकक्ष दृश्य: आप वृक्ष की पत्तियों को भारित पथ की लंबाई को कम करने के लिए लेबल असाइन कर रहे हैं, जहां प्रत्येक पत्ती का वजन इसकी प्रायिकता है।
लालची चरणों को निष्पादित करना
प्रायिकताएं: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1। योग = 1.0 ✓
चरण 1: सबसे कम दो: C(0.2), D(0.1)। मिलाएं → CD(0.3)। सूची: A(0.4), B(0.3), CD(0.3)।
चरण 2: सबसे कम दो: B(0.3), CD(0.3) (बराबर — कोई भी वैध)। मिलाएं → BCD(0.6)। सूची: A(0.4), BCD(0.6)।
चरण 3: A(0.4), BCD(0.6) को मिलाएं → root(1.0)। A=0, BCD=1 असाइन करें।
पश्चवर्ती: BCD → B=10 (l=2), CD=11 → C=110 (l=3), D=111 (l=3)।
L = 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 0.4+0.6+0.6+0.3 = 1.9 bits।
कोड-लंबाई विचरण
दो हफ़मैन कोड समान L प्राप्त कर सकते हैं लेकिन कोड-लंबाई वितरण अलग हो सकते हैं। कोड लंबाई का विचरण इस प्रसार को मापता है:
Var(l) = E[l²] − (E[l])²
जहां E[l] = L (औसत कोड लंबाई) और E[l²] = Σ p_i · l_i²।
विचरण क्यों महत्वपूर्ण है:
1. बफर आवश्यकताएं। रीयल-टाइम डिकोडिंग में, प्रत्येक प्रतीक बिट्स की एक परिवर्तनशील संख्या लेता है। उच्च विचरण का मतलब है कि कुछ प्रतीक कई बिट्स लेते हैं — आपको एक बड़े इनपुट बफर की आवश्यकता होती है यह गारंटी देने के लिए कि आप हमेशा एक पूर्ण प्रतीक पढ़ सकते हैं।
2. डिकोडिंग विलंबता। उच्च-विचरण कोड में लंबे सबसे खराब स्थिति वाले डिकोडिंग पथ होते हैं। कम-विचरण (व्यस्त) कोड सबसे खराब स्थिति को अधिक कसकर बांधते हैं।
3. मजबूती। एक उच्च-विचरण कोड में एक खोई हुई बिट अधिक समन्वय क्षति का कारण बनती है क्योंकि लंबे कोडवर्ड को पूरी तरह से फिर से पढ़ा जाना चाहिए।
हैमिंग की सिफारिश: जब कई वैध हफ़मैन कोड मौजूद होते हैं (टाई-ब्रेकिंग विकल्प), कम विचरण वाले को पसंद करें — व्यस्त वृक्ष।
दो वृक्षों के लिए विचरण की गणना करना
p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1 और कोड A=0, B=10, C=110, D=111 का उपयोग करते हुए:
E[l] = L = 1.9
E[l²] = 0.4·1² + 0.3·2² + 0.2·3² + 0.1·3² = 0.4+1.2+1.8+0.9 = 4.3
Var = 4.3 − 1.9² = 4.3 − 3.61 = 0.69
3-प्रतीक हफ़मैन कोड अंत से अंत तक
एक पूर्ण अंत-से-अंत उदाहरण: हफ़मैन कोड बनाएं, L की गणना करें, H की गणना करें, L ≥ H सत्यापित करें, Var की गणना करें।
स्रोत: p(X)=0.6, p(Y)=0.3, p(Z)=0.1।
हफ़मैन निर्माण:
चरण 1: क्रमबद्ध: X(0.6), Y(0.3), Z(0.1)। सबसे कम दो: Y(0.3), Z(0.1)।
मिलाएं → YZ(0.4)। सूची: X(0.6), YZ(0.4)।
चरण 2: X(0.6), YZ(0.4) को मिलाएं → root(1.0)। X=0, YZ=1 असाइन करें।
YZ → Y=10, Z=11।
कोड: X=0 (l=1), Y=10 (l=2), Z=11 (l=2)।
L = 0.6·1 + 0.3·2 + 0.1·2 = 0.6 + 0.6 + 0.2 = 1.4 bits।
एन्ट्रॉपी: H = −0.6·log₂(0.6) − 0.3·log₂(0.3) − 0.1·log₂(0.1)
log₂(0.6) ≈ −0.737, log₂(0.3) ≈ −1.737, log₂(0.1) ≈ −3.322
H = 0.6·0.737 + 0.3·1.737 + 0.1·3.322 = 0.442 + 0.521 + 0.332 = 1.295 bits।
L = 1.4 ≥ H = 1.295 ✓। L/H = 1.4/1.295 ≈ 1.081। एन्ट्रॉपी से 8.1% ऊपर।
विचरण: E[l²] = 0.6·1 + 0.3·4 + 0.1·4 = 0.6+1.2+0.4 = 2.2। Var = 2.2 − 1.4² = 2.2 − 1.96 = 0.24।
आपकी बारी: एक पूर्ण पाइपलाइन
संदर्भ के लिए log₂ मान: log₂(0.5)=−1.000, log₂(0.25)=−2.000, log₂(0.125)=−3.000, log₂(0.375)≈−1.415, log₂(0.625)≈−0.678।