वृक्ष के रूप में कोड
एक उपसर्ग-मुक्त कोड एक बाइनरी वृक्ष से मैप करता है: रूट डिकोडिंग की शुरुआत का प्रतिनिधित्व करता है, बाएं शाखाएं बिट 0 का प्रतिनिधित्व करती हैं, दाई शाखाएं बिट 1 का प्रतिनिधित्व करती हैं, और पत्तियां पूर्ण कोडवर्ड का प्रतिनिधित्व करती हैं।
ज्यामितीय बाधा: प्रत्येक पत्ती एक रूट-से-पत्ती पथ को समाप्त करती है। कोई भी पत्ती एक वंशज नहीं हो सकती (यदि ऐसा होता, तो इसका कोडवर्ड वंशज के कोडवर्ड का उपसर्ग होता, जो उपसर्ग-मुक्त संपत्ति का उल्लंघन करता)।
यह क्राफ्ट असमानता को एक ज्यामितीय व्याख्या देता है:
गहराई d पर प्रत्येक पत्ती कुल वृक्ष क्षमता का 2^(−d) अंश 'कब्जा' करती है। गहराई D पर एक पूर्ण बाइनरी वृक्ष की कुल क्षमता 1 है। एक उपसर्ग-मुक्त कोड विभिन्न गहराई पर पत्तियों का उपयोग करता है; क्राफ्ट योग कुल अधिकार को मापता है।
क्राफ्ट योग = 1: पूर्ण कोड (हर पथ एक पत्ती पर समाप्त होता है — पूर्ण पैकिंग)।
क्राफ्ट योग < 1: अपूर्ण कोड (कुछ वृक्ष क्षमता अप्रयुक्त — अधिक प्रतीकों को जोड़ा जा सकता है)।
क्राफ्ट योग > 1: उपसर्ग-मुक्त कोड के लिए असंभव (कुछ पथों को एक पत्ती साझा करनी होगी)।
गहरी पत्तियां = लंबे कोड = कम क्षमता
गहराई 1 पर एक पत्ती वृक्ष क्षमता का आधा उपयोग करती है (2^(−1) = 0.5)।
गहराई 3 पर एक पत्ती एक आठवां उपयोग करती है (2^(−3) = 0.125)।
वृक्ष में ऊंचाई पर एक छोटा कोडवर्ड रखने से इसके सभी वंशज उपयोग से रोके जाते हैं — आप एक छोटे कोड को कई संभावित लंबे कोड के लिए व्यापार करते हैं।
एक उपसर्ग-मुक्त वृक्ष का निर्माण
5 प्रतीकों पर l = {1, 2, 3, 3, 3} की लंबाई पर विचार करें। क्राफ्ट योग = 2^(−1) + 2^(−2) + 3·2^(−3) = 0.5 + 0.25 + 0.375 = 1.125 > 1।
यह 1 से अधिक है: ये लंबाई एक उपसर्ग-मुक्त कोड के साथ असंगत हैं। कम से कम एक लंबाई को बढ़ाया जाना चाहिए।
ठीक करें: l_1 को 1 से 2 में बदलें। नई लंबाई {2, 2, 3, 3, 3}: क्राफ्ट = 2·2^(−2) + 3·2^(−3) = 0.5 + 0.375 = 0.875 < 1। वैध, लेकिन अपूर्ण।
ठीक करें: l_1 को 2 रखें, शेष क्षमता का उपयोग करने के लिए l_2 = 3 जोड़ें। क्राफ्ट = 0.875; शेष = 0.125 = 2^(−3): एक अधिक गहराई-3 पत्ती के लिए जगह।
एंट्रॉपी कोड लंबाई को क्यों सीमित करता है
क्राफ्ट की असमानता कोड संरचना को बाधित करती है (लंबाई वृक्ष में फिट होनी चाहिए)। शैनन की एंट्रॉपी कोड दक्षता को बाधित करती है (औसत लंबाई एक सैद्धांतिक तल को हरा नहीं सकती)।
इष्टतम कोड लंबाई। p_i संभावना वाले प्रतीक के लिए, आदर्श कोड लंबाई log₂(1/p_i) है। दुर्लभ प्रतीक लंबे कोड के योग्य हैं; बार-बार आने वाले प्रतीक छोटे कोड के योग्य हैं। यह क्राफ्ट समानता को दर्शाता है: 2^(−l_i) = p_i जब l_i = log₂(1/p_i)।
लेकिन log₂(1/p_i) शायद ही कभी एक पूर्णांक है। ⌈log₂(1/p_i)⌉ तक गोल करना हफमैन लंबाई देता है, जो H ≤ L < H + 1 को संतुष्ट करता है।
ज्यामितीय पठन। प्रत्येक प्रतीक को गहराई l_i पर बाइनरी वृक्ष पर एक बिंदु के रूप में प्लॉट करें। क्राफ्ट योग कुल पत्ती कवरेज को मापता है। एंट्रॉपी भारित औसत गहराई को मापता है, संभावना द्वारा भारित। शैनन का प्रमेय: संभावना-भारित औसत गहराई ≥ संभावना-भारित सूचना सामग्री।
एंट्रॉपी सीमा सत्यापन
कार्य किया गया उदाहरण: प्रतीकों {A, B, C, D} के लिए p = [1/2, 1/4, 1/8, 1/8]।
इष्टतम लंबाई: l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3।
ये सभी पूर्णांक हैं — एक पूर्ण मेल। हफमैन कोड: A=0, B=10, C=110, D=111।
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75।
H = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75। L = H बिल्कुल: इष्टतम कोड।
एक पूर्ण कार्य किया गया उदाहरण
पूर्ण पाइपलाइन: संभावनाएं दी गई, एंट्रॉपी की गणना करें, सत्यापित करें कि एक कोड सीमा को पूरा करता है।
स्रोत: p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125।
H = 1.75 बिट्स (ऊपर गणना की गई)।
एक भोली ब्लॉक कोड: 4 प्रतीक → 2 बिट्स प्रत्येक → L = 2.0। एंट्रॉपी पर ओवरहेड: 2.0 − 1.75 = 0.25 बिट्स/प्रतीक = 12.5% बर्बादी।
परिवर्तनशील-लंबाई कोड निश्चित-लंबाई की तुलना में 12.5% बचाता है। बड़े संदेशों के लिए, यह पर्याप्त है।
अंग्रेजी की एंट्रॉपी दर। शैनन ने लिखित अंग्रेजी की एंट्रॉपी का अनुमान लगभग 1.0 से 1.3 बिट्स प्रति वर्ण लगाया, 5-बिट ASCII कोड का उपयोग करने के बावजूद। वह 4:1 अनुपात प्राकृतिक भाषा में भारी अतिरेक को प्रतिबिंबित करता है — सामान्य अक्षर क्लस्टर, शब्द दोहराते हैं, व्याकरण अनुक्रमों को बाधित करता है।
संपीड़न एंट्रॉपी को हरा नहीं सकता
संपीड़न अनुपात: H / (ब्लॉक कोड लंबाई)। हमारे उदाहरण के लिए: 1.75/2.0 = 0.875 — 87.5% दक्षता।
क्या आप आगे संपीड़ित कर सकते हैं? केवल संदर्भ का उपयोग करके: यदि आप प्रतीकों की जोड़ियों या ट्रिपल को एक साथ एन्कोड करते हैं, तो संयुक्त एंट्रॉपी H(X,Y) 2·H(X) से कम हो सकता है सांख्यिकीय निर्भरता के कारण। यह n-ग्राम के लिए noiseless कोडिंग प्रमेय का विस्तार है।