डेटा कम्प्रेशन में प्रयुक्त एल्गोरिदम

प्रविष्टि

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

हफ़मैन एल्गोरिदम

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

कोड बिल्डिंग

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

• एबीसी
• ४ २ १

हम बी और सी की प्रक्रिया करते हैं

अगला कदम एक ऐसे पेड़ का निर्माण करना है जहां कोने "प्रतीक" हैं और उनके लिए पथ उनके उपसर्ग कोड के अनुरूप हैं। ऐसा करने के लिए, प्रत्येक चरण में हम दो पात्रों को न्यूनतम घटना आवृत्ति के साथ लेंगे, और उन्हें नए तथाकथित वर्णों में संयोजित करेंगे, जिनके साथ हम संयुक्त होते हैं, और उन्हें किनारों से जोड़ते हैं, इस प्रकार एक पेड़ बनाते हैं (आकृति देखें)। हम उन सभी वर्णों से न्यूनतम दो वर्णों को चुनेंगे, जिन्हें हमने पहले ही चुना है। उदाहरण में, हम वर्ण b और c को वर्ण bc में 3 की आवृत्ति के साथ जोड़ते हैं। अगला, a और bc को वर्ण abc में मिलाते हैं, जिससे एक वृक्ष प्राप्त होता है। अब रूट (एबीसी) से पत्तियों तक के रास्ते हफमैन कोड (प्रत्येक किनारे 1 या 0 से मेल खाते हैं)

• एबीसी
• 0 11 10

परिणामी वृक्ष

एमटीएफ रूपांतरण

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

कोड बिल्डिंग

प्रारंभ में, प्रत्येक संभावित बाइट मान एक सूची (वर्णमाला) में दर्ज किया जाता है, एक सेल में बाइट मान के बराबर संख्या के साथ, अर्थात। (0, 1, 2, 3, ..., 255)। डेटा प्रोसेसिंग के दौरान, यह सूची बदल जाती है। जैसे ही अगला चरित्र आता है, उसके मान वाले तत्व की संख्या आउटपुट होती है। उसके बाद, यह चरित्र सूची की शुरुआत में रहता है, शेष तत्वों को दाईं ओर स्थानांतरित करता है।
आधुनिक एल्गोरिदम (उदाहरण के लिए, bzip2) MTF एल्गोरिथ्म से पहले BWT एल्गोरिथ्म का उपयोग करते हैं, इसलिए, उदाहरण के रूप में, स्ट्रिंग "ABACABA" से प्राप्त स्ट्रिंग s = "BCABAAA" पर विचार करें, जो बर्गस-व्हीलर ट्रांसफॉर्म (बाद में इसके बारे में) के परिणामस्वरूप होता है। स्ट्रिंग s = 'B' का पहला वर्ण वर्णमाला "ABC" का दूसरा तत्व है, इसलिए, आउटपुट 1. वर्णमाला के आरंभ में 'B' को स्थानांतरित करने के बाद, यह "BAC" रूप लेता है। एल्गोरिथ्म के आगे काम:

• प्रतीक सूची आउटपुट
• बी एबीसी १
• सी बीएसी 2
• एक CBA 2
• बी एसीबी २
• एक बीएसी १
• एक एबीसी ०
• एक एबीसी ०

इस प्रकार, एमटीएफ (एस) एल्गोरिथ्म का परिणाम "1222100" है।

उलटा परिवर्तन

स्ट्रिंग को = "1222100" और मूल वर्णमाला "एबीसी" दिया जाए। वर्णमाला में वर्ण संख्या 1 'B' है। आउटपुट 'बी' है, और यह चरित्र वर्णमाला की शुरुआत में चलता है। वर्णमाला में वर्ण संख्या 2 'A' है, इसलिए 'A' आउटपुट है और वर्णमाला की शुरुआत में ले जाया जाता है। आगे भी रूपांतरण समान है।

• प्रतीक सूची आउटपुट
• 1 एबीसी बी
• 2 बीएसी सी
• 2 सीबीए ए
• 2 एसीबी बी
• 1 बीएसी ए
• 0 एबीसी ए
• 0 एबीसी ए

तो मूल स्ट्रिंग s = "BCABAAA" है।

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

बरोज़-व्हीलर ट्रांसफ़ॉर्म (बीडब्ल्यूटी) एक एल्गोरिथ्म है जिसका उपयोग डेटा कंप्रेशन तकनीकों में स्रोत डेटा को बदलने के लिए किया जाता है।
Bzip2 एक ही अक्षर के तार में कई वैकल्पिक पात्रों के दृश्यों को चालू करने के लिए बरोज़-व्हीलर ट्रांसफ़ॉर्म का उपयोग करता है, फिर MTF ट्रांसफ़ॉर्म और अंततः हफ़मैन कोडिंग लागू करता है।

एल्गोरिदम ऑपरेशन

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

हम संक्षेप में इस तरह से परिणाम लिखते हैं: BWT (s) ("BCABAAA", 3), जहां 3 क्रमबद्ध मैट्रिक्स में मूल पंक्ति की संख्या है, क्योंकि यह उलटा परिवर्तन के लिए आवश्यक हो सकता है।
यह ध्यान दिया जाना चाहिए कि कभी-कभी तथाकथित $ अंत-लाइन चरित्र स्रोत लाइन में दिया जाता है, जिसे रूपांतरण में अंतिम चरित्र माना जाएगा, फिर मूल पंक्ति की संख्या को सहेजने की आवश्यकता नहीं है। ऊपर दिए गए समान रूपांतरण के साथ, मैट्रिक्स में वह रेखा, जो पंक्ति वर्ण के अंत के साथ समाप्त होगी और मूल एक होगी ("ABACABA $")। इस मामले में, मैट्रिक्स को छांटते समय, इस प्रतीक को वर्णमाला के सभी प्रतीकों के बाद सबसे हाल का माना जाएगा। फिर परिणाम BWT (s) = "$ CBBAAAA" के रूप में लिखा जा सकता है। यह पहले के बराबर होगा, क्योंकि इसमें मूल स्ट्रिंग के सभी वर्ण भी शामिल हैं।

उलटा परिवर्तन

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

यह भी ध्यान दिया जाना चाहिए कि अगर हमें BWT (s) = "$ CBBAAAA" दिया जाता है, तो हमें अपना मूल स्ट्रिंग भी मिलेगा, केवल अंत में लाइन का पात्र $ के साथ: ABACABA $।

निष्कर्ष

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