हफ़मैन कोडिंग की व्याख्या

कंप्यूटर आमतौर पर हर अक्षर को उतने ही बिटों में रखते हैं, साधारण ASCII में आठ। यह सरल है पर फ़िज़ूलखर्ची भी, क्योंकि कुछ अक्षर बाकियों से कहीं ज़्यादा आम होते हैं। 1951 में एक छात्र ने हर प्रतीक को उसकी अपनी लंबाई का कोड देने का सबसे अच्छा तरीका खोजा, बार-बार आने वाले प्रतीकों को छोटा और दुर्लभ प्रतीकों को लंबा, ऐसी सरल रचना के साथ जो कुछ ही पंक्तियों में समा जाती है। आज हफ़मैन कोडिंग लगभग हर उस कम्प्रेस की हुई फ़ाइल, तस्वीर और ध्वनि के भीतर है जिसे आप खोलते हैं।

एक हफ़मैन ट्री, जिसकी पत्तियाँ ABRACADABRA के अक्षर हैं, किनारों पर 0 और 1 लिखे हैं, और A का छोटा कोड हाइलाइट किया गया है
एक हफ़मैन ट्री, जिसकी पत्तियाँ ABRACADABRA के अक्षर हैं, किनारों पर 0 और 1 लिखे हैं, और A का छोटा कोड हाइलाइट किया गया है

आम प्रतीकों के लिए छोटे कोड

मोर्स कोड 1830 के दशक में ही इस विचार का इस्तेमाल करता था: अंग्रेज़ी का सबसे आम अक्षर E एक अकेला डॉट है, जबकि Q डैश डैश डॉट डैश। ऐसा कोड तब समय और जगह बचाता है जब कुछ प्रतीक दूसरों से ज़्यादा बार आते हैं। लेकिन अलग-अलग लंबाइयाँ एक समस्या खड़ी करती हैं जिसे मोर्स ने विरामों से सुलझाया: आप कैसे जानें कि एक कोड कहाँ खत्म होता है और अगला कहाँ शुरू? और कुल योग को जितना हो सके छोटा रखने के लिए हर प्रतीक को कौन-सी लंबाई मिलनी चाहिए?

प्रीफ़िक्स कोड

पहली समस्या गायब हो जाती है अगर कोई कोड किसी दूसरे कोड की शुरुआत न हो। A = 0, B = 10, C = 110 और D = 111 कोडों के साथ, बिट 0101100 को केवल A B C A ही पढ़ा जा सकता है: जैसे ही अब तक पढ़े गए बिट कोई कोड बनाते हैं, वह कोड पूरा हो जाता है। ऐसे प्रीफ़िक्स कोड ठीक उन बाइनरी ट्री से मेल खाते हैं जिनकी पत्तियों पर प्रतीक होते हैं, जहाँ हर बाईं शाखा 0 और हर दाईं शाखा 1 के लिए होती है। कोड चुनना ट्री चुनना है।

हफ़मैन की रचना

हर प्रतीक के लिए एक पत्ती से शुरू करें, जिसका भार यह हो कि वह प्रतीक कितनी बार आता है। दो सबसे हल्के ट्री लें और उन्हें एक नए नोड के नीचे जोड़ें जिसका भार उनका योग हो, और यह तब तक दोहराएँ जब तक एक ही ट्री न बचे। बस यही पूरा एल्गोरिदम है। दुर्लभ प्रतीक पहले जुड़ते हैं और ट्री में गहराई पर पहुँचते हैं, लंबे कोडों के साथ; आम प्रतीक आखिर में जुड़ते हैं और ऊपर के पास रहते हैं, छोटे कोडों के साथ। प्रायोरिटी क्यू के साथ n प्रतीकों के लिए इसमें n log n के अनुपात में समय लगता है।

यह इष्टतम क्यों है

सबसे अच्छे संभव ट्री में दो सबसे दुर्लभ प्रतीकों को हमेशा सबसे गहरे स्तर पर सहोदरों की तरह रखा जा सकता है: वहाँ जो भी हो, उससे उनकी अदला-बदली कुल योग को केवल छोटा ही कर सकती है। उन्हें उनके संयुक्त भार वाले एक प्रतीक में जोड़ दें, तो बाकी वही समस्या रह जाती है जिसमें एक प्रतीक कम है, इसलिए यह ग्रीडी चरण कभी भी सबसे अच्छे उत्तर का रास्ता बंद नहीं करता। इस्तेमाल हुए बिटों की कुल संख्या सभी भीतरी नोडों के भारों के योग के बराबर होती है, जिसे जोड़ने की प्रक्रिया जितना हो सके छोटा रखती है।

परीक्षा के बजाय एक टर्म पेपर

1951 में MIT के स्नातकोत्तर छात्र डेविड हफ़मैन ने रॉबर्ट फ़ानो का सूचना सिद्धांत का कोर्स लिया। फ़ानो ने अपने छात्रों को विकल्प दिया: अंतिम परीक्षा दें या सबसे कुशल बाइनरी कोड खोजने पर एक टर्म पेपर लिखें। हफ़मैन पेपर से लगभग हार मान चुके थे, तभी उन्होंने देखा कि ट्री को नीचे से ऊपर की ओर बनाना, न कि शैनन–फ़ानो विधि की तरह ऊपर से नीचे बाँटना, हमेशा सबसे अच्छा परिणाम देता है। उन्होंने इसे 1952 में प्रकाशित किया; छात्र की विधि उस विधि से बेहतर निकली जो उनके प्रोफ़ेसर ने क्लॉड शैनन के साथ तैयार की थी।

डेविड हफ़मैन, यूसी सांता क्रूज़ में प्रोफ़ेसर रहते हुए खींची गई तस्वीर। 1951 में MIT में स्नातकोत्तर छात्र के रूप में उन्होंने रॉबर्ट फ़ानो के पाठ्यक्रम के एक टर्म पेपर में अपना इष्टतम कोड खोजा।
डेविड हफ़मैन, यूसी सांता क्रूज़ में प्रोफ़ेसर रहते हुए खींची गई तस्वीर। 1951 में MIT में स्नातकोत्तर छात्र के रूप में उन्होंने रॉबर्ट फ़ानो के पाठ्यक्रम के एक टर्म पेपर में अपना इष्टतम कोड खोजा।
क्लॉड शैनन, जिन्होंने 1948 में बेल लैब्स में यह स्पष्ट किया कि किसी संदेश में कितनी सूचना होती है, और उसे बिट्स में मापा।
क्लॉड शैनन, जिन्होंने 1948 में बेल लैब्स में यह स्पष्ट किया कि किसी संदेश में कितनी सूचना होती है, और उसे बिट्स में मापा।

एंट्रॉपी के करीब

क्लॉड शैनन ने दिखाया कि कोई भी कोड औसतन स्रोत की एंट्रॉपी से कम बिट प्रति प्रतीक इस्तेमाल नहीं कर सकता। हफ़मैन कोड ठीक तब एंट्रॉपी तक पहुँचता है जब हर प्रायिकता आधे की कोई घात हो, और कभी भी उससे प्रति प्रतीक पूरा एक बिट ऊपर नहीं होता। यह अंतर तब मायने रखता है जब कोई एक प्रतीक बहुत आम हो: 99% हिस्से वाले प्रतीक को भी कम से कम एक पूरा बिट चाहिए, जबकि उसमें केवल लगभग 0.015 बिट सूचना होती है। अंकगणितीय कोडिंग और नए कम्प्रेसरों की असममित संख्या प्रणालियाँ (ANS) इस सीमा से बचती हैं।

हर जगह हफ़मैन कोड

हफ़मैन कोडिंग शायद ही कभी अकेले इस्तेमाल होती है, पर कई फ़ॉर्मैट का अंतिम चरण बनती है। Deflate, जो ZIP, gzip और PNG के भीतर है, पहले दोहरावों को रेफ़रेंस से बदलता है और फिर परिणाम को हफ़मैन कोड से लिखता है। JPEG इनका इस्तेमाल तस्वीर के रूपांतरण के बाद बची संख्याओं के लिए करता है, MP3 अपने ऑडियो डेटा के लिए, और फ़ैक्स मशीनें काले और सफ़ेद रनों की लंबाइयों के लिए। फ़ॉर्मैट आमतौर पर एक कैनोनिकल हफ़मैन कोड भेजते हैं, जिसमें केवल कोड लंबाइयाँ संग्रहीत करनी होती हैं, क्योंकि कोड खुद उनसे दोबारा बनाए जा सकते हैं।

खुद आज़माएँ

हफ़मैन कोडिंग बिल्डर खोलें और ABRACADABRA, MISSISSIPPI RIVER, अपने खुद के किसी वाक्य या किसी भी दूसरे टेक्स्ट का ट्री एक-एक चरण में बनाएँ। हर चरण में दो सबसे हल्के ट्री को जुड़ते देखें, किसी पत्ती का कोड देखने के लिए उस पर क्लिक करें, किसी प्रतीक को एनकोड किए गए बिटों में देखें, और कुल योग की तुलना निश्चित लंबाई वाले कोड, UTF-8 और एंट्रॉपी से करें।

अक्सर पूछे जाने वाले प्रश्न

हफ़मैन और शैनन–फ़ानो कोडिंग में क्या अंतर है?

शैनन–फ़ानो कोडिंग ट्री को ऊपर से बनाती है, प्रतीकों को बार-बार लगभग बराबर भार वाले दो समूहों में बाँटकर। यह अक्सर अच्छी होती है पर हमेशा इष्टतम नहीं। हफ़मैन दो सबसे हल्के ट्री को जोड़कर ट्री को नीचे से बनाता है, और हमेशा सबसे छोटा संभव प्रीफ़िक्स कोड देता है।

क्या डिकोडर को ट्री चाहिए?

हाँ, उसे वही कोड चाहिए। इसलिए कम्प्रेस की हुई फ़ाइलें उसे संग्रहीत करती हैं, आमतौर पर कैनोनिकल कोड की कोड लंबाइयों की सूची के रूप में, जिसमें केवल कुछ दर्जन बाइट लगते हैं। छोटे टेक्स्ट के लिए यह अतिरिक्त भार बचत से ज़्यादा हो सकता है; बिल्डर केवल एनकोड किए गए बिट गिनता है।

क्या हफ़मैन कोडिंग किसी फ़ाइल को बड़ा कर सकती है?

एनकोड किए गए प्रतीक कभी भी उन्हीं प्रतीकों के निश्चित लंबाई वाले कोड से ज़्यादा बिट नहीं लेते। लेकिन कोड तालिका भी संग्रहीत करनी पड़ती है, इसलिए बहुत छोटे या लगभग रैंडम डेटा के लिए परिणाम मूल से थोड़ा बड़ा हो सकता है।

क्राफ़्ट असमिका क्या कहती है?

यह कि कोड लंबाइयों l₁, l₂, … वाला प्रीफ़िक्स कोड ठीक तब मौजूद होता है जब सभी प्रतीकों पर 2 की घात −l का योग अधिकतम 1 हो। किसी पूर्ण ट्री के लिए, जैसे कम से कम दो प्रतीकों वाला हर हफ़मैन ट्री, यह योग ठीक 1 होता है।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

हफ़मैन कोडिंग बिल्डर खोलें