🔡 👩🏻‍🏫 ⬛️ दोषरहित सूचना संपीड़न। भाग दो 👨🏽‍🏫 👩🏾‍🎓 🛣️

पहला भाग।

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

तो, चलो अंकगणित कोडिंग के साथ शुरू करते हैं - मेरी राय में, सबसे सुरुचिपूर्ण (विचारों के दृष्टिकोण से) संपीड़न विधियों में से एक।

परिचय

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

जैसा कि आप देख सकते हैं, ऐसे मामलों में जहां रिश्तेदार आवृत्तियों में दो की शक्तियां नहीं हैं, एल्गोरिथ्म स्पष्ट रूप से दक्षता में खो देता है। यह आसानी से क्रमशः 253/256 और 3/256 आवृत्तियों के साथ दो प्रतीकों a और b की धारा के एक सरल उदाहरण के साथ सत्यापित किया जा सकता है। इस मामले में, आदर्श रूप से, हमें ज़रूरत है

, यानी 24 बिट्स। उसी समय, हफ़मैन पद्धति इन वर्णों को क्रमशः 0 और 1 कोड के साथ एन्कोड करती है, और संदेश 256 बिट्स लेता है, जो निश्चित रूप से, मूल संदेश के 256 बाइट्स से कम है (याद रखें, हम मानते हैं कि प्रत्येक वर्ण में शुरू में बाइट्स का एक आकार है), लेकिन फिर भी इष्टतम से 10 गुना कम है।

तो, आइए अंकगणित कोडिंग पर विचार करें, जो हमें सबसे अच्छा परिणाम प्राप्त करने की अनुमति देगा।

अंकगणित कोडिंग

हफ़मैन विधि की तरह, अंकगणित कोडिंग एक एन्ट्रापी संपीड़न विधि है। एन्कोड किए गए डेटा को एक अंश के रूप में प्रस्तुत किया जाता है, जिसे चुना जाता है ताकि पाठ को सबसे कॉम्पैक्ट तरीके से प्रस्तुत किया जा सके। इसका वास्तव में क्या मतलब है?

अंतराल पर अंशों के निर्माण पर विचार करें [0,1) (गणना की सुविधा के लिए इस तरह के अंतराल को चुना जाता है), और शब्द "बॉक्स" के रूप में इनपुट डेटा के उदाहरण पर। हमारा काम वर्णों की उपस्थिति की संभावनाओं के बराबर लंबाई के साथ प्रारंभिक अंतराल को उप-अंतराल में तोड़ना होगा।

चलिए हमारे इनपुट टेक्स्ट के लिए एक प्रायिकता तालिका बनाते हैं:

प्रतीक	आवृत्ति	संभावना	की सीमा
ओह	2	0.4	[0.0, 0.4)
कश्मीर	1	0.2	[0.4, 0.6)
पी	1	0.2	[०.६, ०.,)
बी	1	0.2	[0.8, 1.0)

यहाँ, "फ़्रिक्वेंसी" का अर्थ है इनपुट स्ट्रीम में किसी वर्ण के होने की संख्या।

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

जहाँ N वर्णमाला के वर्णों की संख्या है, p _i i-th वर्ण की संभावना है।

हमारे मामले में, यह ऐसा दिखता है

इसलिए, हमने अनुक्रमिक रूप से इनपुट स्ट्रीम के प्रत्येक चरित्र के लिए अंतराल को कम कर दिया जब तक कि हमें अंतिम चरित्र पर 0.45312 से 0.4544 तक अंतराल नहीं मिला। कोडिंग करते समय हम इसका उपयोग करेंगे।

अब हमें इस अंतराल में पड़ी किसी भी संख्या को लेने की आवश्यकता है। इसे 0.454 होने दें। हैरानी की बात है (लेकिन मेरे लिए, जब मैं सिर्फ इस पद्धति का अध्ययन कर रहा था, तो यह बहुत आश्चर्यजनक था), यह संख्या, प्रतीक आवृत्तियों के मूल्यों के साथ, मूल संदेश को पूरी तरह से पुनर्स्थापित करने के लिए पर्याप्त है।

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

डिकोडिंग कैसे काम करता है? डिकोडिंग एक समान तरीके से होती है (रिवर्स ऑर्डर में नहीं, बल्कि इसी तरह से)।

हम 0 से 1 के अंतराल से शुरू करते हैं, प्रतीक आवृत्तियों के अनुसार टूट जाते हैं। हम जाँच करते हैं कि किस अंतराल में हमारी संख्या गिरती है (0.454)। इस अंतराल के अनुरूप वर्ण अनुक्रम में पहला वर्ण होगा। अगला, हम इस अंतराल को पूरे पैमाने पर बढ़ाते हैं, और प्रक्रिया को दोहराते हैं।

हमारे मामले के लिए, प्रक्रिया इस तरह दिखाई देगी:

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

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

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

253/256 और 3/256 संभावनाओं वाले लेख की शुरुआत में प्रस्तावित प्रतीकों a और b के अनुक्रम पर विचार करें। 256 वर्णों की स्ट्रिंग के लिए अंतिम कार्य अंतराल की लंबाई बराबर होगी

इस मामले में, वांछित एन 24 के बराबर होगा (23 एक अंतराल बहुत बड़ा देता है, और 25 न्यूनतम नहीं होगा), अर्थात, हम हफ़मैन पद्धति के 256 बिट्स के खिलाफ, केवल 24 बिट्स कोडिंग पर खर्च करेंगे।

बरोज़-व्हीलर परिवर्तन

इसलिए, हमें पता चला कि संपीड़न विधियाँ विभिन्न डेटा सेटों पर अलग-अलग दक्षता दिखाती हैं। इससे आगे बढ़ते हुए, एक बहुत तार्किक सवाल उठता है: यदि संपीड़न एल्गोरिदम कुछ डेटा पर बेहतर काम करते हैं, तो क्या इसकी "गुणवत्ता" में सुधार के लिए संपीड़न से पहले डेटा पर कुछ संचालन करना संभव है?

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

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

मूल लेख में, 1994 में प्रकाशित, लेखकों ने तीन एल्गोरिदम पर कोडिंग के कार्यान्वयन का प्रस्ताव दिया:

दरअसल, बीडब्ल्यूटी
मूव-टू-फ्रंट परिवर्तन, जिसे रूसी साहित्य में पुस्तकों के ढेर के रूप में जाना जाता है
डेटा के पहले दो चरणों में प्राप्त सांख्यिकीय संपीड़न एनकोडर।

सच है, दूसरे चरण को दूसरे समान एल्गोरिथ्म द्वारा प्रतिस्थापित किया जा सकता है, या एन्कोडिंग चरण की जटिलता के कारण पूरी तरह से बाहर रखा गया है। यह समझना महत्वपूर्ण है कि BWT किसी भी तरह से डेटा के आकार को प्रभावित नहीं करता है , यह सिर्फ ब्लॉकों की व्यवस्था को बदलता है।

रूपांतरण एल्गोरिथ्म

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

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

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

हम इसे वर्णों के एक मैट्रिक्स के रूप में मानेंगे, जहां प्रत्येक कोशिका क्रमशः एक वर्ण है, पंक्ति पूरे शब्द से मेल खाती है। हम मूल पंक्ति को चिह्नित करते हैं, और मैट्रिक्स को सॉर्ट करते हैं।
छांटना पहले चरित्र द्वारा पहले किया जाता है, फिर, उन पंक्तियों के लिए जहां पहला चरित्र मेल खाता है - दूसरा, और इसी तरह। इस तरह की छँटाई के बाद, हमारा मैट्रिक्स निम्नलिखित रूप लेगा:

–

सामान्य तौर पर, इस पर रूपांतरण लगभग समाप्त हो गया है: जो कुछ भी करना बाकी है वह मूल पंक्ति की संख्या को याद करने के लिए भूलकर, अंतिम कॉलम को लिखना है। ऐसा करने के बाद, हम प्राप्त करते हैं:

 «>><<»

या, दूसरे तरीके से,

 «»,2

जैसा कि आप देख सकते हैं, पात्रों का वितरण बहुत बेहतर हो गया है: अब 5 वर्णों में से 4 "एक" एक दूसरे के बगल में हैं, जैसा कि दोनों वर्ण "बी" हैं।

उलटने अथवा पुलटने योग्यता

जैसा कि मैंने उल्लेख किया है, रूपांतरण पूरी तरह से प्रतिवर्ती है। यह समझ में आता है, क्योंकि अन्यथा इसका कोई मतलब नहीं होगा। तो संदेश के मूल स्वरूप को कैसे पुनर्स्थापित करें?

सबसे पहले, हमें अपने पात्रों को क्रम में क्रमबद्ध करना होगा। यह हमें स्ट्रिंग "आआआआआआआआद्बद्दर्र" देगा। चूंकि चक्रीय क्रमपरिवर्तन का हमारा मैट्रिक्स क्रम में क्रमबद्ध था, इसलिए अक्षरों का यह क्रम चक्रीय क्रमपरिवर्तन के हमारे मैट्रिक्स के पहले स्तंभ से अधिक कुछ नहीं है। इसके अलावा, हम अंतिम कॉलम (वास्तव में, रूपांतरण का परिणाम) भी जानते हैं। तो, इस स्तर पर, हम मैट्रिक्स को कुछ इस तरह से पुनर्स्थापित कर सकते हैं:

और	...	आर
और	...	घ
और	...	और
और	...	को
और	...	आर
ख	...	और
ख	...	और
घ	...	और
को	...	और
आर	...	ख
आर	...	ख

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

दूसरे शब्दों में, बहाली इस प्रकार की गई है:

पहले के पात्रों के लिए बाईं ओर अंतिम कॉलम के पात्रों को संलग्न करें
अंतिम को छोड़कर सभी स्तंभों को क्रमबद्ध करें

मैट्रिक्स पूरी तरह से भरे जाने तक इन दो चरणों को दोहराया जाना चाहिए।

हमारे उदाहरण के लिए, पहले चार रिकवरी चरण इस तरह दिखाई देंगे:

  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...

कार्य पर संसाधन लागत

हमने डेटा के उत्क्रमण को साबित करने के बाद, हम यह साबित करते हैं कि एल्गोरिथ्म के कार्यान्वयन के लिए पूरे मैट्रिक्स को मेमोरी में स्टोर करना आवश्यक नहीं है। वास्तव में - यदि हमने मैट्रिक्स को पूरी तरह से संग्रहीत किया है, उदाहरण के लिए, 1 मेगाबाइट ब्लॉक के लिए, तो हमें मेमोरी की एक जबरदस्त मात्रा की आवश्यकता होगी - क्योंकि मैट्रिक्स वर्ग है। स्वाभाविक रूप से, यह विकल्प अस्वीकार्य है।

व्युत्क्रम परिवर्तन के लिए, वास्तविक डेटा के अतिरिक्त, हमें व्युत्क्रम परिवर्तन के वेक्टर की आवश्यकता होती है - संख्याओं की एक सरणी जिसका आकार ब्लॉक में वर्णों की संख्या के बराबर है। इस प्रकार, रैखिक रूपांतरण के दौरान मेमोरी ओवरहेड ब्लॉक आकार के साथ रैखिक रूप से बढ़ता है।

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

ट्रांसफ़ॉर्म वेक्टर लाइन नंबरों के मान से बनता है: {2,5,6,7,8,9,10,1,3,3,4}।

अब आप आसानी से मूल स्ट्रिंग प्राप्त कर सकते हैं। उलटा परिवर्तन वेक्टर के तत्व को लें, जो मैट्रिक्स में मूल पंक्ति की संख्या से मेल खाती है: टी [2] = 6। दूसरे शब्दों में, मूल स्ट्रिंग के पहले चरित्र के रूप में, आपको "rdakraaaabb" स्ट्रिंग के छठे चरित्र को लेने की आवश्यकता है - चरित्र "a"।
उसके बाद, हम देखते हैं कि किस प्रतीक ने "प्रतीक" को उसी के बीच दूसरे स्थान पर ले जाया। ऐसा करने के लिए, हम संख्या को स्ट्रिंग के रूपांतरण वेक्टर से लेते हैं जिसमें से वर्ण "a" लिया गया था: यह संख्या 6 है।
फिर हम लाइन नंबर 6 को देखते हैं और वहां से अंतिम चरित्र का चयन करते हैं - यह चरित्र "बी" है। शेष पात्रों के लिए इस प्रक्रिया को जारी रखते हुए, हम आसानी से मूल स्ट्रिंग को पुनर्स्थापित कर सकते हैं।

पुस्तकों का ढेर लगना

पुस्तकों के ढेर को स्थानांतरित करना एक मध्यवर्ती एल्गोरिथ्म है जो लेखक बीडब्ल्यूटी के बाद और सीधे कोडिंग से पहले उपयोग करने की सलाह देते हैं। एल्गोरिथ्म निम्नानुसार काम करता है।

लाइन "rdakraaaabb" पर विचार करें, पिछले भाग में BWT पर हमारे द्वारा प्राप्त किया गया था। इस मामले में, हमारी वर्णमाला में 5 वर्ण हैं। उन्हें आदेश दिया, हम प्राप्त करते हैं
एम = {ए, बी, डी, के, पी}।

तो, हम अपनी लाइन पर पुस्तकों के ढेर को स्थानांतरित करने के लिए एल्गोरिथ्म का उपयोग करते हैं। स्ट्रिंग का पहला चरित्र ("पी") वर्णमाला में 4 वें स्थान पर है। यह संख्या (4) हम आउटपुट ब्लॉक में लिखते हैं। फिर हम उस प्रतीक को डालते हैं जिसका उपयोग हम पहले स्थान पर करते हैं, और दूसरे प्रतीक के साथ प्रक्रिया को दोहराते हैं, फिर तीसरे और इसी तरह। प्रसंस्करण इस तरह दिखेगा ("संख्या" के तहत मैं उस संख्या को मानता हूं जो आउटपुट स्ट्रीम पर जाएगी):

प्रतीक	वर्णमाला	संख्या
आर	abdkr	4
घ	rabdk	3
और	drabk	2
को	adrbk	4
आर	kadrb	3
और	rkadb	2
और	arkdb	0
और	arkdb	0
और	arkdb	0
ख	arkdb	4
ख	barkd	0

परिणाम अनुक्रम होगा

43243200040

इस स्तर पर, यह पूरी तरह से स्पष्ट नहीं है कि यह एल्गोरिथ्म कितना अच्छा है। वास्तव में, वहाँ अच्छा उपयोग है। अधिक सार अनुक्रम पर विचार करें:

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

 M={,,,}.

एल्गोरिथ्म का उपयोग करने के बाद, स्ट्रिंग जैसा दिखेगा

 10002000030000300003

इस स्थिति में, वर्णों की घटना की आवृत्ति बहुत भिन्न होगी:

प्रतीक	आवृत्ति	संभावना	हफमैन कोड
0	15	3/4	0
3	3	3/20	10
2	1	1/20	110
1	1	1/20	111

इस मामले में, कोडिंग के बाद, हमें 15 + 6 + 3 + 3 = 27 बिट्स का एक क्रम मिलता है, जो कि 40 बिट्स से बहुत कम है, जो पुस्तकों के ढेर को स्थानांतरित किए बिना प्राप्त किया जाता है।

निष्कर्ष

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

साहित्य

वैटोलिन डी।, रतुश्नायक ए।, स्मिरनोव एम। युकिन वी। डेटा संपीड़न के तरीके। डिवाइस अभिलेखागार, छवि और वीडियो संपीड़न; आईएसबीएन 5-86404-170-एक्स; 2003 वर्ष
लिडोव्स्की वी.वी. सूचना सिद्धांत: पाठ्यपुस्तक। - एम।: स्पुतनिक + कंपनी, 2004।
असत्य जानकारी की आर्थिक कोडिंग सेमेन्युक वी.वी. - एसपीबी।: एसपीबीजीटीएमओ (टीयू), 2001।
Witten IH, नील आरएम, डेटा संपीड़न के लिए स्पष्ट JG अंकगणितीय कोडिंग, CACM, 1987।

दोषरहित सूचना संपीड़न। भाग दो