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

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

अंतर्वस्तु

• 1कलन विधि
  • 1.1एन्कोडिंग
  • 1.2डिकोडिंग
  • 1.3चर-चौड़ाई कोड
  • 1.4पैकिंग आदेश
• 2उदाहरण
  • 2.1एन्कोडिंग
  • 2.2डिकोडिंग
• 3आगे कोडिंग
• 4उपयोग
• 5पेटेंट
• 6वेरिएंट
• 7यह सभी देखें
• 8संदर्भ
• 9बाहरी कड़ियाँ

एल्गोरिथ्म

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

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

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

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

एन्कोडिंग

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

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

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

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