व्याख्यान क्रमांक 4. सूचना का संपीड़न

सूचना संपीड़न सिद्धांत

डेटा संपीड़न का उद्देश्य संचार चैनलों पर अधिक किफायती भंडारण और संचरण के लिए स्रोत द्वारा उत्पन्न डेटा का एक कॉम्पैक्ट प्रतिनिधित्व प्रदान करना है।

मान लीजिए हमारे पास आकार में 1 (एक) मेगाबाइट की फ़ाइल है। हमें इससे एक छोटी फ़ाइल प्राप्त करने की आवश्यकता है। कुछ भी जटिल नहीं है - हम एक संग्रहकर्ता चलाते हैं, उदाहरण के लिए, विनज़िप, और हमें 600 किलोबाइट आकार की एक फ़ाइल मिलती है। शेष 424 किलोबाइट कहाँ गए?

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

संपीड़न प्रकार

सूचना संपीड़न के सभी तरीकों को सशर्त रूप से दो बड़े गैर-अतिव्यापी वर्गों में विभाजित किया जा सकता है: संपीड़न के साथ हानिसूचना और संपीड़न कोई नुकसान नहींजानकारी।

जानकारी के नुकसान के बिना संपीड़न।

हम मुख्य रूप से इन संपीड़न विधियों में रुचि रखते हैं, क्योंकि इनका उपयोग पाठ दस्तावेज़ों और कार्यक्रमों को स्थानांतरित करते समय, ग्राहक को पूर्ण कार्य जारी करते समय, या कंप्यूटर पर संग्रहीत जानकारी की बैकअप प्रतियां बनाते समय किया जाता है।

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

यहाँ एक सरल उदाहरण है। रूसी में 33 अक्षर, दस संख्याएँ और लगभग एक दर्जन या तो विराम चिह्न और अन्य विशेष वर्ण हैं। लिखे गए पाठ के लिए केवल अपरकेस रूसी अक्षरों में(जैसे टेलीग्राम और रेडियोग्राम में) साठ अलग-अलग मूल्य पर्याप्त होंगे। हालांकि, प्रत्येक वर्ण आमतौर पर एक बाइट द्वारा एन्कोड किया जाता है जिसमें 8 बिट होते हैं और 256 विभिन्न कोड व्यक्त कर सकते हैं। यह अतिरेक का पहला कारण है। हमारे "टेलीग्राफिक" टेक्स्ट के लिए, प्रति वर्ण छह बिट पर्याप्त होंगे।

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

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

ग्राफिक चित्रण विशेष रूप से एक ही बाइट्स के बड़े दोहराव वाले दृश्यों द्वारा प्रतिष्ठित होते हैं, लेकिन फोटोग्राफिक वाले नहीं (बहुत अधिक शोर होता है और पड़ोसी बिंदु मापदंडों में काफी भिन्न होते हैं), लेकिन वे जिन्हें कलाकार "चिकना" रंग से चित्रित करते हैं, जैसा कि एनिमेटेड फिल्मों में होता है .

हानिपूर्ण संपीड़न।

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

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

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

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

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

स्वीकार्य संपीड़न हानि की मात्रा को आमतौर पर नियंत्रित किया जा सकता है। यह आपको इष्टतम आकार / गुणवत्ता अनुपात का प्रयोग करने और प्राप्त करने की अनुमति देता है। स्क्रीन पर प्रदर्शित करने के उद्देश्य से फोटोग्राफिक चित्रण में, 5% जानकारी का नुकसान आमतौर पर महत्वपूर्ण नहीं होता है, और कुछ मामलों में, 20-25% को सहन किया जा सकता है।

दोषरहित संपीड़न एल्गोरिदम

शैनन-फ़ानो कोड

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

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

आइए एक पाठ की कल्पना करें, जिसके वर्णमाला में केवल 16 अक्षर हैं: ए, बी, सी, डी, डी, ई, एफ, जेड, आई, के, एल, एम, एन, ओ, पी, आर। इनमें से प्रत्येक संकेतों को केवल 4 बिट्स के साथ एन्कोड किया जा सकता है: 0000 से 1111 तक। अब कल्पना करें कि इन वर्णों की संभावनाएं निम्नानुसार वितरित की जाती हैं:

बेशक, इन संभावनाओं का योग एक है। आइए इन प्रतीकों को दो समूहों में विभाजित करें ताकि प्रत्येक समूह के प्रतीकों की कुल संभावना ~ 0.5 (छवि) हो। हमारे उदाहरण में, ये समूह होंगे अक्षर ए-बीऔर श्रीमान आकृति में वृत्त, प्रतीकों के समूहों को निरूपित करते हुए, नोड्स या नोड्स कहलाते हैं, और इन नोड्स के निर्माण को ही बाइनरी ट्री (बी-ट्री) कहा जाता है। आइए प्रत्येक नोड को अपना कोड असाइन करें, एक नोड को नंबर 0 के साथ और दूसरे को नंबर 1 के साथ दर्शाते हैं।

आइए हम पहले समूह (AB) को फिर से दो उपसमूहों में विभाजित करें ताकि उनकी कुल संभावनाएँ एक-दूसरे के यथासंभव निकट हों। आइए पहले उपसमूह के कोड में नंबर 0 और दूसरे के कोड में नंबर 1 जोड़ें।

हम इस ऑपरेशन को तब तक दोहराते रहेंगे जब तक कि हमारे "पेड़" के प्रत्येक शीर्ष पर एक प्रतीक न रह जाए। हमारे वर्णमाला के पूरे पेड़ में 31 नोड होंगे।

वर्ण कोड (पेड़ के सबसे दाहिने नोड्स) में असमान लंबाई के कोड होते हैं। तो, अक्षर ए, जिसमें हमारे काल्पनिक पाठ के लिए पी = 0.2 की संभावना है, केवल दो बिट्स के साथ एन्कोड किया गया है, और अक्षर पी (आकृति में नहीं दिखाया गया है), जिसमें पी = 0.013 की संभावना है, के साथ एन्कोड किया गया है छह-बिट संयोजन।

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

जहाँ ni i-वें प्रतीक को कूटबद्ध करने वाले बिट्स की संख्या है, pi i-वें प्रतीक की प्रायिकता है।

हफमैन कोड।

हफ़मैन का एल्गोरिथ्म प्रीफ़िक्स सेट का उपयोग करके एन्ट्रापी कोडिंग के सामान्य विचार को इनायत से लागू करता है और निम्नानुसार काम करता है:

1. वर्णमाला के सभी प्रतीकों को आरोही या अवरोही क्रम में पाठ में उनके प्रकट होने की संभावना के क्रम में लिखें।

2. एक नए संयुक्त प्रतीक में प्रकट होने की सबसे कम संभावनाओं वाले दो प्रतीकों को लगातार संयोजित करें, जिसकी संभावना को इसके घटक प्रतीकों की संभावनाओं के योग के बराबर माना जाता है। अंत में, हम एक पेड़ का निर्माण करेंगे, जिसके प्रत्येक नोड के नीचे सभी नोड्स की कुल संभावना होगी।

3. पेड़ के प्रत्येक पत्ते के लिए पथ का पता लगाएं, प्रत्येक नोड को दिशा चिह्नित करें (उदाहरण के लिए, दाएं - 1, बाएं - 0)। परिणामी अनुक्रम प्रत्येक वर्ण के अनुरूप एक कोड शब्द देता है (चित्र।)

आइए निम्नलिखित वर्णमाला वाले संदेश के लिए एक कोड ट्री बनाएं:

तरीकों के नुकसान

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

इस समस्या का समाधान एन्कोडेड डेटा का सांख्यिकीय विश्लेषण है, जो डेटा पर पहले पास के दौरान किया जाता है, और इसके आधार पर एक कोड ट्री तैयार करता है। इस मामले में, वास्तविक एन्कोडिंग दूसरे पास में किया जाता है।

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

ये कोड वर्णों के बीच संबंधों को ध्यान में नहीं रखते हैं, जो लगभग किसी भी पाठ में मौजूद हैं। उदाहरण के लिए, यदि पाठ on अंग्रेजी भाषाहम अक्षर q का सामना करते हैं, तो हम विश्वास के साथ कह सकते हैं कि अक्षर u उसके बाद आएगा।

रन लेंथ एन्कोडिंग (आरएलई) सबसे पुराने और सरल संग्रह एल्गोरिदम में से एक है। आरएलई में संपीड़न समान बाइट्स के स्ट्रिंग्स को काउंटर-वैल्यू जोड़े के साथ बदलकर होता है। ("लाल, लाल, ..., लाल" को "एन लाल" के रूप में लिखा गया है)।

एल्गोरिदम के कार्यान्वयन में से एक इस प्रकार है: वे कम से कम लगातार बाइट की खोज करते हैं, इसे एक उपसर्ग कहते हैं, और समान वर्णों के तारों को "उपसर्ग, काउंटर, मान" के साथ प्रतिस्थापित करते हैं। यदि यह बाइट स्रोत फ़ाइल में लगातार एक या दो बार होती है, तो इसे "उपसर्ग, 1" या "उपसर्ग, 2" की एक जोड़ी से बदल दिया जाता है। एक अप्रयुक्त जोड़ी "उपसर्ग, 0" है जिसका उपयोग पैक किए गए डेटा के अंत के संकेत के रूप में किया जा सकता है।

Exe फ़ाइलों को एन्कोड करते समय, आप प्रपत्र AxAyAzAwAt ... के अनुक्रमों को खोज और पैक कर सकते हैं, जो अक्सर संसाधनों में पाए जाते हैं (यूनिकोड में एन्कोडेड स्ट्रिंग्स)

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

LZW कोड (लेम्पेल-ज़िव और वेल्च) अब तक के सबसे सामान्य दोषरहित संपीड़न कोडों में से एक है। यह LZW- कोड की मदद से है कि TIFF और GIF जैसे ग्राफिक स्वरूपों में संपीड़न किया जाता है, LZW संशोधनों की मदद से, कई सार्वभौमिक अभिलेखागार अपने कार्य करते हैं। एल्गोरिथ्म का संचालन वर्णों के बार-बार अनुक्रम के लिए इनपुट फ़ाइल की खोज पर आधारित है, जो लंबाई में 8 से 12 बिट्स के संयोजन के साथ एन्कोडेड हैं। इस प्रकार, यह एल्गोरिथम टेक्स्ट फाइलों और ग्राफिक फाइलों पर सबसे प्रभावी है, जिसमें बड़े मोनोक्रोम क्षेत्र या पिक्सल के दोहराए जाने वाले अनुक्रम हैं।

LZW कोडिंग के दौरान सूचना हानि की अनुपस्थिति ने इसके आधार पर TIFF प्रारूप का व्यापक उपयोग किया। यह प्रारूप छवि के आकार और रंग की गहराई पर कोई प्रतिबंध नहीं लगाता है और व्यापक रूप से उपयोग किया जाता है, उदाहरण के लिए, मुद्रण उद्योग में। एक अन्य एलजेडडब्ल्यू-आधारित प्रारूप - जीआईएफ - अधिक आदिम है - यह आपको 8 बिट / पिक्सेल से अधिक की रंग गहराई वाली छवियों को संग्रहीत करने की अनुमति देता है। जीआईएफ फ़ाइल की शुरुआत में एक पैलेट है - एक तालिका जो एक रंग सूचकांक के बीच एक पत्राचार स्थापित करती है - 0 से 255 की सीमा में एक संख्या और एक सही, 24-बिट रंग मान।

हानिपूर्ण संपीड़न एल्गोरिदम

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

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

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

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

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

भग्न संपीड़न

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

भग्न संग्रह इस तथ्य पर आधारित है कि पुनरावृत्त कार्यों की प्रणाली के गुणांकों का उपयोग करके, छवि को अधिक कॉम्पैक्ट रूप में प्रस्तुत किया जाता है। संग्रह प्रक्रिया को देखने से पहले, आइए देखें कि IFS एक छवि कैसे बनाता है।

कड़ाई से बोलते हुए, आईएफएस त्रि-आयामी एफ़िन परिवर्तनों का एक सेट है जो एक छवि को दूसरी छवि में बदल देता है। त्रि-आयामी अंतरिक्ष में बिंदु (x निर्देशांक, y समन्वय, चमक) रूपांतरित हो जाते हैं।

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

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

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

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

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

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

नतीजतन, बिंदु अनिवार्य रूप से मूल छवि में काले क्षेत्र के अंदर कहीं जाएगा। इस ऑपरेशन को कई बार करने के बाद, हम सभी ब्लैक स्पेस को भर देंगे, जिससे तस्वीर वापस आ जाएगी।

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

यह स्पष्ट हो जाता है कि संग्रहकर्ता कैसे काम करता है और इसमें इतना समय क्यों लगता है। वास्तव में, फ्रैक्टल संपीड़न एक छवि में स्वयं-समान क्षेत्रों की खोज है और उनके लिए एफ़िन परिवर्तनों के परिभाषित पैरामीटर हैं।

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

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

जेपीईजी के साथ तुलना

आज, सबसे आम ग्राफिक्स संग्रह एल्गोरिथ्म JPEG है। आइए इसकी तुलना फ्रैक्टल कम्प्रेशन से करें।

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

अंतर तब शुरू होता है जब हम एल्गोरिदम को ज़िप / अनज़िप करने में लगने वाले समय पर विचार करते हैं। इस प्रकार, फ्रैक्टल एल्गोरिथ्म JPEG की तुलना में सैकड़ों या हजारों गुना अधिक समय तक संकुचित होता है। दूसरी ओर, इमेज अनपैकिंग 5-10 गुना तेज होगी। इसलिए, यदि छवि को केवल एक बार संपीड़ित किया जाएगा, लेकिन नेटवर्क पर प्रसारित किया जाएगा और कई बार अनपैक किया जाएगा, तो फ्रैक्टल एल्गोरिथम का उपयोग करना अधिक लाभदायक है।

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

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

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

संग्रहकर्ता

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

संग्रह फ़ाइलएक विशेष रूप से बनाई गई फ़ाइल है जिसमें एक या अधिक संपीड़ित फ़ाइलें होती हैं।

संक्षिप्तीकरण अनुपात: के सी = वी सी / वी ओ * 100%

कश्मीर- संक्षिप्तीकरण अनुपात, वी सी- संपीड़ित फ़ाइल का आकार, वी ओ- फ़ाइल का मूल आकार।

संपीड़न अनुपात इस पर निर्भर करता है:

1) प्रयुक्त कार्यक्रम - संग्रहकर्ता,

2) संपीड़न विधि,

3) स्रोत फ़ाइल का प्रकार: पाठ, ग्राफिक, वीडियो, ध्वनि, आदि।

प्रोग्राम जो फाइलों को पैक और अनपैक करते हैं उन्हें आर्काइव्स कहा जाता है। सबसे आम हैं: एआरजे, ज़िप, आरएआर। संग्रह फ़ाइलों का विस्तार उन्हें बनाने के लिए उपयोग किए जाने वाले संग्रहकर्ता के नाम से मेल खाता है।

अभिलेखागार आपको स्वयं निकालने वाली संग्रह फ़ाइलें बनाने की अनुमति देता है, अर्थात। उन्हें अनपैक करने के लिए, आपको संग्रहकर्ता प्रोग्राम चलाने की आवश्यकता नहीं है, क्योंकि वे स्वयं अनपैकिंग प्रोग्राम रखते हैं। इन अभिलेखागारों को एसएफएक्स अभिलेखागार कहा जाता है
(सेल्फ-एक्सट्रैक्टिंग)। ऐसी फाइलों का विस्तार * .EXE है।

सूचना संपीड़न सिद्धांत

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

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

3. निम्नलिखित सिद्धांत नियमितता का उपयोग करता है कि पाठ में अक्षर विभिन्न आवृत्तियों के साथ होते हैं। उदाहरण के लिए, इस पाठ में स्थान सबसे सामान्य वर्ण है, प्रतीक "ए", "और" बहुत बार पाए जाते हैं। इन सामान्य प्रतीकों को बिट्स के एक छोटे संयोजन द्वारा दर्शाया जा सकता है, शेष प्रतीकों को लंबे अनुक्रम के साथ एन्कोड किया जा सकता है। उदाहरण के लिए:

4. भौतिक रूप से, पीसी 4 केबी ब्लॉक में डिस्क पर फ़ाइलों को क्लस्टर में रखने के लिए स्थान आवंटित करता है। कम उजागर करना असंभव है। उदाहरण के लिए, यदि फ़ाइल 8193 बाइट्स (8 केबी और 1 बाइट) है, तो भौतिक रूप से यह 16 केबी या 16384 बाइट्स होगी। फ़ाइलों के समूह को एक में मिलाने से आप इन बचे हुए को सहेज सकते हैं। छोटी फ़ाइलों को पैक करते समय, यह एक बड़ी बचत है।

कुल मिलाकर, जब फाइलें अलग से रखी जाती हैं, तो 6 केबी का उपयोग नहीं किया जाता है, जो फाइलों की सामग्री का 100% है। दूसरे मामले में, 2 केबी, 33%, अप्रयुक्त रहता है।

ज़िप संग्रहकर्ता

pkzip फ़ाइलें पैक करना [कुंजी]<имя архива>[फ़ाइल पथ]

चांबियाँ: -आरपीसंरचना को ध्यान में रखते हुए उपनिर्देशिकाओं के साथ संग्रह करना

एस लोक निर्माण विभागपुरालेख पासवर्ड सुरक्षा (पीडब्ल्यूडी)

संग्रह में फ़ाइलें जोड़ें

एम फाइलों को संग्रह में ले जाएं

वी संग्रह की सामग्री देखें

यदि निर्देशिका में सभी फ़ाइलें संग्रहीत की जा रही हैं, तो मास्क निर्दिष्ट करना सुनिश्चित करें *.*

pkunzip फ़ाइलें खोलना [कुंजी]<имя архива>[फ़ाइल नाम]

स्विच: -d संरचना को ध्यान में रखते हुए उपनिर्देशिकाओं के साथ अनपैकिंग

एसपीडब्ल्यूडी आर्काइव पासवर्ड (पीडब्ल्यूडी)

अर्ज संग्रहकर्ता

जे<команда>[चांबियाँ]<имя архива>[फ़ाइल नाम]

arj संग्रहकर्ता के लिए, एक फ़ाइल अनपैकिंग और पैकिंग दोनों कार्य करती है।

आदेश: एसंग्रह

ई निर्देशिका संरचना को संरक्षित किए बिना अनपैकिंग

एक्ससंरचना के संरक्षण के साथ अनपैकिंग

मैं संग्रह सामग्री देखें

एम फाइलों को संग्रह में ले जाएं

डी संग्रह से फ़ाइलें हटाएं

स्विचेस: -r संरचना को ध्यान में रखते हुए उपनिर्देशिकाओं के साथ पैकिंग

V वॉल्यूम वॉल्यूम के साथ संग्रह को वॉल्यूम में विभाजित करना (यदि निर्दिष्ट हो)

मानक फ़्लॉपीज़ का आकार (360, 720, 1200, 1440) किलोबाइट में दर्शाया गया है, गैर-मानक फ़्लॉपी का आकार बाइट्स में दर्शाया गया है

मल्टीवॉल्यूम संग्रह को अनपैक करते समय V इंगित किया जाता है

जी लोक निर्माण विभागसंग्रह पासवर्ड ( लोक निर्माण विभाग)

ज़िप फ़ाइलें

फ़ाइलें खोलना

© 2015-2019 साइट
सभी अधिकार उनके लेखकों के हैं। यह साइट लेखकत्व का दावा नहीं करती है, लेकिन मुफ्त उपयोग प्रदान करती है।
पृष्ठ बनने की तिथि: 2016-08-08

गोरकॉफ़ 24 फरवरी, 2015 पूर्वाह्न 11:41 बजे

डेटा संपीड़न के तरीके

• एल्गोरिदम

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

फिलहाल, बड़ी संख्या में दोषरहित संपीड़न एल्गोरिदम हैं, जिन्हें सशर्त रूप से दो बड़े समूहों में विभाजित किया जा सकता है:
1. स्ट्रीम और डिक्शनरी एल्गोरिदम। इस समूह में RLE (रन-लेंथ एन्कोडिंग), LZ *, आदि परिवारों के एल्गोरिदम शामिल हैं। इस समूह के सभी एल्गोरिदम की एक विशेषता यह है कि एन्कोडिंग संदेश में वर्णों की आवृत्तियों के बारे में जानकारी नहीं, बल्कि अनुक्रमों के बारे में जानकारी का उपयोग करता है। जिनका सामना पहले किया गया था।
2. सांख्यिकीय (एन्ट्रॉपी) संपीड़न के लिए एल्गोरिदम। एल्गोरिदम का यह समूह उन आवृत्तियों की असमानता का उपयोग करके जानकारी को संपीड़ित करता है जिसके साथ संदेश में विभिन्न वर्ण होते हैं। इस समूह के एल्गोरिदम में अंकगणित और उपसर्ग कोडिंग के लिए एल्गोरिदम शामिल हैं (शैनन-फैनो, हफमैन, सेकेंड ट्री का उपयोग करके)।
सूचना परिवर्तन एल्गोरिदम को एक अलग समूह में प्रतिष्ठित किया जा सकता है। इस समूह के एल्गोरिदम सीधे जानकारी को संपीड़ित नहीं करते हैं, लेकिन उनका अनुप्रयोग स्ट्रीम, डिक्शनरी और एन्ट्रॉपी एल्गोरिदम का उपयोग करके आगे के संपीड़न को बहुत सरल करता है।

स्ट्रीमिंग और शब्दकोश एल्गोरिदम

रन लेंथ कोडिंग

रन-लेंथ एन्कोडिंग (आरएलई) सबसे सरल और सबसे आम डेटा संपीड़न एल्गोरिदम में से एक है। इस एल्गोरिथम में, दोहराए गए वर्णों के अनुक्रम को एक वर्ण से बदल दिया जाता है और जितनी बार इसे दोहराया जाता है।
उदाहरण के लिए, स्ट्रिंग "AAAAAA", जिसे स्टोर करने के लिए 5 बाइट्स की आवश्यकता होती है (यह मानते हुए कि एक बाइट को एक वर्ण को संग्रहीत करने के लिए आवंटित किया गया है), को "5A" से बदला जा सकता है, जिसमें दो बाइट्स होते हैं। जाहिर है, पुनरावृत्ति श्रृंखला जितनी लंबी होगी, यह एल्गोरिथ्म उतना ही अधिक कुशल होगा।

इस एल्गोरिथम का मुख्य नुकसान गैर-दोहराए जाने वाले वर्णों के अनुक्रमों पर इसकी अत्यंत कम दक्षता है। उदाहरण के लिए, यदि हम अनुक्रम "ABABAB" (6 बाइट्स) पर विचार करते हैं, तो RLE एल्गोरिथम लागू करने के बाद यह "1A1B1A1B1A1B" (12 बाइट्स) में बदल जाएगा। गैर-दोहराए जाने वाले पात्रों की समस्या से निपटने के लिए विभिन्न तरीके हैं।

सबसे सरल तरीका निम्नलिखित संशोधन है: दोहराव की संख्या को बाइट एन्कोडिंग न केवल दोहराने की संख्या के बारे में, बल्कि उनकी उपस्थिति के बारे में भी जानकारी संग्रहीत करनी चाहिए। यदि पहला बिट 1 है, तो अगले 7 बिट्स संबंधित वर्ण के दोहराव की संख्या को इंगित करते हैं, और यदि पहला बिट 0 है, तो अगले 7 बिट्स वर्णों की संख्या को इंगित करते हैं जिन्हें बिना दोहराव के लिया जाना चाहिए। यदि आप इस संशोधन का उपयोग करके "ABABAB" को एनकोड करते हैं, तो हमें "-6ABABAB" (7 बाइट्स) मिलता है। जाहिर है, प्रस्तावित तकनीक वर्णों के गैर-दोहराए जाने वाले अनुक्रमों पर RLE एल्गोरिथम की दक्षता में काफी सुधार कर सकती है। प्रस्तावित दृष्टिकोण का कार्यान्वयन सूची 1 में दिखाया गया है:

1. प्रकार
2. समारोह RLEEncode (InMsg: शॉर्टस्ट्रिंग): TRLEncodedString;
3. मैचफ्ल: बूलियन;
4. मैचकाउंट: शॉर्टिंट;
5. एन्कोडेडस्ट्रिंग: TRLEncodedString;
6. एन, मैं: बाइट;
7. शुरू
8. एन: = 0;
9. सेटलेंथ (एन्कोडेडस्ट्रिंग, 2 * लंबाई (इनएमएसजी));
10. जबकि लंबाई (InMsg)> = 1 do
11. शुरू
12. MatchFl: = (लंबाई (InMsg)> 1) और (InMsg [1] = InMsg [2]);
13. मैचकाउंट: = 1;
14. जबकि (मैचकाउंट<= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
15. मैचकाउंट: = मैचकाउंट + 1;
16. अगर मैचफ्ल तो
17. शुरू
18. एन: = एन + 2;
19. एन्कोडेडस्ट्रिंग [एन - 2]: = मैचकाउंट + 128;
20. एन्कोडेडस्ट्रिंग [एन -1]: = ऑर्ड (इनएमएसजी [1]);
21. अन्यथा
22. शुरू
23. अगर मैचकाउंट<>लंबाई (InMsg) तब
24. मैचकाउंट: = मैचकाउंट - 1;
25. एन: = एन + 1 + मैचकाउंट;
26. एन्कोडेडस्ट्रिंग [एन -1 - मैचकाउंट]: = - मैचकाउंट + 128;
27. i के लिए: = 1 से MatchCount do
28. एन्कोडेडस्ट्रिंग [एन -1 - मैचकाउंट + आई]: = ऑर्ड (इनएमएसजी [i]);
29. समाप्त;
30. हटाएं (इनएमएसजी, 1, मैचकाउंट);
31. समाप्त;
32. सेटलेंथ (एन्कोडेडस्ट्रिंग, एन);
33. आरएलईएनकोड: = एनकोडेडस्ट्रिंग;
34. समाप्त;

एक संपीड़ित संदेश को डिकोड करना बहुत सरल है और संकुचित संदेश पर एक ही पास तक उबाल जाता है, सूचीकरण 2 देखें:

1. प्रकार
2. TRLEncodedString = बाइट की सरणी;
3. समारोह RLEDecode (InMsg: TRLEncodedString): शॉर्टस्ट्रिंग;
4. रिपीटकाउंट: शॉर्टिंट;
5. मैं, जे: शब्द;
6. आउट संदेश: शॉर्टस्ट्रिंग;
7. शुरू
8. आउट संदेश: = "";
9. मैं: = 0;
10. मैं जबकि< length(InMsg) do
11. शुरू
12. रिपीटकाउंट: = इनएमएसजी [i] - 128;
13. मैं: = मैं + 1;
14. अगर रिपीटकाउंट< 0 then
15. शुरू
16. रिपीटकाउंट: = एब्स (रिपीटकाउंट);
17. j के लिए: = i से i + रिपीटकाउंट - 1 do
18. OutMsg: = OutMsg + chr (InMsg [j]);
19. i: = i + रिपीटकाउंट;
20. अन्यथा
21. शुरू
22. j के लिए: = 1 दोहराएँ करने के लिए do
23. OutMsg: = OutMsg + chr (InMsg [i]);
24. मैं: = मैं + 1;
25. समाप्त;
26. समाप्त;
27. आरएलईडीकोड: = आउटएमएसजी;
28. समाप्त;

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

1. स्थिरांक
2. ईओएमएसजी = "|" ;
3. समारोह BWTEncode (InMsg: शॉर्टस्ट्रिंग): शॉर्टस्ट्रिंग;
4. आउट संदेश: शॉर्टस्ट्रिंग;
5. LastChar: ANSIChar;
6. एन, मैं: शब्द;
7. शुरू
8. InMsg: = InMsg + EOMsg;
9. एन: = लंबाई (इनएमएसजी);
10. शिफ्टटेबल [1]: = इनएमएसजी;
11. i के लिए: = 2 से N do
12. शुरू
13. लास्टचर: = इनएमएसजी [एन];
14. InMsg: = LastChar + copy (InMsg, 1, N-1);
15. शिफ्टटेबल [i]: = इनएमएसजी;
16. समाप्त;
17. क्रमबद्ध करें (ShiftTable);
18. आउट संदेश: = "";
19. i के लिए: = 1 से N do
20. OutMsg: = OutMsg + ShiftTable [i] [N];
21. बीडब्ल्यूटीईएनकोड: = आउटएमएसजी;
22. समाप्त;

इस परिवर्तन को समझाने का सबसे आसान तरीका एक विशिष्ट उदाहरण है। आइए स्ट्रिंग "ANANAS" लें और सहमत हों कि अंतिम वर्ण "|" का प्रतीक होगा। इस रेखा के सभी चक्रीय क्रमपरिवर्तन और उनकी शब्दावली छँटाई के परिणाम तालिका में दिखाए गए हैं। एक।

वे। प्रत्यक्ष रूपांतरण का परिणाम स्ट्रिंग "| " होगा। यह देखना आसान है कि यह स्ट्रिंग मूल स्ट्रिंग की तुलना में बहुत बेहतर है; यह RLE एल्गोरिथम द्वारा संकुचित है, क्योंकि इसमें दोहराए गए अक्षरों के लंबे क्रम शामिल हैं।
अन्य परिवर्तनों की मदद से एक समान प्रभाव प्राप्त किया जा सकता है, लेकिन बीडब्ल्यूटी ट्रांसफ़ॉर्म का लाभ यह है कि यह प्रतिवर्ती है, हालांकि, उलटा परिवर्तन प्रत्यक्ष की तुलना में अधिक कठिन है। मूल स्ट्रिंग को पुनर्स्थापित करने के लिए, आपको निम्न कार्य करने होंगे:
एक खाली n * n मैट्रिक्स बनाएं, जहां n एन्कोडेड संदेश में वर्णों की संख्या है;
एन्कोडेड संदेश के साथ सबसे दाहिना खाली कॉलम भरें;
लेक्सिकोग्राफिक क्रम में तालिका पंक्तियों को क्रमबद्ध करें;
चरण 2-3 को तब तक दोहराएं जब तक कि खाली कॉलम न हों;
वह रेखा लौटाएं जो अंत-पंक्ति वर्ण के साथ समाप्त होती है।

पहली नज़र में, रिवर्स ट्रांसफ़ॉर्मेशन सीधा है, और विकल्पों में से एक लिस्टिंग 4 में दिखाया गया है।

1. स्थिरांक
2. ईओएमएसजी = "|" ;
3. समारोह BWTDecode (InMsg: शॉर्टस्ट्रिंग): शॉर्टस्ट्रिंग;
4. आउट संदेश: शॉर्टस्ट्रिंग;
5. शिफ्टटेबल: शॉर्टस्ट्रिंग की सरणी;
6. एन, आई, जे: शब्द;
7. शुरू
8. आउट संदेश: = "";
9. एन: = लंबाई (इनएमएसजी);
10. सेटलेंथ (ShiftTable, N + 1);
11. i के लिए: = 0 से N do
12. शिफ्टटेबल [i]: = "";
13. i के लिए: = 1 से N do
14. शुरू
15. j के लिए: = 1 से N do
16. शिफ्टटेबल [जे]: = इनएमएसजी [जे] + शिफ्टटेबल [जे];
17. क्रमबद्ध करें (ShiftTable);
18. समाप्त;
19. i के लिए: = 1 से N do
20. अगर शिफ्टटेबल [i] [एन] = ईओएमएसजी तो
21. आउट संदेश: = शिफ्टटेबल [i];
22. हटाएं (आउटएमएसजी, एन, 1);
23. बीडब्ल्यूटीडीकोड: = आउटएमएसजी;
24. समाप्त;

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

सातवें चरण में प्राप्त तालिका को छाँटने के बाद, तालिका से "|" वर्ण के साथ समाप्त होने वाली एक पंक्ति का चयन करना आवश्यक है। यह देखना आसान है कि यह एकमात्र पंक्ति है। वह। हमने एक विशिष्ट उदाहरण का उपयोग करके BWT परिवर्तन की जांच की।

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

शब्दकोश संपीड़न (एलजेड एल्गोरिदम)

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

शब्दकोश एल्गोरिथ्म का सबसे सरल संस्करण नीचे वर्णित है:
इनपुट स्ट्रिंग में प्रकट होने वाले सभी वर्णों के साथ शब्दकोश को प्रारंभ करें;
शब्दकोश में सबसे लंबा अनुक्रम (एस) खोजें जो एन्कोडेड संदेश की शुरुआत से मेल खाता हो;
पाए गए अनुक्रम का कोड जारी करें और इसे एन्कोडेड संदेश की शुरुआत से हटा दें;
यदि संदेश का अंत नहीं हुआ है, तो अगला अक्षर पढ़ें और शब्दकोश में Sc जोड़ें, चरण 2 पर जाएं। अन्यथा, बाहर निकलें।

उदाहरण के लिए, "CUCKOOKUCHONKUPILACAPUCHON" वाक्यांश के लिए नई आरंभिक शब्दावली तालिका में दिखाई गई है। 3:

संपीड़न प्रक्रिया के दौरान, संदेश में पाए जाने वाले अनुक्रमों के साथ शब्दकोश को पूरक किया जाएगा। शब्दकोश को फिर से भरने की प्रक्रिया तालिका में दिखाई गई है। 4.

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

सबसे पहले, आइए एक डिक्शनरी को एक रिकॉर्ड के रूप में परिभाषित करें जो न केवल पाए गए सबस्ट्रिंग को स्टोर करता है, बल्कि डिक्शनरी में स्टोर किए गए सबस्ट्रिंग्स की संख्या भी:

पहले सामने आए बाद के क्रम Words सरणी में संग्रहीत किए जाते हैं, और उनके कोड इस सरणी में बाद की संख्या होते हैं।
हम शब्दकोश में खोजने और शब्दकोश में जोड़ने के लिए कार्यों को भी परिभाषित करते हैं:

1. स्थिरांक
2. MAX_DICT_LENGTH = 256;
3. फ़ंक्शन FindInDict (D: TDictionary; str: ShortString): पूर्णांक;
4. आर: पूर्णांक;
5. मैं: पूर्णांक;
6. फ्लो: बूलियन;
7. शुरू
8. आर: = - 1;
9. अगर डी। वर्डकाउंट> 0 तो
10. शुरू
11. i: = डी. वर्डकाउंट;
12. एफएल: = झूठा;
13. जबकि (fl नहीं) और (i> = 0) do
14. शुरू
15. मैं: = मैं - 1;
16. fl: = D. शब्द [i] = str;
17. समाप्त;
18. समाप्त;
19. अगर fl तो
20. आर: = मैं;
21. FindInDict: = r;
22. समाप्त;
23. प्रक्रिया AddToDict (var D: TDictionary; str: ShortString);
24. शुरू
25. अगर डी। वर्डकाउंट< MAX_DICT_LENGTH then
26. शुरू
27. डी। वर्डकाउंट: = डी। वर्डकाउंट + 1;
28. सेटलेंथ (डी। वर्ड्स, डी। वर्डकाउंट);
29. डी शब्द [डी वर्डकाउंट - 1]: = str;
30. समाप्त;
31. समाप्त;

इन कार्यों का उपयोग करके, वर्णित एल्गोरिथम के अनुसार कोडिंग प्रक्रिया को निम्नानुसार लागू किया जा सकता है:

1. समारोह LZWEncode (InMsg: शॉर्टस्ट्रिंग): TEncodedString;
2. आउट संदेश: टेनकोडेडस्ट्रिंग;
3. tmpstr: शॉर्टस्ट्रिंग;
4. डी: टीडिक्शनरी;
5. मैं, एन: बाइट;
6. शुरू
7. सेटलेंथ (आउटएमएसजी, लंबाई (आईएनएमएसजी));
8. एन: = 0;
9. इनिटडिक्ट (डी);
10. जबकि लंबाई (InMsg)> 0 do
11. शुरू
12. tmpstr: = इनएमएसजी [1];
13. जबकि (FindInDict (D, tmpstr)> = 0) और (लंबाई (InMsg)> लंबाई (tmpstr)) करते हैं
14. tmpstr: = tmpstr + InMsg [लंबाई (tmpstr) + 1];
15. अगर FindInDict (डी, tmpstr)< 0 then
16. हटाएं (tmpstr, लंबाई (tmpstr), 1);
17. आउट संदेश [एन]: = FindInDict (डी, tmpstr);
18. एन: = एन + 1;
19. हटाएं (InMsg, 1, लंबाई (tmpstr));
20. अगर लंबाई (InMsg)> 0 तो
21. AddToDict (डी, tmpstr + InMsg [1]);
22. समाप्त;
23. सेटलेंथ (आउटएमएसजी, एन);
24. LZWEncode: = आउटएमएसजी;
25. समाप्त;

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

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

1. समारोह LZWDecode (InMsg: TEncodedString): शॉर्टस्ट्रिंग;
2. डी: टीडिक्शनरी;
3. आउट संदेश, tmpstr: शॉर्टस्ट्रिंग;
4. मैं: बाइट;
5. शुरू
6. आउट संदेश: = "";
7. tmpstr: = "";
8. इनिटडिक्ट (डी);
9. i के लिए: = 0 से लंबाई (InMsg) - 1 do
10. शुरू
11. अगर InMsg [i]> = D. वर्डकाउंट तो
12. tmpstr: = D. शब्द [InMsg [i - 1]] + D. शब्द [InMsg [i - 1]] [1]
13. अन्यथा
14. tmpstr: = D. शब्द [InMsg [i]];
15. आउट संदेश: = आउट संदेश + tmpstr;
16. अगर मैं> 0 तो
17. AddToDict (D, D. Words [InMsg [i - 1]] + tmpstr [1]);
18. समाप्त;
19. एलजेडडब्ल्यूडीकोड: = आउटएमएसजी;
20. समाप्त;

शब्दकोश एल्गोरिदम के लाभों में RLE की तुलना में उनकी उच्च संपीड़न दक्षता शामिल है। फिर भी, यह समझा जाना चाहिए कि इन एल्गोरिदम का वास्तविक उपयोग कुछ कार्यान्वयन कठिनाइयों से जुड़ा है।

एन्ट्रापी कोडिंग

शैनन-फ़ानो पेड़ों के साथ एन्कोडिंग

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

एन्कोडिंग के बिना, संदेश 40 बिट्स पर कब्जा कर लेगा (यह मानते हुए कि प्रत्येक वर्ण 4 बिट्स के साथ एन्कोड किया गया है), और शैनन-फ़ानो एल्गोरिथम 4 * 2 + 2 + 4 + 4 + 3 + 3 + 3 = 27 बिट्स का उपयोग करते हुए। संदेश की मात्रा में 32.5% की कमी आई है, लेकिन यह नीचे दिखाया जाएगा कि इस परिणाम में काफी सुधार किया जा सकता है।

हफमैन पेड़ के साथ एन्कोडिंग

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

उसी उदाहरण पर विचार करें जैसे शैनन-फ़ानो एल्गोरिथम के मामले में। हफ़मैन ट्री और "AAAAABVGDEZH" संदेश के लिए प्राप्त कोड अंजीर में दिखाए गए हैं। 2:

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

सिकंट फंक्शन ट्री के साथ एन्कोडिंग

सेकेंड फ़ंक्शन का उपयोग करके एन्कोडिंग लेखकों द्वारा विकसित एक एल्गोरिदम है जो उपसर्ग कोड प्राप्त करने की अनुमति देता है। एल्गोरिथ्म एक पेड़ के निर्माण के विचार पर आधारित है, जिसके प्रत्येक नोड में एक सेकेंडरी फ़ंक्शन होता है। एल्गोरिथ्म का अधिक विस्तार से वर्णन करने के लिए, कई परिभाषाओं को पेश करना आवश्यक है।
एक शब्द m बिट्स का एक क्रमबद्ध क्रम है (संख्या m को शब्द की लंबाई कहा जाता है)।
सेकेंड लिटरल अंक के अंक-मान के प्रकार की एक जोड़ी है। उदाहरण के लिए, शाब्दिक (4,1) का अर्थ है कि शब्द के 4 बिट 1 होने चाहिए। यदि शाब्दिक शर्त पूरी होती है, तो शाब्दिक को सत्य माना जाता है, अन्यथा यह गलत है।
एक k-bit secant k अक्षर का एक सेट है। यदि सभी अक्षर सत्य हैं, तो सेकेंट फ़ंक्शन स्वयं सत्य है, अन्यथा यह असत्य है।

पेड़ बनाया गया है ताकि प्रत्येक नोड वर्णमाला को निकटतम संभव भागों में विभाजित करे। अंजीर में। 3 एक छेदक वृक्ष का एक उदाहरण दिखाता है:

सामान्य स्थिति में सेकेंट फ़ंक्शंस का पेड़ इष्टतम कोडिंग की गारंटी नहीं देता है, लेकिन यह नोड्स में ऑपरेशन की सादगी के कारण काम की अत्यधिक उच्च गति प्रदान करता है।

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

अंकगणित कोडिंग सबसे अधिक में से एक है प्रभावी तरीकेसूचना का संपीड़न। हफ़मैन एल्गोरिथ्म के विपरीत, अंकगणितीय कोडिंग आपको प्रति प्रतीक 1 बिट से कम की एन्ट्रापी वाले संदेशों को एन्कोड करने की अनुमति देती है। चूंकि अधिकांश अंकगणितीय कोडिंग एल्गोरिदम पेटेंट द्वारा संरक्षित हैं, केवल मूल विचारों का वर्णन नीचे किया जाएगा।
मान लीजिए कि प्रयुक्त वर्णमाला में क्रमशः p_1, ..., p_N, आवृत्तियों के साथ N प्रतीक a_1, ..., a_N हैं। तब अंकगणित कोडिंग एल्गोरिथ्म इस तरह दिखेगा:
एक कार्यशील अर्ध-अंतराल के रूप में लें)