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

अब जानकारी को संपीड़ित करने के लिए कई एल्गोरिदम हैं। उनमें से ज्यादातर व्यापक रूप से जाने जाते हैं, लेकिन कुछ बहुत प्रभावी हैं, लेकिन, कम-ज्ञात एल्गोरिदम। यह लेख अंकगणित कोडिंग की विधि के बारे में बात करता है, जो एन्ट्रापी का सबसे अच्छा है, लेकिन फिर भी बहुत कम लोग इसके बारे में जानते हैं।
इससे पहले कि हम अंकगणित कोडिंग के बारे में बात करें, मुझे हफमैन एल्गोरिथ्म के बारे में कुछ शब्द कहना चाहिए। यह विधि प्रभावी है जब प्रतीक आवृत्तियों 1/2 ^एन (जहां एन एक सकारात्मक पूर्णांक है) के आनुपातिक हैं। यह कथन स्पष्ट हो जाता है यदि हम याद करते हैं कि प्रत्येक वर्ण के लिए हफमैन कोड हमेशा एक पूर्णांक संख्या में होते हैं। ऐसी स्थिति पर विचार करें जहां एक प्रतीक की घटना की आवृत्ति 0.2 है, फिर इस प्रतीक को एन्कोडिंग के लिए इष्टतम कोड की लंबाई _-2 (0.2) = 2.3 बिट होनी चाहिए। यह स्पष्ट है कि हफमैन उपसर्ग कोड में इतनी लंबाई नहीं हो सकती है, अर्थात्। यह अंततः खराब डेटा संपीड़न की ओर जाता है।
अंकगणित कोडिंग का उद्देश्य इस समस्या को हल करना है। मुख्य विचार अलग-अलग वर्णों को नहीं, बल्कि उनके अनुक्रमों को कोड असाइन करना है।
सबसे पहले, एल्गोरिथ्म के पीछे के विचार पर विचार करें, फिर एक छोटे व्यावहारिक उदाहरण पर विचार करें।
जैसा कि सभी एन्ट्रापी एल्गोरिदम में है, हमारे पास वर्णमाला के प्रत्येक प्रतीक के उपयोग की आवृत्ति के बारे में जानकारी है। यह जानकारी विचाराधीन विधि का स्रोत है। अब हम एक कामकाजी खंड की अवधारणा को पेश करते हैं। एक आधा-अंतराल [a; b) उस पर स्थित बिंदुओं के साथ एक कार्यकर्ता कहलाता है। इसके अलावा, अंक स्थित हैं ताकि उनके द्वारा गठित खंडों की लंबाई वर्णों के उपयोग की आवृत्ति के बराबर हो। जब एल्गोरिथ्म को आरंभीकृत किया जाता है, तो एक = 0 बी = 1।
एक कोडिंग चरण में एक सरल ऑपरेशन होता है: एन्कोडेड वर्ण लिया जाता है, क्योंकि इसके लिए कार्य खंड पर संबंधित अनुभाग खोजा जाता है। पाया गया अनुभाग एक नया कार्य खंड बन जाता है (यानी, इसे डॉट्स का उपयोग करके विभाजित करने की भी आवश्यकता होती है)।
यह ऑपरेशन स्रोत धारा के कई पात्रों के लिए किया जाता है। एक चरित्र स्ट्रिंग को कोडित करने का परिणाम अंतिम कार्य खंड से किसी भी संख्या (साथ ही उसके बिट रिकॉर्ड की लंबाई) है (सबसे अधिक बार खंड की बाईं सीमा ली जाती है)।
यह बहुत जटिल लगता है। आइए इसे एक छोटे से उदाहरण के साथ जानने की कोशिश करें। हम वर्णित विधि का उपयोग करके "THIS_METHOD_BETTER_HAFFMANA" संदेश को एनकोड करते हैं।



वर्णों की घटना की आवृत्ति की एक तालिका संकलित करने के बाद, हम कोडिंग शुरू कर सकते हैं। पहले चरण में हम एक कामकाजी खंड बनाएंगे। यह इस तरह दिखेगा:



हम धारा से पहला प्रतीक लेते हैं, यह प्रतीक "ई" है। संबंधित खंड खंड [0.96; 1) है। यदि हम किसी एक वर्ण को एनकोड करना चाहते हैं, तो एन्कोडिंग परिणाम इस सेगमेंट का कोई भी नंबर होगा। लेकिन हम एक प्रतीक पर नहीं रुकेंगे, बल्कि एक और जोड़ देंगे। प्रतीक "टी"। ऐसा करने के लिए, हम एक = 0.96 और बी = 1 के साथ एक नया कार्य खंड तैयार करेंगे। हम इस लाइन को उसी तरह से डॉट्स से तोड़ते हैं जैसे हमने ओरिजिनल लाइन के लिए किया था और नए "टी" सिंबल को पढ़ा। "टी" प्रतीक सीमा [0.24; 0.36) से मेल खाती है, लेकिन हमारे काम करने वाले सेगमेंट को पहले से ही कम कर दिया गया है [0.96; 1)। यानी सीमाओं की हमें जरूरत है। आप निम्न दो सूत्रों का उपयोग करके ऐसा कर सकते हैं: उच्च = निम्न _{पुराना} + (उच्च _{पुराना-} निम्न _{पुराना} ) * श्रेणी _उच्च (x), निम्न = निम्न _{पुराना} + (उच्च _{पुराना-} कम _{पुराना} ) * श्रेणी _{निम्न} (x), जहाँ निम्न _{पुराना} - अंतराल की निचली सीमा, उच्च _{पुरानी} - रेंज रेंज _उच्च और रेंज _कम की ऊपरी सीमा - एन्कोडेड वर्ण की ऊपरी और निचली सीमा।
इन फ़ार्मुलों का उपयोग करते हुए, हम संदेश के पहले शब्द को समग्र रूप से कूटबद्ध करते हैं:



एन्कोडिंग परिणाम आधे-अंतराल [0.97218816 से किसी भी संख्या में होगा; .९,७२,२३,४२४)।
मान लें कि अर्ध-अंतराल की बाईं सीमा, अर्थात्। नंबर 0.97218816।
डिकोडिंग प्रक्रिया पर विचार करें। कोड आधे-अंतराल [0.96; 1) में निहित है। यानी संदेश "ई" का पहला चरित्र। दूसरे वर्ण को डीकोड करने के लिए (जो कि आधे-अंतराल [0.96; 1) में एन्कोडेड था), आधे-अंतराल को सामान्य किया जाना चाहिए, अर्थात्। फार्म को कास्ट [0; 1)। यह निम्नलिखित सूत्र का उपयोग करके किया जाता है: कोड = (कोड-रेंज _लो (x)) / (रेंज _हाई (x) -Range _लो (x)), जहां कोड वर्तमान कोड मान है।
इस सूत्र को लागू करते हुए, हम एक नया मूल्य कोड प्राप्त करते हैं = (0.97218816-0.96) / (1-0.96) = 0.3004704। यानी अनुक्रम "टी" का दूसरा चरित्र।
फिर से हम सूत्र लागू करते हैं: कोड = (0.3004704-0.24) / (0.36-0.24) = 0.5392। अनुक्रम का तीसरा चरित्र "ओ" है।
निरंतर डिकोडिंग, वर्णित योजना के अनुसार, हम स्रोत पाठ को पूरी तरह से पुनर्स्थापित कर सकते हैं।

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