दोषरहित संपीड़न: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 106: Line 106:
जीनोमिक अनुक्रम संपीड़न एल्गोरिदम, जिसे डीएनए अनुक्रम कंप्रेशर्स के रूप में भी जाना जाता है, इस तथ्य का पता लगाते हैं कि डीएनए अनुक्रमों में विशिष्ट गुण होते हैं, जैसे कि उलटा दोहराव। सबसे सफल कंप्रेशर्स XM और GeCo हैं।<ref name="Pratas">{{cite book |last1=Pratas |first1=D. |last2=Pinho |first2=A. J. |last3=Ferreira |first3=P. J. S. G. |date=2016 |chapter=Efficient compression of genomic sequences |title=डेटा संपीड़न सम्मेलन|location=Snowbird, Utah |url=http://sweet.ua.pt/pratas/papers/Pratas-2016b.pdf}}</ref> [[ यूकैर्योसाइटों | यूकैर्योसाइटों]] के लिए एक्सएम संपीड़न अनुपात में थोड़ा बेहतर है, हालांकि 100 एमबी से बड़े अनुक्रमों के लिए इसकी कम्प्यूटेशनल आवश्यकताएं अव्यावहारिक हैं।
जीनोमिक अनुक्रम संपीड़न एल्गोरिदम, जिसे डीएनए अनुक्रम कंप्रेशर्स के रूप में भी जाना जाता है, इस तथ्य का पता लगाते हैं कि डीएनए अनुक्रमों में विशिष्ट गुण होते हैं, जैसे कि उलटा दोहराव। सबसे सफल कंप्रेशर्स XM और GeCo हैं।<ref name="Pratas">{{cite book |last1=Pratas |first1=D. |last2=Pinho |first2=A. J. |last3=Ferreira |first3=P. J. S. G. |date=2016 |chapter=Efficient compression of genomic sequences |title=डेटा संपीड़न सम्मेलन|location=Snowbird, Utah |url=http://sweet.ua.pt/pratas/papers/Pratas-2016b.pdf}}</ref> [[ यूकैर्योसाइटों | यूकैर्योसाइटों]] के लिए एक्सएम संपीड़न अनुपात में थोड़ा बेहतर है, हालांकि 100 एमबी से बड़े अनुक्रमों के लिए इसकी कम्प्यूटेशनल आवश्यकताएं अव्यावहारिक हैं।


=== निष्पादन योग्य ===
=== निष्पादन योग्य67 ===
{{main article|निष्पादन योग्य संपीड़न}}
{{main article|निष्पादन योग्य संपीड़न}}


Line 114: Line 114:
दोषरहित संपीड़न एल्गोरिदम और उनके कार्यान्वयन का नियमित रूप से हेड-टू-हेड [[बेंचमार्क (कंप्यूटिंग)|बेंचमार्क]] में परीक्षण किया जाता है। कई बेहतर-ज्ञात संपीड़न बेंचमार्क हैं। कुछ बेंचमार्क केवल डेटा कम्प्रेशन अनुपात को कवर करते हैं, इसलिए शीर्ष प्रदर्शन करने वालों की धीमी गति के कारण इन बेंचमार्क में विजेता दैनिक उपयोग के लिए अनुपयुक्त हो सकते हैं। कुछ बेंचमार्क की एक और कमी यह है कि उनकी डेटा फाइलें जानी जाती हैं, इसलिए कुछ प्रोग्राम राइटर किसी विशेष डेटा सेट पर सर्वश्रेष्ठ प्रदर्शन के लिए अपने प्रोग्राम को ऑप्टिमाइज़ कर सकते हैं। इन बेंचमार्क पर विजेता अक्सर [[प्रसंग-मिश्रण]] कम्प्रेशन सॉफ्टवेयर की श्रेणी से आते हैं।
दोषरहित संपीड़न एल्गोरिदम और उनके कार्यान्वयन का नियमित रूप से हेड-टू-हेड [[बेंचमार्क (कंप्यूटिंग)|बेंचमार्क]] में परीक्षण किया जाता है। कई बेहतर-ज्ञात संपीड़न बेंचमार्क हैं। कुछ बेंचमार्क केवल डेटा कम्प्रेशन अनुपात को कवर करते हैं, इसलिए शीर्ष प्रदर्शन करने वालों की धीमी गति के कारण इन बेंचमार्क में विजेता दैनिक उपयोग के लिए अनुपयुक्त हो सकते हैं। कुछ बेंचमार्क की एक और कमी यह है कि उनकी डेटा फाइलें जानी जाती हैं, इसलिए कुछ प्रोग्राम राइटर किसी विशेष डेटा सेट पर सर्वश्रेष्ठ प्रदर्शन के लिए अपने प्रोग्राम को ऑप्टिमाइज़ कर सकते हैं। इन बेंचमार्क पर विजेता अक्सर [[प्रसंग-मिश्रण]] कम्प्रेशन सॉफ्टवेयर की श्रेणी से आते हैं।


मैट महोनी (कंप्यूटर वैज्ञानिक), अपने फरवरी 2010 के मुफ्त बुकलेट डेटा कम्प्रेशन एक्सप्लेन के संस्करण में अतिरिक्त रूप से निम्नलिखित को सूचीबद्ध करता है:<ref>{{cite web|title=डेटा संपीड़न समझाया|author=Matt Mahoney |year=2010|url=http://nishi.dreamhosters.com/u/dce2010-02-26.pdf|pages=3–5}}</ref>
मैट महोनी ने अपने फरवरी 2010 संस्करण में फ्री बुकलेट डेटा कम्प्रेशन एक्सप्लेनड में अतिरिक्त रूप से निम्नलिखित को सूचीबद्ध किया है:<ref>{{cite web|title=डेटा संपीड़न समझाया|author=Matt Mahoney |year=2010|url=http://nishi.dreamhosters.com/u/dce2010-02-26.pdf|pages=3–5}}</ref>
* 1987 से [[कैलगरी कॉर्पस]] अपने छोटे आकार के कारण अब व्यापक रूप से उपयोग नहीं किया जाता है। मैट महोनी ने 21 मई 1996 से 21 मई 2016 तक लियोनिड ए. ब्रोखिस द्वारा बनाए गए कैलगरी कंप्रेशन चैलेंज को बनाए रखा और बनाए रखा।
* 1987 से [[कैलगरी कॉर्पस]] अपने छोटे आकार के कारण अब व्यापक रूप से उपयोग नहीं किया जाता है। मैट महोनी ने 21 मई 1996 से 21 मई 2016 तक लियोनिड ए. ब्रोखिस द्वारा बनाए गए कैलगरी कंप्रेशन चैलेंज को बनाए रखा और बनाए रखा।
* बड़ा पाठ संपीड़न बेंचमार्क<ref>{{cite web|url=http://mattmahoney.net/dc/text.html|title=बड़ा पाठ संपीड़न बेंचमार्क|website=mattmahoney.net}}</ref> और इसी तरह के [[ हटर पुरस्कार ]]़ दोनों एक संक्षिप्त [[विकिपीडिया]] [[XML]] [[UTF-8]] डेटा सेट का उपयोग करते हैं।
* बड़ा पाठ संपीड़न बेंचमार्क<ref>{{cite web|url=http://mattmahoney.net/dc/text.html|title=बड़ा पाठ संपीड़न बेंचमार्क|website=mattmahoney.net}}</ref> और इसी तरह के [[ हटर पुरस्कार ]]़ दोनों एक संक्षिप्त [[विकिपीडिया]] [[XML]] [[UTF-8]] डेटा सेट का उपयोग करते हैं।
Line 122: Line 122:


संपीड़न रेटिंग वेबसाइट ने संपीड़न अनुपात और समय में सीमा का एक चार्ट सारांश प्रकाशित किया।<ref>{{Cite web|url=https://web.archive.org/web/20160901094802/http://compressionratings.com/rating_sum.html|title=सारांश|date=September 1, 2016|website=web.archive.org}}</ref>
संपीड़न रेटिंग वेबसाइट ने संपीड़न अनुपात और समय में सीमा का एक चार्ट सारांश प्रकाशित किया।<ref>{{Cite web|url=https://web.archive.org/web/20160901094802/http://compressionratings.com/rating_sum.html|title=सारांश|date=September 1, 2016|website=web.archive.org}}</ref>
संपीड़न विश्लेषण उपकरण<ref>{{cite web|url=https://www.noemax.com/free-tools/compression-analysis-tool.asp |title=संपीड़न विश्लेषण उपकरण|publisher=Noemax Technologies |website=Free Tools}}</ref> एक विंडोज एप्लिकेशन है जो अंतिम उपयोगकर्ताओं को अपने स्वयं के डेटा का उपयोग करके LZF4, Deflate, ZLIB, GZIP, BZIP2 और LZMA के स्ट्रीमिंग कार्यान्वयन की प्रदर्शन विशेषताओं को बेंचमार्क करने में सक्षम बनाता है। यह माप और चार्ट तैयार करता है जिसके साथ उपयोगकर्ता विभिन्न संपीड़न विधियों की संपीड़न गति, डीकंप्रेसन गति और संपीड़न अनुपात की तुलना कर सकते हैं और यह जांचने के लिए कि संपीड़न स्तर, बफर आकार और फ्लशिंग ऑपरेशन परिणामों को कैसे प्रभावित करते हैं।
संपीड़न विश्लेषण उपकरण<ref>{{cite web|url=https://www.noemax.com/free-tools/compression-analysis-tool.asp |title=संपीड़न विश्लेषण उपकरण|publisher=Noemax Technologies |website=Free Tools}}</ref> एक विंडोज एप्लिकेशन है जो अंतिम उपयोगकर्ताओं को अपने स्वयं के डेटा का उपयोग करके LZF4, Deflate, ZLIB, GZIP, BZIP2 और LZMA के स्ट्रीमिंग कार्यान्वयन की प्रदर्शन विशेषताओं को बेंचमार्क करने में सक्षम बनाता है। यह माप और चार्ट तैयार करता है जिसके साथ उपयोगकर्ता विभिन्न संपीड़न विधियों की संपीड़न गति, डीकंप्रेसन गति और संपीड़न अनुपात की तुलना कर सकते हैं और यह जांचने के लिए कि संपीड़न स्तर, बफर आकार और फ्लशिंग ऑपरेशन परिणामों को कैसे प्रभावित करते हैं।


Line 129: Line 130:
* मान लीजिए कि एक संपीड़न एल्गोरिदम है जो प्रत्येक फ़ाइल को आउटपुट फ़ाइल में बदल देता है जो मूल फ़ाइल से अधिक नहीं है, और कम से कम एक फ़ाइल को आउटपुट फ़ाइल में संपीड़ित किया जाएगा जो मूल फ़ाइल से छोटा है।
* मान लीजिए कि एक संपीड़न एल्गोरिदम है जो प्रत्येक फ़ाइल को आउटपुट फ़ाइल में बदल देता है जो मूल फ़ाइल से अधिक नहीं है, और कम से कम एक फ़ाइल को आउटपुट फ़ाइल में संपीड़ित किया जाएगा जो मूल फ़ाइल से छोटा है।
* एम को कम से कम संख्या दें जैसे कि लंबाई एम बिट्स वाली एक फ़ाइल एफ है जो कुछ कम करने के लिए संपीड़ित होती है। मान लीजिए कि N, F के संपीडित संस्करण की लंबाई (बिट्स में) है।
* एम को कम से कम संख्या दें जैसे कि लंबाई एम बिट्स वाली एक फ़ाइल एफ है जो कुछ कम करने के लिए संपीड़ित होती है। मान लीजिए कि N, F के संपीडित संस्करण की लंबाई (बिट्स में) है।
* क्योंकि N<M, लंबाई N की 'प्रत्येक' फ़ाइल संपीड़न के दौरान अपना आकार बनाए रखती है। वहाँ 2 है<sup>N</sup> ऐसी फ़ाइलें संभव हैं। F के साथ मिलकर, यह 2 बनाता है<sup>N</sup>+1 फ़ाइलें जो सभी 2 में से एक में संपीड़ित होती हैं<sup>N</sup> लंबाई की फ़ाइलें N.
*क्योंकि N <M, लंबाई N की प्रत्येक फ़ाइल संपीड़न के दौरान अपना आकार बनाए रखती है। ऐसी 2<sup>N</sup> फाइलें संभव हैं। F के साथ मिलकर, यह 2<sup>N</sup>+1 फ़ाइलें बनाता है जो सभी लंबाई N की 2<sup>N</sup> फ़ाइलों में से एक में संपीड़ित होती हैं।
*लेकिन 2<sup>N</sup> 2 से छोटा है<sup>N</sup>+1, इसलिए कबूतर सिद्धांत द्वारा लंबाई N की कुछ फ़ाइल होनी चाहिए जो एक साथ दो अलग-अलग इनपुट पर संपीड़न फ़ंक्शन का आउटपुट हो। उस फ़ाइल को मज़बूती से विघटित नहीं किया जा सकता है (दो मूल में से कौन सा उपज होना चाहिए?), जो इस धारणा का खंडन करता है कि एल्गोरिथ्म दोषरहित था।
*लेकिन 2<sup>N</sup> 2<sup>N</sup>+1 से छोटा है, इसलिए कबूतर के सिद्धांत के अनुसार लंबाई N की कुछ फ़ाइल होनी चाहिए जो एक साथ दो अलग-अलग इनपुट पर संपीड़न फ़ंक्शन का आउटपुट हो। उस फ़ाइल को मज़बूती से विघटित नहीं किया जा सकता है (दो मूल में से कौन सा उपज होना चाहिए?), जो इस धारणा का खंडन करता है कि एल्गोरिथ्म दोषरहित था।
* इसलिए हमें यह निष्कर्ष निकालना चाहिए कि हमारी मूल परिकल्पना (संपीड़न फ़ंक्शन किसी फ़ाइल को लंबा नहीं बनाता है) आवश्यक रूप से असत्य है।
* इसलिए हमें यह निष्कर्ष निकालना चाहिए कि हमारी मूल परिकल्पना (संपीड़न फ़ंक्शन अब कोई फ़ाइल नहीं बनाता है) आवश्यक रूप से असत्य है।


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


वास्तव में, यदि हम लंबाई N की फ़ाइलों पर विचार करते हैं, यदि सभी फाइलें समान रूप से संभावित थीं, तो किसी भी दोषरहित संपीड़न के लिए जो किसी फ़ाइल के आकार को कम करता है, एक संपीड़ित फ़ाइल की अपेक्षित लंबाई (लंबाई N की सभी संभावित फ़ाइलों पर औसत) आवश्यक रूप से होनी चाहिए। N से बड़ा हो।<ref>{{Cite web |title=Lossless Compression - an overview {{!}} ScienceDirect Topics |url=https://www.sciencedirect.com/topics/computer-science/lossless-compression |access-date=2022-10-30 |website=www.sciencedirect.com}}</ref> इसलिए यदि हम उस डेटा के गुणों के बारे में कुछ नहीं जानते हैं जिसे हम कंप्रेस कर रहे हैं, तो हम इसे बिल्कुल भी कंप्रेस नहीं कर सकते हैं। दोषरहित कम्प्रेशन एल्गोरिद्म तभी उपयोगी होता है जब हम दूसरों की तुलना में कुछ प्रकार की फ़ाइलों को संपीड़ित करने की अधिक संभावना रखते हैं; तो एल्गोरिदम को उन प्रकार के डेटा को बेहतर ढंग से संपीड़ित करने के लिए डिज़ाइन किया जा सकता है।
वास्तव में, यदि हम लंबाई N की फ़ाइलों पर विचार करते हैं, यदि सभी फाइलें समान रूप से संभावित थीं, तो किसी भी दोषरहित संपीड़न के लिए जो किसी फ़ाइल के आकार को कम करता है, एक संपीड़ित फ़ाइल की अपेक्षित लंबाई (लंबाई N की सभी संभावित फ़ाइलों पर औसत) आवश्यक रूप से होनी चाहिए। एन से अधिक हो।<ref>{{Cite web |title=Lossless Compression - an overview {{!}} ScienceDirect Topics |url=https://www.sciencedirect.com/topics/computer-science/lossless-compression |access-date=2022-10-30 |website=www.sciencedirect.com}}</ref> इसलिए यदि हम उस डेटा के गुणों के बारे में कुछ नहीं जानते हैं जिसे हम कंप्रेस कर रहे हैं, तो हम इसे बिल्कुल भी कंप्रेस नहीं कर सकते हैं। दोषरहित कम्प्रेशन एल्गोरिद्म तभी उपयोगी होता है जब हम दूसरों की तुलना में कुछ प्रकार की फ़ाइलों को संपीड़ित करने की अधिक संभावना रखते हैं; तो एल्गोरिदम को उन प्रकार के डेटा को बेहतर ढंग से संपीड़ित करने के लिए डिज़ाइन किया जा सकता है।


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


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


विशेष रूप से, यादृच्छिक डेटा की फ़ाइलों को किसी भी बोधगम्य दोषरहित डेटा संपीड़न एल्गोरिथम द्वारा लगातार संपीड़ित नहीं किया जा सकता है; वास्तव में, इस परिणाम का उपयोग [[कोलमोगोरोव जटिलता]] में यादृच्छिकता की अवधारणा को परिभाषित करने के लिए किया जाता है।{{Sfn|Sayood|2002|p=38}}
विशेष रूप से, यादृच्छिक डेटा की फ़ाइलों को किसी भी बोधगम्य दोषरहित डेटा संपीड़न एल्गोरिथम द्वारा लगातार संपीड़ित नहीं किया जा सकता है; वास्तव में, इस परिणाम का उपयोग [[कोलमोगोरोव जटिलता]] में यादृच्छिकता की अवधारणा को परिभाषित करने के लिए किया जाता है।{{Sfn|Sayood|2002|p=38}}


एक एल्गोरिदम बनाना असंभव साबित होता है जो किसी भी डेटा को हानि रहित रूप से संपीड़ित कर सकता है। जबकि कंपनियों के वर्षों के दौरान पूर्ण संपीड़न प्राप्त करने के कई दावे किए गए हैं, जहां यादृच्छिक बिट्स की एक मनमानी संख्या N को हमेशा N − 1 बिट तक संकुचित किया जा सकता है, इस प्रकार के दावों को कथित के बारे में कोई और विवरण देखे बिना सुरक्षित रूप से खारिज किया जा सकता है संपीड़न योजना। ऐसा एल्गोरिद्म गणित के मौलिक नियमों का खंडन करता है, क्योंकि यदि यह अस्तित्व में है, तो इसे किसी फ़ाइल की लंबाई 1 तक कम करने के लिए बार-बार लागू किया जा सकता है।<ref name=ISSEP-2015/>
एक एल्गोरिदम बनाना असंभव साबित होता है जो किसी भी डेटा को हानि रहित रूप से संपीड़ित कर सकता है। जबकि कंपनियों द्वारा "पूर्ण संपीड़न" प्राप्त करने के वर्षों के दौरान कई दावे किए गए हैं, जहां यादृच्छिक बिट्स की एक मनमाना संख्या N को हमेशा N - 1 बिट्स तक संकुचित किया जा सकता है, इस प्रकार के दावों को बिना किसी और विवरण को देखे सुरक्षित रूप से खारिज किया जा सकता है। कथित संपीड़न योजना। ऐसा एल्गोरिद्म गणित के मौलिक नियमों का खंडन करता है, क्योंकि यदि यह अस्तित्व में होता, तो इसे किसी भी फ़ाइल को दोषरहित रूप से 1 की लंबाई तक कम करने के लिए बार-बार लागू किया जा सकता था।<ref name=ISSEP-2015/>


दूसरी ओर, यह भी सिद्ध हो चुका है<ref>{{cite book|first1=Ming|last1=Li|first2=Paul|last2=Vitányi|title=कोलमोगोरोव जटिलता और उसके अनुप्रयोगों का परिचय|year=1993|location=New York|publisher=Springer|page=102|isbn=0-387-94053-7|url=https://archive.org/details/introductiontoko00limi/page/102/mode/2up|quotation=Theorem 2.6 The function <math>C(x)</math> is not partial recursive.}}</ref> यह निर्धारित करने के लिए कोई एल्गोरिथ्म नहीं है कि कोल्मोगोरोव जटिलता के अर्थ में कोई फ़ाइल असं[[ अनुकरणीय ]]ड़ित है या नहीं। इसलिए यह संभव है कि कोई विशेष फ़ाइल, भले ही वह यादृच्छिक प्रतीत हो, महत्वपूर्ण रूप से संकुचित हो सकती है, यहां तक ​​कि डीकंप्रेसर के आकार सहित भी। एक उदाहरण गणितीय स्थिरांक पाई के अंक हैं, जो यादृच्छिक दिखाई देते हैं लेकिन एक बहुत छोटे प्रोग्राम द्वारा उत्पन्न किए जा सकते हैं। हालाँकि, भले ही यह निर्धारित नहीं किया जा सकता है कि कोई विशेष फ़ाइल असम्पीडित है, एक कोलमोगोरोव जटिलता # संपीड़न से पता चलता है कि किसी भी लंबाई की 99% से अधिक फ़ाइलों को एक से अधिक बाइट (डीकंप्रेसर के आकार सहित) द्वारा संपीड़ित नहीं किया जा सकता है।
दूसरी ओर, यह भी सिद्ध हो चुका है<ref>{{cite book|first1=Ming|last1=Li|first2=Paul|last2=Vitányi|title=कोलमोगोरोव जटिलता और उसके अनुप्रयोगों का परिचय|year=1993|location=New York|publisher=Springer|page=102|isbn=0-387-94053-7|url=https://archive.org/details/introductiontoko00limi/page/102/mode/2up|quotation=Theorem 2.6 The function <math>C(x)</math> is not partial recursive.}}</ref> कि यह निर्धारित करने के लिए कोई एल्गोरिद्म नहीं है कि कोलमोगोरोव जटिलता के अर्थ में कोई फाइल असंपीड्य है या नहीं। इसलिए यह संभव है कि कोई विशेष फ़ाइल, भले ही वह यादृच्छिक प्रतीत हो, महत्वपूर्ण रूप से संकुचित हो सकती है, यहां तक कि डीकंप्रेसर के आकार सहित भी। एक उदाहरण गणितीय स्थिरांक पाई के अंक हैं, जो यादृच्छिक दिखाई देते हैं लेकिन एक बहुत छोटे प्रोग्राम द्वारा उत्पन्न किए जा सकते हैं। हालाँकि, भले ही यह निर्धारित नहीं किया जा सकता है कि कोई विशेष फ़ाइल असम्पीडित है, असम्पीडित स्ट्रिंग्स के बारे में एक सरल प्रमेय से पता चलता है कि किसी भी लंबाई की 99% से अधिक फ़ाइलों को एक से अधिक बाइट (डीकंप्रेसर के आकार सहित) द्वारा संपीड़ित नहीं किया जा सकता है।


=== गणितीय पृष्ठभूमि ===
=== गणितीय पृष्ठभूमि ===
संक्षेप में, एक संपीड़न एल्गोरिदम को अनुक्रमों (आमतौर पर ऑक्टेट) पर एक फ़ंक्शन (गणित) के रूप में देखा जा सकता है। संपीड़न सफल होता है यदि परिणामी अनुक्रम मूल अनुक्रम (और डिकंप्रेशन मानचित्र के लिए निर्देश) से छोटा होता है। [[ संपीड़न एल्गोरिथ्म ]] [[दोषरहित]] होने के लिए, कम्प्रेशन मैप को प्लेन से कंप्रेस्ड बिट सीक्वेंस के लिए एक [[ इंजेक्शन समारोह ]] बनाना चाहिए। कबूतर सिद्धांत लंबाई एन के अनुक्रमों के संग्रह और लंबाई एन-1 के अनुक्रमों के संग्रह के किसी भी उपसमुच्चय के बीच एक आक्षेप को प्रतिबंधित करता है। इसलिए, दोषरहित एल्गोरिथ्म का उत्पादन करना संभव नहीं है जो हर संभव इनपुट अनुक्रम के आकार को कम करता है।<ref>{{cite book|chapter-url=https://books.google.com/books?id=Bn6dBwAAQBAJ&pg=PA21|title=सबूत पैटर्न|chapter=Chapter 3 – The Pigeonhole Principle|author=[[Mark S. Joshi|Joshi, Mark S.]]|publisher=[[Springer Nature|Springer]]|date=2015-03-18|access-date=2021-08-24|page=21|doi=10.1007/978-3-319-16250-8_3|isbn=978-3-319-16250-8}}</ref>
संक्षेप में, एक संपीड़न एल्गोरिदम को अनुक्रमों (आमतौर पर ऑक्टेट) पर एक फ़ंक्शन के रूप में देखा जा सकता है। संपीड़न सफल होता है यदि परिणामी अनुक्रम मूल अनुक्रम (और डिकंप्रेशन मानचित्र के लिए निर्देश) से छोटा होता है। [[ संपीड़न एल्गोरिथ्म |संपीड़न एल्गोरिथ्म]] [[दोषरहित]] होने के लिए, संपीड़न मानचित्र को "सादे" से "संपीड़ित" बिट अनुक्रमों में एक [[ इंजेक्शन समारोह |इंजेक्शन]] बनाना चाहिए। कबूतर सिद्धांत लंबाई एन के अनुक्रमों के संग्रह और लंबाई एन-1 के अनुक्रमों के संग्रह के किसी भी उपसमुच्चय के बीच एक आक्षेप को प्रतिबंधित करता है। इसलिए, दोषरहित एल्गोरिथम का निर्माण करना संभव नहीं है जो हर संभव इनपुट अनुक्रम के आकार को कम करता है।<ref>{{cite book|chapter-url=https://books.google.com/books?id=Bn6dBwAAQBAJ&pg=PA21|title=सबूत पैटर्न|chapter=Chapter 3 – The Pigeonhole Principle|author=[[Mark S. Joshi|Joshi, Mark S.]]|publisher=[[Springer Nature|Springer]]|date=2015-03-18|access-date=2021-08-24|page=21|doi=10.1007/978-3-319-16250-8_3|isbn=978-3-319-16250-8}}</ref>
=== वास्तविक संपीड़न सिद्धांत में अनुप्रयोग के बिंदु ===
=== वास्तविक संपीड़न सिद्धांत में आवेदन के बिंदु ===
वास्तविक संपीड़न एल्गोरिथम डिजाइनर स्वीकार करते हैं कि उच्च सूचना एन्ट्रापी की धाराओं को संकुचित नहीं किया जा सकता है, और तदनुसार, इस स्थिति का पता लगाने और संभालने के लिए सुविधाएं शामिल हैं। पता लगाने का एक स्पष्ट तरीका कच्चे संपीड़न एल्गोरिदम को लागू करना और परीक्षण करना है कि इसका आउटपुट इसके इनपुट से छोटा है या नहीं। कभी-कभी, अनुमानी द्वारा पता लगाया जाता है; उदाहरण के लिए, एक संपीड़न अनुप्रयोग उन फ़ाइलों पर विचार कर सकता है जिनके नाम .zip , .arj या .lha में समाप्त होते हैं, बिना किसी अधिक परिष्कृत खोज के। इस स्थिति को संभालने का एक सामान्य तरीका इनपुट, या आउटपुट में इनपुट के असम्पीडित भागों को उद्धृत करना है, जिससे कंप्रेशन ओवरहेड को कम किया जा सके। उदाहरण के लिए, ZIP (फ़ाइल स्वरूप) डेटा प्रारूप उन इनपुट फ़ाइलों के लिए 'संग्रहीत' की 'संपीड़न विधि' निर्दिष्ट करता है जिन्हें संग्रह में शब्दशः कॉपी किया गया है।<ref>{{cite web |url=http://www.pkware.com/documents/casestudies/APPNOTE.TXT |title=.ZIP फ़ाइल स्वरूप विशिष्टता|publisher=[[PKWARE, Inc.]] |at=chapter V, section J}}</ref>
वास्तविक संपीड़न एल्गोरिथम डिजाइनर स्वीकार करते हैं कि उच्च सूचना एन्ट्रापी की धाराओं को संकुचित नहीं किया जा सकता है, और तदनुसार, इस स्थिति का पता लगाने और संभालने के लिए सुविधाएं शामिल हैं। पता लगाने का एक स्पष्ट तरीका कच्चे संपीड़न एल्गोरिदम को लागू करना और परीक्षण करना है कि इसका आउटपुट इसके इनपुट से छोटा है या नहीं। कभी-कभी, अनुमानी द्वारा पता लगाया जाता है; उदाहरण के लिए, एक संपीड़न अनुप्रयोग उन फ़ाइलों पर विचार कर सकता है जिनके नाम ".zip", ".arj" या ".lha" में समाप्त होते हैं, बिना किसी अधिक परिष्कृत पहचान के असम्पीडित। इस स्थिति को संभालने का एक सामान्य तरीका इनपुट, या आउटपुट में इनपुट के असम्पीडित भागों को उद्धृत करना है, जिससे कंप्रेशन ओवरहेड को कम किया जा सके। उदाहरण के लिए, ज़िप डेटा प्रारूप उन इनपुट फ़ाइलों के लिए 'संग्रहीत' की 'संपीड़न विधि' निर्दिष्ट करता है जिन्हें शब्दशः संग्रह में कॉपी किया गया है।<ref>{{cite web |url=http://www.pkware.com/documents/casestudies/APPNOTE.TXT |title=.ZIP फ़ाइल स्वरूप विशिष्टता|publisher=[[PKWARE, Inc.]] |at=chapter V, section J}}</ref>
=== द मिलियन रैंडम डिजिट चैलेंज ===
=== द मिलियन रैंडम डिजिट चैलेंज ===
मार्क नेल्सन, कॉम्प.कम्प्रेशन में दिखाई देने वाले जादू संपीड़न एल्गोरिदम के दावों के जवाब में, अत्यधिक एंट्रोपिक सामग्री की 415,241 बाइट बाइनरी फ़ाइल का निर्माण किया है, और किसी को प्रोग्राम लिखने के लिए $ 100 की सार्वजनिक चुनौती जारी की है, जो इसके इनपुट के साथ, उसके प्रदान किए गए बाइनरी डेटा से छोटा हो फिर भी त्रुटि के बिना इसे पुनर्गठित करने में सक्षम हो।<ref>{{cite web
मार्क नेल्सन, कॉम्प.संपीड़न में दिखाई देने वाले "मैजिक" कम्प्रेशन एल्गोरिदम के दावों के जवाब में, अत्यधिक एंट्रोपिक सामग्री की 415,241 बाइट बाइनरी फ़ाइल का निर्माण किया है, और किसी को प्रोग्राम लिखने के लिए $100 की एक सार्वजनिक चुनौती जारी की है, जो इसके इनपुट के साथ मिलकर, उनके द्वारा प्रदान किए गए बाइनरी डेटा से छोटा होगा फिर भी बिना किसी त्रुटि के इसे पुनर्गठित करने में सक्षम होगा।<ref>{{cite web
   | last = Nelson
   | last = Nelson
   | first = Mark
   | first = Mark
   | title = The Million Random Digit Challenge Revisited
   | title = The Million Random Digit Challenge Revisited
   | date = 2006-06-20
   | date = 2006-06-20
   | url = https://marknelson.us/posts/2006/06/20/million-digit-challenge.html }}</ref>
   | url = https://marknelson.us/posts/2006/06/20/million-digit-challenge.html }}</ref> माइक गोल्डमैन द्वारा पुरस्कार के रूप में $5,000 के साथ एक ऐसी ही चुनौती जारी की गई थी।<ref>{{cite web
माइक गोल्डमैन द्वारा पुरस्कार के रूप में $5,000 के साथ एक समान चुनौती जारी की गई थी।<ref>{{cite web
   | last = Craig
   | last = Craig
   | first = Patrick
   | first = Patrick

Revision as of 00:26, 22 March 2023

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

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

कई अनुप्रयोगों में दोषरहित डेटा संपीड़न का उपयोग किया जाता है। उदाहरण के लिए, इसका उपयोग ZIP फ़ाइल स्वरूप और GNU टूल gzip में किया जाता है। यह अक्सर हानिकारक डेटा संपीड़न तकनीकों के भीतर एक घटक के रूप में भी प्रयोग किया जाता है (उदाहरण के लिए MP3 एन्कोडर्स और अन्य हानिपूर्ण ऑडियो एन्कोडर्स द्वारा हानि रहित मध्य/साइड संयुक्त स्टीरियो प्रीप्रोसेसिंग)।[3]

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

तकनीक

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

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

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

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

मल्टीमीडिया

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

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

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

ऐतिहासिक कानूनी मुद्दे

इनमें से कई तरीके ओपन-सोर्स और मालिकाना उपकरण, विशेष रूप से LZW और इसके वेरिएंट में लागू किए गए हैं। संयुक्त राज्य अमेरिका और अन्य देशों में कुछ एल्गोरिदम का पेटेंट कराया जाता है और उनके कानूनी उपयोग के लिए पेटेंट धारक द्वारा लाइसेंस की आवश्यकता होती है। कुछ प्रकार के LZW संपीड़न पर पेटेंट के कारण, और विशेष रूप से पेटेंट धारक यूनिसिस द्वारा लाइसेंसिंग प्रथाओं के कारण, जिसे कई डेवलपर्स अपमानजनक मानते थे, कुछ खुले स्रोत के समर्थकों ने लोगों को पोर्टेबल के पक्ष में स्थिर छवि फ़ाइलों को संपीड़ित करने के लिए ग्राफिक्स इंटरचेंज फॉर्मेट (GIF) का उपयोग करने से बचने के लिए प्रोत्साहित किया। नेटवर्क ग्राफ़िक्स (PNG), जो डोमेन-विशिष्ट भविष्यवाणी फ़िल्टर के चयन के साथ LZ77 और LZ78 आधारित डिफ्लेट एल्गोरिथम को जोड़ती है। हालांकि, LZW पर पेटेंट 20 जून, 2003 को समाप्त हो गया।[4]

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

जैसा कि पहले उल्लेख किया गया है, दोषरहित ध्वनि संपीड़न कुछ विशिष्ट क्षेत्र है। दोषरहित ध्वनि संपीड़न एल्गोरिदम डेटा की तरंग जैसी प्रकृति द्वारा दिखाए गए दोहराए जाने वाले पैटर्न का लाभ उठा सकते हैं - अनिवार्य रूप से अगले मूल्य की भविष्यवाणी करने के लिए ऑटोरेग्रेसिव मॉडल का उपयोग करना और अपेक्षित मूल्य और वास्तविक डेटा के बीच (उम्मीद से छोटा) अंतर को एन्कोडिंग करना। यदि अनुमानित और वास्तविक डेटा (त्रुटि कहा जाता है) के बीच का अंतर छोटा होता है, तो कुछ अंतर मान (जैसे 0, +1, -1 आदि नमूना मूल्यों पर) बहुत बार-बार हो जाते हैं, जो उन्हें एन्कोडिंग द्वारा शोषण किया जा सकता है कुछ आउटपुट बिट्स में।

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

विधियाँ

See also: श्रेणी: दोषरहित संपीड़न एल्गोरिदम and दोषरहित संपीड़न एल्गोरिदम की सूची

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

कुछ सबसे आम दोषरहित संपीड़न एल्गोरिदम नीचे सूचीबद्ध हैं।

सामान्य उद्देश्य

  • असममित अंक प्रणाली - एंट्रॉपी एन्कोडिंग, LZFSE और Zमानक द्वारा उपयोग किया जाता है
  • अंकगणित कोडिंग - एंट्रॉपी एन्कोडिंग
  • बरोज-व्हीलर टेक्स्ट डेटा को अधिक कंप्रेसेबल बनाने के लिए रिवर्सेबल ट्रांसफॉर्मेशन ट्रांसफॉर्म करता है, जिसका उपयोग bzip2 द्वारा किया जाता है
  • हफमैन कोडिंग - एंट्रॉपी एन्कोडिंग, अन्य एल्गोरिदम के साथ जोड़े
  • लेम्पेल-ज़िव कम्प्रेशन (LZ77 और LZ78) - शब्दकोश-आधारित एल्गोरिदम जो कई अन्य एल्गोरिदम के लिए आधार बनाता है
    • लेम्पेल-ज़िव-मार्कोव चेन एल्गोरिथम (LZMA) - बहुत उच्च संपीड़न अनुपात, 7zip और XZ Utils द्वारा उपयोग किया जाता है
    • लेम्पेल-ज़िव-स्टोरर-सिमांस्की (LZSS) - WinRAR द्वारा कोडिंग के साथ मिलकर उपयोग किया जाता है
      • डिफ्लेट - ZIP (फ़ाइल स्वरूप), gzip, और पोर्टेबल नेटवर्क ग्राफ़िक्स छवियों द्वारा उपयोग किए जाने वाले हफ़मैन कोडिंग के साथ LZSS संपीड़न को जोड़ती है
    • लेम्पेल-ज़िव-वेल्च (LZW) - जीआईएफ छवियों और यूनिक्स की compress उपयोगिता द्वारा उपयोग किया जाता है
  • आंशिक मिलान (पीपीएम) द्वारा भविष्यवाणी - सादे पाठ को संपीड़ित करने के लिए अनुकूलित
  • रन-लेंथ एन्कोडिंग (आरएलई) - सरल योजना जो एक ही मूल्य के कई रन वाले डेटा का अच्छा संपीड़न प्रदान करती है

ऑडियो

रेखापुंज ग्राफिक्स

  • AVIF - AV1 छवि फ़ाइल स्वरूप
  • FLIF - नि: शुल्क दोषरहित छवि प्रारूप
  • HEIF - उच्च दक्षता छवि फ़ाइल प्रारूप (एचईवीसी का उपयोग करके दोषरहित या हानिपूर्ण संपीड़न)
  • ILBM - (अमिगा इंटरचेंज फ़ाइल स्वरूप छवियों का दोषरहित RLE संपीड़न)
  • JBIG2 - (B&W छवियों का दोषरहित या हानिपूर्ण संपीड़न)
  • JPEG 2000 - (ले गैल-तबाताबाई 5/3 के माध्यम से दोषरहित संपीड़न विधि शामिल है)[5][6][7] प्रतिवर्ती पूर्णांक तरंगिका परिवर्तन)
  • JPEG-LS - (दोषरहित/लगभग-दोषरहित संपीड़न मानक)
  • JPEG XL - (दोषरहित या हानिपूर्ण संपीड़न)
  • JPEG XR - पूर्व में WMPhoto और HD Photo में दोषरहित संपीड़न विधि शामिल है
  • LDCT - दोषरहित असतत कोसाइन रूपांतरण[8][9]
  • PCX - पिक्चर एक्सचेंज
  • PDF - पोर्टेबल दस्तावेज़ स्वरूप (दोषरहित या हानिपूर्ण संपीड़न)
  • QOI - काफी ठीक छवि प्रारूप
  • PNG - पोर्टेबल नेटवर्क ग्राफिक्स
  • TGA - ट्रूविज़न टीजीए
  • TIFF - टैग की गई छवि फ़ाइल स्वरूप (दोषरहित या हानिपूर्ण संपीड़न)
  • WebP - (आरजीबी और आरजीबीए छवियों का दोषरहित या हानिपूर्ण संपीड़न)

3डी ग्राफिक्स

  • OpenCTM - 3डी त्रिकोण जालों का दोषरहित संपीड़न

वीडियो

दोषरहित वीडियो कोडेक्स की सूची देखें

क्रिप्टोग्राफी

क्रिप्टोसिस्टम्स अक्सर अतिरिक्त सुरक्षा के लिए एन्क्रिप्शन से पहले डेटा ("प्लेन टेक्स्ट") को संपीड़ित करते हैं। जब ठीक से लागू किया जाता है, तो क्रिप्ट एनालिसिस की सुविधा देने वाले पैटर्न को हटाकर संपीड़न एकता दूरी को बहुत बढ़ा देता है। [10] हालांकि, कई सामान्य हानि रहित संपीड़न एल्गोरिदम हेडर, रैपर, टेबल या अन्य अनुमानित आउटपुट उत्पन्न करते हैं जो क्रिप्टैनालिसिस को आसान बना सकते हैं। इस प्रकार, क्रिप्टोसिस्टम्स को कम्प्रेशन एल्गोरिदम का उपयोग करना चाहिए जिनके आउटपुट में ये अनुमानित पैटर्न नहीं होते हैं।

जेनेटिक्स और जीनोमिक्स

जेनेटिक्स कंप्रेशन एल्गोरिदम (आनुवंशिक एल्गोरिदम के साथ भ्रमित नहीं होना) दोषरहित एल्गोरिदम की नवीनतम पीढ़ी है जो पारंपरिक संपीड़न एल्गोरिदम और जेनेटिक डेटा के अनुकूल विशिष्ट एल्गोरिदम दोनों का उपयोग करके डेटा (आमतौर पर न्यूक्लियोटाइड्स के अनुक्रम) को संपीड़ित करता है। 2012 में, जॉन्स हॉपकिन्स विश्वविद्यालय के वैज्ञानिकों की एक टीम ने पहला जेनेटिक कम्प्रेशन एल्गोरिथम प्रकाशित किया जो कम्प्रेशन के लिए बाहरी जेनेटिक डेटाबेस पर निर्भर नहीं करता है। हैपज़िपर को हैपमैप डेटा के लिए तैयार किया गया था और 20 गुना से अधिक संपीड़न (फ़ाइल आकार में 95% की कमी) प्राप्त करता है, जो प्रमुख सामान्य-उद्देश्य संपीड़न उपयोगिताओं की तुलना में 2- से 4 गुना बेहतर संपीड़न प्रदान करता है।[10]

जीनोमिक अनुक्रम संपीड़न एल्गोरिदम, जिसे डीएनए अनुक्रम कंप्रेशर्स के रूप में भी जाना जाता है, इस तथ्य का पता लगाते हैं कि डीएनए अनुक्रमों में विशिष्ट गुण होते हैं, जैसे कि उलटा दोहराव। सबसे सफल कंप्रेशर्स XM और GeCo हैं।[11] यूकैर्योसाइटों के लिए एक्सएम संपीड़न अनुपात में थोड़ा बेहतर है, हालांकि 100 एमबी से बड़े अनुक्रमों के लिए इसकी कम्प्यूटेशनल आवश्यकताएं अव्यावहारिक हैं।

निष्पादन योग्य67

Main article: निष्पादन योग्य संपीड़न

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

मानक

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

मैट महोनी ने अपने फरवरी 2010 संस्करण में फ्री बुकलेट डेटा कम्प्रेशन एक्सप्लेनड में अतिरिक्त रूप से निम्नलिखित को सूचीबद्ध किया है:[12]

  • 1987 से कैलगरी कॉर्पस अपने छोटे आकार के कारण अब व्यापक रूप से उपयोग नहीं किया जाता है। मैट महोनी ने 21 मई 1996 से 21 मई 2016 तक लियोनिड ए. ब्रोखिस द्वारा बनाए गए कैलगरी कंप्रेशन चैलेंज को बनाए रखा और बनाए रखा।
  • बड़ा पाठ संपीड़न बेंचमार्क[13] और इसी तरह के हटर पुरस्कार ़ दोनों एक संक्षिप्त विकिपीडिया XML UTF-8 डेटा सेट का उपयोग करते हैं।
  • सामान्य संपीड़न बेंचमार्क,[14] मैट महोनी द्वारा बनाए रखा गया, यादृच्छिक ट्यूरिंग मशीन द्वारा उत्पन्न डेटा के संपीड़न का परीक्षण करता है।
  • सामी रनसास (नैनोज़िप के लेखक) ने कम्प्रेशन रेटिंग बनाए रखी, जो अधिकतम कम्प्रेशन मल्टीपल फाइल टेस्ट के समान एक बेंचमार्क है, लेकिन न्यूनतम गति आवश्यकताओं के साथ। इसने कैलकुलेटर की पेशकश की जिसने उपयोगकर्ता को गति और संपीड़न अनुपात के महत्व को भारित करने की अनुमति दी। गति की आवश्यकता के कारण शीर्ष कार्यक्रम काफी भिन्न थे। जनवरी 2010 में, शीर्ष कार्यक्रम NanoZip था जिसके बाद FreeArc, CCM (सॉफ्टवेयर), flashzip और 7-ज़िप थे।
  • नानिया फ्रांसेस्को एंटोनियो द्वारा द मॉन्स्टर ऑफ कम्प्रेशन बेंचमार्क ने 40 मिनट की समय सीमा के साथ 1 जीबी सार्वजनिक डेटा पर संपीड़न का परीक्षण किया। दिसंबर 2009 में, नैनोजिप 0.07a शीर्ष क्रम का संग्रहकर्ता था और शीर्ष क्रम वाला एकल फ़ाइल कंप्रेसर ccmx 1.30c था।

संपीड़न रेटिंग वेबसाइट ने संपीड़न अनुपात और समय में सीमा का एक चार्ट सारांश प्रकाशित किया।[15]

संपीड़न विश्लेषण उपकरण[16] एक विंडोज एप्लिकेशन है जो अंतिम उपयोगकर्ताओं को अपने स्वयं के डेटा का उपयोग करके LZF4, Deflate, ZLIB, GZIP, BZIP2 और LZMA के स्ट्रीमिंग कार्यान्वयन की प्रदर्शन विशेषताओं को बेंचमार्क करने में सक्षम बनाता है। यह माप और चार्ट तैयार करता है जिसके साथ उपयोगकर्ता विभिन्न संपीड़न विधियों की संपीड़न गति, डीकंप्रेसन गति और संपीड़न अनुपात की तुलना कर सकते हैं और यह जांचने के लिए कि संपीड़न स्तर, बफर आकार और फ्लशिंग ऑपरेशन परिणामों को कैसे प्रभावित करते हैं।

सीमाएं

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

  • मान लें कि प्रत्येक फ़ाइल को कुछ मनमाने ढंग से लंबाई के बिट्स की एक स्ट्रिंग के रूप में दर्शाया गया है।
  • मान लीजिए कि एक संपीड़न एल्गोरिदम है जो प्रत्येक फ़ाइल को आउटपुट फ़ाइल में बदल देता है जो मूल फ़ाइल से अधिक नहीं है, और कम से कम एक फ़ाइल को आउटपुट फ़ाइल में संपीड़ित किया जाएगा जो मूल फ़ाइल से छोटा है।
  • एम को कम से कम संख्या दें जैसे कि लंबाई एम बिट्स वाली एक फ़ाइल एफ है जो कुछ कम करने के लिए संपीड़ित होती है। मान लीजिए कि N, F के संपीडित संस्करण की लंबाई (बिट्स में) है।
  • क्योंकि N <M, लंबाई N की प्रत्येक फ़ाइल संपीड़न के दौरान अपना आकार बनाए रखती है। ऐसी 2N फाइलें संभव हैं। F के साथ मिलकर, यह 2N+1 फ़ाइलें बनाता है जो सभी लंबाई N की 2N फ़ाइलों में से एक में संपीड़ित होती हैं।
  • लेकिन 2N 2N+1 से छोटा है, इसलिए कबूतर के सिद्धांत के अनुसार लंबाई N की कुछ फ़ाइल होनी चाहिए जो एक साथ दो अलग-अलग इनपुट पर संपीड़न फ़ंक्शन का आउटपुट हो। उस फ़ाइल को मज़बूती से विघटित नहीं किया जा सकता है (दो मूल में से कौन सा उपज होना चाहिए?), जो इस धारणा का खंडन करता है कि एल्गोरिथ्म दोषरहित था।
  • इसलिए हमें यह निष्कर्ष निकालना चाहिए कि हमारी मूल परिकल्पना (संपीड़न फ़ंक्शन अब कोई फ़ाइल नहीं बनाता है) आवश्यक रूप से असत्य है।

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

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

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

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

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

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

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

गणितीय पृष्ठभूमि

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

वास्तविक संपीड़न सिद्धांत में आवेदन के बिंदु

वास्तविक संपीड़न एल्गोरिथम डिजाइनर स्वीकार करते हैं कि उच्च सूचना एन्ट्रापी की धाराओं को संकुचित नहीं किया जा सकता है, और तदनुसार, इस स्थिति का पता लगाने और संभालने के लिए सुविधाएं शामिल हैं। पता लगाने का एक स्पष्ट तरीका कच्चे संपीड़न एल्गोरिदम को लागू करना और परीक्षण करना है कि इसका आउटपुट इसके इनपुट से छोटा है या नहीं। कभी-कभी, अनुमानी द्वारा पता लगाया जाता है; उदाहरण के लिए, एक संपीड़न अनुप्रयोग उन फ़ाइलों पर विचार कर सकता है जिनके नाम ".zip", ".arj" या ".lha" में समाप्त होते हैं, बिना किसी अधिक परिष्कृत पहचान के असम्पीडित। इस स्थिति को संभालने का एक सामान्य तरीका इनपुट, या आउटपुट में इनपुट के असम्पीडित भागों को उद्धृत करना है, जिससे कंप्रेशन ओवरहेड को कम किया जा सके। उदाहरण के लिए, ज़िप डेटा प्रारूप उन इनपुट फ़ाइलों के लिए 'संग्रहीत' की 'संपीड़न विधि' निर्दिष्ट करता है जिन्हें शब्दशः संग्रह में कॉपी किया गया है।[23]

द मिलियन रैंडम डिजिट चैलेंज

मार्क नेल्सन, कॉम्प.संपीड़न में दिखाई देने वाले "मैजिक" कम्प्रेशन एल्गोरिदम के दावों के जवाब में, अत्यधिक एंट्रोपिक सामग्री की 415,241 बाइट बाइनरी फ़ाइल का निर्माण किया है, और किसी को प्रोग्राम लिखने के लिए $100 की एक सार्वजनिक चुनौती जारी की है, जो इसके इनपुट के साथ मिलकर, उनके द्वारा प्रदान किए गए बाइनरी डेटा से छोटा होगा फिर भी बिना किसी त्रुटि के इसे पुनर्गठित करने में सक्षम होगा।[24] माइक गोल्डमैन द्वारा पुरस्कार के रूप में $5,000 के साथ एक ऐसी ही चुनौती जारी की गई थी।[25]

यह भी देखें

संदर्भ

  1. ↑ "Unit 4 Lab 4: Data Representation and Compression, Page 6". bjc.edc.org. Retrieved 2022-04-09.
  2. ↑ "सावधान की झुंझलाहट - छवि rars". Retrieved 2021-09-27.
  3. ↑ Price, Andy (3 March 2022). "Lossless Streaming – the future of high res audio". Audio Media International.
  4. ↑ "LZW पेटेंट जानकारी". About Unisys. Unisys. Archived from the original on 2009-06-02.
  5. ↑ Sullivan, Gary (8–12 December 2003). "टेम्पोरल सबबैंड वीडियो कोडिंग के लिए सामान्य विशेषताएँ और डिज़ाइन विचार". ITU-T. Video Coding Experts Group. Retrieved 13 September 2019.
  6. ↑ Unser, M.; Blu, T. (2003). "Mathematical properties of the JPEG2000 wavelet filters" (PDF). IEEE Transactions on Image Processing. 12 (9): 1080–1090. Bibcode:2003ITIP...12.1080U. doi:10.1109/TIP.2003.812329. PMID 18237979. S2CID 2765169. Archived from the original (PDF) on 2019-10-13.
  7. ↑ Bovik, Alan C. (2009). वीडियो प्रोसेसिंग के लिए आवश्यक गाइड. Academic Press. p. 355. ISBN 9780080922508.
  8. ↑ Ahmed, Nasir; Mandyam, Giridhar D.; Magotra, Neeraj (17 April 1995). "दोषरहित छवि संपीड़न के लिए डीसीटी-आधारित योजना". Digital Video Compression: Algorithms and Technologies 1995. International Society for Optics and Photonics. 2419: 474–478. Bibcode:1995SPIE.2419..474M. doi:10.1117/12.206386. S2CID 13894279.
  9. ↑ Komatsu, K.; Sezaki, Kaoru (1998). "प्रतिवर्ती असतत कोसाइन परिवर्तन". Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '98 (Cat. No.98CH36181). 3: 1769–1772 vol.3. doi:10.1109/ICASSP.1998.681802. ISBN 0-7803-4428-6. S2CID 17045923.
  10. ↑ Chanda, P.; Elhaik, E.; Bader, J.S. (2012). "HapZipper: sharing HapMap populations just got easier". Nucleic Acids Res. 40 (20): 1–7. doi:10.1093/nar/gks709. PMC 3488212. PMID 22844100.
  11. ↑ Pratas, D.; Pinho, A. J.; Ferreira, P. J. S. G. (2016). "Efficient compression of genomic sequences". डेटा संपीड़न सम्मेलन (PDF). Snowbird, Utah.{{cite book}}: CS1 maint: location missing publisher (link)
  12. ↑ Matt Mahoney (2010). "डेटा संपीड़न समझाया" (PDF). pp. 3–5.
  13. ↑ "बड़ा पाठ संपीड़न बेंचमार्क". mattmahoney.net.
  14. ↑ "सामान्य संपीड़न बेंचमार्क". mattmahoney.net.
  15. ↑ "सारांश". web.archive.org. September 1, 2016.
  16. ↑ "संपीड़न विश्लेषण उपकरण". Free Tools. Noemax Technologies.
  17. ↑ Sayood 2002, p. 41.
  18. ↑ 18.0 18.1 Bell, Tim (September 28 – October 1, 2015). "आश्चर्यजनक कंप्यूटर विज्ञान". 8th International Conference on Informatics in Schools: Situation, Evolution, and Perspectives. Lecture Notes in Computer Science. Springer. 9378: 8–9. doi:10.1007/978-3-319-25396-1. ISBN 978-3-319-25396-1. S2CID 26313283. Retrieved 2021-08-24.
  19. ↑ "Lossless Compression - an overview | ScienceDirect Topics". www.sciencedirect.com. Retrieved 2022-10-30.
  20. ↑ Sayood 2002, p. 38.
  21. ↑ Li, Ming; Vitányi, Paul (1993). कोलमोगोरोव जटिलता और उसके अनुप्रयोगों का परिचय. New York: Springer. p. 102. ISBN 0-387-94053-7. Theorem 2.6 The function is not partial recursive.
  22. ↑ Joshi, Mark S. (2015-03-18). "Chapter 3 – The Pigeonhole Principle". सबूत पैटर्न. Springer. p. 21. doi:10.1007/978-3-319-16250-8_3. ISBN 978-3-319-16250-8. Retrieved 2021-08-24.
  23. ↑ ".ZIP फ़ाइल स्वरूप विशिष्टता". PKWARE, Inc. chapter V, section J.
  24. ↑ Nelson, Mark (2006-06-20). "The Million Random Digit Challenge Revisited".
  25. ↑ Craig, Patrick. "The $5000 Compression Challenge". Retrieved 2009-06-08.


अग्रिम पठन

  • Sayood, Khalid (2017-10-27). Introduction to Data Compression. The Morgan Kaufmann Series in Multimedia Information and Systems (5 ed.). Morgan Kaufmann. ISBN 978-0-12809474-7. (790 pages)
  • Sayood, Khalid, ed. (2002-12-18). Lossless Compression Handbook (Communications, Networking and Multimedia) (1 ed.). Academic Press. ISBN 978-0-12390754-7. (488 pages)


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=दोषरहित_संपीड़न&oldid=123829’