कैनोनिकल हफ़मैन कोड: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 28: Line 28:


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


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


विहित कोडवर्ड पर और परिप्रेक्ष्य यह है कि वह निश्चित श्रृंखला के द्विआधारी प्रतिनिधित्व में [[मूलांक बिंदु]] (बाइनरी दशमलव बिंदु) से आगे के अंक हैं। विशेष रूप से, मान लीजिए कि कोडवर्ड की लंबाई l है<sub>1</sub> ... एल<sub>n</sub>. फिर प्रतीक i के लिए विहित कोडवर्ड पहला l है<sub>i</sub> के बाइनरी प्रतिनिधित्व में मूलांक बिंदु से आगे के बाइनरी अंक
विहित कोडवर्ड पर और परिप्रेक्ष्य यह है कि वह निश्चित श्रृंखला के द्विआधारी प्रतिनिधित्व में [[मूलांक बिंदु]] (बाइनरी दशमलव बिंदु) से आगे के अंक हैं। विशेष रूप से, मान लीजिए कि कोडवर्ड की लंबाई ''l''<sub>1</sub> ... ''l''<sub>n</sub> है‚ फिर प्रतीक i के लिए विहित कोडवर्ड पहला ''l''<sub>i</sub> है के बाइनरी प्रतिनिधित्व में मूलांक बिंदु से आगे के बाइनरी अंक हैंः


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


==कोडबुक को एन्कोड करना==
==कोडबुक को एन्कोड करना==
Line 55: Line 56:
  डी = 100
  डी = 100


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


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


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


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


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


  ए = 10 (कोड मान: 2 दशमलव, बिट्स: 2)
  ए = 10 (कोड मान: 2 दशमलव, बिट्स: 2)
Line 70: Line 71:
  डी = 111 (कोड मान: 7 दशमलव, बिट्स: 3)
  डी = 111 (कोड मान: 7 दशमलव, बिट्स: 3)


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


  2, 1, 3, 3
  2, 1, 3, 3


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


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


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


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


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


  0, 0, 2, 2, 2, 0, ... , 2, ...
  0, 0, 2, 2, 2, 0, ... , 2, ...
Line 90: Line 91:
  (0,4), ('सी','ओ','डी','ई')
  (0,4), ('सी','ओ','डी','ई')


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


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


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


  'एल्गोरिदम' गणना हफ़मैन कोड 'है'
  '<nowiki/>'''एल्गोरिदम'''<nowiki/>' गणना हफ़मैन कोड ''''है'''<nowiki/>'
  'इनपुट:' संदेश समूह ((संदेश, संभाव्यता) का समूह)।
  ''''इनपुट:'''<nowiki/>' संदेश समूह ((संदेश, संभाव्यता) का समूह)।
          आधारित।
      आधारित।
  'आउटपुट:' कोड संयोजन ((संदेश, कोड) का समूह)।
  'आउटपुट:' कोड संयोजन ((संदेश, कोड) का समूह)।
    
    
  1- संभाव्यता कम करके संदेश समूह को क्रमबद्ध करें।
  1- संभाव्यता कम करके संदेश समूह को क्रमबद्ध करें।
  2- एन संदेश समूह का कार्डिनल है (विभिन्न की संख्या)।
  2- एन संदेश समूह का कार्डिनल है (विभिन्न की संख्या)।
    संदेश)।
  संदेश)।
  3- पूर्णांक की गणना करें {{tmath|n_0}} जैसे कि {{tmath|2 \le n_0 \le D}} और {{tmath|(N - n_0)/(D - 1)}} पूर्णांक है.
  3- पूर्णांक की गणना करें {{tmath|n_0}} जैसे कि {{tmath|2 \le n_0 \le D}} और {{tmath|(N - n_0)/(D - 1)}} पूर्णांक है.
  4- का चयन करें {{tmath|n_0}} कम से कम संभावित संदेश, और उन्हें प्रत्येक को असाइन करें
  4- का चयन करें {{tmath|n_0}} कम से कम संभावित संदेश, और उन्हें प्रत्येक को असाइन करें
    नंबर कोड।
  नंबर कोड।
  5- चयनित संदेशों को समग्र संदेश द्वारा प्रतिस्थापित करें
  5- चयनित संदेशों को समग्र संदेश द्वारा प्रतिस्थापित करें
    उनकी संभावना, और इसे पुनः क्रमित करें।
  उनकी संभावना, और इसे पुनः क्रमित करें।
  6- जब से अधिक संदेश हों, तब 8 से चरण अपनाएँ।
  6- जब से अधिक संदेश हों, तब 8 से चरण अपनाएँ।
  7- डी न्यूनतम संभावित संदेशों का चयन करें, और उन्हें प्रत्येक को असाइन करें
  7- डी न्यूनतम संभावित संदेशों का चयन करें, और उन्हें प्रत्येक को असाइन करें
      नंबर कोड।
    नंबर कोड।
  8- चयनित संदेशों को समग्र संदेश से प्रतिस्थापित करें
  8- चयनित संदेशों को समग्र संदेश से प्रतिस्थापित करें
      उनकी संभाव्यता का योग करें, और इसे पुनः क्रमित करें।
    उनकी संभाव्यता का योग करें, और इसे पुनः क्रमित करें।
  9- प्रत्येक संदेश का कोड के संयोजन द्वारा दिया गया है
  9- प्रत्येक संदेश का कोड के संयोजन द्वारा दिया गया है
    जिस समुच्चय में उन्हें डाला गया है उसके कोड अंक।
  जिस समुच्चय में उन्हें डाला गया है उसके कोड अंक।
<ref>This algorithm described in:
<ref>This algorithm described in:
"A Method for the Construction of Minimum-Redundancy Codes"
"A Method for the Construction of Minimum-Redundancy Codes"

Revision as of 14:56, 16 July 2023

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

प्रेरणा

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

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

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

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

एल्गोरिदम

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

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

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

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

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

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

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

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

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

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

यह परिप्रेक्ष्य क्राफ्ट की असमानता के आलोक में विशेष रूप से उपयोगी है, जो कहता है कि उपरोक्त योग सदैव 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), ('सी','ओ','डी','ई')

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

छद्मकोड

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

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

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

[1]

[2]

संदर्भ

  1. ↑ This algorithm described in: "A Method for the Construction of Minimum-Redundancy Codes" David A. Huffman, Proceedings of the I.R.E.
  2. ↑ Managing Gigabytes: book with an implementation of canonical huffman codes for word dictionaries.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=कैनोनिकल_हफ़मैन_कोड&oldid=221963’