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

From Vigyanwiki
No edit summary
No edit summary
 
(10 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[कंप्यूटर विज्ञान]] और [[सूचना सिद्धांत]] में, '''कैनोनिकल [[हफ़मैन कोड]]''' अद्वितीय गुणों वाला एक विशेष प्रकार का हफ़मैन कोड है जो इसे बहुत ही संक्षिप्त तरीके से वर्णित करने की अनुमति देता है। कोड ट्री की संरचना को स्पष्ट रूप से संग्रहीत करने के अतिरिक्त, कैनोनिकल हफ़मैन कोड को इस तरह से ऑर्डर किया जाता है कि यह केवल कोडवर्ड की लंबाई को संग्रहीत करने के लिए पर्याप्त है, जो कोडबुक के ओवरहेड को कम करता है।
[[कंप्यूटर विज्ञान]] और [[सूचना सिद्धांत]] में, '''कैनोनिकल [[हफ़मैन कोड]]''' अद्वितीय गुणों वाला विशेष प्रकार का हफ़मैन कोड है जो इसे बहुत ही संक्षिप्त तरीके से वर्णित करने की अनुमति देता है। इस प्रकार कोड ट्री की संरचना को स्पष्ट रूप से संग्रहीत करने के अतिरिक्त, कैनोनिकल हफ़मैन कोड को इस तरह से आदेशित किया जाता है कि यह केवल कोडवर्ड की लंबाई को संग्रहीत करने के लिए पर्याप्त है, जो कोडबुक के ओवरहेड को कम करता है।


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


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


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


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


==एल्गोरिदम==
==एल्गोरिदम==
सामान्य हफ़मैन कोडिंग एल्गोरिदम [[वर्णमाला]] के प्रत्येक प्रतीक के लिए एक चर लंबाई कोड निर्दिष्ट करता है। अधिक बार उपयोग किए जाने वाले प्रतीकों को एक छोटा कोड सौंपा जाएगा। उदाहरण के लिए, मान लें कि हमारे पास निम्नलिखित गैर-विहित कोडबुक है:
सामान्य हफ़मैन कोडिंग एल्गोरिदम [[वर्णमाला]] के प्रत्येक प्रतीक के लिए चर लंबाई कोड निर्दिष्ट करता है। इस प्रकार अधिक बार उपयोग किए जाने वाले प्रतीकों को छोटा कोड सौंपा जाएगा। उदाहरण के लिए, मान लें कि हमारे पास निम्नलिखित गैर-विहित कोडबुक है:
A = 11
B = 0
C = 101
D = 100
यहां अक्षर A को 2 [[ अंश |बिट]] , B को 1 बिट, और C तथा D दोनों को 3 बिट दिए गए हैं। कोड को कैनोनिकल हफ़मैन कोड बनाने के लिए, कोडों को पुनः क्रमांकित किया जाता है। इस प्रकार बिट की लंबाई समान रहती है, कोड बुक को पहले कोडवर्ड की लंबाई के आधार पर और दूसरे अक्षर के वर्णमाला [[मूल्य (कंप्यूटर विज्ञान)]] के आधार पर क्रमबद्ध किया जाता है:
B = 0
A = 11
C = 101
D = 100
निम्नलिखित [[ कलन विधि |एल्गोरिथम]] का उपयोग करके प्रत्येक उपस्तिथा कोड को समान लंबाई के नए कोड से बदल दिया जाता है:


ए = 11
* सूची में पहले प्रतीक को कोडवर्ड सौंपा जाता है जिसकी लंबाई प्रतीक के मूल कोडवर्ड के समान होती है किन्तु सभी शून्य होते हैं। इस प्रकार यह प्रायः एकल शून्य ('0') होगा।
बी = 0
* प्रत्येक पश्चात् वाले प्रतीक को अनुक्रम में अगला [[बाइनरी अंक प्रणाली]] नंबर सौंपा गया है, यह सुनिश्चित करते हुए कि निम्नलिखित कोड सदैव मूल्य में अधिक हैं।
सी = 101
* जब आप किसी लंबे कोडवर्ड तक पहुंच जाएं तब बढ़ाते-बढ़ाते शून्य तब तक लगाएं जब तक नए कोडवर्ड की लंबाई पुराने कोडवर्ड की लंबाई के सामान्तर न हो जाए. इस प्रकार इसे [[तार्किक बदलाव]] के रूप में उपयोग किया जा सकता हैं।
डी = 100
 
यहां अक्षर A को 2 [[ अंश |अंश]] , B को 1 बिट, और C तथा D दोनों को 3 बिट दिए गए हैं। कोड को कैनोनिकल हफ़मैन कोड बनाने के लिए, कोडों को पुनः क्रमांकित किया जाता है। बिट की लंबाई समान रहती है, कोड बुक को पहले कोडवर्ड की लंबाई के आधार पर और दूसरे अक्षर के वर्णमाला [[मूल्य (कंप्यूटर विज्ञान)]] के आधार पर क्रमबद्ध किया जाता है:
 
बी = 0
ए = 11
सी = 101
डी = 100
 
निम्नलिखित [[ कलन विधि |कलन विधि]] का उपयोग करके प्रत्येक उपस्तिथा कोड को समान लंबाई के एक नए कोड से बदल दिया जाता है:
 
* सूची में पहले प्रतीक को एक कोडवर्ड सौंपा जाता है जिसकी लंबाई प्रतीक के मूल कोडवर्ड के समान होती है किन्तु सभी शून्य होते हैं। यह प्रायः एकल शून्य ('0') होगा।
* प्रत्येक बाद वाले प्रतीक को अनुक्रम में अगला [[बाइनरी अंक प्रणाली]] नंबर सौंपा गया है, यह सुनिश्चित करते हुए कि निम्नलिखित कोड हमेशा मूल्य में अधिक हैं।
* जब आप किसी लंबे कोडवर्ड तक पहुंच जाएं तो बढ़ाते-बढ़ाते शून्य तब तक लगाएं जब तक नए कोडवर्ड की लंबाई पुराने कोडवर्ड की लंबाई के बराबर न हो जाए. इसे एक [[तार्किक बदलाव]] के रूप में सोचा जा सकता है।


इन तीन नियमों का पालन करके, उत्पादित कोड बुक का विहित संस्करण होगा:
इन तीन नियमों का पालन करके, उत्पादित कोड बुक का विहित संस्करण होगा:
 
  B = 0
  बी = 0
  A = 10
  = 10
  C = 110
  सी = 110
  D = 111
  डी = 111


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


विहित कोडवर्ड पर एक और परिप्रेक्ष्य यह है कि वे एक निश्चित श्रृंखला के द्विआधारी प्रतिनिधित्व में [[मूलांक बिंदु]] (बाइनरी दशमलव बिंदु) से आगे के अंक हैं। विशेष रूप से, मान लीजिए कि कोडवर्ड की लंबाई 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 से कम या उसके सामान्तर होगा (क्योंकि लंबाई उपसर्ग मुक्त कोड से आती है)। इससे पता चलता है कि उपरोक्त एल्गोरिदम में जोड़ने से कभी भी अतिप्रवाह नहीं होता है और ऐसा कोडवर्ड बनता है जो इच्छित से अधिक लंबा होता है।


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


आइए हम अपनी मूल हफ़मैन कोडबुक लें:
आइए हम अपनी मूल हफ़मैन कोडबुक लें:
 
  A = 11
  = 11
  B = 0
  बी = 0
  C = 101
  सी = 101
  D = 100
  डी = 100
ऐसे अनेक तरीके हैं जिनसे हम इस हफ़मैन पेड़ को एनकोड कर सकते हैं। इस प्रकार उदाहरण के लिए, हम प्रत्येक प्रतीक के पश्चात् '''बिट्स की संख्या''' और '''कोड''' लिख सकते हैं:
 
  ('A',2,11), ('B',1,0), ('C',3,101), ('D',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)


हमारे ''कैनोनिकल'' संस्करण के साथ हमें यह ज्ञान है कि प्रतीक अनुक्रमिक वर्णमाला क्रम में हैं ''और'' कि बाद का कोड हमेशा पहले वाले की तुलना में मूल्य में अधिक होगा। संचारित करने के लिए बचे एकमात्र भाग प्रत्येक प्रतीक के लिए बिट-लंबाई (बिट्स की संख्या) हैं। ध्यान दें कि हमारे विहित हफ़मैन पेड़ में लंबी [[बिट लंबाई]] के लिए हमेशा उच्च मान होते हैं और समान बिट लंबाई (''सी'' और ''डी'') के किसी भी प्रतीक में उच्च प्रतीकों के लिए उच्च कोड मान होते हैं:
हमारे विहित संस्करण के साथ हमें यह ज्ञान है कि प्रतीक अनुक्रमिक वर्णमाला क्रम में हैं और इस प्रकार कि पश्चात् का कोड सदैव पहले वाले की तुलना में मूल्य में अधिक होगा। इस प्रकार संचारित करने के लिए बचे एकमात्र भाग प्रत्येक प्रतीक के लिए बिट-लंबाई ('''बिट्स की संख्या''') हैं। ध्यान दें कि हमारे विहित हफ़मैन पेड़ में लंबी [[बिट लंबाई]] के लिए सदैव उच्च मान होते हैं और समान बिट लंबाई ('''सी और डी''') के किसी भी प्रतीक में उच्च प्रतीकों के लिए उच्च कोड मान होते हैं:
 
  A = 10 (code value: 2 decimal, bits: '''2''')
  = 10 (कोड मान: 2 दशमलव, बिट्स: 2)
  B = 0 (code value: 0 decimal, bits: '''1''')
  बी = 0 (कोड मान: 0 दशमलव, बिट्स: 1)
  C = 110 (code value: 6 decimal, bits: '''3''')
  सी = 110 (कोड मान: 6 दशमलव, बिट्स: 3)
  D = 111 (code value: 7 decimal, bits: '''3''')
  डी = 111 (कोड मान: 7 दशमलव, बिट्स: 3)
चूँकि दो-तिहाई बाधाएँ ज्ञात हैं, इस प्रकार प्रत्येक प्रतीक के लिए केवल '''बिट्स की संख्या''' प्रसारित करने की आवश्यकता है:
 
चूँकि दो-तिहाई बाधाएँ ज्ञात हैं, प्रत्येक प्रतीक के लिए केवल बिट्स की संख्या प्रसारित करने की आवश्यकता है:


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


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


कोडबुक का प्रतिनिधित्व करने का एक अन्य प्रभावी प्रणाली सभी प्रतीकों को उनकी बिट-लंबाई के आधार पर बढ़ते क्रम में सूचीबद्ध करना है, और प्रत्येक बिट-लंबाई के लिए प्रतीकों की संख्या रिकॉर्ड करना है। ऊपर उल्लिखित उदाहरण के लिए, एन्कोडिंग बन जाती है:
कोडबुक का प्रतिनिधित्व करने का अन्य प्रभावी प्रणाली सभी प्रतीकों को उनकी बिट-लंबाई के आधार पर बढ़ते क्रम में सूचीबद्ध करना है और प्रत्येक बिट-लंबाई के लिए प्रतीकों की संख्या रिकॉर्ड करना है। इस प्रकार ऊपर उल्लिखित उदाहरण के लिए, एन्कोडिंग बन जाती है:
(1,1,2), ('B','A','C','D')
इसका कारण यह है कि पहला प्रतीक बी लंबाई 1 का है, फिर ए लंबाई 2 का है, और शेष 3 का है। चूंकि प्रतीकों को बिट-लंबाई के अनुसार क्रमबद्ध किया जाता है, इस प्रकार इसलिए हम कुशलतापूर्वक कोडबुक का पुनर्निर्माण कर सकते हैं। पुनर्निर्माण का वर्णन करने वाला [[छद्म कोड]] अगले भाग में प्रस्तुत किया गया है।


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


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


या रिकॉर्ड करें कि हमने कौन से 4 अक्षरों का उपयोग किया है। प्रत्येक प्रणाली विवरण को इससे अधिक लंबा बनाता है:
या रिकॉर्ड करें कि हमने कौन से 4 अक्षरों का उपयोग किया है। इस प्रकार प्रत्येक प्रणाली विवरण को इससे अधिक लंबा बनाता है:
 
  (0,4), ('C','O','D','E')
  (0,4), ('सी','','डी','')
जेपीईजी फ़ाइल इंटरचेंज प्रारूप एन्कोडिंग की इस पद्धति का उपयोग करता है, इस प्रकार क्योंकि [[8 बिट]] वर्णमाला में से अधिकतम केवल 162 प्रतीक, जिसका आकार 256 है, कोडबुक में होंगे।
 
JPEG फ़ाइल इंटरचेंज प्रारूप एन्कोडिंग की इस पद्धति का उपयोग करता है, क्योंकि [[8 बिट]] वर्णमाला में से अधिकतम केवल 162 प्रतीक, जिसका आकार 256 है, कोडबुक में होंगे।


==[[छद्मकोड]]==
==[[छद्मकोड|स्यूडोकोड]]==
बिट-लंबाई के आधार पर क्रमबद्ध प्रतीकों की एक सूची को देखते हुए, निम्नलिखित छद्मकोड एक कैनोनिकल हफ़मैन कोड बुक प्रिंट करेगा:
बिट-लंबाई के आधार पर क्रमबद्ध प्रतीकों की सूची को देखते हुए, इस प्रकार निम्नलिखित [[छद्मकोड|स्यूडोकोड]] कैनोनिकल हफ़मैन कोड बुक प्रिंट करेगा:
''code'' := 0
'''while''' more symbols '''do'''
  print symbol, ''code''
  ''code'' := (''code'' + 1) << ((bit length of the next symbol) − (current bit length))


  कोड := 0
  '''algorithm''' compute huffman code '''is'''
'जबकि' अधिक प्रतीक 'करते हैं'
  '''input:''' message ensemble (set of (message, probability)).
  प्रिंट प्रतीक, कोड
  base ''D''.
  कोड�:= (कोड + 1) << ((अगले प्रतीक की बिट लंबाई) - (वर्तमान बिट लंबाई))


'एल्गोरिदम' गणना हफ़मैन कोड 'है'
  '''output:''' code ensemble (set of (message, code)).
  'इनपुट:' संदेश समूह ((संदेश, संभाव्यता) का सेट)।
          आधारित।
  'आउटपुट:' कोड संयोजन ((संदेश, कोड) का सेट)
    
    
  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"
David A. Huffman, Proceedings of the I.R.E.</ref>
David A. Huffman, Proceedings of the I.R.E.</ref><ref>[https://web.archive.org/web/20121012042751/http://ww2.cs.mu.oz.au/mg/ Managing Gigabytes]: book with an implementation of canonical huffman codes for word dictionaries.</ref>
 
<ref>[https://web.archive.org/web/20121012042751/http://ww2.cs.mu.oz.au/mg/ Managing Gigabytes]: book with an implementation of canonical huffman codes for word dictionaries.</ref>
== संदर्भ ==
== संदर्भ ==


<references />
<references />


{{Compression methods}}
{{DEFAULTSORT:Canonical Huffman Code}}
 
{{DEFAULTSORT:Canonical Huffman Code}}[[Category: दोषरहित संपीड़न एल्गोरिदम]] [[Category: कोडिंग सिद्धांत]]
 
 


[[Category: Machine Translated Page]]
[[Category:Created On 07/07/2023|Canonical Huffman Code]]
[[Category:Created On 07/07/2023]]
[[Category:Machine Translated Page|Canonical Huffman Code]]
[[Category:कोडिंग सिद्धांत|Canonical Huffman Code]]
[[Category:दोषरहित संपीड़न एल्गोरिदम|Canonical Huffman Code]]

Latest revision as of 19:04, 21 July 2023

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

प्रेरणा

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

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

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

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

एल्गोरिदम

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

A = 11
B = 0
C = 101
D = 100

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

B = 0
A = 11
C = 101
D = 100

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

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

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

B = 0
A = 10
C = 110
D = 111

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

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

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

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

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

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

A = 11
B = 0
C = 101
D = 100

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

('A',2,11), ('B',1,0), ('C',3,101), ('D',3,100)

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

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

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

A = 10 (code value: 2 decimal, bits: 2)
B = 0 (code value: 0 decimal, bits: 1)
C = 110 (code value: 6 decimal, bits: 3)
D = 111 (code value: 7 decimal, bits: 3)

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

2, 1, 3, 3

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

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

(1,1,2), ('B','A','C','D')

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

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

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

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

(0,4), ('C','O','D','E')

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

स्यूडोकोड

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

code := 0
while more symbols do
 print symbol, code
 code := (code + 1) << ((bit length of the next symbol) − (current bit length))
algorithm compute huffman code is
 input: message ensemble (set of (message, probability)).
 base D.
 output: code ensemble (set of (message, code)).
 
 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.