बड़े अक्षर के लिए उपसर्ग एन्ट्रापी कोडिंग के कार्यान्वयन की सुविधाओं पर

मुझे लगता है कि उपसर्ग कोड (शैनन-फ़ानो, हफ़मैन, आदि) एल्गोरिदम का उपयोग करते हुए एन्ट्रापी संपीड़न एल्गोरिदम अच्छी तरह से हैबर के सभी पाठकों के लिए जाने जाते हैं। इन एल्गोरिदम की एक विशेषता यह है कि किसी विशेष वर्ण की कोड लंबाई एन्कोडेड संदेश में उस वर्ण की आवृत्ति पर निर्भर करती है। तदनुसार, जब एक संदेश को डिकोड किया जाता है, तो आवृत्ति तालिका होना आवश्यक है। यह लेख थोड़ा अध्ययन, लेकिन महत्वपूर्ण कार्य - मूल वर्णमाला की आवृत्तियों के हस्तांतरण के लिए समर्पित है।
शुरुआत में, एन्ट्रापी उपसर्ग कोडिंग के पीछे मूल विचार को देखते हैं। मान लीजिए कि हमारे पास रूसी वर्णमाला के अक्षरों से मिलकर एक संदेश है, उदाहरण के लिए, "KUKUSHAKAKUKUSHONUKUPILAKAPUSHON"। इस संदेश में, केवल दस अलग-अलग वर्ण {K, Y, W, A, O, N, P, I, L, Y} हैं, जिसका अर्थ है कि प्रत्येक वर्ण को चार बिट्स का उपयोग करके एन्कोड किया जा सकता है।

यही है, इस तरह के एक भोले ब्लॉक कोडिंग के साथ पूरा संदेश 116 बिट्स पर कब्जा करेगा।
लेकिन अन्य कोड प्रतीकों से जुड़े हो सकते हैं, उदाहरण के लिए:

टैब से कोड का उपयोग करते समय। 2, संदेश की लंबाई पहले से ही 90 बिट होगी, और लाभ 22% से अधिक है। एक चौकस पाठक यह नोटिस करेगा कि टैब में कोड। 1 की निरंतर लंबाई होती है, जिसका अर्थ है कि उन्हें आसानी से डिकोड किया जा सकता है। टैब में। 2 कोड की एक चर लंबाई है, लेकिन उनके पास एक और महत्वपूर्ण संपत्ति है - उपसर्ग। उपसर्ग संपत्ति का मतलब है कि कोई भी कोड किसी अन्य कोड की शुरुआत नहीं है। किसी भी उपसर्ग कोड के लिए, एक संबंधित ट्री बनाया जा सकता है, जिसके साथ आप विशिष्ट रूप से संदेश को डिकोड कर सकते हैं:

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

1. वर्णमाला के सभी वर्णों को मुक्त नोड के रूप में दर्शाया गया है, जबकि नोड का वजन संदेश में प्रतीक की आवृत्ति के आनुपातिक है;
2. मुक्त नोड्स के सेट से, न्यूनतम वजन वाले दो नोड्स का चयन किया जाता है और चयनित नोड्स के वजन के योग के बराबर वजन के साथ एक नया (माता-पिता) नोड बनाया जाता है;
3. चयनित नोड्स को मुक्त सूची से हटा दिया जाता है, और उनके आधार पर बनाए गए मूल नोड को इस सूची में जोड़ा जाता है;
4. चरण 2-3 दोहराए जाते हैं जब तक कि मुक्त सूची में एक से अधिक नोड न हों;
5. निर्मित पेड़ के आधार पर, वर्णमाला के प्रत्येक प्रतीक को एक उपसर्ग कोड सौंपा गया है।

हमारे संदेश के लिए, हफमैन पेड़ इस तरह दिखेगा:

हफ़मैन एल्गोरिथ्म का उपयोग करके एन्कोड किया गया संदेश केवल 87 बिट्स (ब्लॉक कोड की तुलना में 25% लाभ) पर कब्जा कर लेगा।
हमारी सभी गणनाओं में, हमने स्पष्ट रूप से निहित किया है कि प्रतीक-कोड पत्राचार तालिका को डिकोड करने की प्रक्रिया में जाना जाता है, लेकिन व्यवहार में यह स्थिति पूरी नहीं होती है, इसलिए तालिका स्वयं एन्कोडेड संदेश के साथ प्रेषित होती है। ज्यादातर मामलों में, एन्कोडेड संदेश की मात्रा की तुलना में यह तालिका छोटी है, और इसके संचरण के तथ्य का संपीड़न क्षमता पर बहुत कम प्रभाव पड़ता है।
फिर भी, कभी-कभी ऐसे हालात होते हैं जब तालिका का वजन महत्वपूर्ण हो जाता है। उदाहरण के लिए, दोषरहित वीडियो संपीड़न पर मेरे शोध प्रबंध में, यह स्थिति लगातार होती है। इसके अलावा, वर्णमाला की शक्ति दसियों और लाखों लाखों प्रविष्टियां हैं।
यदि आप पारंपरिक दृष्टिकोण का उपयोग करते हैं, जब तालिका को एक तत्व पास किया जाता है - संबंधित कोड, ओवरहेड इतना बड़ा हो जाता है कि आप प्रभावी संपीड़न के बारे में भूल सकते हैं। प्रपत्र तत्व का संचरण - आवृत्ति भी कमियों के बिना नहीं है:

1. डिकोडर के कंधों पर कोड ट्री के निर्माण का कम्प्यूटेशनल रूप से कठिन कार्य निहित है;
2. आवृत्ति फैलता परिमाण के कई आदेश हैं, और मानक वास्तविक अंकगणित हमेशा आपको इसे सही ढंग से प्रदर्शित करने की अनुमति नहीं देता है।

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

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

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

पेड़ पर चढ़ता है

इस तरह के रूपांतरण के बाद, एक एकल बिट का मतलब न केवल एक विभाजन नोड है, बल्कि इस स्तर पर संसाधित एक के बाईं ओर के सभी नोड भी विभाजित हैं।
इस तरह के अनुकूलन आपके लिए महत्वहीन लग सकते हैं, लेकिन यह वे थे जिन्होंने दुनिया में सबसे अधिक नुकसान-रहित संपीड़न अनुपात (अधिकांश परीक्षण वीडियो अनुक्रमों) को प्राप्त करना संभव बना दिया।
PS यहां तक ​​कि पूरी तरह से निर्मित हफमैन पेड़ के मामले में, छोटे सरणियों के मामले में प्राथमिक एक से एक तत्व कोड प्राप्त करने का कार्य व्यावहारिक रूप से असंभव हो जाता है, जो अंततः एक नए प्रकार के द्विआधारी पेड़ों के उद्भव का कारण बना। अगर यह किसी के लिए दिलचस्प होगा, तो मैं खुशी के साथ एक और विषय लिखूंगा।
PPS मैं निश्चित रूप से प्रस्तावित वीडियो संपीड़न विधि के बारे में आपको बताऊंगा, लेकिन थोड़ी देर बाद।