लेम्पेल-ज़िव-वेल्च

From Vigyanwiki
Revision as of 21:18, 12 December 2023 by alpha>AshishG

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

एल्गोरिदम

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

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

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

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

एन्कोडिंग

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

  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 बिट चौड़ा हो।

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

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

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

पैकिंग ऑर्डर

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

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

उदाहरण

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

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

टोबेऑर्नोटोबियोर्टोबॉर्ननॉट#

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

कंप्यूटर इन्हें अंश ्स की स्ट्रिंग के रूप में प्रस्तुत करता है। 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 बिट्स।

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

आगे की कोडिंग

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

उपयोग

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

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

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

पेटेंट

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

LZW और इसी तरह के एल्गोरिदम के लिए संयुक्त राज्य अमेरिका और अन्य देशों में विभिन्न पेटेंट जारी किए गए हैं। LZ78 द्वारा कवर किया गया था U.S. Patent 4,464,650 लेम्पेल, ज़िव, कोहन और ईस्टमैन द्वारा, जिसे स्पेरी कॉर्पोरेशन, बाद में यूनिसिस कॉर्पोरेशन को सौंपा गया, 10 अगस्त 1981 को दायर किया गया। LZW एल्गोरिथ्म के लिए दो अमेरिकी पेटेंट जारी किए गए थे: 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 में भार रहित पोर्टेबल नेटवर्क ग्राफ़िक्स (पीएनजी) फ़ाइल स्वरूप।

LZW एल्गोरिथम पर यूनिसिस का अमेरिकी पेटेंट 20 जून 2003 को समाप्त हो गया।[4] इसके दाखिल होने के 20 साल बाद. यूनाइटेड किंगडम, फ्रांस, जर्मनी, इटली, जापान और कनाडा में दायर किए गए सभी पेटेंट 2004 में समाप्त हो गए।[4]इसी तरह उनके दाखिल होने के 20 साल बाद।

वेरिएंट

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

यह भी देखें

संदर्भ

  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=279946’