डेटा कम्प्रेशन समझाया गया
आपके द्वारा खोला गया हर वेब पेज, हर ZIP फ़ाइल और हर PNG इमेज कम्प्रेस की गई है: एक भी बिट खोए बिना छोटी की गई, और पहुँचने पर फिर से खोली गई। इसके पीछे की विधियाँ आश्चर्यजनक रूप से सरल हैं। वे दोहराई जाने वाली चीज़ें ढूँढ़ती हैं, और उन्हें फिर से कहने के बजाय कहती हैं “पहले जैसा ही”। यह विचार कितनी दूर तक जाता है, और कहाँ रुकता है, यह कंप्यूटर विज्ञान की सबसे सुंदर कहानियों में से एक है।
लॉसलेस और लॉसी
कम्प्रेशन दो तरह का होता है। लॉसलेस कम्प्रेशन ठीक मूल को वापस देता है, जो टेक्स्ट, प्रोग्राम, स्प्रेडशीट और हर उस चीज़ के लिए ज़रूरी है जहाँ एक भी ग़लत बिट मायने रखता है। लॉसी कम्प्रेशन, जो फ़ोटो, संगीत और वीडियो के लिए इस्तेमाल होता है, ऐसे ब्यौरे हटा देता है जिन्हें लोग मुश्किल से महसूस करते हैं और कहीं छोटे आकार तक पहुँचता है, पर मूल हमेशा के लिए चला जाता है। यह पेज और डेमो लॉसलेस कम्प्रेशन के बारे में हैं, जो अतिरिक्तता को ढूँढ़कर और हटाकर काम करता है: डेटा के वे हिस्से जिनका अनुमान लगाया जा सकता था।
रन-लेंथ एनकोडिंग
सबसे सरल विधि एक जैसे प्रतीकों के रन को एक गिनती और उस प्रतीक से बदल देती है: बारह सफ़ेद पिक्सेल 12W बन जाते हैं। फ़ैक्स मशीनें, शुरुआती बिटमैप फ़ॉर्मैट और PCX इमेज फ़ॉर्मैट इसका इस्तेमाल करते थे, क्योंकि स्कैन किए गए पन्ने और सरल चित्र लंबे रन से भरे होते हैं। साधारण टेक्स्ट पर यह बेकार, बल्कि नुकसानदेह है: रन दुर्लभ होते हैं, और हर एक अक्षर के लिए गिनती लिखने से आकार दोगुना हो जाता है। रन-लेंथ एनकोडिंग आज भी दूसरी विधियों के भीतर ज़िंदा है, शून्यों के उन रन के लिए जो पहले रूपांतरण के बाद बचते हैं।
LZ77: पीछे की ओर इशारा
1977 में इज़राइल के टेक्नियन के दो शोधकर्ताओं, अब्राहम लेम्पेल और जैकब ज़िव, ने एक ऐसी विधि प्रकाशित की जिसने इस क्षेत्र को बदल दिया। एनकोडर अभी-अभी प्रोसेस किए गए टेक्स्ट की एक विंडो रखता है। अगर अगले अक्षर उस विंडो में पहले आ चुके हों, तो वह एक जोड़ी लिखता है: पहले वाली कॉपी कितनी पीछे शुरू होती है और कितनी लंबी है। वरना वह अक्षर को ही लिख देता है। डिकोडर को किसी शब्दकोश की ज़रूरत नहीं होती, केवल उस टेक्स्ट की जिसे वह पहले ही दोबारा बना चुका है। एक रेफ़रेंस उस टेक्स्ट पर भी चढ़ सकता है जिसे वह ख़ुद बना रहा है, इसलिए 100 एक जैसे अक्षरों का रन बस एक अक्षर और एक रेफ़रेंस होता है।
LZW: शब्दकोश सीखना
लेम्पेल और ज़िव की दूसरी विधि, LZ78, विंडो में पीछे देखने के बजाय एक शब्दकोश बनाती है। टेरी वेल्च का 1984 का सुधार, LZW, सभी 256 बाइट मानों से शुरू होता है और हर चरण में अपनी जानी हुई सबसे लंबी स्ट्रिंग की संख्या भेजता है, फिर उस स्ट्रिंग और अगले अक्षर को नई प्रविष्टि के रूप में जोड़ता है। डिकोडर केवल संख्याओं से वही शब्दकोश फिर से बना लेता है। LZW तेज़ और सरल था, और Unix के compress कमांड, GIF इमेज फ़ॉर्मैट और TIFF फ़ाइलों में इस्तेमाल हुआ, जब तक कि 1990 के दशक में उस पर पेटेंट को लेकर एक लंबा विवाद नहीं छिड़ गया।
Deflate, ZIP और उससे आगे
फ़िल काट्ज़ की deflate विधि, जो 1993 में PKZIP 2 के साथ आई, LZ77 को हफ़मैन कोडिंग के साथ जोड़ती है: दोहराव ढूँढ़ने के बाद वह सबसे आम लिटरल, लंबाइयों और दूरियों को सबसे छोटे बिट कोड देती है। Deflate का इस्तेमाल ZIP, gzip, PNG इमेज और वेब पेजों के कम्प्रेशन में होता है, और डेमो इसी विधि को ब्राउज़र के अपने कम्प्रेसर से मापता है। Zstandard, Brotli और xz जैसी नई विधियाँ बड़ी विंडो, ज़्यादा समझदार मिलान और ज़्यादा सटीक एंट्रॉपी कोडिंग का इस्तेमाल करती हैं, और आम फ़ाइलों को 10 से 30% और छोटा कर देती हैं।
सब कुछ छोटा क्यों नहीं हो सकता
कोई भी विधि हर फ़ाइल को छोटा नहीं कर सकती। n बिट की 2ⁿ फ़ाइलें होती हैं, पर उससे छोटी फ़ाइलें केवल 2ⁿ − 1, इसलिए अगर कोई विधि सभी को छोटा कर दे, तो दो फ़ाइलें एक जैसी हो जाएँगी और दोनों को वापस नहीं पाया जा सकेगा: यही कबूतरखाना सिद्धांत है। इसलिए हर कम्प्रेसर कुछ इनपुट को बड़ा कर देता है, आमतौर पर रैंडम-से दिखने वाले डेटा को, जैसे एन्क्रिप्ट की गई फ़ाइलें, पहले से कम्प्रेस की गई फ़ाइलें और नॉइज़। यह यादृच्छिकता की एक कसौटी भी है: जिस डेटा को कोई कम्प्रेसर छोटा न कर सके, वह रैंडम दिखता है।
एंट्रॉपी की सीमा
क्लॉड शैनन ने 1948 में दिखाया कि किसी स्रोत की एंट्रॉपी किसी भी लॉसलेस कोड के लिए प्रति प्रतीक बिटों की सबसे कम संभव औसत संख्या है। अक्षर-दर-अक्षर गिनने पर अंग्रेज़ी टेक्स्ट की एंट्रॉपी लगभग 4 बिट प्रति अक्षर है, यानी उन 8 बिट का आधा जिनमें उसे संग्रहीत किया जाता है। संदर्भ का इस्तेमाल करने वाली विधियाँ, जैसे LZ77, दोहराव वाले टेक्स्ट पर इस एक-अक्षर वाले आँकड़े से नीचे चली जाती हैं, क्योंकि एक रेफ़रेंस एक साथ पूरे हिस्से का प्रतिनिधित्व करता है। सबसे अच्छे आधुनिक कम्प्रेसर, जो हर अक्षर का अनुमान उससे पहले आई हर चीज़ से लगाते हैं, अंग्रेज़ी को 2 बिट प्रति अक्षर से भी नीचे ले आते हैं।
ख़ुद आज़माएँ
कम्प्रेशन डेमो खोलें और LZ77, LZW और रन-लेंथ एनकोडिंग को किसी अनुच्छेद, मुखड़े वाले गीत, पिक्सेल की पंक्ति, डेटा तालिका, रैंडम अक्षरों या DNA पर, या अपने ख़ुद के टेक्स्ट पर चलाएँ। किसी भी LZ77 रेफ़रेंस पर क्लिक करके देखें कि वह क्या कॉपी करता है, LZW शब्दकोश को बढ़ते देखें, और सभी विधियों की तुलना ZIP और एंट्रॉपी की सीमा से करें।
अक्सर पूछे जाने वाले प्रश्न
3 : 1 के कम्प्रेशन अनुपात का क्या मतलब है?
यह कि मूल, कम्प्रेस किए गए संस्करण से तीन गुना बड़ा है, इसलिए कम्प्रेस की गई फ़ाइल एक-तिहाई जगह लेती है और दो-तिहाई बचाती है। ZIP से टेक्स्ट आमतौर पर 2 : 1 से 4 : 1 तक पहुँचता है; बहुत दोहराव वाला डेटा, जैसे लॉग फ़ाइलें, अक्सर इससे कहीं ज़्यादा।
ZIP फ़ाइल को फिर से कम्प्रेस करने से फ़ायदा क्यों नहीं होता?
पहली बार में ही दोहराव हट चुके होते हैं, और उसका आउटपुट लगभग रैंडम दिखता है। दूसरी बार में वापस इशारा करने के लिए कुछ नहीं मिलता और केवल उसका अपना ओवरहेड जुड़ता है, इसलिए फ़ाइल उतनी ही रहती है या थोड़ी बढ़ जाती है।
LZ77 की बड़ी विंडो बेहतर क्यों है?
बड़ी विंडो से एनकोडर उन दोहरावों को भी ढूँढ़ पाता है जो और पीछे हैं, जैसे कई अंतरों के बाद लौटने वाला मुखड़ा। इसकी कीमत यह है कि हर दूरी लिखने में ज़्यादा बिट लगते हैं और खोज में ज़्यादा समय लगता है, इसीलिए deflate 32 KB पर रुक जाता है और नई विधियाँ मेगाबाइट तक की अनुमति देती हैं।
क्या कम्प्रेशन और एन्क्रिप्शन एक ही चीज़ हैं?
नहीं। कम्प्रेशन डेटा को छोटा करता है और कोई भी उसे पलट सकता है; एन्क्रिप्शन डेटा को कुंजी के बिना अपठनीय बना देता है। दोनों को अक्सर साथ इस्तेमाल किया जाता है, और तब डेटा को पहले कम्प्रेस करना होता है: एन्क्रिप्ट किया गया डेटा रैंडम दिखता है और फिर कम्प्रेस नहीं हो सकता।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
कम्प्रेशन डेमो खोलें