दोषरहित संपीड़न

From alpha
Jump to navigation Jump to search

दोषरहित संपीड़न डेटा संपीड़न का एक वर्ग होता है जो मूल डेटा को जानकारी के नुकसान के बिना संपीड़ित डेटा से पूरी तरह से पुनर्निर्माण करने की अनुमति देता है। दोषरहित संपीड़न संभव होता है क्योंकि अधिकांश वास्तविक-विश्व डेटा सांख्यिकीय अतिरेक प्रदर्शित करता है।[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डी त्रिकोण का दोषरहित संपीड़न

वीडियो

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

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

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

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

जेनेटिक्स कंप्रेशन एल्गोरिदम (आनुवंशिक एल्गोरिदम के साथ भ्रमित नहीं होना) दोषरहित एल्गोरिदम की नवीनतम पीढ़ी है जो पारंपरिक संपीड़न एल्गोरिदम और जेनेटिक डेटा के अनुकूल विशिष्ट एल्गोरिदम दोनों का उपयोग करके डेटा (सामान्यतः न्यूक्लियोटाइड्स के अनुक्रम) को संपीड़ित करता है। 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.
  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://alpha.indicwiki.in/index.php?title=दोषरहित_संपीड़न&oldid=166375"