कैनोनिकल हफ़मैन कोड

कंप्यूटर विज्ञान और सूचना सिद्धांत में, कैनोनिकल हफ़मैन कोड अद्वितीय गुणों वाला एक विशेष प्रकार का हफ़मैन कोड है जो इसे बहुत ही संक्षिप्त तरीके से वर्णित करने की अनुमति देता है। कोड ट्री की संरचना को स्पष्ट रूप से संग्रहीत करने के बजाय, कैनोनिकल हफ़मैन कोड को इस तरह से ऑर्डर किया जाता है कि यह केवल कोडवर्ड की लंबाई को संग्रहीत करने के लिए पर्याप्त है, जो कोडबुक के ओवरहेड को कम करता है।

प्रेरणा

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

हफ़मैन कोड जैसी प्रतीक कोड योजना को डीकंप्रेस करने के लिए, स्रोत डेटा को संपीड़ित करने के लिए उपयोग किए जाने वाले एन्कोडिंग एल्गोरिदम को वही मॉडल डिकोडिंग एल्गोरिदम को प्रदान किया जाना चाहिए ताकि वह एन्कोडेड डेटा को डीकंप्रेस करने के लिए इसका उपयोग कर सके। मानक हफ़मैन कोडिंग में यह मॉडल चर-लंबाई कोड के एक पेड़ का रूप लेता है, जिसमें सबसे अधिक बार आने वाले प्रतीक संरचना के शीर्ष पर स्थित होते हैं और सबसे कम बिट्स द्वारा दर्शाए जाते हैं।

हालाँकि, यह कोड ट्री कोडिंग योजना के कार्यान्वयन में दो महत्वपूर्ण अक्षमताओं का परिचय देता है। सबसे पहले, पेड़ के प्रत्येक नोड को या तो उसके चाइल्ड नोड्स या उस प्रतीक का संदर्भ संग्रहीत करना चाहिए जिसका वह प्रतिनिधित्व करता है। यह मेमोरी उपयोग में महंगा है और यदि स्रोत डेटा में अद्वितीय प्रतीकों का उच्च अनुपात है तो कोड ट्री का आकार समग्र एन्कोडेड डेटा की एक महत्वपूर्ण मात्रा के लिए जिम्मेदार हो सकता है। दूसरे, पेड़ को पार करना कम्प्यूटेशनल रूप से महंगा है, क्योंकि इसमें एल्गोरिदम को मेमोरी में संरचना के माध्यम से यादृच्छिक रूप से कूदने की आवश्यकता होती है क्योंकि एन्कोडेड डेटा में प्रत्येक बिट को पढ़ा जाता है।

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

एल्गोरिदम

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

ए = 11
बी = 0
सी = 101
डी = 100

यहां अक्षर A को 2 अंश , B को 1 बिट, और C तथा D दोनों को 3 बिट दिए गए हैं। कोड को कैनोनिकल हफ़मैन कोड बनाने के लिए, कोडों को पुनः क्रमांकित किया जाता है। बिट की लंबाई समान रहती है, कोड बुक को पहले कोडवर्ड की लंबाई के आधार पर और दूसरे अक्षर के वर्णमाला मूल्य (कंप्यूटर विज्ञान) के आधार पर क्रमबद्ध किया जाता है:

बी = 0
ए = 11
सी = 101
डी = 100

निम्नलिखित कलन विधि का उपयोग करके प्रत्येक मौजूदा कोड को समान लंबाई के एक नए कोड से बदल दिया जाता है:

• सूची में पहले प्रतीक को एक कोडवर्ड सौंपा जाता है जिसकी लंबाई प्रतीक के मूल कोडवर्ड के समान होती है लेकिन सभी शून्य होते हैं। यह प्रायः एकल शून्य ('0') होगा।
• प्रत्येक बाद वाले प्रतीक को अनुक्रम में अगला बाइनरी अंक प्रणाली नंबर सौंपा गया है, यह सुनिश्चित करते हुए कि निम्नलिखित कोड हमेशा मूल्य में अधिक हैं।
• जब आप किसी लंबे कोडवर्ड तक पहुंच जाएं तो बढ़ाते-बढ़ाते शून्य तब तक लगाएं जब तक नए कोडवर्ड की लंबाई पुराने कोडवर्ड की लंबाई के बराबर न हो जाए. इसे एक तार्किक बदलाव के रूप में सोचा जा सकता है।

इन तीन नियमों का पालन करके, उत्पादित कोड बुक का विहित संस्करण होगा:

बी = 0
ए = 10
सी = 110
डी = 111

एक भिन्नात्मक बाइनरी संख्या के रूप में

विहित कोडवर्ड पर एक और परिप्रेक्ष्य यह है कि वे एक निश्चित श्रृंखला के द्विआधारी प्रतिनिधित्व में मूलांक बिंदु (बाइनरी दशमलव बिंदु) से आगे के अंक हैं। विशेष रूप से, मान लीजिए कि कोडवर्ड की लंबाई l है₁ ... एल_n. फिर प्रतीक i के लिए विहित कोडवर्ड पहला l है_i के बाइनरी प्रतिनिधित्व में मूलांक बिंदु से आगे के बाइनरी अंक

$\sum _{j=1}^{i-1}2^{-l_{j}}.$ यह परिप्रेक्ष्य क्राफ्ट की असमानता के आलोक में विशेष रूप से उपयोगी है, जो कहता है कि उपरोक्त योग हमेशा 1 से कम या उसके बराबर होगा (क्योंकि लंबाई एक उपसर्ग मुक्त कोड से आती है)। इससे पता चलता है कि उपरोक्त एल्गोरिदम में एक जोड़ने से कभी भी अतिप्रवाह नहीं होता है और एक ऐसा कोडवर्ड बनता है जो इच्छित से अधिक लंबा होता है।

कोडबुक को एन्कोड करना

विहित हफ़मैन वृक्ष का लाभ यह है कि इसे एक मनमाने वृक्ष की तुलना में कम बिट्स में एन्कोड किया जा सकता है।

आइए हम अपनी मूल हफ़मैन कोडबुक लें:

ए = 11
बी = 0
सी = 101
डी = 100

ऐसे कई तरीके हैं जिनसे हम इस हफ़मैन पेड़ को एनकोड कर सकते हैं। उदाहरण के लिए, हम प्रत्येक प्रतीक के बाद बिट्स की संख्या और कोड लिख सकते हैं:

('ए',2,11), ('बी',1,0), ('सी',3,101), ('डी',3,100)

चूँकि हम प्रतीकों को अनुक्रमिक वर्णमाला क्रम में सूचीबद्ध कर रहे हैं, हम केवल बिट्स और कोड की संख्या सूचीबद्ध करके प्रतीकों को छोड़ सकते हैं:

(2,11), (1,0), (3,101), (3,100)

हमारे कैनोनिकल संस्करण के साथ हमें यह ज्ञान है कि प्रतीक अनुक्रमिक वर्णमाला क्रम में हैं और कि बाद का कोड हमेशा पहले वाले की तुलना में मूल्य में अधिक होगा। संचारित करने के लिए बचे एकमात्र भाग प्रत्येक प्रतीक के लिए बिट-लंबाई (बिट्स की संख्या) हैं। ध्यान दें कि हमारे विहित हफ़मैन पेड़ में लंबी बिट लंबाई के लिए हमेशा उच्च मान होते हैं और समान बिट लंबाई (सी और डी) के किसी भी प्रतीक में उच्च प्रतीकों के लिए उच्च कोड मान होते हैं:

ए = 10 (कोड मान: 2 दशमलव, बिट्स: 2)
बी = 0 (कोड मान: 0 दशमलव, बिट्स: 1)
सी = 110 (कोड मान: 6 दशमलव, बिट्स: 3)
डी = 111 (कोड मान: 7 दशमलव, बिट्स: 3)

चूँकि दो-तिहाई बाधाएँ ज्ञात हैं, प्रत्येक प्रतीक के लिए केवल बिट्स की संख्या प्रसारित करने की आवश्यकता है:

2, 1, 3, 3

कैनोनिकल हफ़मैन एल्गोरिथ्म के ज्ञान के साथ, केवल बिट-लंबाई से संपूर्ण तालिका (प्रतीक और कोड मान) को फिर से बनाना संभव है। अप्रयुक्त प्रतीकों को आम तौर पर शून्य बिट लंबाई के रूप में प्रसारित किया जाता है।

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

(1,1,2), ('बी','ए','सी','डी')

इसका मतलब यह है कि पहला प्रतीक बी लंबाई 1 का है, फिर ए लंबाई 2 का है, और शेष 3 का है। चूंकि प्रतीकों को बिट-लंबाई के अनुसार क्रमबद्ध किया जाता है, हम कुशलतापूर्वक कोडबुक का पुनर्निर्माण कर सकते हैं। पुनर्निर्माण का वर्णन करने वाला एक छद्म कोड अगले भाग में प्रस्तुत किया गया है।

इस प्रकार की एन्कोडिंग तब फायदेमंद होती है जब वर्णमाला में केवल कुछ प्रतीकों को संपीड़ित किया जा रहा हो। उदाहरण के लिए, मान लीजिए कि कोडबुक में केवल 4 अक्षर सी, ओ, डी और ई हैं, प्रत्येक की लंबाई 2 है। ओ अक्षर का प्रतिनिधित्व करने के लिए इसका उपयोग करें पिछली विधि में, हमें या तो बहुत सारे शून्य जोड़ने होंगे:

0, 0, 2, 2, 2, 0, ... , 2, ...

या रिकॉर्ड करें कि हमने कौन से 4 अक्षरों का उपयोग किया है। प्रत्येक तरीका विवरण को इससे अधिक लंबा बनाता है:

(0,4), ('सी','ओ','डी','ई')

JPEG फ़ाइल इंटरचेंज प्रारूप एन्कोडिंग की इस पद्धति का उपयोग करता है, क्योंकि 8 बिट वर्णमाला में से अधिकतम केवल 162 प्रतीक, जिसका आकार 256 है, कोडबुक में होंगे।

छद्मकोड

बिट-लंबाई के आधार पर क्रमबद्ध प्रतीकों की एक सूची को देखते हुए, निम्नलिखित छद्मकोड एक कैनोनिकल हफ़मैन कोड बुक प्रिंट करेगा:

कोड := 0
'जबकि' अधिक प्रतीक 'करते हैं'
    प्रिंट प्रतीक, कोड
    कोड := (कोड + 1) << ((अगले प्रतीक की बिट लंबाई) - (वर्तमान बिट लंबाई))

'एल्गोरिदम' गणना हफ़मैन कोड 'है'
    'इनपुट:' संदेश समूह ((संदेश, संभाव्यता) का सेट)।
                  आधारित।
    'आउटपुट:' कोड संयोजन ((संदेश, कोड) का सेट)।
 
    1- संभाव्यता कम करके संदेश समूह को क्रमबद्ध करें।
    2- एन संदेश समूह का कार्डिनल है (विभिन्न की संख्या)।
       संदेश)।
    3- पूर्णांक की गणना करें $n_{0}$ जैसे कि $2\leq n_{0}\leq D$ और $(N-n_{0})/(D-1)$ पूर्णांक है.
    4- का चयन करें $n_{0}$ कम से कम संभावित संदेश, और उन्हें प्रत्येक को असाइन करें
       नंबर कोड।
    5- चयनित संदेशों को एक समग्र संदेश द्वारा प्रतिस्थापित करें
       उनकी संभावना, और इसे पुनः क्रमित करें।
    6- जब एक से अधिक संदेश हों, तो 8 से चरण अपनाएँ।
    7- डी न्यूनतम संभावित संदेशों का चयन करें, और उन्हें प्रत्येक को असाइन करें
          नंबर कोड।
    8- चयनित संदेशों को एक समग्र संदेश से प्रतिस्थापित करें
          उनकी संभाव्यता का योग करें, और इसे पुनः क्रमित करें।
    9- प्रत्येक संदेश का कोड के संयोजन द्वारा दिया गया है
       जिस समुच्चय में उन्हें डाला गया है उसके कोड अंक।