LZ77 और LZ78

From Vigyanwiki
Revision as of 13:10, 7 December 2023 by alpha>Indicwiki (Created page with "{{Short description|Lossless data compression algorithms}} {{Use dmy dates|date=August 2021}} LZ77 और LZ78 दो दोषरहित डेटा संपीड़...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

LZ77 और LZ78 दो दोषरहित डेटा संपीड़न कलन विधि हैं जिन्हें 1977 में अब्राहम लेम्पेल और जैकब ज़िव द्वारा पत्रों में प्रकाशित किया गया था।[1] और 1978.[2] इन्हें क्रमशः LZ1 और LZ2 के नाम से भी जाना जाता है।[3] ये दो एल्गोरिदम लेम्पेल-ज़िव-वेल्च, लेम्पेल-ज़िव-स्टॉरर-स्ज़िमंस्की, लेम्पेल-ज़िव-मार्कोव श्रृंखला एल्गोरिथ्म और अन्य सहित कई विविधताओं का आधार बनाते हैं। अपने अकादमिक प्रभाव के अलावा, इन एल्गोरिदम ने कई सर्वव्यापी संपीड़न योजनाओं का आधार बनाया, जिसमें GIF और पोर्टेबल नेटवर्क ग्राफ़िक्स और ज़िप (फ़ाइल प्रारूप) में उपयोग किए जाने वाले DEFLATE एल्गोरिदम शामिल हैं।

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

चूँकि LZ77 पहले देखे गए वर्णों पर एक स्लाइडिंग विंडो से एनकोड और डीकोड करता है, इसलिए डीकंप्रेसन हमेशा इनपुट की शुरुआत में शुरू होना चाहिए। वैचारिक रूप से, यदि संपूर्ण शब्दकोश पहले से ज्ञात हो तो LZ78 डीकंप्रेसन इनपुट तक यादृच्छिक पहुंच की अनुमति दे सकता है। हालाँकि, व्यवहार में जब भी कोई टोकन आउटपुट होता है तो एक नया वाक्यांश बनाकर एन्कोडिंग और डिकोडिंग के दौरान शब्दकोश बनाया जाता है।[4] 2004 में एल्गोरिदम को IEEE मील के पत्थर की सूची का नाम दिया गया था।[5] 2021 में जैकब ज़िव को उनके विकास में भागीदारी के लिए आईईईई मेडल ऑफ ऑनर से सम्मानित किया गया था।[6]


सैद्धांतिक दक्षता

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


LZ77

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

मिलान का पता लगाने के लिए, एनकोडर को नवीनतम डेटा की कुछ मात्रा पर नज़र रखनी होगी, जैसे कि अंतिम 2 किलोबाइट, 4 केबी, या 32 केबी। जिस संरचना में यह डेटा रखा जाता है उसे स्लाइडिंग विंडो कहा जाता है, यही कारण है कि LZ77 को कभी-कभी स्लाइडिंग-विंडो संपीड़न भी कहा जाता है। एनकोडर को मैचों को देखने के लिए इस डेटा को रखने की आवश्यकता होती है, और डिकोडर को एनकोडर द्वारा संदर्भित मैचों की व्याख्या करने के लिए इस डेटा को रखने की आवश्यकता होती है। स्लाइडिंग विंडो जितनी बड़ी होगी, एनकोडर संदर्भ बनाने के लिए उतनी ही देर तक खोज कर सकता है।

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

चीजों को देखने का दूसरा तरीका इस प्रकार है: एन्कोडिंग करते समय, खोज सूचक को खोज विंडो के अंत से पहले मिलान जोड़े को ढूंढना जारी रखने के लिए, ऑफसेट डी पर पहले मिलान से लेकर खोज विंडो के अंत तक सभी वर्णों का मिलान होना चाहिए इनपुट, और ये (पहले देखे गए) अक्षर हैं जिनमें लंबाई एल की एकल रन इकाई शामिल हैR, जो डी के बराबर होना चाहिए। फिर जैसे ही खोज सूचक खोज विंडो से आगे बढ़ता है और आगे बढ़ता है, जहां तक ​​​​रन पैटर्न इनपुट में दोहराता है, खोज और इनपुट सूचक सिंक में होंगे और रन पैटर्न बाधित होने तक वर्णों का मिलान करेंगे। फिर कुल मिलाकर L वर्णों का मिलान किया गया है, L > D, और कोड है [D, L, c]।

[डी, एल, सी] को डिकोड करने पर, फिर से, डी = एलR. जब प्रथम एलR वर्णों को आउटपुट में पढ़ा जाता है, यह आउटपुट बफ़र से जुड़ी एकल रन इकाई से मेल खाता है। इस बिंदु पर, पढ़े गए पॉइंटर को केवल int(L/L) वापस करने की आवश्यकता के रूप में सोचा जा सकता हैR) + (1 यदि एल मोडएलR ≠ 0) उस एकल बफ़र्ड रन यूनिट की शुरुआत से पहले, एल पढ़ेंR अक्षर (या शायद अंतिम रिटर्न पर कम), और तब तक दोहराएँ जब तक कि कुल L अक्षर न पढ़ लिए जाएँ। लेकिन एन्कोडिंग प्रक्रिया को प्रतिबिंबित करते हुए, चूंकि पैटर्न दोहराव वाला है, रीड पॉइंटर को केवल रन लेंथ एल के बराबर एक निश्चित दूरी तक राइट पॉइंटर के साथ सिंक करने की आवश्यकता होती है।R जब तक L अक्षर कुल मिलाकर आउटपुट में कॉपी नहीं हो जाते।

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

छद्मकोड

स्यूडोकोड LZ77 कम्प्रेशन एल्गोरिदम स्लाइडिंग विंडो का पुनरुत्पादन है। 

जबकि इनपुट खाली नहीं है
    मिलान := इनपुट की सबसे लंबी बार-बार होने वाली घटना जो विंडो में शुरू होती है
    
    यदि मिलान मौजूद है तो
        d := मैच शुरू होने की दूरी
        एल := मैच की लंबाई
        c := चार इनपुट में मिलान के बाद
    अन्य
        डी := 0
        एल := 0
        c := इनपुट का पहला अक्षर
    अगर अंत
    
    आउटपुट (डी, एल, सी)
    
    विंडो के सामने से l + 1 अक्षर हटा दें
    s := इनपुट के सामने से पॉप l + 1 वर्ण
    विंडो के पीछे s जोड़ें
दोहराना

कार्यान्वयन

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

  • लेम्पेल और ज़िव के मूल 1977 लेख में चित्रित एल्गोरिदम एक समय में अपने सभी डेटा को तीन मानों को आउटपुट करता है: बफर में पाए गए सबसे लंबे मिलान की लंबाई और दूरी, और उस मिलान के बाद का शाब्दिक अर्थ। यदि इनपुट स्ट्रीम में दो क्रमिक वर्णों को केवल शाब्दिक रूप में एन्कोड किया जा सकता है, तो लंबाई-दूरी जोड़ी की लंबाई 0 होगी।
  • LZSS 1-बिट फ़्लैग का उपयोग करके यह इंगित करने के लिए LZ77 में सुधार करता है कि डेटा का अगला हिस्सा एक शाब्दिक या लंबाई-दूरी जोड़ी है, और यदि लंबाई-दूरी जोड़ी लंबी होगी तो शाब्दिक का उपयोग किया जाएगा।
  • पामडॉक प्रारूप में, एक लंबाई-दूरी जोड़ी को हमेशा दो-बाइट अनुक्रम द्वारा एन्कोड किया जाता है। इन दो बाइट्स को बनाने वाले 16 बिट्स में से 11 बिट्स दूरी को एन्कोड करने के लिए जाते हैं, 3 बिट्स लंबाई एन्कोडिंग के लिए जाते हैं, और शेष दो का उपयोग यह सुनिश्चित करने के लिए किया जाता है कि डिकोडर पहले बाइट को ऐसे दो की शुरुआत के रूप में पहचान सकता है- बाइट क्रम.
  • इलेक्ट्रॉनिक आर्ट्स द्वारा कई खेलों के लिए उपयोग किए जाने वाले कार्यान्वयन में,[8] लंबाई-दूरी जोड़ी के बाइट्स में आकार लंबाई-दूरी जोड़ी के पहले बाइट के अंदर ही निर्दिष्ट किया जा सकता है; इस पर निर्भर करते हुए कि पहला बाइट 0, 10, 110, या 111 से शुरू होता है (जब endianness|बिग-एंडियन बिट ओरिएंटेशन में पढ़ा जाता है), पूरी लंबाई-दूरी जोड़ी की लंबाई 1 से 4 बाइट्स हो सकती है।
  • As of 2008, सबसे लोकप्रिय LZ77-आधारित संपीड़न विधि DEFLATE है; यह LZSS को हफ़मैन कोडिंग के साथ जोड़ता है।[9] डेटा के वर्तमान ब्लॉक के अंत को इंगित करने के लिए अक्षर, लंबाई और एक प्रतीक सभी को एक वर्णमाला में एक साथ रखा गया है। दूरियों को सुरक्षित रूप से एक अलग वर्णमाला में रखा जा सकता है; क्योंकि दूरी केवल लंबाई के ठीक बाद होती है, इसे किसी अन्य प्रकार के प्रतीक के रूप में या इसके विपरीत गलत नहीं माना जा सकता है।

LZ78

LZ78 एल्गोरिदम इनपुट से टोकन अनुक्रमों का एक शब्दकोश बनाकर अनुक्रमिक डेटा को संपीड़ित करता है, और फिर शब्दकोश प्रविष्टि के संदर्भ के साथ डेटा स्ट्रीम में अनुक्रम की दूसरी और बाद की घटना को प्रतिस्थापित करता है। अवलोकन यह है कि दोहराए गए अनुक्रमों की संख्या किसी अनुक्रम की गैर-यादृच्छिक प्रकृति का एक अच्छा माप है। एल्गोरिदम शब्दकोश को एक एन-एरी ट्री के रूप में प्रस्तुत करता है जहां एन टोकन अनुक्रम बनाने के लिए उपयोग किए जाने वाले टोकन की संख्या है। प्रत्येक शब्दकोश प्रविष्टि प्रपत्र की है dictionary[...] = {index, token}, जहां सूचकांक एक शब्दकोश प्रविष्टि का सूचकांक है जो पहले देखे गए अनुक्रम का प्रतिनिधित्व करता है, और टोकन इनपुट से अगला टोकन है जो इस प्रविष्टि को शब्दकोश में अद्वितीय बनाता है। ध्यान दें कि एल्गोरिथ्म कितना लालची है, और इसलिए तालिका में तब तक कुछ भी नहीं जोड़ा जाता है जब तक कि एक अद्वितीय निर्माण टोकन नहीं मिल जाता है। एल्गोरिथ्म अंतिम मिलान सूचकांक = 0 और अगले उपलब्ध सूचकांक = 1 को प्रारंभ करना है और फिर, इनपुट स्ट्रीम के प्रत्येक टोकन के लिए, शब्दकोश एक मैच की खोज करता है: {last matching index, token}. यदि कोई मिलान पाया जाता है, तो अंतिम मिलान सूचकांक को मिलान प्रविष्टि के सूचकांक पर सेट किया जाता है, कुछ भी आउटपुट नहीं होता है, और अंतिम मिलान सूचकांक अब तक के इनपुट का प्रतिनिधित्व करने के लिए छोड़ दिया जाता है। इनपुट तब तक संसाधित किया जाता है जब तक कोई मिलान न मिल जाए। फिर एक नई शब्दकोश प्रविष्टि बनाई जाती है, dictionary[next available index] = {last matching index, token}, और एल्गोरिदम अंतिम मिलान सूचकांक को आउटपुट करता है, उसके बाद टोकन देता है, फिर अंतिम मिलान सूचकांक = 0 को रीसेट करता है और अगले उपलब्ध सूचकांक को बढ़ाता है। उदाहरण के तौर पर टोकन के अनुक्रम पर विचार करें AABBA जो शब्दकोश को इकट्ठा करेगा; 

0 {0,_}
1 {0,A}
2 {1,B}
3 {0,B}

और संपीड़ित डेटा का आउटपुट अनुक्रम होगा 0A1B0B. ध्यान दें कि अंतिम A का अभी तक प्रतिनिधित्व नहीं किया गया है क्योंकि एल्गोरिथम यह नहीं जान सकता कि आगे क्या होगा। व्यवहार में एक EOF मार्कर को इनपुट में जोड़ा जाता है - AABBA$ उदाहरण के लिए। यह भी ध्यान दें कि इस मामले में आउटपुट 0A1B0B1$ मूल इनपुट से अधिक लंबा है, लेकिन जैसे-जैसे शब्दकोश बढ़ता है, संपीड़न अनुपात में काफी सुधार होता है, और बाइनरी में इंडेक्स को न्यूनतम संख्या से अधिक बिट्स द्वारा प्रस्तुत करने की आवश्यकता नहीं होती है।[10] डीकंप्रेसन में संपीड़ित अनुक्रम से शब्दकोश का पुनर्निर्माण शामिल है। क्रम से 0A1B0B1$ पहली प्रविष्टि हमेशा टर्मिनेटर होती है 0 {...} , और अनुक्रम से पहला होगा 1 {0,A} . वह A आउटपुट में जोड़ा जाता है। इनपुट से दूसरी जोड़ी है 1B और शब्दकोश में प्रविष्टि संख्या 2 में परिणाम, {1,B}. टोकन बी आउटपुट है, जिसके पहले शब्दकोश प्रविष्टि 1 द्वारा दर्शाया गया अनुक्रम है। प्रविष्टि 1 एक 'ए' है (प्रविष्टि 0 के बाद - कुछ भी नहीं) इसलिए AB आउटपुट में जोड़ा जाता है। अगला 0B को शब्दकोश में अगली प्रविष्टि के रूप में जोड़ा गया है, 3 {0,B} , और बी (पहले कुछ नहीं) को आउटपुट में जोड़ा जाता है। अंत में एक शब्दकोष प्रविष्टि 1$ बनाया गया है और A$ परिणामी आउटपुट है A AB B A$ या AABBAरिक्त स्थान और EOF मार्कर को हटाना।

LZW

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

BTLZ एक LZ78-आधारित एल्गोरिदम है जिसे वास्तविक समय संचार प्रणालियों (मूल रूप से मॉडेम) में उपयोग के लिए विकसित किया गया था और CCITT/ITU द्वारा V.42bis के रूप में मानकीकृत किया गया था। जब त्रि-संरचित शब्दकोश भर जाता है, तो यह सुनिश्चित करने के लिए एक सरल पुन: उपयोग/पुनर्प्राप्ति एल्गोरिदम का उपयोग किया जाता है कि शब्दकोश बदलते डेटा के अनुसार अनुकूलन जारी रख सकता है। एक काउंटर शब्दकोष के माध्यम से घूमता है। जब एक नई प्रविष्टि की आवश्यकता होती है, तो काउंटर शब्दकोष के माध्यम से तब तक कदम उठाता है जब तक कि एक लीफ नोड नहीं मिल जाता (कोई आश्रित नोड नहीं)। इसे हटा दिया गया है और नई प्रविष्टि के लिए स्थान का पुन: उपयोग किया गया है। एलआरयू या एलएफयू की तुलना में इसे लागू करना आसान है और समकक्ष प्रदर्शन प्राप्त होता है।

यह भी देखें

  • लेम्पेल-ज़िव-स्टैक (एलजेडएस)

संदर्भ

  1. ↑ Ziv, Jacob; Lempel, Abraham (May 1977). "A Universal Algorithm for Sequential Data Compression". IEEE Transactions on Information Theory. 23 (3): 337–343. CiteSeerX 10.1.1.118.8921. doi:10.1109/TIT.1977.1055714. S2CID 9267632.
  2. ↑ Ziv, Jacob; Lempel, Abraham (September 1978). "Compression of Individual Sequences via Variable-Rate Coding". IEEE Transactions on Information Theory. 24 (5): 530–536. CiteSeerX 10.1.1.14.2892. doi:10.1109/TIT.1978.1055934.
  3. ↑ US Patent No. 5532693 Adaptive data compression system with systolic string matching logic
  4. ↑ "Lossless Data Compression: LZ78". cs.stanford.edu.
  5. ↑ "Milestones:Lempel-Ziv Data Compression Algorithm, 1977". IEEE Global History Network. Institute of Electrical and Electronics Engineers. 22 July 2014. Retrieved 9 November 2014.
  6. ↑ Joanna, Goodrich. "आईईईई मेडल ऑफ ऑनर डेटा कंप्रेशन पायनियर जैकब ज़िव को जाता है". IEEE Spectrum: Technology, Engineering, and Science News (in English). Retrieved 18 January 2021.
  7. ↑ Peter Shor (14 October 2005). "Lempel-Ziv notes" (PDF). Archived from the original (PDF) on 28 May 2021. Retrieved 9 November 2014.
  8. ↑ "QFS Compression (RefPack)". Niotso Wiki. Retrieved 9 November 2014.
  9. ↑ Feldspar, Antaeus (23 August 1997). "An Explanation of the Deflate Algorithm". comp.compression newsgroup. zlib.net. Retrieved 9 November 2014.
  10. ↑ https://math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf[bare URL PDF]


बाहरी संबंध

  • "The LZ78 algorithm". Data Compression Reference Center: RASIP working group. Faculty of Electrical Engineering and Computing, University of Zagreb. 1997. Archived from the original on 7 January 2013. Retrieved 22 June 2012.
  • "The LZW algorithm". Data Compression Reference Center: RASIP working group. Faculty of Electrical Engineering and Computing, University of Zagreb. 1997. Archived from the original on 7 January 2013. Retrieved 22 June 2012.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=LZ77_और_LZ78&oldid=279968’