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

From Vigyanwiki
No edit summary
 
(6 intermediate revisions by 2 users not shown)
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>
===डिकोडिंग===
===डिकोडिंग===
डिकोडिंग एल्गोरिदम का उच्च-स्तरीय दृश्य यहां दिखाया गया है:
डिकोडिंग एल्गोरिदम का उच्च-स्तरीय दृश्य यहां दिखाया गया है:
# लंबाई की सभी पंक्तियों को शामिल करने के लिए शब्दकोश को प्रारंभ करें।
# लंबाई की सभी पंक्तियों को सम्मिलित करने के लिए शब्दकोश को प्रारंभ करें।
# अगला एन्कोडेड प्रतीक पढ़ें: क्या यह शब्दकोश में एन्कोड किया गया है?
# अगला एन्कोडेड सिम्बल पढ़ें: क्या यह शब्दकोश में एन्कोड किया गया है?
##हाँ:
##हाँ:
###संबंधित स्ट्रिंग W को आउटपुट में उत्सर्जित करें।
###संबंधित स्ट्रिंग W को आउटपुट में उत्सर्जित करें।
###W के पहले प्रतीक के साथ आउटपुट में उत्सर्जित पिछली स्ट्रिंग को संयोजित करें। इसे शब्दकोश में जोड़ें।
###W के पहले सिम्बल के साथ आउटपुट में उत्सर्जित पिछली स्ट्रिंग को संयोजित करें। इसे शब्दकोश में जोड़ें।
##नहीं:
##नहीं:
###आउटपुट में उत्सर्जित पिछली स्ट्रिंग को उसके पहले प्रतीक के साथ संयोजित करें। इस स्ट्रिंग को V कॉल करें.
###आउटपुट में उत्सर्जित पिछली स्ट्रिंग को उसके पहले सिम्बल के साथ संयोजित करें। इस स्ट्रिंग को V कॉल करें.
###शब्दकोश में 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 मान देते हैं। (एलजेडडब्ल्यू के अधिकांश फ्लेवर डेटा वर्णमाला के पश्चात् स्टॉप कोड डालेंगे, किन्तु मूल एल्गोरिदम में कुछ भी इसकी आवश्यकता नहीं है। एनकोडर और डिकोडर को केवल इस तथ्य पर सहमत होना होगा कि इसका क्या मूल्य है।)


प्लेनटेक्स्ट वर्णमाला में 26 प्रतीक हैं (बड़े अक्षर A से Z तक)। # का उपयोग स्टॉप कोड को दर्शाने के लिए किया जाता है: प्लेनटेक्स्ट वर्णमाला के बाहर कोड जो विशेष हैंडलिंग को ट्रिगर करता है। हम मनमाने ढंग से अक्षरों के लिए 1 से 26 तक मान निर्दिष्ट करते हैं, और स्टॉप कोड '#' के लिए 0 मान देते हैं। (LZW के अधिकांश फ्लेवर डेटा वर्णमाला के बाद स्टॉप कोड डालेंगे, लेकिन मूल एल्गोरिदम में कुछ भी इसकी आवश्यकता नहीं है। एनकोडर और डिकोडर को केवल इस बात पर सहमत होना होगा कि इसका क्या मूल्य है।)
इस प्रकार कंप्यूटर इन्हें बिट्स की स्ट्रिंग के रूप में प्रस्तुत करता है। 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;"
|-
|-
! Symbol !! Binary !! Decimal
! सिम्बल !! बाइनरी !! दशमलव
|-
|-
| # || 00000 ||  0
| # || 00000 ||  0
Line 127: Line 125:


===एन्कोडिंग===
===एन्कोडिंग===
अनुक्रम ω में बफ़र इनपुट वर्ण जब तक ω + अगला वर्ण शब्दकोश में नहीं है। ω के लिए कोड हटाएं, और शब्दकोश में ω + अगला वर्ण जोड़ें। अगले अक्षर के साथ फिर से बफरिंग शुरू करें। (एन्कोड की जाने वाली स्ट्रिंग 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;"
|-
|-
! scope="col" width="6em" rowspan="2" | Current Sequence
! scope="col" width="6em" rowspan="2" | वर्तमान अनुक्रम
! scope="col" width="4em" rowspan="2" | Next Char
! scope="col" width="4em" rowspan="2" | अगला चार
! colspan="2" | Output
! colspan="2" | आउटपुट
! scope="col" width="7em" rowspan="2" colspan="2" | Extended Dictionary
! scope="col" width="7em" rowspan="2" colspan="2" | विस्तारित शब्दकोश
! rowspan="2" | Comments
! rowspan="2" | कमेन्ट
|-
|-
! Code || Bits
! कोड || बिट्स
|-
|-
| style="text-align: center;" | NULL
| style="text-align: center;" | NULL
Line 149: Line 147:
| style="border-right: none;" | 27:
| style="border-right: none;" | 27:
| style="border-left: none;" | TO
| style="border-left: none;" | TO
| style="text-align: left;" | 27 = first available code after 0 through 26
| style="text-align: left;" | 27 = 0 से 26 के पश्चात् पहला उपलब्ध कोड
|-
|-
| style="text-align: center;" | O
| style="text-align: center;" | O
Line 180: Line 178:
| style="border-right: none;" | 32:
| style="border-right: none;" | 32:
| style="border-left: none;" | RN
| style="border-left: none;" | RN
| style="text-align: left;" | 32 requires 6 bits, so for next output use 6 bits
| style="text-align: left;" | 32 के लिए 6 बिट्स की आवश्यकता है, इसलिए अगले आउटपुट के लिए 6 बिट्स का उपयोग करें
|-
|-
| style="text-align: center;" | N
| style="text-align: center;" | N
Line 241: Line 239:
| style="border-right: none;" |
| style="border-right: none;" |
| style="border-left: none;" |
| style="border-left: none;" |
| style="text-align: left;" | # stops the algorithm; send the cur seq
| style="text-align: left;" | # एल्गोरिदम रोकता है; क्यूर सीक भेजें
|-
|-
| || || 0 || {{mono|000000}}
| || || 0 || {{mono|000000}}
| style="border-right: none;" |
| style="border-right: none;" |
| style="border-left: none;" |
| style="border-left: none;" |
| style="text-align: left;" | and the stop code
| style="text-align: left;" | और स्टॉप कोड
|-
|-
|}
|}
:अनएन्कोडेड लंबाई = 25 प्रतीक × 5 बिट्स/प्रतीक = 125 बिट्स
:अनएन्कोडेड लंबाई = 25 सिम्बल × 5 बिट्स/सिम्बल = 125 बिट्स
:एन्कोडेड लंबाई = (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;"
|-
|-
! colspan="2" | Input
! colspan="2" | इनपुट
! scope="col" width="6em" rowspan="2" | Output Sequence
! scope="col" width="6em" rowspan="2" | आउटपुट अनुक्रम
! colspan="4" | New Dictionary Entry
! colspan="4" | नई शब्दकोश प्रविष्टि
! rowspan="2" | Comments
! rowspan="2" | कमेन्ट
|-
|-
! Bits !! Code
! बिट्स !! कोड
! scope="col" width="6em" colspan="2" | Full
! scope="col" width="6em" colspan="2" | फुल
! scope="col" width="6em" colspan="2" | Conjecture
! scope="col" width="6em" colspan="2" | अनुमान
|-
|-
| 10100 || 20
| 10100 || 20
Line 309: Line 307:
| style="border-right: none;" | 32:
| style="border-right: none;" | 32:
| style="border-left: none;" | R?
| style="border-left: none;" | R?
| style="text-align: left;" | created code 31 (last to fit in 5 bits)
| style="text-align: left;" | कोड 31 बनाया गया (5 बिट्स में फ़िट होने वाला अंतिम)
|-
|-
| 001110 || 14
| 001110 || 14
Line 317: Line 315:
| style="border-right: none;" | 33:
| style="border-right: none;" | 33:
| style="border-left: none;" | N?
| style="border-left: none;" | N?
| style="text-align: left;" | so start reading input at 6 bits
| style="text-align: left;" | इसलिए 6 बिट पर इनपुट पढ़ना प्रारंभ करें
|-
|-
| 001111 || 15
| 001111 || 15
Line 346: Line 344:
| style="border-right: none;" | 37:
| style="border-right: none;" | 37:
| style="border-left: none;" | BE?
| style="border-left: none;" | BE?
| style="text-align: left;" | 36 = TO + 1st symbol (B) of
| style="text-align: left;" | 36 = TO + 1st सिस्म्ब्ल (B)
|-
|-
| 011111 || 31
| 011111 || 31
Line 354: Line 352:
| style="border-right: none;" | 38:
| style="border-right: none;" | 38:
| style="border-left: none;" | OR?
| style="border-left: none;" | OR?
| style="text-align: left;" | next coded sequence received (BE)
| style="text-align: left;" | अगला कोडित अनुक्रम प्राप्त (BE)
|-
|-
| 100100 || 36
| 100100 || 36
Line 392: Line 390:
|-
|-
|}
|}
प्रत्येक चरण में, डिकोडर को कोड 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 नहीं है। एनकोडर cS के लिए कोड उत्सर्जित करता है, शब्दकोश में cSc के लिए नया कोड डालता है। इसके पश्चात् यह इनपुट में cSc देखता है (cScSc के दूसरे सी से प्रारंभ होता है) और अभी डाला गया नया कोड उत्सर्जित करता है। उपरोक्त तर्क से पता चलता है कि जब भी डिकोडर को कोई कोड प्राप्त होता है जो उसके शब्दकोश में नहीं है, तो स्थिति इस तरह दिखनी चाहिए।


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


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


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


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


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


== पेटेंट ==
== पेटेंट ==
{{main|Graphics Interchange Format#Unisys and LZW patent enforcement}}
{{main|ग्राफिक्स इंटरचेंज फोर्मेट#यूनिसिस और एलजेडडब्ल्यू पेटेंट प्रवर्तन}}
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/JPS5719857A/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> - शब्दकोश में पहले से मौजूद सबसे लंबी स्ट्रिंग (वर्तमान मिलान) के लिए इनपुट खोजता है; शब्दकोश में पिछले मिलान का वर्तमान मिलान के साथ संयोजन जोड़ता है। (शब्दकोश प्रविष्टियाँ इस प्रकार अधिक तेजी से बढ़ती हैं; लेकिन इस योजना को लागू करना अधिक जटिल है।) मिलर और वेगमैन भी शब्दकोश भर जाने पर शब्दकोश से कम-आवृत्ति प्रविष्टियों को हटाने का सुझाव देते हैं।
* एलजेएमडब्ल्यू (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> - एलजेएमडब्ल्यू का संशोधन: शब्दकोश में वर्तमान मिलान के साथ पिछले मिलान के संयोजन को जोड़ने के अतिरिक्त, वर्तमान मिलान के प्रत्येक प्रारंभिक सबस्ट्रिंग के साथ पिछले मिलान के संयोजन को जोड़ें (एपी सभी उपसर्गों के लिए है)। उदाहरण के लिए, यदि पिछला मिलान विकी है और वर्तमान मिलान पीडिया है, तो एलजेडएपी एनकोडर शब्दकोश में 5 नए अनुक्रम wikip, wikipe, wikiped, wikipedi, और wikipedia, जोड़ता है: जहां एलजेएमडब्ल्यू एनकोडर केवल अनुक्रम विकिपीडिया जोड़ता है। यह अधिक शब्दकोश प्रविष्टियाँ जोड़ने की मूल्य पर, एलजेएमडब्ल्यू की कुछ सम्मिश्रता को समाप्त करता है।
* [[LZWL]] LZW का शब्दांश-आधारित संस्करण है।
* [[LZWL|एलजेडडब्ल्यूएल]] एलजेडडब्ल्यू का सिलेबल-बेस्ड वर्जन है।


== यह भी देखें ==
== यह भी देखें ==


* LZ77 और LZ78
* LZ77 और LZ78
* [[लेम्पेल-ज़िव-मार्कोव श्रृंखला एल्गोरिथ्म]]
*एलजेडएमए
* लेम्पेल-ज़िव-स्टॉरर-स्ज़िमंस्की
* लेम्पेल-ज़िव-स्टॉरर-स्ज़िमंस्की
* [[एलजेडजेबी]]
* [[एलजेडजेबी]]
* [[प्रसंग वृक्ष भार]]
* कॉन्टेक्स्ट ट्री वेइटिंग
* [[असतत कोसाइन परिवर्तन]] (डीसीटी), [[जेपीईजी]] और [[एमपीईजी]] कोडिंग मानकों में उपयोग किया जाने वाला [[हानिपूर्ण संपीड़न]] एल्गोरिदम
* डिस्क्रेट [[असतत कोसाइन परिवर्तन|कोसाइन ट्रांसफॉर्म]] (डीसीटी), [[जेपीईजी]] और [[एमपीईजी]] कोडिंग मानकों में उपयोग किया जाने वाला [[हानिपूर्ण संपीड़न|लोसी]] कम्प्रेसन एल्गोरिदम


==संदर्भ==
==संदर्भ==
{{Reflist|2}}
{{Reflist|2}}
==बाहरी संबंध==
==बाहरी संबंध==
* [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: खोज और आविष्कार विवाद]]  
Line 457: Line 452:
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 07/12/2023]]
[[Category:Created On 07/12/2023]]
[[Category:Vigyan Ready]]

Latest revision as of 21:42, 18 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-बिट कोड 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 कुछ ω को कोड करता है जो कि χ + ? है, और डिकोडर अज्ञात वर्ण को निम्नानुसार निर्धारित कर सकता है:

  1. डिकोडर X और फिर Z को देखता है, जहां X अनुक्रम χ को कोड करता है और Z कुछ अज्ञात अनुक्रम ω को कोड करता है।
  2. डिकोडर जानता है कि एनकोडर ने Z को χ + कुछ अज्ञात वर्ण c के लिए कोड के रूप में जोड़ा है, इसलिए ω = χ + c है।
  3. चूँकि इनपुट स्ट्रीम में χ के पश्चात् पहला अक्षर c है, और चूँकि ω, χ के तुरंत पश्चात् आने वाली स्ट्रिंग है, इसलिए c को अनुक्रम का पहला अक्षर होना चाहिए।
  4. चूँकि χ, ω का प्रारंभिक उपस्ट्रिंग है, c भी χ का पहला अक्षर होना चाहिए।
  5. तथापि 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) सम्मिलित हैं। एनईसी के जून कनात्सु से, 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, जोड़ता है: जहां एलजेएमडब्ल्यू एनकोडर केवल अनुक्रम विकिपीडिया जोड़ता है। यह अधिक शब्दकोश प्रविष्टियाँ जोड़ने की मूल्य पर, एलजेएमडब्ल्यू की कुछ सम्मिश्रता को समाप्त करता है।
  • एलजेडडब्ल्यूएल एलजेडडब्ल्यू का सिलेबल-बेस्ड वर्जन है।

यह भी देखें

संदर्भ

  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.

बाहरी संबंध