दोषरहित डेटा संपीड़न कैसे काम करता है | क्वांटा पत्रिका

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

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

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

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

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

फ़ानो ने समस्या के इस भाग को हल किया था। उन्होंने महसूस किया कि वे महंगे स्थान की आवश्यकता के बिना अलग-अलग लंबाई के कोड का उपयोग कर सकते हैं, जब तक कि उन्होंने अंकों के समान पैटर्न का उपयोग कभी भी एक पूर्ण कोड और दूसरे कोड की शुरुआत के रूप में नहीं किया। उदाहरण के लिए, यदि किसी विशेष संदेश में अक्षर S इतना सामान्य था कि फ़ानो ने इसे अत्यंत संक्षिप्त कोड 01 निर्दिष्ट किया, तो उस संदेश में कोई भी अन्य अक्षर 01 से शुरू होने वाली किसी भी चीज़ से एन्कोड नहीं किया जाएगा; 010, 011 या 0101 जैसे कोड प्रतिबंधित होंगे। नतीजतन, कोडित संदेश को बिना किसी अस्पष्टता के बाएं से दाएं पढ़ा जा सकता है। उदाहरण के लिए, अक्षर S असाइन किए गए 01 के साथ, अक्षर A असाइन किए गए 000, अक्षर M असाइन किए गए 001, और अक्षर L असाइन किए गए 1, अचानक संदेश 0100100011 को तुरंत "छोटा" शब्द में अनुवादित किया जा सकता है, भले ही L को एक द्वारा दर्शाया गया हो अंक, S को दो अंकों से, और अन्य अक्षरों को तीन-तीन अंकों से।

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

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

परिणाम उल्लेखनीय रूप से प्रभावी संपीड़न था। लेकिन यह केवल एक सन्निकटन था; एक बेहतर संपीड़न रणनीति मौजूद थी। इसलिए फ़ानो ने अपने छात्रों को इसे खोजने की चुनौती दी।

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

एक संदेश पर विचार करें जहां फ़ानो दृष्टिकोण लड़खड़ाता है। "स्कूलरूम" में, O चार बार प्रकट होता है, और S/C/H/L/R/M प्रत्येक एक बार प्रकट होता है। फ़ानो का संतुलन दृष्टिकोण O और एक अन्य अक्षर को बाईं शाखा में निर्दिष्ट करके शुरू होता है, जिसमें उन अक्षरों के पाँच कुल उपयोग शेष अक्षरों के पाँच दिखावे को संतुलित करते हैं। परिणामी संदेश के लिए 27 बिट्स की आवश्यकता होती है।

हफ़मैन, इसके विपरीत, दो असामान्य अक्षरों से शुरू होता है - कहते हैं, आर और एम - और उन्हें एक साथ समूहित करते हैं, जोड़ी को एक अक्षर की तरह मानते हैं।

उसका अपडेटेड फ़्रीक्वेंसी चार्ट तब उसे चार विकल्प प्रदान करता है: O जो चार बार प्रकट होता है, नया संयुक्त RM नोड जो कार्यात्मक रूप से दो बार उपयोग किया जाता है, और एकल अक्षर S, C, H और L। हफ़मैन फिर से दो सबसे कम सामान्य विकल्प चुनते हैं, मेल खाते हैं (कहते हैं) एल के साथ एच।

चार्ट फिर से अपडेट होता है: O का अभी भी 4 का वजन है, RM और HL का अब प्रत्येक का वजन 2 है, और अक्षर S और C अकेले हैं। हफमैन वहां से जारी है, प्रत्येक चरण में दो कम से कम लगातार विकल्पों को समूहीकृत करना और फिर पेड़ और आवृत्ति चार्ट दोनों को अद्यतन करना।

आखिरकार, "स्कूलरूम" 11101111110000110110000101 बन जाता है, जो फ़ानो टॉप-डाउन दृष्टिकोण से थोड़ा हटकर है।

एक बिट ज्यादा नहीं लग सकता है, लेकिन अरबों गीगाबाइट्स द्वारा स्केल किए जाने पर भी छोटी बचत बहुत बड़ी हो जाती है।

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

मूल रूप से स्नातक छात्र की अंतिम परीक्षा छोड़ने की इच्छा से प्रेरित एक परियोजना के लिए बुरा नहीं है।