LZ77 और LZ78
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[update], सबसे लोकप्रिय 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)
संदर्भ
- ↑ 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.
- ↑ 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.
- ↑ US Patent No. 5532693 Adaptive data compression system with systolic string matching logic
- ↑ "Lossless Data Compression: LZ78". cs.stanford.edu.
- ↑ "Milestones:Lempel-Ziv Data Compression Algorithm, 1977". IEEE Global History Network. Institute of Electrical and Electronics Engineers. 2014-07-22. Retrieved 2014-11-09.
- ↑ Joanna, Goodrich. "आईईईई मेडल ऑफ ऑनर डेटा कंप्रेशन पायनियर जैकब ज़िव को जाता है". IEEE Spectrum: Technology, Engineering, and Science News (in English). Retrieved 2021-01-18.
- ↑ Peter Shor (2005-10-14). "Lempel-Ziv notes" (PDF). Archived from the original (PDF) on 28 May 2021. Retrieved 2014-11-09.
- ↑ "QFS Compression (RefPack)". Niotso Wiki. Retrieved 2014-11-09.
- ↑ Feldspar, Antaeus (23 August 1997). "An Explanation of the Deflate Algorithm". comp.compression newsgroup. zlib.net. Retrieved 2014-11-09.
- ↑ https://math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf[bare URL PDF]
