लेम्पेल-ज़िव-वेल्च
लेम्पेल-ज़िव-वेल्च (एलजेडडब्ल्यू) अब्राहम लेम्पेल, जैकब ज़िव और टेरी वेल्च द्वारा बनाया गया सार्वभौमिक लोसलेस डेटा कम्प्रेसन एल्गोरिथ्म है। इसे 1984 में वेल्च द्वारा लेम्पेल और ज़िव द्वारा 1978 में प्रकाशित एलजेड77 और एलजेड78 एल्गोरिदम के उत्तम कार्यान्वयन के रूप में प्रकाशित किया गया था। एल्गोरिदम को प्रयुक्त करना सरल है और इसमें हार्डवेयर कार्यान्वयन में बहुत उच्च थ्रूपुट की क्षमता है।[1] यह यूनिक्स फ़ाइल कम्प्रेशन यूटिलिटी कॉम्प्रेस का एल्गोरिदम है और इसका उपयोग जीआईएफ इमेज प्रारूप में किया जाता है।
एल्गोरिदम
वेल्च के 1984 के पेपर में वर्णित परिदृश्य [1] 8-बिट डेटा के अनुक्रमों को निश्चित-लंबाई वाले 12-बिट कोड के रूप में एन्कोड करता है। 0 से 255 तक के कोड संबंधित 8-बिट वर्ण से युक्त 1-वर्ण अनुक्रम का प्रतिनिधित्व करते हैं, और कोड 256 से 4095 तक डेटा में आने वाले अनुक्रमों के लिए शब्दकोश में बनाए जाते हैं क्योंकि यह एन्कोड किया गया है। कम्प्रेसन के प्रत्येक चरण में, इनपुट बाइट्स को अनुक्रम में एकत्र किया जाता है जब तक कि अगला वर्ण शब्दकोश में अभी तक बिना किसी कोड के अनुक्रम नहीं बनाता है। अनुक्रम के लिए कोड (उस वर्ण के बिना) आउटपुट में जोड़ा जाता है, और नया कोड (उस वर्ण के साथ अनुक्रम के लिए) शब्दकोश में जोड़ा जाता है।
इस विचार को शीघ्र ही अन्य स्थितियों के अनुरूप प्रयुक्त किया गया था। उदाहरण के लिए, कलर टेबल पर बेस्ड इमेज में, प्राकृतिक वर्ण वर्णमाला कलर टेबल अनुक्रमितों का सेट है, और 1980 के दशक में, विभिन्न इमेज में छोटी कलर टेबल (16 कलर के क्रम में) थीं। इस तरह की कम वर्णमाला के लिए, पूर्ण 12-बिट कोड पुअर कम्प्रेसन उत्पन्न करते हैं जब तक कि इमेज बड़ी न हो, इसलिए वैरिएबल-चौड़ाई कोड का विचार प्रस्तुत किया गया था: कोड सामान्यतः एन्कोड किए जा रहे सिम्बलों की तुलना में बिट अधिक चौड़े होते हैं, और प्रत्येक कोड का आकार उपयोग किया जाता है, तो कोड की चौड़ाई 1 बिट बढ़ जाती है, कुछ निर्धारित अधिकतम (सामान्यतः 12 बिट्स) तक जब अधिकतम कोड मान पहुंच जाता है, तो एन्कोडिंग वर्तमान टेबल का उपयोग करके आगे बढ़ती है, किन्तु टेबल में जोड़ने के लिए नए कोड उत्पन्न नहीं होते हैं।
आगे के परिशोधन में यह इंगित करने के लिए कोड आरक्षित करना सम्मिलित है कि कोड टेबल को साफ़ किया जाना चाहिए और उसकी प्रारंभिक स्थिति में पुनर्स्थापित किया जाना चाहिए (क्लियर कोड, सामान्यतः व्यक्तिगत वर्णमाला वर्णों के मानों के तुरंत पश्चात् पहला मान), और डेटा के अंत को इंगित करने के लिए कोड ( स्टॉप कोड, सामान्यतः क्लियर कोड से बड़ा) क्लियर कोड टेबल को भरने के पश्चात् पुन: प्रारंभ करने देता है, जो एन्कोडिंग को इनपुट डेटा में परिवर्तित पैटर्न के अनुकूल होने देता है। स्मार्ट एनकोडर कम्प्रेसन दक्षता की पर्यवेक्षण कर सकते हैं और जब भी वर्तमान टेबल इनपुट से मेल नहीं खाती है तो टेबल को साफ़ कर सकते हैं।
चूँकि कोड डेटा द्वारा निर्धारित विधि से जोड़े जाते हैं, डिकोडर टेबल के निर्माण की नकल करता है क्योंकि वह परिणामी कोड देखता है। यह महत्वपूर्ण है कि एनकोडर और डिकोडर उपयोग किए गए एलजेडडब्ल्यू की विविधता पर सहमत होंता है: वर्णमाला का आकार, अधिकतम टेबल आकार (और कोड चौड़ाई), क्या वैरिएबल-चौड़ाई एन्कोडिंग का उपयोग किया जाता है, प्रारंभिक कोड आकार, और क्या स्पष्ट का उपयोग करना है और स्टॉप कोड (और उनके क्या मूल्य हैं)। एलजेडडब्ल्यू को नियोजित करने वाले अधिकांश प्रारूप इस जानकारी को प्रारूप विनिर्देश में बनाते हैं या डेटा के लिए कम्प्रेसन हेडर में उनके लिए स्पष्ट फ़ील्ड प्रदान करते हैं।
एन्कोडिंग
एन्कोडिंग एल्गोरिदम का उच्च-स्तरीय दृश्य यहां दिखाया गया है:
- एक लंबाई की सभी पंक्तियों को सम्मिलित करने के लिए शब्दकोश को प्रारंभ करें।
- शब्दकोश में सबसे लंबी स्ट्रिंग W खोजे जो वर्तमान इनपुट से मेल खाती हो।
- आउटपुट के लिए W के लिए डिक्शनरी इंडेक्स को उत्सर्जित करें और इनपुट से W को हटा दें।
- शब्दकोश के इनपुट में W के पश्चात् अगला सिम्बल जोड़ें।
- चरण 2 पर जाएँ.
शब्दकोश को सभी संभावित इनपुट वर्णों के अनुरूप एकल-वर्ण स्ट्रिंग्स को सम्मिलित करने के लिए प्रारंभ किया गया है (और यदि उनका उपयोग किया जा रहा है तो स्पष्ट और स्टॉप कोड के अतिरिक्त और कुछ नहीं)। एल्गोरिथम इनपुट स्ट्रिंग के माध्यम से क्रमिक रूप से लंबे सबस्ट्रिंग को स्कैन करके कार्य करता है जब तक कि उसे कोई ऐसा सबस्ट्रिंग न मिल जाए जो शब्दकोश में नहीं है। जब ऐसी कोई स्ट्रिंग पाई जाती है, तो अंतिम वर्ण के बिना स्ट्रिंग के लिए सूचकांक (अर्थात, सबसे लंबी सबस्ट्रिंग जो शब्दकोश में है) को शब्दकोश से पुनर्प्राप्त किया जाता है और आउटपुट पर भेजा जाता है, और नई स्ट्रिंग (अंतिम वर्ण सहित) को अगले उपलब्ध कोड के साथ शब्दकोश में जोड़ा जाता है। अंतिम इनपुट वर्ण का उपयोग सबस्ट्रिंग को स्कैन करने के लिए अगले प्रारंभिक बिंदु के रूप में किया जाता है।
इस तरह, क्रमिक रूप से लंबे तार शब्दकोश में पंजीकृत होते हैं और एकल आउटपुट मान के रूप में पश्चात् के एन्कोडिंग के लिए उपलब्ध होते हैं। एल्गोरिदम दोहराए गए पैटर्न वाले डेटा पर सबसे अच्छा कार्य करता है, इसलिए संदेश के प्रारंभिक भागो में कम्प्रेसन दिखाई देता है। चूंकि, जैसे-जैसे संदेश बढ़ता है, डेटा कम्प्रेसन अनुपात असम्बद्ध रूप से अधिकतम हो जाता है (अर्थात, बढ़ते वक्र पर कम्प्रेसन कारक या अनुपात में सुधार होता है, और रैखिक रूप से नहीं, अनंत समय के अतिरिक्त सीमित समय अवधि के अन्दर सैद्धांतिक अधिकतम तक पहुंचता है)।[2]
डिकोडिंग
डिकोडिंग एल्गोरिदम का उच्च-स्तरीय दृश्य यहां दिखाया गया है:
- लंबाई की सभी पंक्तियों को सम्मिलित करने के लिए शब्दकोश को प्रारंभ करें।
- अगला एन्कोडेड सिम्बल पढ़ें: क्या यह शब्दकोश में एन्कोड किया गया है?
- हाँ:
- संबंधित स्ट्रिंग W को आउटपुट में उत्सर्जित करें।
- W के पहले सिम्बल के साथ आउटपुट में उत्सर्जित पिछली स्ट्रिंग को संयोजित करें। इसे शब्दकोश में जोड़ें।
- नहीं:
- आउटपुट में उत्सर्जित पिछली स्ट्रिंग को उसके पहले सिम्बल के साथ संयोजित करें। इस स्ट्रिंग को V कॉल करें.
- शब्दकोश में V जोड़ें और आउटपुट में V उत्सर्जित करें।
- हाँ:
- चरण 2 को इनपुट स्ट्रिंग के अंत तक दोहराएँ
डिकोडिंग एल्गोरिदम एन्कोडेड इनपुट से मान को पढ़कर और शब्दकोश से संबंधित स्ट्रिंग को आउटपुट करके कार्य करता है। चूंकि, पूर्ण शब्दकोश की आवश्यकता नहीं है, केवल प्रारंभिक शब्दकोश की आवश्यकता है जिसमें एकल-वर्ण स्ट्रिंग्स हैं (और वह सामान्यतः एन्कोडेड डेटा के साथ भेजे जाने के अतिरिक्त प्रोग्राम में हार्ड कोडिंग है)। इसके अतिरिक्त, पूर्ण शब्दकोश को डिकोडिंग प्रक्रिया के समय निम्नलिखित विधि से पुनः बनाया जाता है: मान को डिकोड करने और स्ट्रिंग को आउटपुट करने के पश्चात्, डिकोडर इसे अगली डिकोडेड स्ट्रिंग के पहले अक्षर (या वर्तमान स्ट्रिंग के पहले अक्षर) के साथ जोड़ता है। यदि अगले को डिकोड नहीं किया जा सकता है; चूँकि यदि अगला मान अज्ञात है, तो यह इस पुनरावृत्ति में शब्दकोश में जोड़ा गया मान होना चाहिए, और इसलिए इसका पहला अक्षर पहले अक्षर के समान है वर्तमान स्ट्रिंग), और नई स्ट्रिंग के साथ शब्दकोश को अपडेट करता है। डिकोडर पुनः अगले इनपुट पर आगे बढ़ता है (जो पहले से ही पिछले पुनरावृत्ति में पढ़ा गया था) और इसे पहले की तरह संसाधित करता है, और इसी तरह जब तक यह इनपुट स्ट्रीम समाप्त नहीं हो जाता है।
वैरिएबल-चौड़ाई कोड
यदि वैरिएबल-चौड़ाई कोड का उपयोग किया जा रहा है, तो एन्कोडर और डिकोडर को एन्कोडेड डेटा में समान बिंदुओं पर चौड़ाई परिवर्तन में सावधानी रखनी चाहिए जिससे वह स्ट्रीम में भिन्न-भिन्न कोड के मध्य की सीमाओं पर असहमत नही होंते है। मानक वर्जन में, एनकोडर चौड़ाई को p से p + 1 तक बढ़ाता है जब अनुक्रम ω + s का सामना होता है जो टेबल में नहीं है (जिससे इसके लिए कोड जोड़ा जाना चाहिए) किन्तु टेबल 2p में अगला उपलब्ध कोड है (पहला कोड जिसके लिए p + 1 बिट्स की आवश्यकता होती है)। एनकोडर चौड़ाई p पर ω के लिए कोड उत्सर्जित करता है (क्योंकि उस कोड के लिए p + 1 बिट्स की आवश्यकता नहीं होती है), और फिर कोड की चौड़ाई बढ़ाता है जिससे उत्सर्जित अगला कोड p + 1 बिट चौड़ा होता है।
टेबल बनाने में डिकोडर सदैव एनकोडर के पीछे कोड होता है, इसलिए जब यह ω के लिए कोड देखता है, तो यह कोड 2p − 1 के लिए प्रविष्टि उत्पन्न करता है. चूंकि यह वह बिंदु है जहां एनकोडर कोड की चौड़ाई बढ़ाता है, डिकोडर को यहां भी चौड़ाई बढ़ानी होगी - उस बिंदु पर जहां यह P बिट्स में फिट होने वाला सबसे बड़ा कोड उत्पन्न करता है।
अधिकांशतः, एन्कोडिंग एल्गोरिदम के कुछ प्रारंभिक कार्यान्वयन कोड की चौड़ाई बढ़ाते हैं और फिर पुरानी चौड़ाई के अतिरिक्त नई चौड़ाई पर ω उत्सर्जित करते हैं, जिससे डिकोडर को ऐसा लगता है कि चौड़ाई कोड को बहुत पहले परिवर्तित कर देती है। इसे शीघ्र परिवर्तन कहते हैं; इसने इतना भ्रम उत्पन्न कर दिया कि एडोब अब पीडीएफ फ़ाइलों में दोनों वर्जनों की अनुमति देता है, किन्तु प्रत्येक एलजेडडब्ल्यू-कॉम्प्रेस्सेड स्ट्रीम के हेडर में स्पष्ट फ्लैग सम्मिलित करता है जो यह दर्शाता है कि क्या प्रारंभिक परिवर्तन का उपयोग किया जा रहा है। एलजेडडब्ल्यू कम्प्रेसन का समर्थन करने वाले ग्राफ़िक्स फ़ाइल फोर्मेटों में से, टीआईएफएफ प्रारंभिक परिवर्तन का उपयोग करता है, जबकि जीआईएफ और अधिकांश अन्य नहीं करते हैं।
जब क्लियर कोड के उत्तर में टेबल साफ़ हो जाती है, तो एनकोडर और डिकोडर दोनों क्लियर कोड के पश्चात् कोड की चौड़ाई को प्रारंभिक कोड चौड़ाई में परिवर्तित कर देते हैं, जो क्लियर कोड के तुरंत पश्चात् वाले कोड से प्रारंभ होता है।
पैकिंग ऑर्डर
चूंकि उत्सर्जित कोड सामान्यतः बाइट सीमाओं पर नहीं आते हैं, इसलिए एनकोडर और डिकोडर को इस तथ्य पर सहमत होना चाहिए कि कोड को बाइट्स में कैसे पैक किया जाता है। दो सामान्य विधियाँ हैं एलएसबी-प्रथम (सबसे कम महत्वपूर्ण बिट प्रथम) और एमएसबी-प्रथम (सबसे महत्वपूर्ण बिट प्रथम)। एलएसबी-प्रथम पैकिंग में, पहले कोड को संरेखित किया जाता है जिससे कोड का सबसे कम महत्वपूर्ण बिट पहली स्ट्रीम बाइट के कम से कम महत्वपूर्ण बिट में गिर जाए, और यदि कोड में 8 बिट्स से अधिक है, तो बचे हुए उच्च-ऑर्डर बिट्स हैं अगले बाइट के सबसे कम महत्वपूर्ण बिट्स के साथ संरेखित आगे के कोड एलएसबी के साथ पैक किए जाते हैं, जो वर्तमान स्ट्रीम बाइट में अभी तक उपयोग नहीं किए गए कम से कम महत्वपूर्ण बिट में जाते हैं, आवश्यकतानुसार आगे बाइट्स में आगे बढ़ते हैं। एमएसबी-पहली पैकिंग पहले कोड को संरेखित करती है जिससे इसका सबसे महत्वपूर्ण बिट पहली स्ट्रीम बाइट के एमएसबी में आ जाए, ओवरफ्लो अगले बाइट के एमएसबी के साथ संरेखित होते है; आगे के कोड एमएसबी के साथ लिखे गए हैं जो कि वर्तमान स्ट्रीम बाइट में अभी तक उपयोग नहीं किए गए सबसे महत्वपूर्ण बिट में जाते हैं।
जीआईएफ फ़ाइल एलएसबी-प्रथम पैकिंग ऑर्डर का उपयोग करती हैं। टीआईएफएफ फ़ाइल और पीडीएफ फ़ाइल एमएसबी-प्रथम पैकिंग ऑर्डर का उपयोग करती हैं।
उदाहरण
निम्नलिखित उदाहरण एलजेडडब्ल्यू एल्गोरिथ्म को क्रियान्वित करता है, जो डेटा को एन्कोडिंग और डिकोड करने में प्रत्येक चरण में आउटपुट और कोडर की स्थिति दिखाता है। यह उदाहरण बहुत ही संक्षिप्त संदेश पर उचित कम्प्रेसन देने के लिए बनाया गया है। वास्तविक टेक्स्ट डेटा में, पुनरावृत्ति सामान्यतः कम स्पष्ट होती है, इसलिए कम्प्रेसन दक्षता बनाने से पहले लंबी इनपुट स्ट्रीम सामान्यतः आवश्यक होती हैं।
एन्कोड किया जाने वाला प्लेनटेक्स्ट (केवल बड़े अक्षरों का उपयोग करके वर्णमाला से) है:
TOBEORNOTTOBEORTOBEORNOT#प्लेनटेक्स्ट वर्णमाला में 26 सिम्बल हैं (बड़े अक्षर A से Z तक) का उपयोग स्टॉप कोड को दर्शाने के लिए किया जाता है: प्लेनटेक्स्ट वर्णमाला के बाहर कोड जो विशेष हैंडलिंग को ट्रिगर करता है। हम इच्छानुसार विधि से अक्षरों के लिए 1 से 26 तक मान निर्दिष्ट करते हैं, और स्टॉप कोड '#' के लिए 0 मान देते हैं। (एलजेडडब्ल्यू के अधिकांश फ्लेवर डेटा वर्णमाला के पश्चात् स्टॉप कोड डालेंगे, किन्तु मूल एल्गोरिदम में कुछ भी इसकी आवश्यकता नहीं है। एनकोडर और डिकोडर को केवल इस तथ्य पर सहमत होना होगा कि इसका क्या मूल्य है।)
कंप्यूटर इन्हें बिट्स की स्ट्रिंग के रूप में प्रस्तुत करता है। 27 मानों के इस सेट को सम्मिलित करने के लिए पर्याप्त संयोजन देने के लिए पांच-बिट कोड की आवश्यकता होती है। शब्दकोश को इन 27 मानों के साथ प्रारंभ किया गया है। जैसे-जैसे शब्दकोश बढ़ता है, अतिरिक्त प्रविष्टियों को समायोजित करने के लिए कोड की चौड़ाई भी बढ़नी चाहिए। 5-बिट कोड 25 = बिट्स के 32 संभावित संयोजन देता है, इसलिए जब 33वां शब्दकोश शब्द बनाया जाता है, तो एल्गोरिदम को उस बिंदु पर 5-बिट स्ट्रिंग्स से 6-बिट स्ट्रिंग्स पर स्विच करना होगा (सभी कोड मानों के लिए, जिसमें केवल पांच बिट्स पिछले आउटपुट सम्मिलित हैं)। ध्यान दें कि चूंकि पूर्ण-शून्य कोड 00000 का उपयोग किया गया है, और इसे 0 लेबल किया गया है, 33वीं शब्दकोश प्रविष्टि को '32' लेबल किया गया है। (पहले उत्पन्न आउटपुट कोड-चौड़ाई परिवर्तन से प्रभावित नहीं होता है, किन्तु बार शब्दकोश में 6-बिट मान उत्पन्न हो जाता है, तो यह संभवतः अगला कोड उत्सर्जित हो सकता है, इसलिए पश्चात् के आउटपुट की चौड़ाई उसे समायोजित करने के लिए 6 बिट्स में परिवर्तित कर जाती है। )
प्रारंभिक शब्दकोश में निम्नलिखित प्रविष्टियाँ सम्मिलित हैं:
| सिम्बल | बाइनरी | दशमलव |
|---|---|---|
| # | 00000 | 0 |
| A | 00001 | 1 |
| B | 00010 | 2 |
| C | 00011 | 3 |
| D | 00100 | 4 |
| E | 00101 | 5 |
| F | 00110 | 6 |
| G | 00111 | 7 |
| H | 01000 | 8 |
| I | 01001 | 9 |
| J | 01010 | 10 |
| K | 01011 | 11 |
| L | 01100 | 12 |
| M | 01101 | 13 |
| N | 01110 | 14 |
| O | 01111 | 15 |
| P | 10000 | 16 |
| Q | 10001 | 17 |
| R | 10010 | 18 |
| S | 10011 | 19 |
| T | 10100 | 20 |
| U | 10101 | 21 |
| V | 10110 | 22 |
| W | 10111 | 23 |
| X | 11000 | 24 |
| Y | 11001 | 25 |
| Z | 11010 | 26 |
एन्कोडिंग
अनुक्रम ω में बफ़र इनपुट वर्ण जब तक ω + अगला वर्ण शब्दकोश में नहीं है। ω के लिए कोड हटाएं, और शब्दकोश में ω + अगला वर्ण जोड़ें। अगले अक्षर के साथ फिर से बफरिंग प्रारंभ करें। (एन्कोड की जाने वाली स्ट्रिंग TOBEORNOTTOBERTOBEORNOT# है।)
| वर्तमान अनुक्रम | अगला चार | आउटपुट | विस्तारित शब्दकोश | कमेन्ट | ||
|---|---|---|---|---|---|---|
| कोड | बिट्स | |||||
| NULL | T | |||||
| T | O | 20 | 10100 | 27: | TO | 27 = 0 से 26 के पश्चात् पहला उपलब्ध कोड |
| O | B | 15 | 01111 | 28: | OB | |
| B | E | 2 | 00010 | 29: | BE | |
| E | O | 5 | 00101 | 30: | EO | |
| O | R | 15 | 01111 | 31: | OR | |
| R | N | 18 | 10010 | 32: | RN | 32 के लिए 6 बिट्स की आवश्यकता है, इसलिए अगले आउटपुट के लिए 6 बिट्स का उपयोग करें |
| N | O | 14 | 001110 | 33: | NO | |
| O | T | 15 | 001111 | 34: | OT | |
| T | T | 20 | 010100 | 35: | TT | |
| TO | B | 27 | 011011 | 36: | TOB | |
| BE | O | 29 | 011101 | 37: | BEO | |
| OR | T | 31 | 011111 | 38: | ORT | |
| TOB | E | 36 | 100100 | 39: | TOBE | |
| EO | R | 30 | 011110 | 40: | EOR | |
| RN | O | 32 | 100000 | 41: | RNO | |
| OT | # | 34 | 100010 | # एल्गोरिदम रोकता है; क्यूर सीक भेजें | ||
| 0 | 000000 | और स्टॉप कोड | ||||
- अनएन्कोडेड लंबाई = 25 सिम्बल × 5 बिट्स/सिम्बल = 125 बिट्स
- एन्कोडेड लंबाई = (6 कोड × 5 बिट्स/कोड) + (11 कोड × 6 बिट्स/कोड) = 96 बिट्स।
एलजेडडब्ल्यू के उपयोग से 125 में से 29 बिट्स की बचत हुई है, जिससे संदेश में 23% से अधिक की कमी आई है। यदि संदेश लंबा होता, तो शब्दकोश के शब्द टेक्स्ट के लंबे और लंबे खंडों का प्रतिनिधित्व करना प्रारंभ कर देते, दोहराए गए शब्दों को बहुत संक्षिप्त रूप से भेजते है।
डिकोडिंग
एलजेडडब्ल्यू-कॉम्प्रेस्सेड संग्रह को डीकोड करने के लिए, किसी को पहले से उपयोग किए गए प्रारंभिक शब्दकोश को जानना होगा, किन्तु अतिरिक्त प्रविष्टियों का पुनर्निर्माण किया जा सकता है क्योंकि वह सदैव पिछली प्रविष्टियों का संयोजन होते हैं।
| इनपुट | आउटपुट अनुक्रम | नई शब्दकोश प्रविष्टि | कमेन्ट | ||||
|---|---|---|---|---|---|---|---|
| बिट्स | कोड | फुल | अनुमान | ||||
| 10100 | 20 | T | 27: | T? | |||
| 01111 | 15 | O | 27: | TO | 28: | O? | |
| 00010 | 2 | B | 28: | OB | 29: | B? | |
| 00101 | 5 | E | 29: | BE | 30: | E? | |
| 01111 | 15 | O | 30: | EO | 31: | O? | |
| 10010 | 18 | R | 31: | OR | 32: | R? | कोड 31 बनाया गया (5 बिट्स में फ़िट होने वाला अंतिम) |
| 001110 | 14 | N | 32: | RN | 33: | N? | इसलिए 6 बिट पर इनपुट पढ़ना प्रारंभ करें |
| 001111 | 15 | O | 33: | NO | 34: | O? | |
| 010100 | 20 | T | 34: | OT | 35: | T? | |
| 011011 | 27 | TO | 35: | TT | 36: | TO? | |
| 011101 | 29 | BE | 36: | TOB | 37: | BE? | 36 = TO + 1st सिस्म्ब्ल (B) |
| 011111 | 31 | OR | 37: | BEO | 38: | OR? | अगला कोडित अनुक्रम प्राप्त (BE) |
| 100100 | 36 | TOB | 38: | ORT | 39: | TOB? | |
| 011110 | 30 | EO | 39: | TOBE | 40: | EO? | |
| 100000 | 32 | RN | 40: | EOR | 41: | RN? | |
| 100010 | 34 | OT | 41: | RNO | 42: | OT? | |
| 000000 | 0 | # | |||||
प्रत्येक चरण में, डिकोडर को कोड X प्राप्त होता है; यह टेबल में X को ऊपर देखता है और अनुक्रम को आउटपुट करता है χ यह कोड करता है, और यह अनुमान लगाता है प्रविष्टि के रूप में एनकोडर ने अभी जोड़ा - क्योंकि एनकोडर ने χ के लिए एक्स उत्सर्जित किया था, इसलिए क्योंकि χ +? टेबल में नहीं था, और एन्कोडर आगे बढ़ता है और इसे जोड़ता है। किन्तु विलुप्त पत्र क्या है? यह अगले कोड Z द्वारा कोडित अनुक्रम का पहला अक्षर है जो डिकोडर को प्राप्त होता है। तो डिकोडर Z को देखता है, इसे अनुक्रम ω में डिकोड करता है और पहला अक्षर z लेता है और इसे अगली शब्दकोश प्रविष्टि के रूप में χ के अंत में चिपका देता है।
यह तब तक कार्य करता है जब तक प्राप्त कोड डिकोडर के शब्दकोश में हैं, जिससे उन्हें अनुक्रमों में डिकोड किया जा सकता है। यदि डिकोडर को कोड Z प्राप्त होता है जो अभी तक उसके शब्दकोश में नहीं है तो क्या होगा? चूँकि डिकोडर सदैव एनकोडर के पीछे सिर्फ कोड होता है, Z एनकोडर के शब्दकोश में केवल तभी हो सकता है जब एनकोडर ने इसे उत्पन्न किया हो, जब χ के लिए पिछला कोड X उत्सर्जित किया जाता है। इस प्रकार Z कुछ ω को कोड करता है जो कि χ + ? है, और डिकोडर अज्ञात वर्ण को निम्नानुसार निर्धारित कर सकता है:
- डिकोडर X और फिर Z को देखता है, जहां X अनुक्रम χ को कोड करता है और Z कुछ अज्ञात अनुक्रम ω को कोड करता है।
- डिकोडर जानता है कि एनकोडर ने Z को χ + कुछ अज्ञात वर्ण c के लिए कोड के रूप में जोड़ा है, इसलिए ω = χ + c है।
- चूँकि इनपुट स्ट्रीम में χ के पश्चात् पहला अक्षर c है, और चूँकि ω, χ के तुरंत पश्चात् आने वाली स्ट्रिंग है, इसलिए c को अनुक्रम का पहला अक्षर होना चाहिए।
- चूँकि χ, ω का प्रारंभिक उपस्ट्रिंग है, c भी χ का पहला अक्षर होना चाहिए।
- तथापि Z कोड टेबल में नहीं है, डिकोडर अज्ञात अनुक्रम का अनुमान लगाने में सक्षम है और Z के मान के रूप में टेबल में χ + (χ का पहला अक्षर) जोड़ता है।
यह स्थिति तब होती है जब एनकोडर को cScSc फॉर्म के इनपुट का सामना करना पड़ता है, जहां c एकल वर्ण है, S स्ट्रिंग है और cS पहले से ही शब्दकोश में है, किन्तु cSc नहीं है। एनकोडर cS के लिए कोड उत्सर्जित करता है, शब्दकोश में cSc के लिए नया कोड डालता है। इसके पश्चात् यह इनपुट में cSc देखता है (cScSc के दूसरे सी से प्रारंभ होता है) और अभी डाला गया नया कोड उत्सर्जित करता है। उपरोक्त तर्क से पता चलता है कि जब भी डिकोडर को कोई कोड प्राप्त होता है जो उसके शब्दकोश में नहीं है, तो स्थिति इस तरह दिखनी चाहिए।
चूंकि फॉर्म cScSc का इनपुट असंभावित लग सकता है, यह पैटर्न अधिक सामान्य है जब इनपुट स्ट्रीम को महत्वपूर्ण पुनरावृत्ति की विशेषता होती है। विशेष रूप से, एकल वर्ण की लंबी स्ट्रिंग्स (जो इमेज के प्रकारों में सामान्य हैं एलजेडडब्ल्यू को अधिकांशतः एन्कोड करने के लिए उपयोग किया जाता है) निरंतर इस प्रकार के पैटर्न उत्पन्न करते हैं।
फरदर कोडिंग
ऊपर वर्णित सरल योजना एलजेडडब्ल्यू एल्गोरिथ्म पर ही केंद्रित है। विभिन्न एप्लिकेशन आउटपुट सिम्बलों के अनुक्रम में आगे एन्कोडिंग प्रयुक्त करते हैं। कुछ लोग बाइनरी-टू-टेक्स्ट एन्कोडिंग के कुछ रूप का उपयोग करके कोडित स्ट्रीम को प्रिंट करने योग्य वर्णों के रूप में पैकेज करते हैं; इससे एन्कोडेड लंबाई बढ़ जाती है और कम्प्रेसन दर कम हो जाती है। इसके विपरीत, बढ़ा हुआ कम्प्रेसन अधिकांशतः अनुकूली एन्ट्रापी एनकोडर के साथ प्राप्त किया जा सकता है। ऐसा कोडर अब तक देखे गए मानों की आवृत्तियों के आधार पर, अगले सिम्बल के मान के लिए संभाव्यता वितरण का अनुमान लगाता है। मानक एन्ट्रापी एन्कोडिंग जैसे हफ़मैन कोडिंग या अंकगणित कोडिंग तब उच्च संभावनाओं वाले मानों के लिए छोटे कोड का उपयोग करती है।
उपयोग
एलजेडडब्ल्यू कम्प्रेसन कंप्यूटर पर पहली व्यापक रूप से उपयोग की जाने वाली सार्वभौमिक डेटा कम्प्रेसन विधि बन गई थी। बड़ी इंग्लिश लैंग्वेज की टेक्स्ट फ़ाइल को सामान्यतः एलजेडडब्ल्यू के माध्यम से उसके मूल आकार के प्रायः अर्ध आकार में कॉम्प्रेस्सेड किया जा सकता है।
एलजेडडब्ल्यू का उपयोग सार्वजनिक-डोमेन प्रोग्राम कंप्रेस में किया गया था, जो 1986 के निकट यूनिक्स सिस्टम में कमोबेश मानक उपयोगिता बन गया था। यह तब से विभिन्न वितरणों से विलुप्त हो गया है, क्योंकि इसने एलजेडडब्ल्यू पेटेंट का उल्लंघन किया है और क्योंकि जीजीआईपी ने LZ77-बेस्ड डीफ़्लेट एल्गोरिथ्म का उपयोग करके उत्तम कम्प्रेसन अनुपात का उत्पादन किया है। किन्तु 2008 तक कम से कम फ्रीबीएसडी में वितरण के भाग के रूप में कंप्रेस और अनकॉम्प्रेस दोनों सम्मिलित हैं। विभिन्न अन्य लोकप्रिय कम्प्रेसन उपयोगिताओं ने भी एलजेडडब्ल्यू या निकट संबंधी विधियों का उपयोग किया था।
एलजेडडब्ल्यू का बहुत व्यापक रूप से उपयोग किया जाने लगा जब यह 1987 में जीआईएफ इमेज प्रारूप का भाग बन गया था। इसका उपयोग (वैकल्पिक रूप से) टीआईएफएफ और पीडीएफ फ़ाइलों में भी किया जा सकता है। (चूंकि एलजेडडब्ल्यू एडोब एक्रोबेट सॉफ़्टवेयर में उपलब्ध है, एक्रोबेट डिफ़ॉल्ट रूप से पीडीएफ फ़ाइलों में अधिकांश टेक्स्ट और कलर-टेबल-बेस्ड इमेज डेटा के लिए डीफ़्लेट का उपयोग करता है।)
पेटेंट
एलजेडडब्ल्यू और इसी तरह के एल्गोरिदम के लिए संयुक्त राज्य अमेरिका और अन्य देशों में विभिन्न पेटेंट जारी किए गए हैं। LZ78 लेम्पेल, ज़िव, कोहन और ईस्टमैन द्वारा कवर किया गया था U.S. Patent 4,464,650 , जिसे स्पेरी कॉर्पोरेशन, पश्चात् में यूनिसिस कॉर्पोरेशन को सौंपा गया था, 10 अगस्त 1981 को अंकित किया गया था। एलजेडडब्ल्यू एल्गोरिथ्म के लिए दो अमेरिकी पेटेंट जारी किए गए थे: U.S. Patent 4,814,746 विक्टर एस. मिलर और मार्क एन. वेगमैन द्वारा और आईबीएम को सौंपा गया था, मूल रूप से 1 जून, 1983 को अंकित किया गया था, और U.S. Patent 4,558,302 वेल्च द्वारा, स्पेरी कॉर्पोरेशन को सौंपा गया, पश्चात् में यूनिसिस कॉर्पोरेशन, 20 जून 1983 को अंकित किया गया था।
उपरोक्त पेटेंट के अतिरिक्त, वेल्च के 1983 पेटेंट में विभिन्न अन्य पेटेंट के उद्धरण भी सम्मिलित हैं जिन्होंने इसे प्रभावित किया, जिसमें दो 1980 जापानी पेटेंट (JP9343880A और JP17790880A) सम्मिलित हैं। /patents.google.com/patent/JPS57101937A/en JP17790880A]) एनईसी के जून कनात्सु से, U.S. Patent 4,021,782 (1974) जॉन एस. होर्निंग से, U.S. Patent 4,366,551 (1977) क्लॉस ई. होल्ट्ज़ से, और 1981 जर्मन पेटेंट (DE19813118676) कार्ल एकहार्ट हेंज से [3] 1993-94 में, और फिर 1999 में, यूनिसिस कॉर्पोरेशन को व्यापक निंदा मिली जब उसने जीआईएफ इमेज में एलजेडडब्ल्यू के लिए लाइसेंस शुल्क प्रयुक्त करने का प्रयास किया था। इस प्रकार 1993-1994 यूनिसिस-कॉम्प्युसर्व विवाद (कंप्यूसर्व जीआईएफ प्रारूप का निर्माता है) ने जीआईएफ-प्रतिस्थापन फ़ाइल प्रारूप पर यूज़नेट कॉम्प.ग्राफिक्स विचार को प्रेरित किया था, जिसने स्थान में ईमेल एक्सचेंज को बढ़ावा दिया जो अंततः पेटेंट के निर्माण में परिणत हुआ था, 1995 में भार रहित पोर्टेबल नेटवर्क ग्राफ़िक्स (पीएनजी) फ़ाइल फोर्मेट है।
एलजेडडब्ल्यू एल्गोरिथम पर यूनिसिस का अमेरिकी पेटेंट 20 जून 2003 को समाप्त हो गया था।[4] इसके अंकित होने के 20 वर्ष पश्चात्. यूनाइटेड किंगडम, फ्रांस, जर्मनी, इटली, जापान और कनाडा में अंकित किए गए सभी पेटेंट 2004 में समाप्त हो गए थे।[4] इसी तरह उनके अंकित होने के 20 एक वर्ष पश्चात् समाप्त हो गये थे।
वेरिएंट
- एलजेएमडब्ल्यू (1985, वी. मिलर, एम. वेगमैन द्वारा) [5] - शब्दकोश में पहले से उपस्थित सबसे लंबी स्ट्रिंग (वर्तमान मिलान) के लिए इनपुट खोजता है; शब्दकोश में पिछले मिलान का वर्तमान मिलान के साथ संयोजन जोड़ता है। (शब्दकोश प्रविष्टियाँ इस प्रकार अधिक तीव्रता से बढ़ती हैं; किन्तु इस योजना को प्रयुक्त करना अधिक सम्मिश्र है।) मिलर और वेगमैन भी शब्दकोश भर जाने पर शब्दकोश से कम-आवृत्ति प्रविष्टियों को हटाने का सुझाव देते हैं।
- एलज़ैप (1988, जेम्स स्टोरर द्वारा) [6] - एलजेएमडब्ल्यू का संशोधन: शब्दकोश में वर्तमान मिलान के साथ पिछले मिलान के संयोजन को जोड़ने के अतिरिक्त, वर्तमान मिलान के प्रत्येक प्रारंभिक सबस्ट्रिंग के साथ पिछले मिलान के संयोजन को जोड़ें (एपी सभी उपसर्गों के लिए है)। उदाहरण के लिए, यदि पिछला मिलान विकी है और वर्तमान मिलान पीडिया है, तो एलजेडएपी एनकोडर शब्दकोश में 5 नए अनुक्रम wikip, wikipe, wikiped, wikipedi, और wikipedia, जोड़ता है: जहां एलजेएमडब्ल्यू एनकोडर केवल अनुक्रम विकिपीडिया जोड़ता है। यह अधिक शब्दकोश प्रविष्टियाँ जोड़ने की मूल्य पर, एलजेएमडब्ल्यू की कुछ सम्मिश्रता को समाप्त करता है।
- एलजेडडब्ल्यूएल एलजेडडब्ल्यू का सिलेबल-बेस्ड वर्जन है।
यह भी देखें
- LZ77 और LZ78
- लेम्पेल-ज़िव-मार्कोव श्रृंखला एल्गोरिथ्म
- एलजेडएमए
- लेम्पेल-ज़िव-स्टॉरर-स्ज़िमंस्की
- एलजेडजेबी
- कॉन्टेक्स्ट ट्री वेइटिंग
- डिस्क्रेट कोसाइन ट्रांसफॉर्म (डीसीटी), जेपीईजी और एमपीईजी कोडिंग मानकों में उपयोग किया जाने वाला लोसी कम्प्रेसन एल्गोरिदम
संदर्भ
- ↑ 1.0 1.1 Welch, Terry (1984). "उच्च-प्रदर्शन डेटा संपीड़न के लिए एक तकनीक". Computer. 17 (6): 8–19. doi:10.1109/MC.1984.1659158. S2CID 2055321.
- ↑ Ziv, J.; Lempel, A. (1978). "चर-दर कोडिंग के माध्यम से व्यक्तिगत अनुक्रमों का संपीड़न" (PDF). IEEE Transactions on Information Theory. 24 (5): 530. CiteSeerX 10.1.1.14.2892. doi:10.1109/TIT.1978.1055934. Archived from the original (PDF) on 2012-04-12. Retrieved 2009-03-03.
- ↑ U.S. Patent 4,558,302
- ↑ 4.0 4.1 "LZW पेटेंट सूचना". About Unisys. Unisys. Archived from the original on June 26, 2009. Retrieved March 6, 2014.
- ↑ David Salomon, Data Compression – The complete reference, 4th ed., page 209.
- ↑ David Salomon, Data Compression – The complete reference, 4th ed., page 212.
बाहरी संबंध
- Rosettacode wiki, algorithm in various languages
- U.S. Patent 4,558,302, Terry A. Welch, High speed data compression and decompression apparatus and method
- Sharpएलजेडडब्ल्यू – C# open source implementation
- MIT OpenCourseWare: Lecture including एलजेडडब्ल्यू algorithm
- Mark Nelson, एलजेडडब्ल्यू Data Compression on Dr. Dobbs Journal (October 1, 1989)
- Shrink, Reduce, and Implode: The Legacy Zip Compression Methods explains एलजेडडब्ल्यू and how it was used in PKZIP
