हफ़मैन कोड
निश्चित लंबाई वाला कोड
बचत
एंट्रॉपी

प्रतीक गिनती कोड बिट कुल बिट

हफ़मैन कोडिंग के बारे में अधिक जानकारी

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

र जैसा आम अक्षर उतने ही बिट क्यों ले जितने ङ जैसा दुर्लभ अक्षर? हफ़मैन कोडिंग बार-बार आने वाले प्रतीकों को छोटे कोड और दुर्लभ प्रतीकों को लंबे कोड देती है, और यह सबसे अच्छे संभव तरीके से करती है। कोई टेक्स्ट टाइप करें या कोई उदाहरण चुनें, और उसका हफ़मैन ट्री एक-एक चरण में बनाएँ: दो सबसे हल्के ट्री एक नए नोड के नीचे जुड़ते हैं, बार-बार, जब तक कि एक ही ट्री न बचे। फिर ऊपर से हर रास्ता एक कोड बनाता है, और आप हर प्रतीक को एनकोड किए गए बिटों में देख सकते हैं। कोई टेक्स्ट टाइप करें या कोई उदाहरण चुनें। हर प्रतीक शुरू में अपनी गिनती के साथ एक पत्ती होता है। निर्माण को चरण-दर-चरण चलाएँ: हर चरण दो सबसे हल्के ट्री को एक नए नोड के नीचे जोड़ता है, जिसका भार उन दोनों का योग होता है, जब तक कि एक ही ट्री न बचे। फिर ऊपर से किसी पत्ती तक का रास्ता उसका कोड देता है, बाएँ के लिए 0 और दाएँ के लिए 1। किसी एक प्रतीक को देखने के लिए किसी पत्ती, पंक्ति या बिटों के किसी हिस्से पर क्लिक करें, और कुल योग की तुलना निश्चित लंबाई वाले कोड और एंट्रॉपी से करें।

यह कैसे काम करता है

  1. कोई टेक्स्ट टाइप या पेस्ट करें, या ABRACADABRA या MISSISSIPPI RIVER जैसा कोई उदाहरण चुनें।
  2. “अगला चरण” से निर्माण को चरण-दर-चरण चलाएँ, या “चलाएँ” दबाएँ: हर चरण दो सबसे हल्के ट्री को एक ऐसे नोड के नीचे जोड़ता है जिसका भार उनका योग होता है।
  3. ट्री पूरा होने पर किसी एक प्रतीक को देखने के लिए किसी पत्ती, तालिका की किसी पंक्ति या बिटों के किसी हिस्से पर क्लिक करें, और टाइलों में कुल योगों की तुलना करें।

ट्री कैसे बनता है

गिनें कि हर प्रतीक कितनी बार आता है, और हर प्रतीक को एक अकेली पत्ती वाला ट्री बना दें, जिसका भार उसकी गिनती हो। फिर एक सरल चरण दोहराएँ: सबसे कम भार वाले दो ट्री लें और उन्हें एक नए नोड के नीचे टाँग दें, जिसका भार उनका योग हो। हर चरण में एक ट्री कम हो जाता है, इसलिए n प्रतीकों के लिए n − 1 चरणों के बाद एक ही ट्री बचता है। दुर्लभ प्रतीक पहले जुड़े थे और गहराई में बैठते हैं; आम प्रतीक देर से जुड़े थे और ऊपर के पास बैठते हैं।

कोड पढ़ना

ऊपर से नीचे चलें: बाईं ओर का हर कदम एक 0 जोड़ता है, दाईं ओर का हर कदम एक 1। किसी पत्ती तक का रास्ता ही उस प्रतीक का कोड है। चूँकि प्रतीक केवल पत्तियों पर होते हैं, कोई भी कोड किसी दूसरे कोड की शुरुआत नहीं होता, इसलिए बिटों की किसी भी शृंखला को बिना किसी विभाजक के डीकोड किया जा सकता है: बिटों के साथ ट्री में नीचे चलें, और जब भी किसी पत्ती पर पहुँचें, उसका प्रतीक लिखें और फिर ऊपर से शुरू करें। ABRACADABRA के लिए हफ़मैन को 23 बिट चाहिए, जबकि प्रति अक्षर 3 बिट वाले निश्चित कोड को 33।

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

हफ़मैन कोड सबसे अच्छा संभव क्यों है?

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

प्रीफ़िक्स कोड क्या है?

ऐसा कोड जिसमें कोई भी कोड शब्द किसी दूसरे कोड शब्द की शुरुआत नहीं होता, जैसे 0, 10, 110 और 111। इस गुण के कारण डिकोडर बिटों की धारा को बिना विभाजकों के पढ़ सकता है, क्योंकि उसे हमेशा पता रहता है कि कोई कोड शब्द कहाँ खत्म होता है। हर हफ़मैन कोड एक प्रीफ़िक्स कोड है: प्रतीक केवल ट्री की पत्तियों पर होते हैं।

क्या हफ़मैन ट्री अद्वितीय होता है?

पूरी तरह नहीं: जब दो ट्री का भार बराबर हो, तो किसी को भी पहले लिया जा सकता है, और बाएँ-दाएँ को आपस में बदला जा सकता है। अलग-अलग विकल्प अलग-अलग कोड देते हैं, पर बिटों की कुल संख्या हमेशा वही रहती है। यह बिल्डर बराबरी की स्थिति को हमेशा एक ही तरह से सुलझाता है, इसलिए एक टेक्स्ट से हमेशा एक ही ट्री बनता है।

हफ़मैन एंट्रॉपी के कितने करीब पहुँचता है?

औसत कोड लंबाई कम से कम एंट्रॉपी के बराबर होती है और उससे एक बिट से कम ऊपर। यह एंट्रॉपी के बराबर तब होती है जब हर प्रायिकता आधे की कोई घात हो, जैसे आधी होती गिनतियों वाले उदाहरण में। अंकगणितीय कोडिंग और आधुनिक रेंज कोडर पूरे बिट की सीमा से बचते हैं और और भी करीब पहुँचते हैं।

क्या मेरा टेक्स्ट कहीं भेजा जाता है?

नहीं। ट्री और कोड आपके ब्राउज़र में ही निकाले जाते हैं, और आपका टेक्स्ट इसी ब्राउज़र के लोकल स्टोरेज में रहता है।

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

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

एडिटर पर जाएँ