LZ77 और LZ78: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Lossless data compression algorithms}} {{Use dmy dates|date=August 2021}} LZ77 और LZ78 दो दोषरहित डेटा संपीड़...")
 
m (13 revisions imported from alpha:LZ77_और_LZ78)
 
(12 intermediate revisions by 2 users not shown)
Line 1: Line 1:
{{Short description|Lossless data compression algorithms}}
{{Short description|Lossless data compression algorithms}}
{{Use dmy dates|date=August 2021}}
'''LZ77 और LZ78''' दो [[दोषरहित डेटा संपीड़न|लॉसलेस डेटा कम्प्रेशन]] [[कलन विधि|एल्गोरिथम]] हैं जिन्हें 1977 और 1978 में [[अब्राहम लेम्पेल]] और [[जैकब ज़िव]] द्वारा पेपरों में प्रकाशित किया गया था।<ref>{{cite journal
LZ77 और LZ78 दो [[दोषरहित डेटा संपीड़न]] [[कलन विधि]] हैं जिन्हें 1977 में [[अब्राहम लेम्पेल]] और [[जैकब ज़िव]] द्वारा पत्रों में प्रकाशित किया गया था।<ref>{{cite journal
  | first1 = Jacob
  | first1 = Jacob
  | last1 = Ziv
  | last1 = Ziv
Line 17: Line 16:
  | citeseerx = 10.1.1.118.8921
  | citeseerx = 10.1.1.118.8921
| s2cid = 9267632
| s2cid = 9267632
  }}</ref> और 1978.<ref>{{cite journal
  }}</ref><ref>{{cite journal
  | first1 = Jacob
  | first1 = Jacob
  | last1 = Ziv
  | last1 = Ziv
Line 31: Line 30:
  | date = September 1978
  | date = September 1978
  | doi = 10.1109/TIT.1978.1055934 | citeseerx = 10.1.1.14.2892
  | doi = 10.1109/TIT.1978.1055934 | citeseerx = 10.1.1.14.2892
}}</ref>
}}</ref> इन्हें क्रमशः LZ1 और LZ2 के नाम से भी जाना जाता है।<ref>{{USPTO Patent|patnum=5532693|title=Adaptive data compression system with systolic string matching logic}}</ref> ये दो एल्गोरिथम लेम्पेल-ज़िव-वेल्च, [[लेम्पेल-ज़िव-स्टॉरर-स्ज़िमंस्की]], [[लेम्पेल-ज़िव-मार्कोव श्रृंखला एल्गोरिथ्म|लेम्पेल-ज़िव-मार्कोव चेन एल्गोरिथ्म]] और अन्य सहित कई वेरिएशनों का आधार बनाते हैं। अपने शैक्षणिक प्रभाव के अतिरिक्त, इन एल्गोरिथम ने कई यूबीक्विटस कम्प्रेशन स्कीमों का आधार बनाया, जिसमें [[GIF|ग्राफ़िक्स इंटरचेंज फॉर्मैट]], [[ पोर्टेबल नेटवर्क ग्राफ़िक्स |पोर्टेबल नेटवर्क ग्राफ़िक्स]] और ज़िप (फ़ाइल फॉर्मैट) में उपयोग किए जाने वाले [[DEFLATE|डीफ़्लेट]] एल्गोरिथम सम्मिलित हैं।
इन्हें क्रमशः LZ1 और LZ2 के नाम से भी जाना जाता है।<ref>{{USPTO Patent|patnum=5532693|title=Adaptive data compression system with systolic string matching logic}}</ref> ये दो एल्गोरिदम लेम्पेल-ज़िव-वेल्च, [[लेम्पेल-ज़िव-स्टॉरर-स्ज़िमंस्की]], [[लेम्पेल-ज़िव-मार्कोव श्रृंखला एल्गोरिथ्म]] और अन्य सहित कई विविधताओं का आधार बनाते हैं। अपने अकादमिक प्रभाव के अलावा, इन एल्गोरिदम ने कई सर्वव्यापी संपीड़न योजनाओं का आधार बनाया, जिसमें [[GIF]] और [[ पोर्टेबल नेटवर्क ग्राफ़िक्स ]] और ज़िप (फ़ाइल प्रारूप) में उपयोग किए जाने वाले [[DEFLATE]] एल्गोरिदम शामिल हैं।
 
वे दोनों सैद्धांतिक रूप से [[शब्दकोश कोडर|डिक्शनरी कोडर]] हैं। LZ77 कम्प्रेशन के समय स्लाइडिंग विंडो को मेन्टेन रखता है। इसे कुछ समय पश्चात LZ78 द्वारा निर्मित एक्सप्लिसिट डिक्शनरी के समकक्ष दर्शाया गया - यद्यपि, वे केवल तभी समकक्ष हैं जब संपूर्ण डेटा को डिकम्प्रेस करने का आशय हो।


वे दोनों सैद्धांतिक रूप से [[शब्दकोश कोडर]] हैं। LZ77 संपीड़न के दौरान एक स्लाइडिंग विंडो बनाए रखता है। इसे बाद में LZ78 द्वारा निर्मित स्पष्ट शब्दकोश के समतुल्य दिखाया गया - हालाँकि, वे केवल तभी समतुल्य हैं जब संपूर्ण डेटा को विघटित करने का इरादा हो।
चूँकि LZ77 पूर्व देखे गए कैरेक्टर्स पर स्लाइडिंग विंडो से एनकोड और डीकोड करता है, इसलिए डीकंप्रेसन सदैव इनपुट के प्रारम्भ में ही प्रारम्भ होना चाहिए। वैचारिक रूप से, यदि संपूर्ण डिक्शनरी पूर्व से ज्ञात हो तो LZ78 डीकंप्रेसन इनपुट तक रैंडम एक्सेस की अनुमति दे सकता है। यद्यपि, प्रैक्टिस में जब भी कोई टोकन आउटपुट होता है तो नए फ्रेज को क्रिएट करके एन्कोडिंग और डिकोडिंग के समय डिक्शनरी को क्रिएट किया जाता है।<ref>{{Cite web|url=https://cs.stanford.edu/people/eroberts/courses/soco/projects/data-compression/lossless/lz78/concept.htm|title=Lossless Data Compression: LZ78|website=cs.stanford.edu}}</ref>


चूँकि LZ77 पहले देखे गए वर्णों पर एक स्लाइडिंग विंडो से एनकोड और डीकोड करता है, इसलिए डीकंप्रेसन हमेशा इनपुट की शुरुआत में शुरू होना चाहिए। वैचारिक रूप से, यदि संपूर्ण शब्दकोश पहले से ज्ञात हो तो LZ78 डीकंप्रेसन इनपुट तक यादृच्छिक पहुंच की अनुमति दे सकता है। हालाँकि, व्यवहार में जब भी कोई टोकन आउटपुट होता है तो एक नया वाक्यांश बनाकर एन्कोडिंग और डिकोडिंग के दौरान शब्दकोश बनाया जाता है।<ref>{{Cite web|url=https://cs.stanford.edu/people/eroberts/courses/soco/projects/data-compression/lossless/lz78/concept.htm|title=Lossless Data Compression: LZ78|website=cs.stanford.edu}}</ref>
2004 में एल्गोरिथम को आईईईई माइलस्टोन नाम दिया गया था।<ref>{{cite web
2004 में एल्गोरिदम को IEEE मील के पत्थर की सूची का नाम दिया गया था।<ref>{{cite web
| url=http://www.ieeeghn.org/wiki/index.php/Milestones:Lempel-Ziv_Data_Compression_Algorithm,_1977
| url=http://www.ieeeghn.org/wiki/index.php/Milestones:Lempel-Ziv_Data_Compression_Algorithm,_1977
| title=Milestones:Lempel-Ziv Data Compression Algorithm, 1977
| title=Milestones:Lempel-Ziv Data Compression Algorithm, 1977
Line 45: Line 44:
| access-date=2014-11-09}}</ref> 2021 में जैकब ज़िव को उनके विकास में भागीदारी के लिए [[आईईईई मेडल ऑफ ऑनर]] से सम्मानित किया गया था।<ref>{{Cite web|last=Joanna|first=Goodrich|title=आईईईई मेडल ऑफ ऑनर डेटा कंप्रेशन पायनियर जैकब ज़िव को जाता है|url=https://spectrum.ieee.org/the-institute/ieee-member-news/ieee-medal-of-honor-goes-to-data-compression-pioneer-jacob-ziv|access-date=2021-01-18|website=IEEE Spectrum: Technology, Engineering, and Science News|language=en}}</ref>
| access-date=2014-11-09}}</ref> 2021 में जैकब ज़िव को उनके विकास में भागीदारी के लिए [[आईईईई मेडल ऑफ ऑनर]] से सम्मानित किया गया था।<ref>{{Cite web|last=Joanna|first=Goodrich|title=आईईईई मेडल ऑफ ऑनर डेटा कंप्रेशन पायनियर जैकब ज़िव को जाता है|url=https://spectrum.ieee.org/the-institute/ieee-member-news/ieee-medal-of-honor-goes-to-data-compression-pioneer-jacob-ziv|access-date=2021-01-18|website=IEEE Spectrum: Technology, Engineering, and Science News|language=en}}</ref>


 
== सैद्धांतिक दक्षता ==
==सैद्धांतिक दक्षता==
इन एल्गोरिथम को प्रस्तुत करने वाले दो पेपरों में से दूसरे में उनका विश्लेषण फाइनाइट-स्टेट मशीनों द्वारा डिफाइन एनकोडर के रूप में किया गया है। [[सूचना एन्ट्रापी|इनफार्मेशन एन्ट्रापी]] के अनुरूप माप इंडिविजुअल सीक्वेन्सों (संभाव्य संयोजनों के विपरीत) के लिए विकसित किया गया है। यह माप [[डेटा संपीड़न अनुपात|डेटा कम्प्रेशन रेश्यो]] पर बाउंड देता है जिसे प्राप्त किया जा सकता है। फिर यह दर्शाया गया है कि प्रत्येक सीक्वेंस के लिए फाइनाइट लॉसलेस एनकोडर उपस्थित हैं जो इस बाउंड को प्राप्त करते हैं क्योंकि सीक्वेंस की लेंथ इंफिनिटी तक जाती है। इस अर्थ में इस स्कीम पर आधारित एल्गोरिथम असममित रूप से ऑप्टीमल एन्कोडिंग उत्पन्न करता है। इस परिणाम को प्रत्यक्ष रूप से सिद्ध किया जा सकता है, उदाहरण के लिए इसे [[पीटर शोर]] के नोट्स में दर्शाया गया है।<ref>{{cite web
इन एल्गोरिदम को पेश करने वाले दो पेपरों में से दूसरे में उनका विश्लेषण परिमित-राज्य मशीनों द्वारा परिभाषित एनकोडर के रूप में किया गया है। [[सूचना एन्ट्रापी]] के अनुरूप एक माप व्यक्तिगत अनुक्रमों के लिए विकसित किया गया है (संभाव्य संयोजनों के विपरीत)। यह माप [[डेटा संपीड़न अनुपात]] पर एक सीमा देता है जिसे हासिल किया जा सकता है। फिर यह दिखाया गया है कि प्रत्येक अनुक्रम के लिए परिमित दोषरहित एनकोडर मौजूद हैं जो इस सीमा को प्राप्त करते हैं क्योंकि अनुक्रम की लंबाई अनंत तक बढ़ती है। इस अर्थ में इस योजना पर आधारित एक एल्गोरिदम असममित रूप से इष्टतम एन्कोडिंग उत्पन्न करता है। इस परिणाम को अधिक सीधे तौर पर सिद्ध किया जा सकता है, उदाहरण के लिए [[पीटर शोर]] के नोट्स में।<ref>{{cite web
| url=http://www-math.mit.edu/~shor/PAM/lempel_ziv_notes.pdf
| url=http://www-math.mit.edu/~shor/PAM/lempel_ziv_notes.pdf
| title=Lempel-Ziv notes
| title=Lempel-Ziv notes
Line 59: Line 57:
}}</ref>
}}</ref>


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


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


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


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


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


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


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


  जबकि इनपुट खाली नहीं है
  '''while''' input is not empty '''do'''
     मिलान := इनपुट की सबसे लंबी बार-बार होने वाली घटना जो विंडो में शुरू होती है
     match := longest repeated occurrence of input that begins in window
   
 
     यदि मिलान मौजूद है तो
     '''if''' match exists '''then'''
         d := मैच शुरू होने की दूरी
         d := distance to start of match
         एल := मैच की लंबाई
         l := length of match
         c := चार इनपुट में मिलान के बाद
         c := char following match in input
     अन्य
     '''else'''
         डी := 0
         d:= 0
         एल := 0
         l:= 0
         c := इनपुट का पहला अक्षर
         c:= first char of input
     अगर अंत
     '''end if'''
   
 
     आउटपुट (डी, एल, सी)
     '''output''' (d, l, c)
   
 
     विंडो के सामने से ''l'' + 1 अक्षर हटा दें
     discard ''l'' + 1 chars from front of window
     s := इनपुट के सामने से पॉप ''l'' + 1 वर्ण
     s := pop ''l'' + 1 chars from front of input
     विंडो के पीछे s जोड़ें
     append s to back of window
  दोहराना
  '''repeat'''


===कार्यान्वयन===
===इम्प्लीमेंटेशन्स===
भले ही सभी LZ77 एल्गोरिदम एक ही मूल सिद्धांत पर परिभाषा के अनुसार काम करते हैं, वे लंबाई-दूरी जोड़ी की संख्यात्मक सीमाओं को बदलने के लिए अपने संपीड़ित डेटा को एन्कोड करने के तरीके में व्यापक रूप से भिन्न हो सकते हैं, लंबाई-दूरी जोड़ी के लिए उपभोग किए गए बिट्स की संख्या को बदल सकते हैं, और उनके लंबाई-दूरी जोड़े को शाब्दिक से अलग करें (कच्चे डेटा को लंबाई-दूरी जोड़ी के हिस्से के बजाय स्वयं के रूप में एन्कोड किया गया है)। कुछ उदाहरण:
सभी LZ77 एल्गोरिथम एक ही बेसिक प्रिंसिपल पर परिभाषा के अनुसार कार्य करते हैं, वे लेंथ-डिस्टेंस पेअर की न्यूमेरिकल रेंज को परिवर्तित करने के लिए अपने कंप्रेस्ड डेटा को एन्कोड करने के प्रकार में व्यापक रूप से भिन्न हो सकते हैं, लेंथ-डिस्टेंस पेअर के लिए उपभोग किए गए बिट्स की संख्या को परिवर्तित कर सकते हैं, और उनके लेंथ-डिस्टेंस पेअर को लिटेरल्स से अलग करें (कच्चे डेटा को लेंथ-डिस्टेंस पेअर के भाग के अतिरिक्त स्वयं के रूप में एन्कोड किया गया है)। कुछ उदाहरण इस प्रकार हैं:
* लेम्पेल और ज़िव के मूल 1977 लेख में चित्रित एल्गोरिदम एक समय में अपने सभी डेटा को तीन मानों को आउटपुट करता है: बफर में पाए गए सबसे लंबे मिलान की लंबाई और दूरी, और उस मिलान के बाद का शाब्दिक अर्थ। यदि इनपुट स्ट्रीम में दो क्रमिक वर्णों को केवल शाब्दिक रूप में एन्कोड किया जा सकता है, तो लंबाई-दूरी जोड़ी की लंबाई 0 होगी।
* लेम्पेल और ज़िव के मूल 1977 लेख में चित्रित एल्गोरिथम एक समय में अपने सभी डेटा को तीन मानों को आउटपुट करता है: बफर में पाए गए सबसे लंबे मैच की लेंथ और डिस्टेंस, और उस मैच के पश्चात का लिटेरल्स अर्थ। यदि इनपुट स्ट्रीम में दो क्रमिक करैक्टर को केवल लिटेरल्स रूप में एन्कोड किया जा सकता है, तो लेंथ-डिस्टेंस पेअर की लेंथ 0 होगी।
* [[LZSS]] 1-बिट फ़्लैग का उपयोग करके यह इंगित करने के लिए LZ77 में सुधार करता है कि डेटा का अगला हिस्सा एक शाब्दिक या लंबाई-दूरी जोड़ी है, और यदि लंबाई-दूरी जोड़ी लंबी होगी तो शाब्दिक का उपयोग किया जाएगा।
* [[LZSS]] 1-बिट फ़्लैग का उपयोग करके यह इंगित करने के लिए LZ77 में सुधार करता है कि डेटा का अगला भाग लिटेरल्स या लेंथ-डिस्टेंस पेअर है, और यदि लेंथ-डिस्टेंस पेअर लंबी होगी तो लिटेरल्स का उपयोग किया जाएगा।
* पामडॉक प्रारूप में, एक लंबाई-दूरी जोड़ी को हमेशा दो-बाइट अनुक्रम द्वारा एन्कोड किया जाता है। इन दो बाइट्स को बनाने वाले 16 बिट्स में से 11 बिट्स दूरी को एन्कोड करने के लिए जाते हैं, 3 बिट्स लंबाई एन्कोडिंग के लिए जाते हैं, और शेष दो का उपयोग यह सुनिश्चित करने के लिए किया जाता है कि डिकोडर पहले बाइट को ऐसे दो की शुरुआत के रूप में पहचान सकता है- बाइट क्रम.
* पामडॉक फॉर्मैट में, लेंथ-डिस्टेंस पेअर को सदैव दो-बाइट अनुक्रम द्वारा एन्कोड किया जाता है। इन दो बाइट्स को बनाने वाले 16 बिट्स में से 11 बिट्स डिस्टेंस को एन्कोड करने के लिए जाते हैं, 3 बिट्स लेंथ एन्कोडिंग के लिए जाते हैं, और शेष दो का उपयोग यह सुनिश्चित करने के लिए किया जाता है कि डिकोडर प्रथम बाइट को ऐसे दो बाइट क्रम के प्रारम्भ के रूप में पहचान सकता है।
* [[इलेक्ट्रॉनिक आर्ट]]्स द्वारा कई खेलों के लिए उपयोग किए जाने वाले कार्यान्वयन में,<ref>{{cite web
* [[इलेक्ट्रॉनिक आर्ट|इलेक्ट्रॉनिक आर्ट्स]] द्वारा कई खेलों के लिए उपयोग किए जाने वाले कार्यान्वयन में,<ref>{{cite web
| url=http://wiki.niotso.org/QFS_compression
| url=http://wiki.niotso.org/QFS_compression
| title=QFS Compression (RefPack)
| title=QFS Compression (RefPack)
| work=Niotso Wiki
| work=Niotso Wiki
| access-date=2014-11-09}}</ref> लंबाई-दूरी जोड़ी के बाइट्स में आकार लंबाई-दूरी जोड़ी के पहले बाइट के अंदर ही निर्दिष्ट किया जा सकता है; इस पर निर्भर करते हुए कि पहला बाइट 0, 10, 110, या 111 से शुरू होता है (जब [[endianness]]|बिग-एंडियन बिट ओरिएंटेशन में पढ़ा जाता है), पूरी लंबाई-दूरी जोड़ी की लंबाई 1 से 4 बाइट्स हो सकती है।
| access-date=2014-11-09}}</ref> लेंथ-डिस्टेंस पेअर के बाइट्स में आकार लेंथ-डिस्टेंस पेअर के प्रथम बाइट के अंदर ही निर्दिष्ट किया जा सकता है; इस पर निर्भर करते हुए कि प्रथम बाइट 0, 10, 110, या 111 से प्रारम्भ होता है (जब [[endianness|बिग-एंडियन]] बिट ओरिएंटेशन में पढ़ा जाता है), पूर्ण लेंथ-डिस्टेंस पेअर की लेंथ 1 से 4 बाइट्स हो सकती है।
* {{As of|2008}}, सबसे लोकप्रिय LZ77-आधारित संपीड़न विधि [[DEFLATE]] है; यह LZSS को [[हफ़मैन कोडिंग]] के साथ जोड़ता है।<ref>{{cite web
* {{As of|2008}}, सबसे लोकप्रिय LZ77-आधारित कम्प्रेशन विधि [[DEFLATE]] है; यह LZSS को [[हफ़मैन कोडिंग]] के साथ जोड़ता है।<ref>{{cite web
| url=http://www.zlib.net/feldspar.html
| url=http://www.zlib.net/feldspar.html
| title= An Explanation of the Deflate Algorithm
| title= An Explanation of the Deflate Algorithm
Line 114: Line 111:
| work=comp.compression [[Usenet newsgroup|newsgroup]]
| work=comp.compression [[Usenet newsgroup|newsgroup]]
| publisher=zlib.net
| publisher=zlib.net
| access-date=2014-11-09}}</ref> डेटा के वर्तमान ब्लॉक के अंत को इंगित करने के लिए अक्षर, लंबाई और एक प्रतीक सभी को एक वर्णमाला में एक साथ रखा गया है। दूरियों को सुरक्षित रूप से एक अलग वर्णमाला में रखा जा सकता है; क्योंकि दूरी केवल लंबाई के ठीक बाद होती है, इसे किसी अन्य प्रकार के प्रतीक के रूप में या इसके विपरीत गलत नहीं माना जा सकता है।
| access-date=2014-11-09}}</ref> डेटा के वर्तमान ब्लॉक के अंत को इंगित करने के लिए करैक्टर, लेंथ और सिंबल सभी को वर्णमाला में साथ रखा गया है। दूरियों को सुरक्षित रूप से अलग वर्णमाला में रखा जा सकता है; क्योंकि डिस्टेंस केवल लेंथ के पश्चात होती है, इसे किसी अन्य प्रकार के सिंबल के रूप में या इसके विपरीत गलत नहीं माना जा सकता है।


==LZ78==
==LZ78==
LZ78 एल्गोरिदम इनपुट से टोकन अनुक्रमों का एक शब्दकोश बनाकर अनुक्रमिक डेटा को संपीड़ित करता है, और फिर शब्दकोश प्रविष्टि के संदर्भ के साथ डेटा स्ट्रीम में अनुक्रम की दूसरी और बाद की घटना को प्रतिस्थापित करता है। अवलोकन यह है कि दोहराए गए अनुक्रमों की संख्या किसी अनुक्रम की गैर-यादृच्छिक प्रकृति का एक अच्छा माप है। एल्गोरिदम शब्दकोश को एक एन-एरी ट्री के रूप में प्रस्तुत करता है जहां एन टोकन अनुक्रम बनाने के लिए उपयोग किए जाने वाले टोकन की संख्या है। प्रत्येक शब्दकोश प्रविष्टि प्रपत्र की है {{code|1=dictionary[...] = {index, token} }}, जहां सूचकांक एक शब्दकोश प्रविष्टि का सूचकांक है जो पहले देखे गए अनुक्रम का प्रतिनिधित्व करता है, और टोकन इनपुट से अगला टोकन है जो इस प्रविष्टि को शब्दकोश में अद्वितीय बनाता है। ध्यान दें कि एल्गोरिथ्म कितना लालची है, और इसलिए तालिका में तब तक कुछ भी नहीं जोड़ा जाता है जब तक कि एक अद्वितीय निर्माण टोकन नहीं मिल जाता है। एल्गोरिथ्म अंतिम मिलान सूचकांक = 0 और अगले उपलब्ध सूचकांक = 1 को प्रारंभ करना है और फिर, इनपुट स्ट्रीम के प्रत्येक टोकन के लिए, शब्दकोश एक मैच की खोज करता है: {{code|{{mset|last matching index, token}}}}. यदि कोई मिलान पाया जाता है, तो अंतिम मिलान सूचकांक को मिलान प्रविष्टि के सूचकांक पर सेट किया जाता है, कुछ भी आउटपुट नहीं होता है, और अंतिम मिलान सूचकांक अब तक के इनपुट का प्रतिनिधित्व करने के लिए छोड़ दिया जाता है। इनपुट तब तक संसाधित किया जाता है जब तक कोई मिलान न मिल जाए। फिर एक नई शब्दकोश प्रविष्टि बनाई जाती है, {{code|1=dictionary[next available index] = {last matching index, token} }}, और एल्गोरिदम अंतिम मिलान सूचकांक को आउटपुट करता है, उसके बाद टोकन देता है, फिर अंतिम मिलान सूचकांक = 0 को रीसेट करता है और अगले उपलब्ध सूचकांक को बढ़ाता है। उदाहरण के तौर पर टोकन के अनुक्रम पर विचार करें {{samp|AABBA}} जो शब्दकोश को इकट्ठा करेगा;
LZ78 एल्गोरिथम इनपुट से टोकन अनुक्रमों का डिक्शनरी बनाकर अनुक्रमिक डेटा को कंप्रेस्ड करता है, और फिर डिक्शनरी एंट्री के संदर्भ के साथ डेटा स्ट्रीम में अनुक्रम की दूसरी और पश्चात की घटना को प्रतिस्थापित करता है। अवलोकन यह है कि दोहराए गए अनुक्रमों की संख्या किसी अनुक्रम की नॉन-रैंडम प्रकृति का अच्छा माप है। एल्गोरिथम डिक्शनरी को n-एरी ट्री के रूप में प्रस्तुत करता है जहां n टोकन अनुक्रम बनाने के लिए उपयोग किए जाने वाले टोकन की संख्या है। प्रत्येक डिक्शनरी एंट्री डिक्शनरी फॉर्म की होती है {{code|1=dictionary[...] = {index, token} }}, जहां इंडेक्स डिक्शनरी एंट्री का इंडेक्स है जो पूर्व में देखे गए अनुक्रम का प्रतिनिधित्व करता है, और टोकन इनपुट से नेक्स्ट टोकन है जो इस एंट्री को डिक्शनरी में अद्वितीय बनाता है। ध्यान दें कि एल्गोरिथ्म कितना ग्रीडी है, और इसलिए टेबल में तब तक कुछ भी नहीं जोड़ा जाता है जब तक कि अद्वितीय निर्माण टोकन नहीं मिल जाता है। एल्गोरिथ्म लास्ट मैचिंग इंडेक्स = 0 और अगले उपलब्ध इंडेक्स = 1 को प्रारंभ करना है और फिर, इनपुट स्ट्रीम के प्रत्येक टोकन के लिए, डिक्शनरी मैच की सर्च करता है: {{code|{{mset|last matching index, token}}}}। यदि कोई मैच पाया जाता है, तो लास्ट मैचिंग इंडेक्स को मैचिंग एंट्री के इंडेक्स पर सेट किया जाता है, कुछ भी आउटपुट नहीं होता है, और लास्ट मैचिंग इंडेक्स अब तक के इनपुट का प्रतिनिधित्व करने के लिए छोड़ दिया जाता है। इनपुट तब तक प्रोसेस्ड किया जाता है जब तक कोई मैच न मिल जाए। फिर नई डिक्शनरी एंट्री बनाई जाती है, {{code|1=dictionary[next available index] = {last matching index, token} }}, और एल्गोरिथम लास्ट मैचिंग इंडेक्स को आउटपुट करता है, उसके पश्चात टोकन देता है, फिर लास्ट मैचिंग इंडेक्स = 0 को रीसेट करता है और अगले उपलब्ध इंडेक्स को बढ़ाता है। उदाहरण के रूप में टोकन के अनुक्रम{{samp|AABBA}}पर विचार करें जो डिक्शनरी को एकत्र करेगा;
{{pre|
{{pre|
0 {0,_}
0 {0,_}
Line 124: Line 121:
3 {0,B}
3 {0,B}
}}
}}
और संपीड़ित डेटा का आउटपुट अनुक्रम होगा {{samp|0A1B0B}}. ध्यान दें कि अंतिम A का अभी तक प्रतिनिधित्व नहीं किया गया है क्योंकि एल्गोरिथम यह नहीं जान सकता कि आगे क्या होगा। व्यवहार में एक EOF मार्कर को इनपुट में जोड़ा जाता है - {{samp|AABBA$}} उदाहरण के लिए। यह भी ध्यान दें कि इस मामले में आउटपुट {{samp|0A1B0B1$}} मूल इनपुट से अधिक लंबा है, लेकिन जैसे-जैसे शब्दकोश बढ़ता है, संपीड़न अनुपात में काफी सुधार होता है, और बाइनरी में इंडेक्स को न्यूनतम संख्या से अधिक बिट्स द्वारा प्रस्तुत करने की आवश्यकता नहीं होती है।<ref>https://math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf {{Bare URL PDF|date=March 2022}}</ref>
और कंप्रेस्ड डेटा का आउटपुट अनुक्रम{{samp|0A1B0B}}होगा। ध्यान दें कि अंतिम A का अभी तक प्रतिनिधित्व नहीं किया गया है क्योंकि एल्गोरिथम यह नहीं जान सकता कि आगे क्या होगा। प्रैक्टिस में EOF मार्कर को इनपुट में जोड़ा जाता है - उदाहरण के लिए {{samp|AABBA$}} है। यह भी ध्यान दें कि इस स्थिति में आउटपुट {{samp|0A1B0B1$}} मूल इनपुट से अधिक लंबा है, किन्तु जैसे-जैसे डिक्शनरी बढ़ता है, कम्प्रेशन अनुपात में अधिक सुधार होता है, और बाइनरी में इंडेक्स को न्यूनतम संख्या से अधिक बिट्स द्वारा प्रस्तुत करने की आवश्यकता नहीं होती है।<ref>https://math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf {{Bare URL PDF|date=March 2022}}</ref>
डीकंप्रेसन में संपीड़ित अनुक्रम से शब्दकोश का पुनर्निर्माण शामिल है। क्रम से {{samp|0A1B0B1$}} पहली प्रविष्टि हमेशा टर्मिनेटर होती है {{samp|0 {...} }}, और अनुक्रम से पहला होगा {{samp|1 {0,A} }}. वह {{samp|A}} आउटपुट में जोड़ा जाता है। इनपुट से दूसरी जोड़ी है {{samp|1B}} और शब्दकोश में प्रविष्टि संख्या 2 में परिणाम, {{samp|{{mset|1,B}}}}. टोकन बी आउटपुट है, जिसके पहले शब्दकोश प्रविष्टि 1 द्वारा दर्शाया गया अनुक्रम है। प्रविष्टि 1 एक 'ए' है (प्रविष्टि 0 के बाद - कुछ भी नहीं) इसलिए {{samp|AB}} आउटपुट में जोड़ा जाता है। अगला {{samp|0B}} को शब्दकोश में अगली प्रविष्टि के रूप में जोड़ा गया है, {{samp|3 {0,B} }}, और बी (पहले कुछ नहीं) को आउटपुट में जोड़ा जाता है। अंत में एक शब्दकोष प्रविष्टि {{samp|1$}} बनाया गया है और {{samp|A$}} परिणामी आउटपुट है {{samp|A AB B A$}} या {{samp|AABBA}}रिक्त स्थान और EOF मार्कर को हटाना।
 
डीकंप्रेसन में कंप्रेस्ड अनुक्रम से डिक्शनरी का पुनर्निर्माण सम्मिलित है। अनुक्रम {{samp|0A1B0B1$}} फर्स्ट एंट्री सदैव टर्मिनेटर {{samp|0 {...} }}होती है, और अनुक्रम से फर्स्ट एंट्री {{samp|1 {0,A} }}होगी।{{samp|A}} को आउटपुट में जोड़ा जाता है। इनपुट से दूसरी जोड़ी{{samp|1B}} और इसकी परिणाम डिक्शनरी, {{samp|{{mset|1,B}}}}एंट्री नंबर में होता है। टोकन "B" आउटपुट है, जिसके पूर्व डिक्शनरी एंट्री 1 द्वारा दर्शाया गया अनुक्रम है। एंट्री 1 'A' है (एंट्री 0 के पश्चात कुछ भी नहीं है।) इसलिए {{samp|AB}} आउटपुट में जोड़ा जाता है। अगला {{samp|0B}} को डिक्शनरी में नेक्स्ट एंट्री {{samp|3 {0,B} }}के रूप में जोड़ा गया है, और B (पूर्व कुछ नहीं) को आउटपुट में जोड़ा जाता है। अंत में {{samp|1$}}के लिए डिक्शनरी एंट्री बनाई जाती है और {{samp|A$}} आउटपुट होता है जिसके परिणामस्वरूप  {{samp|A AB B A$}} या {{samp|AABBA}}रिक्त स्पेस और EOF मार्कर को रिमूव कर देता है।


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


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


==यह भी देखें==
==यह भी देखें==
* लेम्पेल-ज़िव-स्टैक (एलजेडएस)
* लेम्पेल-ज़िव-स्टैक (LZS)


==संदर्भ==
==संदर्भ==
{{Reflist}}
{{Reflist}}
==बाहरी संबंध==
*{{commons category-inline|LZ77 algorithm}}
*{{commons category-inline|LZ78 algorithm}}
* {{cite web
| url=http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lz77.html
| title=The LZ77 algorithm
| date=1997
| work=Data Compression Reference Center: RASIP working group
| publisher=[[Faculty of Electrical Engineering and Computing, University of Zagreb]]
| access-date=22 June 2012
| archive-url=https://archive.today/20130107232302/http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lz77.html
| archive-date=7 January 2013
| url-status=dead
}}
* {{cite web
| url=http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lz78.html
| title=The LZ78 algorithm
| date=1997
| work=Data Compression Reference Center: RASIP working group
| publisher=Faculty of Electrical Engineering and Computing, University of Zagreb
| access-date=22 June 2012
| archive-url=https://archive.today/20130107200800/http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lz78.html
| archive-date=7 January 2013
| url-status=dead
}}
* {{cite web
| url=http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lzw.html
| title=The LZW algorithm
| date=1997
| work=Data Compression Reference Center: RASIP working group
| publisher=Faculty of Electrical Engineering and Computing, University of Zagreb
| access-date=22 June 2012
| archive-url=https://archive.today/20130107170646/http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lzw.html
| archive-date=7 January 2013
| url-status=dead
}}
{{Compression Methods}}


{{DEFAULTSORT:Lz77 And Lz78}}[[Category: दोषरहित संपीड़न एल्गोरिदम]] [[Category: इजरायली आविष्कार]] [[Category: स्यूडोकोड उदाहरण सहित लेख]]  
{{DEFAULTSORT:Lz77 And Lz78}}[[Category: दोषरहित संपीड़न एल्गोरिदम]] [[Category: इजरायली आविष्कार]] [[Category: स्यूडोकोड उदाहरण सहित लेख]]  
Line 186: Line 142:
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 07/12/2023]]
[[Category:Created On 07/12/2023]]
[[Category:Vigyan Ready]]

Latest revision as of 21:44, 18 December 2023

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

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

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

2004 में एल्गोरिथम को आईईईई माइलस्टोन नाम दिया गया था।[5] 2021 में जैकब ज़िव को उनके विकास में भागीदारी के लिए आईईईई मेडल ऑफ ऑनर से सम्मानित किया गया था।[6]

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

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

LZ77

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

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

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

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

[D, L, c] को डिकोड करने पर, फिर से, D = LR है। जब प्रथम LR करैक्टर को आउटपुट में पढ़ा जाता है, यह आउटपुट बफ़र से जुड़ी एकल रन यूनिट से ऍपेन्डेड है। इस बिंदु पर, रीड पॉइंटर को केवल उस एकल बफ़र्ड रन यूनिट के प्रारम्भ में int(L/LR) + (1 यदि L mod LR ≠ 0) लौटाने की आवश्यकता है, LR करैक्टर पढ़ें (या संभवतः अंतिम रिटर्न पर कम), और तब तक दोहराएँ जब तक कि कुल L करैक्टर न पढ़ लिए जाएँ। किन्तु एन्कोडिंग प्रक्रिया को प्रतिबिंबित करते हुए, चूंकि पैटर्न रेपेटेटिव है, रीड पॉइंटर को केवल रन लेंथ LR के समान निश्चित डिस्टेंस तक राइट पॉइंटर के साथ सिंक करने की आवश्यकता होती है, जब तक कि L करैक्टर को कुल मिलाकर आउटपुट में कॉपी नहीं किया जाता है।

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

स्यूडोकोड

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

while input is not empty do
    match := longest repeated occurrence of input that begins in window
 
    if match exists then
        d := distance to start of match
        l := length of match
        c := char following match in input
    else
        d:= 0
        l:= 0
        c:= first char of input
    end if
 
    output (d, l, c)
 
    discard l + 1 chars from front of window
    s := pop l + 1 chars from front of input
    append s to back of window
repeat

इम्प्लीमेंटेशन्स

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

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

LZ78

LZ78 एल्गोरिथम इनपुट से टोकन अनुक्रमों का डिक्शनरी बनाकर अनुक्रमिक डेटा को कंप्रेस्ड करता है, और फिर डिक्शनरी एंट्री के संदर्भ के साथ डेटा स्ट्रीम में अनुक्रम की दूसरी और पश्चात की घटना को प्रतिस्थापित करता है। अवलोकन यह है कि दोहराए गए अनुक्रमों की संख्या किसी अनुक्रम की नॉन-रैंडम प्रकृति का अच्छा माप है। एल्गोरिथम डिक्शनरी को n-एरी ट्री के रूप में प्रस्तुत करता है जहां n टोकन अनुक्रम बनाने के लिए उपयोग किए जाने वाले टोकन की संख्या है। प्रत्येक डिक्शनरी एंट्री डिक्शनरी फॉर्म की होती है 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 और इसकी परिणाम डिक्शनरी, {1,B}एंट्री नंबर में होता है। टोकन "B" आउटपुट है, जिसके पूर्व डिक्शनरी एंट्री 1 द्वारा दर्शाया गया अनुक्रम है। एंट्री 1 'A' है (एंट्री 0 के पश्चात कुछ भी नहीं है।) इसलिए AB आउटपुट में जोड़ा जाता है। अगला 0B को डिक्शनरी में नेक्स्ट एंट्री 3 {0,B} के रूप में जोड़ा गया है, और B (पूर्व कुछ नहीं) को आउटपुट में जोड़ा जाता है। अंत में 1$के लिए डिक्शनरी एंट्री बनाई जाती है और A$ आउटपुट होता है जिसके परिणामस्वरूप A AB B A$ या AABBAरिक्त स्पेस और EOF मार्कर को रिमूव कर देता है।

LZW

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

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

यह भी देखें

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

संदर्भ

  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. 2014-07-22. Retrieved 2014-11-09.
  6. ↑ Joanna, Goodrich. "आईईईई मेडल ऑफ ऑनर डेटा कंप्रेशन पायनियर जैकब ज़िव को जाता है". IEEE Spectrum: Technology, Engineering, and Science News (in English). Retrieved 2021-01-18.
  7. ↑ Peter Shor (2005-10-14). "Lempel-Ziv notes" (PDF). Archived from the original (PDF) on 28 May 2021. Retrieved 2014-11-09.
  8. ↑ "QFS Compression (RefPack)". Niotso Wiki. Retrieved 2014-11-09.
  9. ↑ Feldspar, Antaeus (23 August 1997). "An Explanation of the Deflate Algorithm". comp.compression newsgroup. zlib.net. Retrieved 2014-11-09.
  10. ↑ https://math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf[bare URL PDF]
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=LZ77_और_LZ78&oldid=279981’