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 को कभी-कभी स्लाइडिंग-विंडो कम्प्रेशन भी कहा जाता है। एनकोडर को मैचों को देखने के लिए इस डेटा को रखने की आवश्यकता होती है, और डिकोडर को एनकोडर द्वारा संदर्भित मैचों की व्याख्या करने के लिए इस डेटा को रखने की आवश्यकता होती है। स्लाइडिंग विंडो जितनी बड़ी होगी, एनकोडर संदर्भ बनाने के लिए उतनी ही देर तक सर्च कर सकता है।
यह न केवल स्वीकार्य है यद्यपि प्रायः उपयोगी भी होता है कि लंबाई-दूरी के पेअर को ऐसी लंबाई निर्दिष्ट करने की अनुमति दी जाए जो वास्तव में दूरी से अधिक हो। कॉपी कमांड के रूप में, यह हैरान करने वाला है: चार करैक्टर पीछे जाएं और उस स्थिति से दस करैक्टर वर्तमान स्थिति में कॉपी करें। दस करैक्टर की कॉपी कैसे बनाई जा सकती है जबकि उनमें से केवल चार ही वास्तव में बफ़र में हैं? एक समय में एक बाइट के निवारण पर, इस अनुरोध को पूर्ण करने में कोई समस्या नहीं होती है, क्योंकि जैसे ही बाइट कॉपी की जाती है, इसे कॉपी कमांड में इनपुट के रूप में फिर से फीड किया जा सकता है। जब कॉपी-फ़्रॉम पोजीशन इनिशियल डेस्टिनेशन पोजीशन पर पहुंचती है, तो इसके परिणामस्वरूप उसे वह डेटा फीड किया जाता है जो कॉपी-फ़्रॉम पोजीशन के प्रारम्भ में पेस्ट किया गया था। इस प्रकार यह ऑपरेशन उस कथन के समतुल्य है जो आपको दिया गया डेटा कॉपी करता है और इसे फिट होने तक बार-बार पेस्ट करता है। चूंकि इस प्रकार की जोड़ी डेटा की ही कॉपी को कई बार रिपीट करती है, इसलिए इसका उपयोग रन-लेंथ एन्कोडिंग के फ्लेक्सिबल और सरल रूप को सम्मिलित करने के लिए किया जा सकता है।
चीजों को देखने का दूसरा तरीका इस प्रकार है: एन्कोडिंग करते समय, खोज सूचक को खोज विंडो के अंत से पहले मिलान जोड़े को ढूंढना जारी रखने के लिए, ऑफसेट डी पर पहले मिलान से लेकर खोज विंडो के अंत तक सभी करैक्टर का मिलान होना चाहिए इनपुट, और ये (पहले देखे गए) करैक्टर हैं जिनमें लंबाई एल की ल रन इकाई सम्मिलित हैR, जो डी के समान होना चाहिए। फिर जैसे ही खोज सूचक खोज विंडो से आगे बढ़ता है और आगे बढ़ता है, जहां तक रन पैटर्न इनपुट में दोहराता है, खोज और इनपुट सूचक सिंक में होंगे और रन पैटर्न बाधित होने तक करैक्टर का मिलान करेंगे। फिर कुल मिलाकर L करैक्टर का मिलान किया गया है, L > D, और कोड है [D, L, c]।
[डी, एल, सी] को डिकोड करने पर, फिर से, डी = एलR. जब प्रथम एलR करैक्टर को आउटपुट में पढ़ा जाता है, यह आउटपुट बफ़र से जुड़ी ल रन इकाई से मेल खाता है। इस बिंदु पर, पढ़े गए पॉइंटर को केवल int(L/L) वापस करने की आवश्यकता के रूप में सोचा जा सकता हैR) + (1 यदि एल मोडएलR ≠ 0) उस ल बफ़र्ड रन यूनिट की शुरुआत से पहले, एल पढ़ेंR करैक्टर (या शायद अंतिम रिटर्न पर कम), और तब तक दोहराएँ जब तक कि कुल L करैक्टर न पढ़ लिए जाएँ। लेकिन एन्कोडिंग प्रक्रिया को प्रतिबिंबित करते हुए, चूंकि पैटर्न दोहराव वाला है, रीड पॉइंटर को केवल रन लेंथ एल के समान निश्चित दूरी तक राइट पॉइंटर के साथ सिंक करने की आवश्यकता होती है।R जब तक 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 से शुरू होता है (जब endianness|बिग-एंडियन बिट ओरिएंटेशन में पढ़ा जाता है), पूरी लंबाई-दूरी जोड़ी की लंबाई 1 से 4 बाइट्स हो सकती है।
- As of 2008[update], सबसे लोकप्रिय 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 के रूप में मानकीकृत किया गया था। जब त्रि-संरचित डिक्शनरी भर जाता है, तो यह सुनिश्चित करने के लिए सरल पुन: उपयोग/पुनर्प्राप्ति एल्गोरिथम का उपयोग किया जाता है कि डिक्शनरी बदलते डेटा के अनुसार अनुकूलन जारी रख सकता है। काउंटर शब्दकोष के माध्यम से घूमता है। जब नई प्रविष्टि की आवश्यकता होती है, तो काउंटर शब्दकोष के माध्यम से तब तक कदम उठाता है जब तक कि लीफ नोड नहीं मिल जाता (कोई आश्रित नोड नहीं)। इसे हटा दिया गया है और नई प्रविष्टि के लिए स्थान का पुन: उपयोग किया गया है। एलआरयू या एलएफयू की तुलना में इसे लागू करना आसान है और समकक्ष प्रदर्शन प्राप्त होता है।
यह भी देखें
- लेम्पेल-ज़िव-स्टैक (एलजेडएस)
संदर्भ
- ↑ 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]
