लेम्पेल-ज़िव-वेल्च: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{short description|Universal lossless data compression algorithm}}
{{short description|Universal lossless data compression algorithm}}
लेम्पेल-ज़िव-वेल्च (LZW) [[अब्राहम लेम्पेल]], [[जैकब ज़िव]] और [[टेरी वेल्च]] द्वारा बनाया गया सार्वभौमिक [[दोषरहित डेटा संपीड़न]] [[कलन विधि]] है। इसे 1984 में वेल्च द्वारा लेम्पेल और ज़िव द्वारा 1978 में प्रकाशित एलजेड77 और एलजेड78 एल्गोरिदम के बेहतर कार्यान्वयन के रूप में प्रकाशित किया गया था। एल्गोरिदम को लागू करना सरल है और इसमें हार्डवेयर कार्यान्वयन में बहुत उच्च थ्रूपुट की क्षमता है।<ref name="WelchIEEE">{{Cite journal | last1 = Welch | first1 = Terry| author-link1 = Terry Welch| doi = 10.1109/MC.1984.1659158 | title = उच्च-प्रदर्शन डेटा संपीड़न के लिए एक तकनीक| journal = Computer | volume = 17 | issue = 6 | pages = 8–19 | year = 1984 | s2cid = 2055321| url = https://ieeexplore.ieee.org/document/1659158}}</ref> यह [[यूनिक्स]] फ़ाइल कम्प्रेशन यूटिलिटी [[ संकुचित करें |संकुचित करें]] का एल्गोरिदम है और इसका उपयोग [[ GIF |GIF]] छवि प्रारूप में किया जाता है।
'''लेम्पेल-ज़िव-वेल्च''' '''(एलजेडडब्ल्यू)''' [[अब्राहम लेम्पेल]], [[जैकब ज़िव]] और [[टेरी वेल्च]] द्वारा बनाया गया सार्वभौमिक [[दोषरहित डेटा संपीड़न|लोसलेस डेटा]] कम्प्रेसन [[कलन विधि|एल्गोरिथ्म]] है। इसे 1984 में वेल्च द्वारा लेम्पेल और ज़िव द्वारा 1978 में प्रकाशित एलजेड77 और एलजेड78 एल्गोरिदम के उत्तम कार्यान्वयन के रूप में प्रकाशित किया गया था। एल्गोरिदम को प्रयुक्त करना सरल है और इसमें हार्डवेयर कार्यान्वयन में बहुत उच्च थ्रूपुट की क्षमता है।<ref name="WelchIEEE">{{Cite journal | last1 = Welch | first1 = Terry| author-link1 = Terry Welch| doi = 10.1109/MC.1984.1659158 | title = उच्च-प्रदर्शन डेटा संपीड़न के लिए एक तकनीक| journal = Computer | volume = 17 | issue = 6 | pages = 8–19 | year = 1984 | s2cid = 2055321| url = https://ieeexplore.ieee.org/document/1659158}}</ref> यह [[यूनिक्स]] फ़ाइल कम्प्रेशन यूटिलिटी [[ संकुचित करें |कॉम्प्रेस]] का एल्गोरिदम है और इसका उपयोग [[ GIF |जीआईएफ]] छवि प्रारूप में किया जाता है।


==एल्गोरिदम==
==एल्गोरिदम==
वेल्च के 1984 के पेपर में वर्णित परिदृश्य<ref name="WelchIEEE"/>8-बिट डेटा के अनुक्रमों को निश्चित-लंबाई वाले 12-बिट कोड के रूप में एन्कोड करता है। 0 से 255 तक के कोड संबंधित 8-बिट वर्ण से युक्त 1-वर्ण अनुक्रम का प्रतिनिधित्व करते हैं, और कोड 256 से 4095 तक डेटा में आने वाले अनुक्रमों के लिए शब्दकोश में बनाए जाते हैं क्योंकि यह एन्कोड किया गया है। संपीड़न के प्रत्येक चरण में, इनपुट बाइट्स को अनुक्रम में इकट्ठा किया जाता है जब तक कि अगला वर्ण शब्दकोश में अभी तक बिना किसी कोड के अनुक्रम नहीं बना लेता। अनुक्रम के लिए कोड (उस वर्ण के बिना) आउटपुट में जोड़ा जाता है, और नया कोड (उस वर्ण के साथ अनुक्रम के लिए) शब्दकोश में जोड़ा जाता है।
वेल्च के 1984 के पेपर में वर्णित परिदृश्य <ref name="WelchIEEE"/> 8-बिट डेटा के अनुक्रमों को निश्चित-लंबाई वाले 12-बिट कोड के रूप में एन्कोड करता है। 0 से 255 तक के कोड संबंधित 8-बिट वर्ण से युक्त 1-वर्ण अनुक्रम का प्रतिनिधित्व करते हैं, और कोड 256 से 4095 तक डेटा में आने वाले अनुक्रमों के लिए शब्दकोश में बनाए जाते हैं क्योंकि यह एन्कोड किया गया है। कम्प्रेसन के प्रत्येक चरण में, इनपुट बाइट्स को अनुक्रम में एकत्र किया जाता है जब तक कि अगला वर्ण शब्दकोश में अभी तक बिना किसी कोड के अनुक्रम नहीं बनाता है। अनुक्रम के लिए कोड (उस वर्ण के बिना) आउटपुट में जोड़ा जाता है, और नया कोड (उस वर्ण के साथ अनुक्रम के लिए) शब्दकोश में जोड़ा जाता है।


इस विचार को शीघ्र ही अन्य स्थितियों के अनुरूप ढाल लिया गया। उदाहरण के लिए, रंग तालिका पर आधारित छवि में, प्राकृतिक वर्ण वर्णमाला रंग तालिका अनुक्रमितों का सेट है, और 1980 के दशक में, कई छवियों में छोटी रंग तालिकाएँ (16 रंगों के क्रम में) थीं। इस तरह की कम वर्णमाला के लिए, पूर्ण 12-बिट कोड खराब संपीड़न उत्पन्न करते हैं जब तक कि छवि बड़ी न हो, इसलिए चर-चौड़ाई कोड का विचार पेश किया गया था: कोड आम तौर पर एन्कोड किए जा रहे प्रतीकों की तुलना में बिट अधिक चौड़े होते हैं, और प्रत्येक कोड का आकार उपयोग किया जाता है, तो कोड की चौड़ाई 1 बिट बढ़ जाती है, कुछ निर्धारित अधिकतम (आमतौर पर 12 बिट्स) तक। जब अधिकतम कोड मान पहुंच जाता है, तो एन्कोडिंग मौजूदा तालिका का उपयोग करके आगे बढ़ती है, लेकिन तालिका में जोड़ने के लिए नए कोड उत्पन्न नहीं होते हैं।
इस विचार को शीघ्र ही अन्य स्थितियों के अनुरूप प्रयुक्त किया गया था। उदाहरण के लिए, कलर टेबल पर आधारित छवि में, प्राकृतिक वर्ण वर्णमाला कलर टेबल अनुक्रमितों का सेट है, और 1980 के दशक में, विभिन्न छवियों में छोटी कलर टेबल (16 कलर के क्रम में) थीं। इस तरह की कम वर्णमाला के लिए, पूर्ण 12-बिट कोड पुअर कम्प्रेसन उत्पन्न करते हैं जब तक कि छवि बड़ी न हो, इसलिए वैरिएबल-चौड़ाई कोड का विचार प्रस्तुत किया गया था: कोड सामान्यतः एन्कोड किए जा रहे प्रतीकों की तुलना में बिट अधिक चौड़े होते हैं, और प्रत्येक कोड का आकार उपयोग किया जाता है, तो कोड की चौड़ाई 1 बिट बढ़ जाती है, कुछ निर्धारित अधिकतम (सामान्यतः 12 बिट्स) तक जब अधिकतम कोड मान पहुंच जाता है, तो एन्कोडिंग वर्तमान टेबल का उपयोग करके आगे बढ़ती है, किन्तु टेबल में जोड़ने के लिए नए कोड उत्पन्न नहीं होते हैं।


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


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


===एन्कोडिंग===
===एन्कोडिंग===
एन्कोडिंग एल्गोरिदम का उच्च-स्तरीय दृश्य यहां दिखाया गया है:
एन्कोडिंग एल्गोरिदम का उच्च-स्तरीय दृश्य यहां दिखाया गया है:


# एक लंबाई की सभी पंक्तियों को शामिल करने के लिए शब्दकोश को प्रारंभ करें।
# एक लंबाई की सभी पंक्तियों को सम्मिलित करने के लिए शब्दकोश को प्रारंभ करें।
# शब्दकोश में सबसे लंबी स्ट्रिंग W ढूंढें जो वर्तमान इनपुट से मेल खाती हो।
# शब्दकोश में सबसे लंबी स्ट्रिंग W खोजे जो वर्तमान इनपुट से मेल खाती हो।
# आउटपुट के लिए W के लिए डिक्शनरी इंडेक्स को उत्सर्जित करें और इनपुट से W को हटा दें।
# आउटपुट के लिए W के लिए डिक्शनरी इंडेक्स को उत्सर्जित करें और इनपुट से W को हटा दें।
# शब्दकोश के इनपुट में W के बाद अगला प्रतीक जोड़ें।
# शब्दकोश के इनपुट में W के पश्चात् अगला प्रतीक जोड़ें।
# चरण 2 पर जाएँ.
# चरण 2 पर जाएँ.


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


इस तरह, क्रमिक रूप से लंबे तार शब्दकोश में पंजीकृत होते हैं और एकल आउटपुट मान के रूप में बाद के एन्कोडिंग के लिए उपलब्ध होते हैं। एल्गोरिदम दोहराए गए पैटर्न वाले डेटा पर सबसे अच्छा काम करता है, इसलिए संदेश के शुरुआती हिस्सों में थोड़ा संपीड़न दिखाई देता है। हालाँकि, जैसे-जैसे संदेश बढ़ता है, [[डेटा संपीड़न अनुपात]] असम्बद्ध रूप से अधिकतम हो जाता है (यानी, बढ़ते वक्र पर संपीड़न कारक या अनुपात में सुधार होता है, और रैखिक रूप से नहीं, अनंत समय के बजाय सीमित समय अवधि के भीतर सैद्धांतिक अधिकतम तक पहुंचता है)।<ref>{{Cite journal | last1 = Ziv | first1 = J. | last2 = Lempel | first2 = A. | doi = 10.1109/TIT.1978.1055934 | url = http://www.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1978_variable-rate.pdf | title = चर-दर कोडिंग के माध्यम से व्यक्तिगत अनुक्रमों का संपीड़न| journal = IEEE Transactions on Information Theory | volume = 24 | issue = 5 | pages = 530 | year = 1978 | citeseerx = 10.1.1.14.2892 | access-date = 2009-03-03 | archive-date = 2012-04-12 | archive-url = https://web.archive.org/web/20120412115357/http://www.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1978_variable-rate.pdf | url-status = dead }}</ref>
इस तरह, क्रमिक रूप से लंबे तार शब्दकोश में पंजीकृत होते हैं और एकल आउटपुट मान के रूप में पश्चात् के एन्कोडिंग के लिए उपलब्ध होते हैं। एल्गोरिदम दोहराए गए पैटर्न वाले डेटा पर सबसे अच्छा कार्य करता है, इसलिए संदेश के प्रारंभिक भागो में कम्प्रेसन दिखाई देता है। चूंकि, जैसे-जैसे संदेश बढ़ता है, [[डेटा संपीड़न अनुपात|डेटा कम्प्रेसन अनुपात]] असम्बद्ध रूप से अधिकतम हो जाता है (अर्थात, बढ़ते वक्र पर कम्प्रेसन कारक या अनुपात में सुधार होता है, और रैखिक रूप से नहीं, अनंत समय के अतिरिक्त सीमित समय अवधि के अन्दर सैद्धांतिक अधिकतम तक पहुंचता है)।<ref>{{Cite journal | last1 = Ziv | first1 = J. | last2 = Lempel | first2 = A. | doi = 10.1109/TIT.1978.1055934 | url = http://www.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1978_variable-rate.pdf | title = चर-दर कोडिंग के माध्यम से व्यक्तिगत अनुक्रमों का संपीड़न| journal = IEEE Transactions on Information Theory | volume = 24 | issue = 5 | pages = 530 | year = 1978 | citeseerx = 10.1.1.14.2892 | access-date = 2009-03-03 | archive-date = 2012-04-12 | archive-url = https://web.archive.org/web/20120412115357/http://www.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1978_variable-rate.pdf | url-status = dead }}</ref>




===डिकोडिंग===
===डिकोडिंग===
डिकोडिंग एल्गोरिदम का उच्च-स्तरीय दृश्य यहां दिखाया गया है:
डिकोडिंग एल्गोरिदम का उच्च-स्तरीय दृश्य यहां दिखाया गया है:
# लंबाई की सभी पंक्तियों को शामिल करने के लिए शब्दकोश को प्रारंभ करें।
# लंबाई की सभी पंक्तियों को सम्मिलित करने के लिए शब्दकोश को प्रारंभ करें।
# अगला एन्कोडेड प्रतीक पढ़ें: क्या यह शब्दकोश में एन्कोड किया गया है?
# अगला एन्कोडेड प्रतीक पढ़ें: क्या यह शब्दकोश में एन्कोड किया गया है?
##हाँ:
##हाँ:
Line 36: Line 36:
###शब्दकोश में V जोड़ें और आउटपुट में V उत्सर्जित करें।
###शब्दकोश में V जोड़ें और आउटपुट में V उत्सर्जित करें।
#चरण 2 को इनपुट स्ट्रिंग के अंत तक दोहराएँ
#चरण 2 को इनपुट स्ट्रिंग के अंत तक दोहराएँ
डिकोडिंग एल्गोरिदम एन्कोडेड इनपुट से मान को पढ़कर और शब्दकोश से संबंधित स्ट्रिंग को आउटपुट करके काम करता है। हालाँकि, पूर्ण शब्दकोश की आवश्यकता नहीं है, केवल प्रारंभिक शब्दकोश की आवश्यकता है जिसमें एकल-वर्ण स्ट्रिंग्स हैं (और वह आमतौर पर एन्कोडेड डेटा के साथ भेजे जाने के बजाय प्रोग्राम में [[ कठिन कोडिंग |कठिन कोडिंग]] है)। इसके बजाय, पूर्ण शब्दकोश को डिकोडिंग प्रक्रिया के दौरान निम्नलिखित तरीके से फिर से बनाया जाता है: मान को डिकोड करने और स्ट्रिंग को आउटपुट करने के बाद, डिकोडर इसे ''अगली'' डिकोडेड स्ट्रिंग के पहले अक्षर (या वर्तमान स्ट्रिंग के पहले अक्षर) के साथ जोड़ता है। यदि अगले को डिकोड नहीं किया जा सकता है; चूँकि यदि अगला मान अज्ञात है, तो यह ''इस'' पुनरावृत्ति में शब्दकोश में जोड़ा गया मान होना चाहिए, और इसलिए इसका पहला अक्षर पहले अक्षर के समान है वर्तमान स्ट्रिंग), और नई स्ट्रिंग के साथ शब्दकोश को अद्यतन करता है। डिकोडर फिर अगले इनपुट पर आगे बढ़ता है (जो पहले से ही पिछले पुनरावृत्ति में पढ़ा गया था) और इसे पहले की तरह संसाधित करता है, और इसी तरह जब तक यह इनपुट स्ट्रीम समाप्त नहीं हो जाता।
डिकोडिंग एल्गोरिदम एन्कोडेड इनपुट से मान को पढ़कर और शब्दकोश से संबंधित स्ट्रिंग को आउटपुट करके कार्य करता है। चूंकि, पूर्ण शब्दकोश की आवश्यकता नहीं है, केवल प्रारंभिक शब्दकोश की आवश्यकता है जिसमें एकल-वर्ण स्ट्रिंग्स हैं (और वह सामान्यतः एन्कोडेड डेटा के साथ भेजे जाने के अतिरिक्त प्रोग्राम में [[ कठिन कोडिंग |हार्ड कोडिंग]] है)। इसके अतिरिक्त, पूर्ण शब्दकोश को डिकोडिंग प्रक्रिया के समय निम्नलिखित विधि से पुनः बनाया जाता है: मान को डिकोड करने और स्ट्रिंग को आउटपुट करने के पश्चात्, डिकोडर इसे ''अगली'' डिकोडेड स्ट्रिंग के पहले अक्षर (या वर्तमान स्ट्रिंग के पहले अक्षर) के साथ जोड़ता है। यदि अगले को डिकोड नहीं किया जा सकता है; चूँकि यदि अगला मान अज्ञात है, तो यह ''इस'' पुनरावृत्ति में शब्दकोश में जोड़ा गया मान होना चाहिए, और इसलिए इसका पहला अक्षर पहले अक्षर के समान है वर्तमान स्ट्रिंग), और नई स्ट्रिंग के साथ शब्दकोश को अपडेट करता है। डिकोडर पुनः अगले इनपुट पर आगे बढ़ता है (जो पहले से ही पिछले पुनरावृत्ति में पढ़ा गया था) और इसे पहले की तरह संसाधित करता है, और इसी तरह जब तक यह इनपुट स्ट्रीम समाप्त नहीं हो जाता है।


===परिवर्तनीय-चौड़ाई कोड===
===वैरिएबल-चौड़ाई कोड===
यदि चर-चौड़ाई कोड का उपयोग किया जा रहा है, तो एन्कोडर और डिकोडर को एन्कोडेड डेटा में समान बिंदुओं पर चौड़ाई बदलने में सावधानी बरतनी चाहिए ताकि वे स्ट्रीम में अलग-अलग कोड के बीच की सीमाओं पर असहमत न हों। मानक संस्करण में, एनकोडर चौड़ाई को p से p + 1 तक बढ़ाता है जब अनुक्रम ω + s का सामना होता है जो तालिका में नहीं है (ताकि इसके लिए कोड जोड़ा जाना चाहिए) लेकिन तालिका में अगला उपलब्ध कोड है 2<sup>p</sup> (पहला कोड जिसके लिए p + 1 बिट्स की आवश्यकता होती है)। एनकोडर चौड़ाई p पर ω के लिए कोड उत्सर्जित करता है (क्योंकि उस कोड के लिए p + 1 बिट्स की आवश्यकता नहीं होती है), और फिर कोड की चौड़ाई बढ़ाता है ताकि उत्सर्जित अगला कोड p + 1 बिट चौड़ा हो।
यदि वैरिएबल-चौड़ाई कोड का उपयोग किया जा रहा है, तो एन्कोडर और डिकोडर को एन्कोडेड डेटा में समान बिंदुओं पर चौड़ाई परिवर्तन में सावधानी रखनी चाहिए जिससे वह स्ट्रीम में भिन्न-भिन्न कोड के मध्य की सीमाओं पर असहमत नही होंते है। मानक वर्जन में, एनकोडर चौड़ाई को p से p + 1 तक बढ़ाता है जब अनुक्रम ω + s का सामना होता है जो टेबल में नहीं है (जिससे इसके लिए कोड जोड़ा जाना चाहिए) किन्तु टेबल 2<sup>p</sup> में अगला उपलब्ध कोड है (पहला कोड जिसके लिए p + 1 बिट्स की आवश्यकता होती है)। एनकोडर चौड़ाई p पर ω के लिए कोड उत्सर्जित करता है (क्योंकि उस कोड के लिए p + 1 बिट्स की आवश्यकता नहीं होती है), और फिर कोड की चौड़ाई बढ़ाता है जिससे उत्सर्जित अगला कोड p + 1 बिट चौड़ा होता है।


तालिका बनाने में डिकोडर हमेशा एनकोडर के पीछे कोड होता है, इसलिए जब यह ω के लिए कोड देखता है, तो यह कोड 2 के लिए प्रविष्टि उत्पन्न करता है<sup>पी</sup> − 1. चूंकि यह वह बिंदु है जहां एनकोडर कोड की चौड़ाई बढ़ाता है, डिकोडर को यहां भी चौड़ाई बढ़ानी होगी - उस बिंदु पर जहां यह पी बिट्स में फिट होने वाला सबसे बड़ा कोड उत्पन्न करता है।
टेबल बनाने में डिकोडर सदैव एनकोडर के पीछे कोड होता है, इसलिए जब यह ω के लिए कोड देखता है, तो यह कोड 2<sup>p</sup> − 1 के लिए प्रविष्टि उत्पन्न करता है. चूंकि यह वह बिंदु है जहां एनकोडर कोड की चौड़ाई बढ़ाता है, डिकोडर को यहां भी चौड़ाई बढ़ानी होगी - उस बिंदु पर जहां यह P बिट्स में फिट होने वाला सबसे बड़ा कोड उत्पन्न करता है।


दुर्भाग्य से, एन्कोडिंग एल्गोरिदम के कुछ शुरुआती कार्यान्वयन कोड की चौड़ाई बढ़ाते हैं और फिर पुरानी चौड़ाई के बजाय नई चौड़ाई पर ω उत्सर्जित करते हैं, जिससे डिकोडर को ऐसा लगता है कि चौड़ाई कोड को बहुत पहले बदल देती है। इसे शीघ्र परिवर्तन कहते हैं; इसने इतना भ्रम पैदा कर दिया कि Adobe अब PDF फ़ाइलों में दोनों संस्करणों की अनुमति देता है, लेकिन प्रत्येक LZW-संपीड़ित स्ट्रीम के हेडर में स्पष्ट ध्वज शामिल करता है जो यह दर्शाता है कि क्या प्रारंभिक परिवर्तन का उपयोग किया जा रहा है। LZW संपीड़न का समर्थन करने वाले ग्राफ़िक्स फ़ाइल स्वरूपों में से, [[TIFF]] प्रारंभिक परिवर्तन का उपयोग करता है, जबकि GIF और अधिकांश अन्य नहीं करते हैं।
अधिकांशतः, एन्कोडिंग एल्गोरिदम के कुछ प्रारंभिक कार्यान्वयन कोड की चौड़ाई बढ़ाते हैं और फिर पुरानी चौड़ाई के अतिरिक्त नई चौड़ाई पर ω उत्सर्जित करते हैं, जिससे डिकोडर को ऐसा लगता है कि चौड़ाई कोड को बहुत पहले परिवर्तित कर देती है। इसे शीघ्र परिवर्तन कहते हैं; इसने इतना भ्रम उत्पन्न कर दिया कि एडोब अब पीडीएफ फ़ाइलों में दोनों वर्जनों की अनुमति देता है, किन्तु प्रत्येक एलजेडडब्ल्यू-कॉम्प्रेस्सेड स्ट्रीम के हेडर में स्पष्ट फ्लैग सम्मिलित करता है जो यह दर्शाता है कि क्या प्रारंभिक परिवर्तन का उपयोग किया जा रहा है। एलजेडडब्ल्यू कम्प्रेसन का समर्थन करने वाले ग्राफ़िक्स फ़ाइल स्वरूपों में से, [[TIFF|टीआईएफएफ]] प्रारंभिक परिवर्तन का उपयोग करता है, जबकि जीआईएफ और अधिकांश अन्य नहीं करते हैं।


जब स्पष्ट कोड के जवाब में तालिका साफ़ हो जाती है, तो एनकोडर और डिकोडर दोनों स्पष्ट कोड के बाद कोड की चौड़ाई को प्रारंभिक कोड चौड़ाई में बदल देते हैं, जो स्पष्ट कोड के तुरंत बाद वाले कोड से शुरू होता है।
जब क्लियर कोड के उत्तर में टेबल साफ़ हो जाती है, तो एनकोडर और डिकोडर दोनों क्लियर कोड के पश्चात् कोड की चौड़ाई को प्रारंभिक कोड चौड़ाई में परिवर्तित कर देते हैं, जो क्लियर कोड के तुरंत पश्चात् वाले कोड से प्रारंभ होता है।


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


GIF फ़ाइलें LSB-प्रथम पैकिंग ऑर्डर का उपयोग करती हैं। TIFF फ़ाइलें और PDF फ़ाइलें MSB-प्रथम पैकिंग ऑर्डर का उपयोग करती हैं।
जीआईएफ फ़ाइल एलएसबी-प्रथम पैकिंग ऑर्डर का उपयोग करती हैं। टीआईएफएफ फ़ाइल और पीडीएफ फ़ाइल एमएसबी-प्रथम पैकिंग ऑर्डर का उपयोग करती हैं।


==उदाहरण==
==उदाहरण==
निम्नलिखित उदाहरण LZW एल्गोरिथ्म को क्रियान्वित करता है, जो डेटा को एन्कोडिंग और डिकोड करने में हर चरण में आउटपुट और [[ शब्दकोश कोडर |शब्दकोश कोडर]] की स्थिति दिखाता है। यह उदाहरण बहुत ही संक्षिप्त संदेश पर उचित संपीड़न देने के लिए बनाया गया है। वास्तविक पाठ डेटा में, पुनरावृत्ति आमतौर पर कम स्पष्ट होती है, इसलिए संपीड़न दक्षता बनाने से पहले लंबी इनपुट स्ट्रीम आमतौर पर आवश्यक होती हैं।
निम्नलिखित उदाहरण एलजेडडब्ल्यू एल्गोरिथ्म को क्रियान्वित करता है, जो डेटा को एन्कोडिंग और डिकोड करने में प्रत्येक चरण में आउटपुट और [[ शब्दकोश कोडर |कोडर]] की स्थिति दिखाता है। यह उदाहरण बहुत ही संक्षिप्त संदेश पर उचित कम्प्रेसन देने के लिए बनाया गया है। वास्तविक टेक्स्ट डेटा में, पुनरावृत्ति सामान्यतः कम स्पष्ट होती है, इसलिए कम्प्रेसन दक्षता बनाने से पहले लंबी इनपुट स्ट्रीम सामान्यतः आवश्यक होती हैं।


एन्कोड किया जाने वाला सादा पाठ (केवल बड़े अक्षरों का उपयोग करके वर्णमाला से) है:
एन्कोड किया जाने वाला प्लेनटेक्स्ट (केवल बड़े अक्षरों का उपयोग करके वर्णमाला से) है:


<syntaxhighlight>
TOBEORNOTTOBEORTOBEORNOT#
</syntaxhighlight>
  टोबेऑर्नोटोबियोर्टोबॉर्ननॉट#
  टोबेऑर्नोटोबियोर्टोबॉर्ननॉट#


प्लेनटेक्स्ट वर्णमाला में 26 प्रतीक हैं (बड़े अक्षर A से Z तक)। # का उपयोग स्टॉप कोड को दर्शाने के लिए किया जाता है: प्लेनटेक्स्ट वर्णमाला के बाहर कोड जो विशेष हैंडलिंग को ट्रिगर करता है। हम मनमाने ढंग से अक्षरों के लिए 1 से 26 तक मान निर्दिष्ट करते हैं, और स्टॉप कोड '#' के लिए 0 मान देते हैं। (LZW के अधिकांश फ्लेवर डेटा वर्णमाला के बाद स्टॉप कोड डालेंगे, लेकिन मूल एल्गोरिदम में कुछ भी इसकी आवश्यकता नहीं है। एनकोडर और डिकोडर को केवल इस बात पर सहमत होना होगा कि इसका क्या मूल्य है।)
प्लेनटेक्स्ट वर्णमाला में 26 प्रतीक हैं (बड़े अक्षर A से Z तक)। # का उपयोग स्टॉप कोड को दर्शाने के लिए किया जाता है: प्लेनटेक्स्ट वर्णमाला के बाहर कोड जो विशेष हैंडलिंग को ट्रिगर करता है। हम मनमाने ढंग से अक्षरों के लिए 1 से 26 तक मान निर्दिष्ट करते हैं, और स्टॉप कोड '#' के लिए 0 मान देते हैं। (एलजेडडब्ल्यू के अधिकांश फ्लेवर डेटा वर्णमाला के पश्चात् स्टॉप कोड डालेंगे, किन्तु मूल एल्गोरिदम में कुछ भी इसकी आवश्यकता नहीं है। एनकोडर और डिकोडर को केवल इस तथ्य पर सहमत होना होगा कि इसका क्या मूल्य है।)


कंप्यूटर इन्हें [[ अंश |अंश]] ्स की स्ट्रिंग के रूप में प्रस्तुत करता है। 27 मानों के इस सेट को शामिल करने के लिए पर्याप्त संयोजन देने के लिए पांच-बिट कोड की आवश्यकता होती है। शब्दकोश को इन 27 मानों के साथ प्रारंभ किया गया है। जैसे-जैसे शब्दकोश बढ़ता है, अतिरिक्त प्रविष्टियों को समायोजित करने के लिए कोड की चौड़ाई भी बढ़नी चाहिए। 5-बिट कोड 2 देता है<sup>5</sup> = बिट्स के 32 संभावित संयोजन, इसलिए जब 33वां शब्दकोश शब्द बनाया जाता है, तो एल्गोरिदम को उस बिंदु पर 5-बिट स्ट्रिंग्स से 6-बिट स्ट्रिंग्स पर स्विच करना होगा (सभी कोड मानों के लिए, जिसमें केवल पिछले आउटपुट शामिल हैं) पांच बिट्स)। ध्यान दें कि चूंकि पूर्ण-शून्य कोड 00000 का उपयोग किया गया है, और इसे 0 लेबल किया गया है, 33वीं शब्दकोश प्रविष्टि को '32' लेबल किया गया है। (पहले उत्पन्न आउटपुट कोड-चौड़ाई परिवर्तन से प्रभावित नहीं होता है, लेकिन बार शब्दकोश में 6-बिट मान उत्पन्न हो जाता है, तो यह संभवतः अगला कोड उत्सर्जित हो सकता है, इसलिए बाद के आउटपुट की चौड़ाई उसे समायोजित करने के लिए 6 बिट्स में बदल जाती है। )
कंप्यूटर इन्हें [[ अंश |अंश]] ्स की स्ट्रिंग के रूप में प्रस्तुत करता है। 27 मानों के इस सेट को सम्मिलित करने के लिए पर्याप्त संयोजन देने के लिए पांच-बिट कोड की आवश्यकता होती है। शब्दकोश को इन 27 मानों के साथ प्रारंभ किया गया है। जैसे-जैसे शब्दकोश बढ़ता है, अतिरिक्त प्रविष्टियों को समायोजित करने के लिए कोड की चौड़ाई भी बढ़नी चाहिए। 5-बिट कोड 2 देता है<sup>5</sup> = बिट्स के 32 संभावित संयोजन, इसलिए जब 33वां शब्दकोश शब्द बनाया जाता है, तो एल्गोरिदम को उस बिंदु पर 5-बिट स्ट्रिंग्स से 6-बिट स्ट्रिंग्स पर स्विच करना होगा (सभी कोड मानों के लिए, जिसमें केवल पिछले आउटपुट सम्मिलित हैं) पांच बिट्स)। ध्यान दें कि चूंकि पूर्ण-शून्य कोड 00000 का उपयोग किया गया है, और इसे 0 लेबल किया गया है, 33वीं शब्दकोश प्रविष्टि को '32' लेबल किया गया है। (पहले उत्पन्न आउटपुट कोड-चौड़ाई परिवर्तन से प्रभावित नहीं होता है, किन्तु बार शब्दकोश में 6-बिट मान उत्पन्न हो जाता है, तो यह संभवतः अगला कोड उत्सर्जित हो सकता है, इसलिए पश्चात् के आउटपुट की चौड़ाई उसे समायोजित करने के लिए 6 बिट्स में परिवर्तित कर जाती है। )


प्रारंभिक शब्दकोश में निम्नलिखित प्रविष्टियाँ शामिल हैं:
प्रारंभिक शब्दकोश में निम्नलिखित प्रविष्टियाँ सम्मिलित हैं:


{| class="wikitable" style="text-align: right; margin-left: auto; margin-right: auto;"
{| class="wikitable" style="text-align: right; margin-left: auto; margin-right: auto;"
Line 127: Line 130:


===एन्कोडिंग===
===एन्कोडिंग===
अनुक्रम ω में बफ़र इनपुट वर्ण जब तक ω + अगला वर्ण शब्दकोश में नहीं है। ω के लिए कोड हटाएं, और शब्दकोश में ω + अगला वर्ण जोड़ें। अगले अक्षर के साथ फिर से बफरिंग शुरू करें। (एन्कोड की जाने वाली स्ट्रिंग TOBEORNOTTOBERTOBEORNOT# है।)
अनुक्रम ω में बफ़र इनपुट वर्ण जब तक ω + अगला वर्ण शब्दकोश में नहीं है। ω के लिए कोड हटाएं, और शब्दकोश में ω + अगला वर्ण जोड़ें। अगले अक्षर के साथ फिर से बफरिंग प्रारंभ करें। (एन्कोड की जाने वाली स्ट्रिंग TOBEORNOTTOBERTOBEORNOT# है।)


{| class="wikitable" style="text-align: right; margin-left: auto; margin-right: auto;"
{| class="wikitable" style="text-align: right; margin-left: auto; margin-right: auto;"
Line 252: Line 255:
:एन्कोडेड लंबाई = (6 कोड × 5 बिट्स/कोड) + (11 कोड × 6 बिट्स/कोड) = 96 बिट्स।
:एन्कोडेड लंबाई = (6 कोड × 5 बिट्स/कोड) + (11 कोड × 6 बिट्स/कोड) = 96 बिट्स।


LZW के उपयोग से 125 में से 29 बिट्स की बचत हुई है, जिससे संदेश में 23% से अधिक की कमी आई है। यदि संदेश लंबा होता, तो शब्दकोश के शब्द पाठ के लंबे और लंबे खंडों का प्रतिनिधित्व करना शुरू कर देते, दोहराए गए शब्दों को बहुत संक्षिप्त रूप से भेजते।
एलजेडडब्ल्यू के उपयोग से 125 में से 29 बिट्स की बचत हुई है, जिससे संदेश में 23% से अधिक की कमी आई है। यदि संदेश लंबा होता, तो शब्दकोश के शब्द टेक्स्ट के लंबे और लंबे खंडों का प्रतिनिधित्व करना प्रारंभ कर देते, दोहराए गए शब्दों को बहुत संक्षिप्त रूप से भेजते।


===डिकोडिंग===
===डिकोडिंग===
एलजेडडब्ल्यू-संपीड़ित संग्रह को डीकोड करने के लिए, किसी को पहले से इस्तेमाल किए गए प्रारंभिक शब्दकोश को जानना होगा, लेकिन अतिरिक्त प्रविष्टियों का पुनर्निर्माण किया जा सकता है क्योंकि वे हमेशा पिछली प्रविष्टियों का संयोजन होते हैं।
एलजेडडब्ल्यू-कॉम्प्रेस्सेड संग्रह को डीकोड करने के लिए, किसी को पहले से इस्तेमाल किए गए प्रारंभिक शब्दकोश को जानना होगा, किन्तु अतिरिक्त प्रविष्टियों का पुनर्निर्माण किया जा सकता है क्योंकि वे सदैव पिछली प्रविष्टियों का संयोजन होते हैं।


   {| class="wikitable" style="text-align: right; margin-left: auto; margin-right: auto;"
   {| class="wikitable" style="text-align: right; margin-left: auto; margin-right: auto;"
Line 392: Line 395:
|-
|-
|}
|}
प्रत्येक चरण में, डिकोडर को कोड X प्राप्त होता है; यह तालिका में X को ऊपर देखता है और अनुक्रम को आउटपुट करता है χ यह कोड करता है, और यह अनुमान लगाता है χ + ? प्रविष्टि के रूप में एनकोडर ने अभी जोड़ा - क्योंकि एनकोडर ने χ के लिए एक्स उत्सर्जित किया, ठीक इसलिए क्योंकि χ +? तालिका में नहीं था, और एन्कोडर आगे बढ़ता है और इसे जोड़ता है। लेकिन गायब पत्र क्या है? यह अगले कोड Z द्वारा कोडित अनुक्रम का पहला अक्षर है जो डिकोडर को प्राप्त होता है। तो डिकोडर Z को देखता है, इसे अनुक्रम ω में डिकोड करता है और पहला अक्षर z लेता है और इसे अगली शब्दकोश प्रविष्टि के रूप में χ के अंत में चिपका देता है।
प्रत्येक चरण में, डिकोडर को कोड X प्राप्त होता है; यह टेबल में X को ऊपर देखता है और अनुक्रम को आउटपुट करता है χ यह कोड करता है, और यह अनुमान लगाता है χ + ? प्रविष्टि के रूप में एनकोडर ने अभी जोड़ा - क्योंकि एनकोडर ने χ के लिए एक्स उत्सर्जित किया, ठीक इसलिए क्योंकि χ +? टेबल में नहीं था, और एन्कोडर आगे बढ़ता है और इसे जोड़ता है। किन्तु गायब पत्र क्या है? यह अगले कोड Z द्वारा कोडित अनुक्रम का पहला अक्षर है जो डिकोडर को प्राप्त होता है। तो डिकोडर Z को देखता है, इसे अनुक्रम ω में डिकोड करता है और पहला अक्षर z लेता है और इसे अगली शब्दकोश प्रविष्टि के रूप में χ के अंत में चिपका देता है।


यह तब तक काम करता है जब तक प्राप्त कोड डिकोडर के शब्दकोश में हैं, ताकि उन्हें अनुक्रमों में डिकोड किया जा सके। यदि डिकोडर को कोड Z प्राप्त होता है जो अभी तक उसके शब्दकोश में नहीं है तो क्या होगा? चूँकि डिकोडर हमेशा एनकोडर के पीछे सिर्फ कोड होता है, Z एनकोडर के शब्दकोश में केवल तभी हो सकता है जब एनकोडर ने इसे उत्पन्न किया हो, जब χ के लिए पिछला कोड X उत्सर्जित किया हो। इस प्रकार Z कुछ ω को कोड करता है जो कि χ + ? है, और डिकोडर अज्ञात वर्ण को निम्नानुसार निर्धारित कर सकता है:
यह तब तक कार्य करता है जब तक प्राप्त कोड डिकोडर के शब्दकोश में हैं, जिससे उन्हें अनुक्रमों में डिकोड किया जा सके। यदि डिकोडर को कोड Z प्राप्त होता है जो अभी तक उसके शब्दकोश में नहीं है तो क्या होगा? चूँकि डिकोडर सदैव एनकोडर के पीछे सिर्फ कोड होता है, Z एनकोडर के शब्दकोश में केवल तभी हो सकता है जब एनकोडर ने इसे उत्पन्न किया हो, जब χ के लिए पिछला कोड X उत्सर्जित किया हो। इस प्रकार Z कुछ ω को कोड करता है जो कि χ + ? है, और डिकोडर अज्ञात वर्ण को निम्नानुसार निर्धारित कर सकता है:


# डिकोडर X और फिर Z को देखता है, जहां X अनुक्रम χ को कोड करता है और Z कुछ अज्ञात अनुक्रम ω को कोड करता है।
# डिकोडर X और फिर Z को देखता है, जहां X अनुक्रम χ को कोड करता है और Z कुछ अज्ञात अनुक्रम ω को कोड करता है।
# डिकोडर जानता है कि एनकोडर ने Z को χ + कुछ अज्ञात वर्ण c के लिए कोड के रूप में जोड़ा है, इसलिए ω = χ + c।
# डिकोडर जानता है कि एनकोडर ने Z को χ + कुछ अज्ञात वर्ण c के लिए कोड के रूप में जोड़ा है, इसलिए ω = χ + c।
# चूँकि इनपुट स्ट्रीम में χ के बाद पहला अक्षर c है, और चूँकि ω, χ के तुरंत बाद आने वाली स्ट्रिंग है, इसलिए c को अनुक्रम का पहला अक्षर होना चाहिए।
# चूँकि इनपुट स्ट्रीम में χ के पश्चात् पहला अक्षर c है, और चूँकि ω, χ के तुरंत पश्चात् आने वाली स्ट्रिंग है, इसलिए c को अनुक्रम का पहला अक्षर होना चाहिए।
# चूँकि χ, ω का प्रारंभिक उपस्ट्रिंग है, c भी χ का पहला अक्षर होना चाहिए।
# चूँकि χ, ω का प्रारंभिक उपस्ट्रिंग है, c भी χ का पहला अक्षर होना चाहिए।
# तो भले ही Z कोड तालिका में नहीं है, डिकोडर अज्ञात अनुक्रम का अनुमान लगाने में सक्षम है और Z के मान के रूप में तालिका में χ + (χ का पहला अक्षर) जोड़ता है।
# तो भले ही Z कोड टेबल में नहीं है, डिकोडर अज्ञात अनुक्रम का अनुमान लगाने में सक्षम है और Z के मान के रूप में टेबल में χ + (χ का पहला अक्षर) जोड़ता है।


यह स्थिति तब होती है जब एनकोडर को cScSc फॉर्म के इनपुट का सामना करना पड़ता है, जहां c एकल वर्ण है, S स्ट्रिंग है और cS पहले से ही शब्दकोश में है, लेकिन cSc नहीं है। एनकोडर सीएस के लिए कोड उत्सर्जित करता है, शब्दकोश में सीएससी के लिए नया कोड डालता है। इसके बाद यह इनपुट में सीएससी देखता है (सीएससीएससी के दूसरे सी से शुरू होता है) और अभी डाला गया नया कोड उत्सर्जित करता है। उपरोक्त तर्क से पता चलता है कि जब भी डिकोडर को कोई कोड प्राप्त होता है जो उसके शब्दकोश में नहीं है, तो स्थिति इस तरह दिखनी चाहिए।
यह स्थिति तब होती है जब एनकोडर को cScSc फॉर्म के इनपुट का सामना करना पड़ता है, जहां c एकल वर्ण है, S स्ट्रिंग है और cS पहले से ही शब्दकोश में है, किन्तु cSc नहीं है। एनकोडर सीएस के लिए कोड उत्सर्जित करता है, शब्दकोश में सीएससी के लिए नया कोड डालता है। इसके पश्चात् यह इनपुट में सीएससी देखता है (सीएससीएससी के दूसरे सी से प्रारंभ होता है) और अभी डाला गया नया कोड उत्सर्जित करता है। उपरोक्त तर्क से पता चलता है कि जब भी डिकोडर को कोई कोड प्राप्त होता है जो उसके शब्दकोश में नहीं है, तो स्थिति इस तरह दिखनी चाहिए।


हालाँकि फॉर्म cScSc का इनपुट असंभावित लग सकता है, यह पैटर्न काफी सामान्य है जब इनपुट स्ट्रीम को महत्वपूर्ण पुनरावृत्ति की विशेषता होती है। विशेष रूप से, एकल वर्ण की लंबी स्ट्रिंग्स (जो छवियों के प्रकारों में आम हैं LZW को अक्सर एन्कोड करने के लिए उपयोग किया जाता है) बार-बार इस प्रकार के पैटर्न उत्पन्न करते हैं।
चूंकि फॉर्म cScSc का इनपुट असंभावित लग सकता है, यह पैटर्न काफी सामान्य है जब इनपुट स्ट्रीम को महत्वपूर्ण पुनरावृत्ति की विशेषता होती है। विशेष रूप से, एकल वर्ण की लंबी स्ट्रिंग्स (जो छवियों के प्रकारों में आम हैं एलजेडडब्ल्यू को अक्सर एन्कोड करने के लिए उपयोग किया जाता है) बार-बार इस प्रकार के पैटर्न उत्पन्न करते हैं।


==आगे की कोडिंग==
==आगे की कोडिंग==
ऊपर वर्णित सरल योजना LZW एल्गोरिथ्म पर ही केंद्रित है। कई एप्लिकेशन आउटपुट प्रतीकों के अनुक्रम में आगे एन्कोडिंग लागू करते हैं। कुछ लोग [[बाइनरी-टू-टेक्स्ट एन्कोडिंग]] के कुछ रूप का उपयोग करके कोडित स्ट्रीम को प्रिंट करने योग्य वर्णों के रूप में पैकेज करते हैं; इससे एन्कोडेड लंबाई बढ़ जाती है और संपीड़न दर कम हो जाती है। इसके विपरीत, बढ़ा हुआ संपीड़न अक्सर अनुकूली एन्ट्रापी एनकोडर के साथ प्राप्त किया जा सकता है। ऐसा कोडर अब तक देखे गए मानों की आवृत्तियों के आधार पर, अगले प्रतीक के मान के लिए संभाव्यता वितरण का अनुमान लगाता है। मानक एन्ट्रापी एन्कोडिंग जैसे [[हफ़मैन कोडिंग]] या अंकगणित कोडिंग तब उच्च संभावनाओं वाले मानों के लिए छोटे कोड का उपयोग करती है।
ऊपर वर्णित सरल योजना एलजेडडब्ल्यू एल्गोरिथ्म पर ही केंद्रित है। विभिन्न एप्लिकेशन आउटपुट प्रतीकों के अनुक्रम में आगे एन्कोडिंग प्रयुक्त करते हैं। कुछ लोग [[बाइनरी-टू-टेक्स्ट एन्कोडिंग]] के कुछ रूप का उपयोग करके कोडित स्ट्रीम को प्रिंट करने योग्य वर्णों के रूप में पैकेज करते हैं; इससे एन्कोडेड लंबाई बढ़ जाती है और कम्प्रेसन दर कम हो जाती है। इसके विपरीत, बढ़ा हुआ कम्प्रेसन अक्सर अनुकूली एन्ट्रापी एनकोडर के साथ प्राप्त किया जा सकता है। ऐसा कोडर अब तक देखे गए मानों की आवृत्तियों के आधार पर, अगले प्रतीक के मान के लिए संभाव्यता वितरण का अनुमान लगाता है। मानक एन्ट्रापी एन्कोडिंग जैसे [[हफ़मैन कोडिंग]] या अंकगणित कोडिंग तब उच्च संभावनाओं वाले मानों के लिए छोटे कोड का उपयोग करती है।


== उपयोग ==
== उपयोग ==
LZW संपीड़न कंप्यूटर पर पहली व्यापक रूप से उपयोग की जाने वाली सार्वभौमिक डेटा संपीड़न विधि बन गई। बड़ी [[अंग्रेजी भाषा]] की टेक्स्ट फ़ाइल को आमतौर पर LZW के माध्यम से उसके मूल आकार के लगभग आधे आकार में संपीड़ित किया जा सकता है।
एलजेडडब्ल्यू कम्प्रेसन कंप्यूटर पर पहली व्यापक रूप से उपयोग की जाने वाली सार्वभौमिक डेटा कम्प्रेसन विधि बन गई। बड़ी [[अंग्रेजी भाषा]] की टेक्स्ट फ़ाइल को सामान्यतः एलजेडडब्ल्यू के माध्यम से उसके मूल आकार के लगभग आधे आकार में कॉम्प्रेस्सेड किया जा सकता है।


LZW का उपयोग सार्वजनिक-डोमेन प्रोग्राम कंप्रेस में किया गया था, जो 1986 के आसपास यूनिक्स सिस्टम में कमोबेश मानक उपयोगिता बन गया। यह तब से कई वितरणों से गायब हो गया है, क्योंकि इसने LZW पेटेंट का उल्लंघन किया है और क्योंकि [[gzip]] ने LZ77 का उपयोग करके बेहतर संपीड़न अनुपात का उत्पादन किया है। -आधारित [[DEFLATE]] एल्गोरिथ्म, लेकिन 2008 तक कम से कम FreeBSD में वितरण के भाग के रूप में कंप्रेस और [[ uncompress |uncompress]] दोनों शामिल हैं। कई अन्य लोकप्रिय संपीड़न उपयोगिताओं ने भी LZW या निकट संबंधी विधियों का उपयोग किया।
एलजेडडब्ल्यू का उपयोग सार्वजनिक-डोमेन प्रोग्राम कंप्रेस में किया गया था, जो 1986 के आसपास यूनिक्स सिस्टम में कमोबेश मानक उपयोगिता बन गया। यह तब से विभिन्न वितरणों से गायब हो गया है, क्योंकि इसने एलजेडडब्ल्यू पेटेंट का उल्लंघन किया है और क्योंकि [[gzip]] ने LZ77 का उपयोग करके उत्तम कम्प्रेसन अनुपात का उत्पादन किया है। -आधारित [[DEFLATE]] एल्गोरिथ्म, किन्तु 2008 तक कम से कम FreeBSD में वितरण के भाग के रूप में कंप्रेस और [[ uncompress |uncompress]] दोनों सम्मिलित हैं। विभिन्न अन्य लोकप्रिय कम्प्रेसन उपयोगिताओं ने भी एलजेडडब्ल्यू या निकट संबंधी विधियों का उपयोग किया।


LZW का बहुत व्यापक रूप से उपयोग किया जाने लगा जब यह 1987 में GIF छवि प्रारूप का हिस्सा बन गया। इसका उपयोग (वैकल्पिक रूप से) TIFF और [[PDF]] फ़ाइलों में भी किया जा सकता है। (हालाँकि LZW [[Adobe Acrobat]] सॉफ़्टवेयर में उपलब्ध है, Acrobat डिफ़ॉल्ट रूप से PDF फ़ाइलों में अधिकांश टेक्स्ट और रंग-तालिका-आधारित छवि डेटा के लिए DEFLATE का उपयोग करता है।)
एलजेडडब्ल्यू का बहुत व्यापक रूप से उपयोग किया जाने लगा जब यह 1987 में जीआईएफ छवि प्रारूप का हिस्सा बन गया। इसका उपयोग (वैकल्पिक रूप से) टीआईएफएफ और [[PDF|पीडीएफ]] फ़ाइलों में भी किया जा सकता है। (चूंकि एलजेडडब्ल्यू [[Adobe Acrobat|एडोब Acrobat]] सॉफ़्टवेयर में उपलब्ध है, Acrobat डिफ़ॉल्ट रूप से पीडीएफ फ़ाइलों में अधिकांश टेक्स्ट और कलर-टेबल-आधारित छवि डेटा के लिए DEFLATE का उपयोग करता है।)


== पेटेंट ==
== पेटेंट ==
{{main|Graphics Interchange Format#Unisys and LZW patent enforcement}}
{{main|Graphics Interchange Format#Unisys and LZW patent enforcement}}
LZW और इसी तरह के एल्गोरिदम के लिए [[संयुक्त राज्य अमेरिका]] और अन्य देशों में विभिन्न [[पेटेंट]] जारी किए गए हैं। LZ78 द्वारा कवर किया गया था {{US patent|4464650}} लेम्पेल, ज़िव, कोहन और ईस्टमैन द्वारा, जिसे [[स्पेरी कॉर्पोरेशन]], बाद में [[यूनिसिस]] कॉर्पोरेशन को सौंपा गया, 10 अगस्त 1981 को दायर किया गया। LZW एल्गोरिथ्म के लिए दो अमेरिकी पेटेंट जारी किए गए थे: {{US patent|4814746}} विक्टर एस. मिलर और मार्क एन. वेगमैन द्वारा और [[आईबीएम]] को सौंपा गया, मूल रूप से 1 जून, 1983 को दायर किया गया था, और {{US patent|4558302}} वेल्च द्वारा, स्पेरी कॉर्पोरेशन को सौंपा गया, बाद में यूनिसिस कॉर्पोरेशन, 20 जून 1983 को दायर किया गया।
एलजेडडब्ल्यू और इसी तरह के एल्गोरिदम के लिए [[संयुक्त राज्य अमेरिका]] और अन्य देशों में विभिन्न [[पेटेंट]] जारी किए गए हैं। LZ78 द्वारा कवर किया गया था {{US patent|4464650}} लेम्पेल, ज़िव, कोहन और ईस्टमैन द्वारा, जिसे [[स्पेरी कॉर्पोरेशन]], पश्चात् में [[यूनिसिस]] कॉर्पोरेशन को सौंपा गया, 10 अगस्त 1981 को दायर किया गया। एलजेडडब्ल्यू एल्गोरिथ्म के लिए दो अमेरिकी पेटेंट जारी किए गए थे: {{US patent|4814746}} विक्टर एस. मिलर और मार्क एन. वेगमैन द्वारा और [[आईबीएम]] को सौंपा गया, मूल रूप से 1 जून, 1983 को दायर किया गया था, और {{US patent|4558302}} वेल्च द्वारा, स्पेरी कॉर्पोरेशन को सौंपा गया, पश्चात् में यूनिसिस कॉर्पोरेशन, 20 जून 1983 को दायर किया गया।


उपरोक्त पेटेंट के अलावा, वेल्च के 1983 पेटेंट में कई अन्य पेटेंट के उद्धरण भी शामिल हैं जिन्होंने इसे प्रभावित किया, जिसमें दो 1980 जापानी पेटेंट ([https://patents.google.com/patent/JPS5719857A/en JP9343880A] और [https:/) शामिल हैं। /patents.google.com/patent/JPS57101937A/en JP17790880A]) [[एनईसी]] के जून कनात्सु से, {{US patent|4021782}} (1974) जॉन एस. होर्निंग से, {{US patent|4366551}} (1977) क्लॉस ई. होल्ट्ज़ से, और 1981 जर्मन पेटेंट ([https://patents.google.com/patent/DE3118676C2/en DE19813118676]) कार्ल एकहार्ट हेंज से।<ref>{{US patent|4558302}}</ref>
उपरोक्त पेटेंट के अतिरिक्त, वेल्च के 1983 पेटेंट में विभिन्न अन्य पेटेंट के उद्धरण भी सम्मिलित हैं जिन्होंने इसे प्रभावित किया, जिसमें दो 1980 जापानी पेटेंट ([https://patents.google.com/patent/JPS5719857A/en JP9343880A] और [https:/) सम्मिलित हैं। /patents.google.com/patent/JPS57101937A/en JP17790880A]) [[एनईसी]] के जून कनात्सु से, {{US patent|4021782}} (1974) जॉन एस. होर्निंग से, {{US patent|4366551}} (1977) क्लॉस ई. होल्ट्ज़ से, और 1981 जर्मन पेटेंट ([https://patents.google.com/patent/DE3118676C2/en DE19813118676]) कार्ल एकहार्ट हेंज से।<ref>{{US patent|4558302}}</ref>
1993-94 में, और फिर 1999 में, यूनिसिस कॉर्पोरेशन को व्यापक निंदा मिली जब उसने जीआईएफ छवियों में एलजेडडब्ल्यू के लिए लाइसेंस शुल्क लागू करने का प्रयास किया। 1993-1994 यूनिसिस-[[कॉम्प्युसर्व]] विवाद (कंप्यूसर्व जीआईएफ प्रारूप का निर्माता है) ने जीआईएफ-प्रतिस्थापन फ़ाइल प्रारूप पर [[यूज़नेट]] कॉम्प.ग्राफिक्स चर्चा को प्रेरित किया, जिसने बदले में ईमेल एक्सचेंज को बढ़ावा दिया जो अंततः पेटेंट के निर्माण में परिणत हुआ। -1995 में भार रहित [[पोर्टेबल नेटवर्क ग्राफ़िक्स]] (पीएनजी) फ़ाइल स्वरूप।
1993-94 में, और फिर 1999 में, यूनिसिस कॉर्पोरेशन को व्यापक निंदा मिली जब उसने जीआईएफ छवियों में एलजेडडब्ल्यू के लिए लाइसेंस शुल्क प्रयुक्त करने का प्रयास किया। 1993-1994 यूनिसिस-[[कॉम्प्युसर्व]] विवाद (कंप्यूसर्व जीआईएफ प्रारूप का निर्माता है) ने जीआईएफ-प्रतिस्थापन फ़ाइल प्रारूप पर [[यूज़नेट]] कॉम्प.ग्राफिक्स चर्चा को प्रेरित किया, जिसने बदले में ईमेल एक्सचेंज को बढ़ावा दिया जो अंततः पेटेंट के निर्माण में परिणत हुआ। -1995 में भार रहित [[पोर्टेबल नेटवर्क ग्राफ़िक्स]] (पीएनजी) फ़ाइल स्वरूप।


LZW एल्गोरिथम पर यूनिसिस का अमेरिकी पेटेंट 20 जून 2003 को समाप्त हो गया।<ref name=LZWPatentInfo>{{cite web |title=LZW पेटेंट सूचना|url=http://www.unisys.com/about__unisys/lzw/ |work=About Unisys |publisher=Unisys |access-date=March 6, 2014 |archive-url=https://web.archive.org/web/20090626052026/http://www.unisys.com/about__unisys/lzw/ |archive-date=June 26, 2009}}</ref> इसके दाखिल होने के 20 साल बाद. यूनाइटेड किंगडम, फ्रांस, जर्मनी, इटली, जापान और कनाडा में दायर किए गए सभी पेटेंट 2004 में समाप्त हो गए।<ref name=LZWPatentInfo/>इसी तरह उनके दाखिल होने के 20 साल बाद।
एलजेडडब्ल्यू एल्गोरिथम पर यूनिसिस का अमेरिकी पेटेंट 20 जून 2003 को समाप्त हो गया।<ref name=LZWPatentInfo>{{cite web |title=LZW पेटेंट सूचना|url=http://www.unisys.com/about__unisys/lzw/ |work=About Unisys |publisher=Unisys |access-date=March 6, 2014 |archive-url=https://web.archive.org/web/20090626052026/http://www.unisys.com/about__unisys/lzw/ |archive-date=June 26, 2009}}</ref> इसके दाखिल होने के 20 साल पश्चात्. यूनाइटेड किंगडम, फ्रांस, जर्मनी, इटली, जापान और कनाडा में दायर किए गए सभी पेटेंट 2004 में समाप्त हो गए।<ref name=LZWPatentInfo/>इसी तरह उनके दाखिल होने के 20 साल पश्चात्।


==वेरिएंट==
==वेरिएंट==
* LZMW (1985, वी. मिलर, एम. वेगमैन द्वारा)<ref>David Salomon, ''Data Compression – The complete reference'', 4th ed., page 209.</ref> - शब्दकोश में पहले से मौजूद सबसे लंबी स्ट्रिंग (वर्तमान मिलान) के लिए इनपुट खोजता है; शब्दकोश में पिछले मिलान का वर्तमान मिलान के साथ संयोजन जोड़ता है। (शब्दकोश प्रविष्टियाँ इस प्रकार अधिक तेजी से बढ़ती हैं; लेकिन इस योजना को लागू करना अधिक जटिल है।) मिलर और वेगमैन भी शब्दकोश भर जाने पर शब्दकोश से कम-आवृत्ति प्रविष्टियों को हटाने का सुझाव देते हैं।
* LZMW (1985, वी. मिलर, एम. वेगमैन द्वारा)<ref>David Salomon, ''Data Compression – The complete reference'', 4th ed., page 209.</ref> - शब्दकोश में पहले से मौजूद सबसे लंबी स्ट्रिंग (वर्तमान मिलान) के लिए इनपुट खोजता है; शब्दकोश में पिछले मिलान का वर्तमान मिलान के साथ संयोजन जोड़ता है। (शब्दकोश प्रविष्टियाँ इस प्रकार अधिक तेजी से बढ़ती हैं; किन्तु इस योजना को प्रयुक्त करना अधिक जटिल है।) मिलर और वेगमैन भी शब्दकोश भर जाने पर शब्दकोश से कम-आवृत्ति प्रविष्टियों को हटाने का सुझाव देते हैं।
* एलज़ैप (1988, जेम्स स्टोरर द्वारा)<ref>David Salomon, ''Data Compression – The complete reference'', 4th ed., page 212.</ref> - LZMW का संशोधन: शब्दकोश में वर्तमान मिलान के साथ पिछले मिलान के संयोजन को जोड़ने के बजाय, वर्तमान मिलान के प्रत्येक प्रारंभिक सबस्ट्रिंग के साथ पिछले मिलान के संयोजन को जोड़ें (एपी सभी उपसर्गों के लिए है)। उदाहरण के लिए, यदि पिछला मिलान विकी है और वर्तमान मिलान पीडिया है, तो LZAP एनकोडर शब्दकोश में 5 नए अनुक्रम जोड़ता है: wikip, wikipe, wikiped, wikipedi, और wikipedia, जहां LZMW एनकोडर केवल अनुक्रम विकिपीडिया जोड़ता है। यह अधिक शब्दकोश प्रविष्टियाँ जोड़ने की कीमत पर, LZMW की कुछ जटिलता को समाप्त करता है।
* एलज़ैप (1988, जेम्स स्टोरर द्वारा)<ref>David Salomon, ''Data Compression – The complete reference'', 4th ed., page 212.</ref> - LZMW का संशोधन: शब्दकोश में वर्तमान मिलान के साथ पिछले मिलान के संयोजन को जोड़ने के अतिरिक्त, वर्तमान मिलान के प्रत्येक प्रारंभिक सबस्ट्रिंग के साथ पिछले मिलान के संयोजन को जोड़ें (एपी सभी उपसर्गों के लिए है)। उदाहरण के लिए, यदि पिछला मिलान विकी है और वर्तमान मिलान पीडिया है, तो LZAP एनकोडर शब्दकोश में 5 नए अनुक्रम जोड़ता है: wikip, wikipe, wikiped, wikipedi, और wikipedia, जहां LZMW एनकोडर केवल अनुक्रम विकिपीडिया जोड़ता है। यह अधिक शब्दकोश प्रविष्टियाँ जोड़ने की कीमत पर, LZMW की कुछ जटिलता को समाप्त करता है।
* [[LZWL]] LZW का शब्दांश-आधारित संस्करण है।
* [[LZWL|एलजेडडब्ल्यूL]] एलजेडडब्ल्यू का शब्दांश-आधारित वर्जन है।


== यह भी देखें ==
== यह भी देखें ==
Line 437: Line 440:
* [[एलजेडजेबी]]
* [[एलजेडजेबी]]
* [[प्रसंग वृक्ष भार]]
* [[प्रसंग वृक्ष भार]]
* [[असतत कोसाइन परिवर्तन]] (डीसीटी), [[जेपीईजी]] और [[एमपीईजी]] कोडिंग मानकों में उपयोग किया जाने वाला [[हानिपूर्ण संपीड़न]] एल्गोरिदम
* [[असतत कोसाइन परिवर्तन]] (डीसीटी), [[जेपीईजी]] और [[एमपीईजी]] कोडिंग मानकों में उपयोग किया जाने वाला [[हानिपूर्ण संपीड़न|हानिपूर्ण]] कम्प्रेसन एल्गोरिदम


==संदर्भ==
==संदर्भ==
Line 446: Line 449:
* [https://rosettacode.org/wiki/LZW_compression Rosettacode wiki, algorithm in various languages]
* [https://rosettacode.org/wiki/LZW_compression Rosettacode wiki, algorithm in various languages]
* {{US patent|4558302}}, Terry A. Welch, ''High speed data compression and decompression apparatus and method''
* {{US patent|4558302}}, Terry A. Welch, ''High speed data compression and decompression apparatus and method''
* [https://sourceforge.net/projects/sharplzw/ SharpLZW – C# open source implementation]
* [https://sourceforge.net/projects/sharplzw/ Sharpएलजेडडब्ल्यू – C# open source implementation]
* MIT OpenCourseWare: [http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-050j-information-and-entropy-spring-2008/videos-homework-and-readings/unit-2-lecture-1/ Lecture including LZW algorithm]
* MIT OpenCourseWare: [http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-050j-information-and-entropy-spring-2008/videos-homework-and-readings/unit-2-lecture-1/ Lecture including एलजेडडब्ल्यू algorithm]
* [https://marknelson.us/posts/1989/10/01/lzw-data-compression.html/ Mark Nelson, ''LZW Data Compression'' on Dr. Dobbs Journal (October 1, 1989)]
* [https://marknelson.us/posts/1989/10/01/lzw-data-compression.html/ Mark Nelson, ''एलजेडडब्ल्यू Data Compression'' on Dr. Dobbs Journal (October 1, 1989)]
* [https://www.hanshq.net/zip2.html Shrink, Reduce, and Implode: The Legacy Zip Compression Methods] explains LZW and how it was used in [[PKZIP]]
* [https://www.hanshq.net/zip2.html Shrink, Reduce, and Implode: The Legacy Zip Compression Methods] explains एलजेडडब्ल्यू and how it was used in [[PKZIP]]


{{DEFAULTSORT:Lempel-Ziv-Welch}}[[Category: दोषरहित संपीड़न एल्गोरिदम]] [[Category: 1984 में कंप्यूटर से संबंधित परिचय]] [[Category: खोज और आविष्कार विवाद]]  
{{DEFAULTSORT:Lempel-Ziv-Welch}}[[Category: दोषरहित संपीड़न एल्गोरिदम]] [[Category: 1984 में कंप्यूटर से संबंधित परिचय]] [[Category: खोज और आविष्कार विवाद]]  

Revision as of 21:47, 12 December 2023

लेम्पेल-ज़िव-वेल्च (एलजेडडब्ल्यू) अब्राहम लेम्पेल, जैकब ज़िव और टेरी वेल्च द्वारा बनाया गया सार्वभौमिक लोसलेस डेटा कम्प्रेसन एल्गोरिथ्म है। इसे 1984 में वेल्च द्वारा लेम्पेल और ज़िव द्वारा 1978 में प्रकाशित एलजेड77 और एलजेड78 एल्गोरिदम के उत्तम कार्यान्वयन के रूप में प्रकाशित किया गया था। एल्गोरिदम को प्रयुक्त करना सरल है और इसमें हार्डवेयर कार्यान्वयन में बहुत उच्च थ्रूपुट की क्षमता है।[1] यह यूनिक्स फ़ाइल कम्प्रेशन यूटिलिटी कॉम्प्रेस का एल्गोरिदम है और इसका उपयोग जीआईएफ छवि प्रारूप में किया जाता है।

एल्गोरिदम

वेल्च के 1984 के पेपर में वर्णित परिदृश्य [1] 8-बिट डेटा के अनुक्रमों को निश्चित-लंबाई वाले 12-बिट कोड के रूप में एन्कोड करता है। 0 से 255 तक के कोड संबंधित 8-बिट वर्ण से युक्त 1-वर्ण अनुक्रम का प्रतिनिधित्व करते हैं, और कोड 256 से 4095 तक डेटा में आने वाले अनुक्रमों के लिए शब्दकोश में बनाए जाते हैं क्योंकि यह एन्कोड किया गया है। कम्प्रेसन के प्रत्येक चरण में, इनपुट बाइट्स को अनुक्रम में एकत्र किया जाता है जब तक कि अगला वर्ण शब्दकोश में अभी तक बिना किसी कोड के अनुक्रम नहीं बनाता है। अनुक्रम के लिए कोड (उस वर्ण के बिना) आउटपुट में जोड़ा जाता है, और नया कोड (उस वर्ण के साथ अनुक्रम के लिए) शब्दकोश में जोड़ा जाता है।

इस विचार को शीघ्र ही अन्य स्थितियों के अनुरूप प्रयुक्त किया गया था। उदाहरण के लिए, कलर टेबल पर आधारित छवि में, प्राकृतिक वर्ण वर्णमाला कलर टेबल अनुक्रमितों का सेट है, और 1980 के दशक में, विभिन्न छवियों में छोटी कलर टेबल (16 कलर के क्रम में) थीं। इस तरह की कम वर्णमाला के लिए, पूर्ण 12-बिट कोड पुअर कम्प्रेसन उत्पन्न करते हैं जब तक कि छवि बड़ी न हो, इसलिए वैरिएबल-चौड़ाई कोड का विचार प्रस्तुत किया गया था: कोड सामान्यतः एन्कोड किए जा रहे प्रतीकों की तुलना में बिट अधिक चौड़े होते हैं, और प्रत्येक कोड का आकार उपयोग किया जाता है, तो कोड की चौड़ाई 1 बिट बढ़ जाती है, कुछ निर्धारित अधिकतम (सामान्यतः 12 बिट्स) तक जब अधिकतम कोड मान पहुंच जाता है, तो एन्कोडिंग वर्तमान टेबल का उपयोग करके आगे बढ़ती है, किन्तु टेबल में जोड़ने के लिए नए कोड उत्पन्न नहीं होते हैं।

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

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

एन्कोडिंग

एन्कोडिंग एल्गोरिदम का उच्च-स्तरीय दृश्य यहां दिखाया गया है:

  1. एक लंबाई की सभी पंक्तियों को सम्मिलित करने के लिए शब्दकोश को प्रारंभ करें।
  2. शब्दकोश में सबसे लंबी स्ट्रिंग W खोजे जो वर्तमान इनपुट से मेल खाती हो।
  3. आउटपुट के लिए W के लिए डिक्शनरी इंडेक्स को उत्सर्जित करें और इनपुट से W को हटा दें।
  4. शब्दकोश के इनपुट में W के पश्चात् अगला प्रतीक जोड़ें।
  5. चरण 2 पर जाएँ.

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

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


डिकोडिंग

डिकोडिंग एल्गोरिदम का उच्च-स्तरीय दृश्य यहां दिखाया गया है:

  1. लंबाई की सभी पंक्तियों को सम्मिलित करने के लिए शब्दकोश को प्रारंभ करें।
  2. अगला एन्कोडेड प्रतीक पढ़ें: क्या यह शब्दकोश में एन्कोड किया गया है?
    1. हाँ:
      1. संबंधित स्ट्रिंग W को आउटपुट में उत्सर्जित करें।
      2. W के पहले प्रतीक के साथ आउटपुट में उत्सर्जित पिछली स्ट्रिंग को संयोजित करें। इसे शब्दकोश में जोड़ें।
    2. नहीं:
      1. आउटपुट में उत्सर्जित पिछली स्ट्रिंग को उसके पहले प्रतीक के साथ संयोजित करें। इस स्ट्रिंग को V कॉल करें.
      2. शब्दकोश में V जोड़ें और आउटपुट में V उत्सर्जित करें।
  3. चरण 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-बिट कोड 2 देता है5 = बिट्स के 32 संभावित संयोजन, इसलिए जब 33वां शब्दकोश शब्द बनाया जाता है, तो एल्गोरिदम को उस बिंदु पर 5-बिट स्ट्रिंग्स से 6-बिट स्ट्रिंग्स पर स्विच करना होगा (सभी कोड मानों के लिए, जिसमें केवल पिछले आउटपुट सम्मिलित हैं) पांच बिट्स)। ध्यान दें कि चूंकि पूर्ण-शून्य कोड 00000 का उपयोग किया गया है, और इसे 0 लेबल किया गया है, 33वीं शब्दकोश प्रविष्टि को '32' लेबल किया गया है। (पहले उत्पन्न आउटपुट कोड-चौड़ाई परिवर्तन से प्रभावित नहीं होता है, किन्तु बार शब्दकोश में 6-बिट मान उत्पन्न हो जाता है, तो यह संभवतः अगला कोड उत्सर्जित हो सकता है, इसलिए पश्चात् के आउटपुट की चौड़ाई उसे समायोजित करने के लिए 6 बिट्स में परिवर्तित कर जाती है। )

प्रारंभिक शब्दकोश में निम्नलिखित प्रविष्टियाँ सम्मिलित हैं:

Symbol Binary Decimal
# 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# है।)

Current Sequence Next Char Output Extended Dictionary Comments
Code Bits
NULL T
T O 20 10100 27: TO 27 = first available code after 0 through 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 requires 6 bits, so for next output use 6 bits
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 # stops the algorithm; send the cur seq
0 000000 and the stop code
अनएन्कोडेड लंबाई = 25 प्रतीक × 5 बिट्स/प्रतीक = 125 बिट्स
एन्कोडेड लंबाई = (6 कोड × 5 बिट्स/कोड) + (11 कोड × 6 बिट्स/कोड) = 96 बिट्स।

एलजेडडब्ल्यू के उपयोग से 125 में से 29 बिट्स की बचत हुई है, जिससे संदेश में 23% से अधिक की कमी आई है। यदि संदेश लंबा होता, तो शब्दकोश के शब्द टेक्स्ट के लंबे और लंबे खंडों का प्रतिनिधित्व करना प्रारंभ कर देते, दोहराए गए शब्दों को बहुत संक्षिप्त रूप से भेजते।

डिकोडिंग

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

Input Output Sequence New Dictionary Entry Comments
Bits Code Full Conjecture
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? created code 31 (last to fit in 5 bits)
001110 14 N 32: RN 33: N? so start reading input at 6 bits
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 symbol (B) of
011111 31 OR 37: BEO 38: OR? next coded sequence received (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 कुछ ω को कोड करता है जो कि χ + ? है, और डिकोडर अज्ञात वर्ण को निम्नानुसार निर्धारित कर सकता है:

  1. डिकोडर X और फिर Z को देखता है, जहां X अनुक्रम χ को कोड करता है और Z कुछ अज्ञात अनुक्रम ω को कोड करता है।
  2. डिकोडर जानता है कि एनकोडर ने Z को χ + कुछ अज्ञात वर्ण c के लिए कोड के रूप में जोड़ा है, इसलिए ω = χ + c।
  3. चूँकि इनपुट स्ट्रीम में χ के पश्चात् पहला अक्षर c है, और चूँकि ω, χ के तुरंत पश्चात् आने वाली स्ट्रिंग है, इसलिए c को अनुक्रम का पहला अक्षर होना चाहिए।
  4. चूँकि χ, ω का प्रारंभिक उपस्ट्रिंग है, c भी χ का पहला अक्षर होना चाहिए।
  5. तो भले ही Z कोड टेबल में नहीं है, डिकोडर अज्ञात अनुक्रम का अनुमान लगाने में सक्षम है और Z के मान के रूप में टेबल में χ + (χ का पहला अक्षर) जोड़ता है।

यह स्थिति तब होती है जब एनकोडर को cScSc फॉर्म के इनपुट का सामना करना पड़ता है, जहां c एकल वर्ण है, S स्ट्रिंग है और cS पहले से ही शब्दकोश में है, किन्तु cSc नहीं है। एनकोडर सीएस के लिए कोड उत्सर्जित करता है, शब्दकोश में सीएससी के लिए नया कोड डालता है। इसके पश्चात् यह इनपुट में सीएससी देखता है (सीएससीएससी के दूसरे सी से प्रारंभ होता है) और अभी डाला गया नया कोड उत्सर्जित करता है। उपरोक्त तर्क से पता चलता है कि जब भी डिकोडर को कोई कोड प्राप्त होता है जो उसके शब्दकोश में नहीं है, तो स्थिति इस तरह दिखनी चाहिए।

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

आगे की कोडिंग

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

उपयोग

एलजेडडब्ल्यू कम्प्रेसन कंप्यूटर पर पहली व्यापक रूप से उपयोग की जाने वाली सार्वभौमिक डेटा कम्प्रेसन विधि बन गई। बड़ी अंग्रेजी भाषा की टेक्स्ट फ़ाइल को सामान्यतः एलजेडडब्ल्यू के माध्यम से उसके मूल आकार के लगभग आधे आकार में कॉम्प्रेस्सेड किया जा सकता है।

एलजेडडब्ल्यू का उपयोग सार्वजनिक-डोमेन प्रोग्राम कंप्रेस में किया गया था, जो 1986 के आसपास यूनिक्स सिस्टम में कमोबेश मानक उपयोगिता बन गया। यह तब से विभिन्न वितरणों से गायब हो गया है, क्योंकि इसने एलजेडडब्ल्यू पेटेंट का उल्लंघन किया है और क्योंकि gzip ने LZ77 का उपयोग करके उत्तम कम्प्रेसन अनुपात का उत्पादन किया है। -आधारित DEFLATE एल्गोरिथ्म, किन्तु 2008 तक कम से कम FreeBSD में वितरण के भाग के रूप में कंप्रेस और uncompress दोनों सम्मिलित हैं। विभिन्न अन्य लोकप्रिय कम्प्रेसन उपयोगिताओं ने भी एलजेडडब्ल्यू या निकट संबंधी विधियों का उपयोग किया।

एलजेडडब्ल्यू का बहुत व्यापक रूप से उपयोग किया जाने लगा जब यह 1987 में जीआईएफ छवि प्रारूप का हिस्सा बन गया। इसका उपयोग (वैकल्पिक रूप से) टीआईएफएफ और पीडीएफ फ़ाइलों में भी किया जा सकता है। (चूंकि एलजेडडब्ल्यू एडोब Acrobat सॉफ़्टवेयर में उपलब्ध है, Acrobat डिफ़ॉल्ट रूप से पीडीएफ फ़ाइलों में अधिकांश टेक्स्ट और कलर-टेबल-आधारित छवि डेटा के लिए DEFLATE का उपयोग करता है।)

पेटेंट

Main article: Graphics Interchange Format § Unisys and LZW patent enforcement

एलजेडडब्ल्यू और इसी तरह के एल्गोरिदम के लिए संयुक्त राज्य अमेरिका और अन्य देशों में विभिन्न पेटेंट जारी किए गए हैं। 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 और [https:/) सम्मिलित हैं। /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 साल पश्चात्।

वेरिएंट

  • LZMW (1985, वी. मिलर, एम. वेगमैन द्वारा)[5] - शब्दकोश में पहले से मौजूद सबसे लंबी स्ट्रिंग (वर्तमान मिलान) के लिए इनपुट खोजता है; शब्दकोश में पिछले मिलान का वर्तमान मिलान के साथ संयोजन जोड़ता है। (शब्दकोश प्रविष्टियाँ इस प्रकार अधिक तेजी से बढ़ती हैं; किन्तु इस योजना को प्रयुक्त करना अधिक जटिल है।) मिलर और वेगमैन भी शब्दकोश भर जाने पर शब्दकोश से कम-आवृत्ति प्रविष्टियों को हटाने का सुझाव देते हैं।
  • एलज़ैप (1988, जेम्स स्टोरर द्वारा)[6] - LZMW का संशोधन: शब्दकोश में वर्तमान मिलान के साथ पिछले मिलान के संयोजन को जोड़ने के अतिरिक्त, वर्तमान मिलान के प्रत्येक प्रारंभिक सबस्ट्रिंग के साथ पिछले मिलान के संयोजन को जोड़ें (एपी सभी उपसर्गों के लिए है)। उदाहरण के लिए, यदि पिछला मिलान विकी है और वर्तमान मिलान पीडिया है, तो LZAP एनकोडर शब्दकोश में 5 नए अनुक्रम जोड़ता है: wikip, wikipe, wikiped, wikipedi, और wikipedia, जहां LZMW एनकोडर केवल अनुक्रम विकिपीडिया जोड़ता है। यह अधिक शब्दकोश प्रविष्टियाँ जोड़ने की कीमत पर, LZMW की कुछ जटिलता को समाप्त करता है।
  • एलजेडडब्ल्यूL एलजेडडब्ल्यू का शब्दांश-आधारित वर्जन है।

यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 Welch, Terry (1984). "उच्च-प्रदर्शन डेटा संपीड़न के लिए एक तकनीक". Computer. 17 (6): 8–19. doi:10.1109/MC.1984.1659158. S2CID 2055321.
  2. ↑ 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.
  3. ↑ U.S. Patent 4,558,302
  4. ↑ 4.0 4.1 "LZW पेटेंट सूचना". About Unisys. Unisys. Archived from the original on June 26, 2009. Retrieved March 6, 2014.
  5. ↑ David Salomon, Data Compression – The complete reference, 4th ed., page 209.
  6. ↑ David Salomon, Data Compression – The complete reference, 4th ed., page 212.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=लेम्पेल-ज़िव-वेल्च&oldid=279947’