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

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

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

RLE - कॉम्पैक्ट एकरूपता

आरएलई एल्गोरिथ्म शायद सभी में सबसे सरल है: इसका सार दोहराव को एनकोड करना है। दूसरे शब्दों में, हम समान तत्वों के अनुक्रम लेते हैं और उन्हें मात्रा / मूल्य जोड़े में "ढहते" हैं। उदाहरण के लिए, "AAAAAAAABCCCC" जैसी स्ट्रिंग को "8 × A, B, 4 × 4" जैसे रिकॉर्ड में बदला जा सकता है। यह, सामान्य तौर पर, आपको एल्गोरिथ्म के बारे में जानने की आवश्यकता है।

कार्यान्वयन का उदाहरण

मान लें कि हमारे पास कुछ पूर्णांक गुणांक का एक सेट है जो 0 से 255 तक मान ले सकता है। तार्किक तरीके से, हम इस निष्कर्ष पर पहुंचे कि इस सेट को बाइट्स के रूप में संग्रहीत करना उचित है:

unsigned char data[] = { 0, 0, 0, 0, 0, 0, 4, 2, 0, 4, 4, 4, 4, 4, 4, 4, 80, 80, 80, 80, 0, 2, 2, 2, 2, 255, 255, 255, 255, 255, 0, 0 }; 

कई लोगों के लिए, यह डेटा को हेक्स डंप के रूप में देखने के लिए अधिक परिचित होगा:
0000: 00 00 00 00 00 00 04 02 00 04 04 04 04 04 04 04
0010: 50 50 50 50 00 02 02 02 02 FF FF FF FF FF 00 00

यह सोचते हुए, हमने फैसला किया कि किसी भी तरह से अंतरिक्ष को बचाने के लिए ऐसे सेट को सेक करना अच्छा होगा। ऐसा करने के लिए, हमने उनका विश्लेषण किया और एक पैटर्न का खुलासा किया: बहुत बार समान तत्वों से मिलकर बाद में आते हैं। बेशक, RLE इसके लिए सिर्फ सही फिट है!

हम ताजा प्राप्त ज्ञान का उपयोग करके अपने डेटा को एनकोड करते हैं: 6 × 0, 4, 2, 0, 7 × 4, 4 × 80, 0, 4 × 2, 5 × 255, 2 × 0।

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

इस स्थिति से कम से कम दो तरीके हैं:

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

हमारे मामले में पहली विधि प्रभावी नहीं लगती है, इसलिए, शायद, हम दूसरे का सहारा लेंगे।

तो, अब हमारे पास दो प्रकार के अनुक्रम हैं: एकल तत्वों की श्रृंखला (जैसे "4, 2, 0") और समान तत्वों की श्रृंखलाएं (जैसे "0, 0, 0, 0, 0, 0")। "सेवा" बाइट्स में, अनुक्रम प्रकार के लिए एक बिट का चयन करें: 0 - एकल तत्व, 1 - समान। इसके लिए कहें, एक बाइट का सबसे महत्वपूर्ण बिट।

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

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

पहली चीज जो आपकी आंख को पकड़नी चाहिए - इस स्थिति में, हमारे पास अप्रयुक्त मूल्यों की एक जोड़ी है। शून्य लंबाई के साथ कोई अनुक्रम नहीं हो सकता है, इसलिए हम अधिकतम लंबाई को 128 बाइट्स तक बढ़ा सकते हैं, एन्कोडिंग के दौरान लंबाई से एक घटाकर और डिकोडिंग के दौरान जोड़ सकते हैं। इस प्रकार, हम 0 से 127 तक की लंबाई के बजाय 1 से 128 तक लंबाई सांकेतिक शब्दों में बदल सकते हैं।

ध्यान देने वाली दूसरी बात यह है कि इकाई लंबाई के समान तत्वों के क्रम नहीं हैं। इसलिए, हम एन्कोडिंग के दौरान ऐसे अनुक्रमों की लंबाई के मूल्य से एक और इकाई को घटाएंगे, जिससे उनकी अधिकतम लंबाई 129 हो जाएगी (एकल तत्वों की श्रृंखला की अधिकतम लंबाई अभी भी 128 के बराबर है)। यानी समान तत्वों की श्रृंखलाओं की लंबाई 2 से 129 हो सकती है।

हम अपने डेटा को फिर से एन्कोड करते हैं, लेकिन अब कंप्यूटर के अनुकूल तरीके से। हम ओवरहेड बाइट्स को [T | L] के रूप में लिखेंगे, जहाँ T अनुक्रम का प्रकार है और L लंबाई है। हम तुरंत ध्यान में रखेंगे कि हम लंबाई को एक परिवर्तित रूप में लिखते हैं: T = 0 पर हम L से एक घटाते हैं, T = 1 में हम दो लेते हैं।

[१ | ४] , ०, [० | २] , ४, २, ०, [१ | ५] , ४, [१ | २] , , ० , [० | ०] , ०, [१ | २] | २, [१ | ३] , २५५, [१ | ०] , ०

आइए हमारे परिणाम को डिकोड करने का प्रयास करें:

• [१ | ४] । टी = 1, फिर अगले बाइट को L + 2 (4 + 2) बार दोहराया जाएगा: 0, 0, 0, 0, 0, 0।
• [० | २] । T = 0, इसलिए अभी L + 1 (2 + 1) बाइट्स पढ़ें: 4, 2, 0।
• [१ | ५] । टी = 1, अगले बाइट को 5 + 2 बार दोहराएं: 4, 4, 4, 4, 4, 4, 4, 4।
• [१ | २] । टी = 1, अगले बाइट को 2 + 2 बार दोहराएं: 80, 80, 80, 80।
• [० | ०] । टी = 0, 0 + 1 बाइट्स पढ़ें: 0।
• [१ | २] । टी = 1, बाइट को 2 + 2 बार दोहराएं: 2, 2, 2, 2।
• [१ | ३] । टी = 1, बाइट को 3 + 2 बार दोहराएं: 255, 255, 255, 255, 255।
• [१ | ०] । टी = 1, बाइट को 0 + 2 बार दोहराएं: 0, 0।

और अब अंतिम चरण: परिणाम को बाइट्स के एक सरणी के रूप में सहेजें। उदाहरण के लिए, बाइट्स में पैक एक जोड़ी [1 | 4] इस तरह दिखेगी:


परिणामस्वरूप, हमें निम्नलिखित मिलते हैं:
0000: 84 00 02 04 02 00 85 04 82 80 00 82 82 83 एफएफ
0010: 80 00

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

संभव सुधार

एल्गोरिथ्म की प्रभावशीलता न केवल एल्गोरिथ्म पर ही निर्भर करती है, बल्कि यह भी कि यह कैसे लागू किया जाता है। इसलिए, विभिन्न डेटा के लिए, एन्कोड किए गए डेटा के विभिन्न कोडिंग विविधताएं और प्रतिनिधित्व विकसित किए जा सकते हैं। उदाहरण के लिए, जब छवियों को एन्कोडिंग करते हैं, तो आप चर लंबाई की श्रृंखला बना सकते हैं: लंबी श्रृंखला के संकेत के लिए एक बिट का चयन करें, और यदि यह एक पर सेट है, तो अगले बाइट में भी लंबाई स्टोर करें। इसलिए हम छोटी श्रृंखलाओं (129 के बजाय 65 तत्वों) की लंबाई का त्याग करते हैं, लेकिन फिर हम केवल 3 बाइट्स (2 ¹⁴ + 2) के साथ लंबाई में 16385 तत्वों तक श्रृंखलाओं को एनकोड करने का अवसर देते हैं!

ह्यूरिस्टिक कोडिंग विधियों का उपयोग करके अतिरिक्त दक्षता हासिल की जा सकती है। उदाहरण के लिए, हम निम्नलिखित श्रृंखला को अपने तरीके से कोड करते हैं: "एबीबीए"। हमें " [0 | 0] , ए, [1 | 0] , बी, [0 | 0] , ए" - यही है। हमने 4 बाइट्स को 6 में बदल दिया, स्रोत डेटा को 1.5 गुना बढ़ा दिया! और इस तरह के कम बारी-बारी से विषम अनुक्रम, अधिक अनावश्यक डेटा। यदि हम इसे ध्यान में रखते हैं, तो हम परिणाम को " [0 | 3] , ए, बी, बी, ए" के रूप में संलग्न कर सकते हैं - हम केवल एक अतिरिक्त बाइट खर्च करेंगे।

LZ77 - पुनरावृत्ति में संक्षिप्तता

LZ77 LZ परिवार में सबसे सरल और सबसे प्रसिद्ध एल्गोरिदम में से एक है। अपने रचनाकारों के सम्मान में नामित: अब्राहम लेम्पेल (अब्राहम एल साम्राज्य) और जैकब जिवा (जैकब जेड iv)। शीर्षक में संख्या 77 का अर्थ वर्ष 1977 है, जिसमें इस एल्गोरिथम का वर्णन करते हुए एक लेख प्रकाशित किया गया था।

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

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

कार्यान्वयन का उदाहरण

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

"संपीड़न और विघटन एक छाप छोड़ते हैं। हाहाहाहाहा ”!

यहां बताया गया है कि यह मेमोरी में कैसे दिखेगा (ANSI एन्कोडिंग):
0000: 54 68 65 20 63 6F 6D 70 72 65 73 73 69 6F 6E 20 The compression
0010: 61 6E 64 20 74 68 65 20 64 65 63 6F 6D 70 72 65 and the decompre
0020: 73 73 69 6F 6E 20 6C 65 61 76 65 20 61 6E 20 69 ssion leave an i
0030: 6D 70 72 65 73 73 69 6F 6E 2E 20 48 61 68 61 68 mpression. Hahah
0040: 61 68 61 68 61 21 ahaha!

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

"संपीड़न और टी [वह] डे [संपीड़न] छोड़ [ ए ] मैं [एमप्रेशन] । हह [आआहहह] ! "

अधिक स्पष्टता के लिए, आइए एक आरेख देखें जहां बार-बार अनुक्रमों के पत्राचार और उनकी पहली घटनाएं दिखाई देती हैं:



शायद यहाँ एकमात्र अस्पष्ट बिंदु अनुक्रम "हाहाहाहा!" है, क्योंकि "अहाहा" वर्णों का तार एक छोटी श्रृंखला "आह" से मेल खाता है। लेकिन यहां कुछ भी असामान्य नहीं है, हमने कुछ तकनीक का इस्तेमाल किया जो एल्गोरिदम को कभी-कभी आरएलई द्वारा पहले बताए गए अनुसार काम करने देता है।

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


हमने इसका पता लगा लिया। अब हम पाए गए पुनरावृत्तियों को शब्दकोश के संदर्भ में बदल देते हैं। हम लिंक को प्रारूप [P | L] में दर्ज करेंगे, जहां P स्ट्रिंग में श्रृंखला की पहली घटना की स्थिति है, L इसकी लंबाई है।

"संपीड़न और टी [२२ | ३] डी [५ | १२] छोड़ दो [१६ | ३] मैं [7 |]] । हह [६१ | ! ] ! "

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

"संपीड़न और टी [२० | ३] डी [२२ | १२] छोड़ दो [२] | ३] मैं [४२ | । ] । हह [२ | ! ] ! "

अब हमें स्ट्रिंग में निरपेक्ष स्थिति प्राप्त करने के लिए वर्तमान एन्कोडिंग स्थिति से P को घटाना होगा।

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

लेकिन यह खिड़की के आकार पर निर्भर करता है कि हम समान श्रृंखलाओं के लिए कितनी गहराई से देखेंगे। चूंकि हम छोटे ग्रंथों के साथ काम कर रहे हैं, इसलिए दो बाइट्स के साथ हमारे द्वारा उपयोग किए जाने वाले बिट्स की संख्या को पूरक करना सही होगा: हम 4096 बाइट्स की सीमा में लिंक को संबोधित करेंगे, इसके लिए 12 बिट्स का उपयोग करेंगे।

आरएलई के साथ हमारे अनुभव से, हम जानते हैं कि सभी मूल्यों का उपयोग नहीं किया जा सकता है। जाहिर है, लिंक का न्यूनतम मान 1 हो सकता है, इसलिए 1.40.4096 की सीमा में पिछड़े को संबोधित करने के लिए, हमें एन्कोडिंग करते समय लिंक से एक को घटाना होगा, और डिकोडिंग के समय वापस जोड़ना होगा। अनुक्रम लंबाई के साथ समान: 0..15 के बजाय हम सीमा 2..17 का उपयोग करेंगे, क्योंकि हम शून्य लंबाई के साथ काम नहीं करते हैं, और व्यक्तिगत वर्ण अनुक्रम नहीं हैं।

तो, इन सुधारों के साथ हमारे एन्कोडेड पाठ की कल्पना करें:

"संपीड़न और टी [१ ९ | १] डे [२१ | १०] छोड़ दो [२ 41 | १] मैं [४१ | ५] । हह [१ | ५] ! "

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

हम समूहों में विभाजित करते हैं:

• "द कम्प"
• «Ression»
• "और टी [19 | 1] डे"
• " [21 | 10] छुट्टी [27 | 1] "
• “मैं [४१ | ५] । हह [२ | ५] »
• "!"

हम समूह बनाते हैं:

{{0,0,0,0,0,0,0,0,0} COMP {0,0,0,0,0,0,0,0,0} छापा {0,0,0,0,0,0,01 , 0,0} और टी [19 | 1] de {1,0,0,0,0,0,1,0} [21 | 10 | छुट्टी [27 | 1] {0,1,0,0 | 0,0,0,1} i [41 | 5] । हह [१ | ५] {०} ! "

इस प्रकार, यदि अनपैकिंग के दौरान हमारा बिट 0 से सामना होता है, तो हम केवल चरित्र को आउटपुट स्ट्रीम में पढ़ते हैं, यदि बिट 1, हम लिंक को पढ़ते हैं, और लिंक को पढ़कर हम शब्दकोश से अनुक्रम पढ़ते हैं।

अब हमें परिणाम को बाइट्स के एक समूह में बदलना है। हम इस बात से सहमत हैं कि हम बिट्स और बाइट्स का उपयोग उच्चतम से निम्नतम क्रम में करते हैं। आइए देखें कि उदाहरण [19 | 1] का उपयोग करके लिंक को बाइट में कैसे पैक किया जाता है:



परिणामस्वरूप, हमारी संकुचित धारा इस तरह दिखाई देगी:

0000: 00 54 68 65 20 63 6f 6d 70 70 72 72 73 73 69 6f # COMP # ressio
0010: 6e 20 04 61 6e 64 20 74 01 31 64 65 82 01 5a 6c n #and t ## de ### l
0020: 65 61 76 65 01 b1 20 41 69 02 97 2e 20 48 61 68 eave ## # i ##। हा
0030: 00 15 00 21 00 00 00 00 00 00 00 00 00 00 ###!

संभव सुधार

असल में, RLE के लिए वर्णित सब कुछ यहाँ सच होगा। विशेष रूप से, कोडिंग में अनुमानी दृष्टिकोण की उपयोगिता प्रदर्शित करने के लिए, निम्नलिखित उदाहरण पर विचार करें:

“लंबा गुओंग। लूडोवर बाध्य है। "

हमें केवल "loooooower" शब्द के लिए अनुक्रम मिलते हैं:

“लंबा गुओंग। [लो] [ooooo] बाध्य थे। "

इस तरह के परिणाम को एनकोड करने के लिए, हमें प्रति लिंक चार बाइट्स की आवश्यकता होती है। हालाँकि, ऐसा करना अधिक किफायती होगा:

“लंबा गुओंग। एल [oooooo] बाध्य थे। "

फिर हम एक-एक बाइट कम खर्च करते।

एक निष्कर्ष के बजाय

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

उनका प्लस सादगी और गति है, और अधिक जटिल और कुशल एल्गोरिदम उनके सिद्धांतों और उनके संयोजन पर आधारित हो सकते हैं।

मुझे उम्मीद है कि इस तरह वर्णित इन एल्गोरिदम का सार किसी को मूल बातें समझने और अधिक गंभीर चीजों की दिशा में देखने में मदद करेगा।