> lz77 | sliding | window <
// LZ77 – स्लाइडिंग विंडो एल्गोरिदम और डिक्शनरी रेफरेंस के साथ कम्प्रेशन
डिक्शनरी कोडिंग
दोहराए जाने वाले पैटर्न को ऑफ़सेट और लंबाई रेफरेंस के रूप में सहेजता है।
स्लाइडिंग विंडो
पैटर्न खोजने के लिए चलती हुई विंडो बनाए रखती है।
आधार एल्गोरिदम
ZIP, GZIP, DEFLATE और PNG जैसे आधुनिक कम्प्रेशन एल्गोरिदम का आधार।
>> तकनीकी जानकारी
LZ77 कैसे काम करता है:
LZ77 हाल ही में देखे गए डेटा की एक स्लाइडिंग विंडो बनाए रखता है। हर पॉज़िशन पर यह विंडो में सबसे लंबा मिलान ढूँढता है। अगर मैच मिलता है तो (ऑफ़सेट, लंबाई, अगला अक्षर) के रूप में रेफरेंस आउटपुट होता है। अगर मैच नहीं मिलता, तो (0,0,अक्षर) जैसा लिटरल लिखा जाता है। इस तरह दोहराए गए पैटर्न छोटे रेफरेंस में बदल जाते हैं और बिना डेटा खोए कम्प्रेशन मिलता है।
LZ77 उदाहरण:
Text: "ABCABCABC" Window=4, Lookahead=4 Position 0: 'A' - no match → (0,0,A) Position 1: 'B' - no match → (0,0,B) Position 2: 'C' - no match → (0,0,C) Position 3: 'ABC' - matches at offset 3 → (3,3,A) Position 7: 'BC' - matches at offset 3 → (3,2,) Output: (0,0,A)(0,0,B)(0,0,C)(3,3,A)(3,2,)
LZ77 क्यों उपयोग करें?:
- ▸लॉसलेस (बिना डेटा हानि) कम्प्रेशन
- ▸डेटा के फ़ॉर्मेट का पूर्व ज्ञान आवश्यक नहीं
- ▸डेटा के पैटर्न के अनुसार अनुकूलित
- ▸इम्प्लीमेंटेशन अपेक्षाकृत सरल
- ▸आधुनिक कम्प्रेशन स्कीमों की आधार तकनीक
>> अक्सर पूछे जाने वाले प्रश्न
LZ77 क्या है?
LZ77 एक सार्वभौमिक लॉसलेस डेटा कम्प्रेशन एल्गोरिदम है जिसे 1977 में अब्राहम लेम्पेल और याकोब ज़िव ने प्रकाशित किया। यह डेटा स्ट्रीम में दोहराए गए हिस्सों को पहले से मौजूद अनुक्रम के रेफरेंस से बदल देता है।
स्लाइडिंग विंडो कैसे काम करती है?
स्लाइडिंग विंडो दो भागों से बनी होती है: सर्च बफ़र (पहले से प्रोसेस्ड डेटा) और लुकअहेड बफ़र (जिसे कम्प्रेस करना है)। एल्गोरिदम सर्च बफ़र में लुकअहेड की शुरुआत से मिलान खोजता है और फिर रेफरेंस या लिटरल आउटपुट करता है।
LZ77 बनाम आधुनिक कम्प्रेशन?
LZ77 कई आधुनिक कम्प्रेशन एल्गोरिदम का आधार है। DEFLATE (ZIP और GZIP में) LZ77 को Huffman कोडिंग के साथ जोड़ता है। LZSS LZ77 की रिडंडेंसी घटाता है, जबकि LZ78 और LZW अलग तरह से डिक्शनरी बनाते हैं पर सिद्धांत समान रखते हैं।
उपयुक्त विंडो साइज क्या है?
सामान्य डेटा के लिए 32 KB से 64 KB विंडो साइज सामान्य है। बड़ी विंडो ज़्यादा मैच ढूँढती है लेकिन मेमोरी और समय अधिक लेती है। DEFLATE 32 KB का उपयोग करता है। लुकअहेड बफ़र अक्सर 256–512 बाइट का होता है। सबसे अच्छा आकार आपके डेटा के पुनरावृत्ति पैटर्न पर निर्भर करता है।
// हल किया गया उदाहरण
| # | Offset | Length | Next | Output |
|---|---|---|---|---|
| 1 | 0 | 0 | a | a |
| 2 | 0 | 0 | b | b |
| 3 | 0 | 0 | r | r |
| 4 | 3 | 1 | c | a + c |
| 5 | 2 | 1 | d | a + d |
| 6 | 7 | 4 | — | abra |
// कोड उदाहरण
Input abracadabra (positions 0..10)
Token (offset, length, next)
offset = distance back into the window, length = bytes copied
Decode copy `length` bytes starting `offset` back, then append `next`
(the copy may overlap its own output, e.g. (1,5,x) repeats a byte)
Window the sliding search buffer; deflate/gzip use 32 KiB
>> और प्रश्न
प्र: ट्रिपल (ऑफ़सेट, लंबाई, अक्षर) का क्या अर्थ है?
उ: ऑफ़सेट बताता है कि देखी जा चुकी विंडो में कितना पीछे जाना है, लंबाई कितने बाइट कॉपी करने हैं, और अक्षर अगला नया बाइट है। डिकोडर इससे आउटपुट चरण-दर-चरण बनाता है।
प्र: कॉपी ओवरलैप क्यों कर सकती है?
उ: यदि ऑफ़सेट लंबाई से छोटा है तो कॉपी अभी लिखे बाइट पढ़ती है। इससे दोहराव बनते हैं: (1, 5, x) पिछले अक्षर को पाँच बार देता है।
प्र: LZ77 कहाँ उपयोग होता है?
उ: LZ77 DEFLATE (gzip, zlib, PNG, ZIP) का आधार है और इसके रूपांतर LZ4, Snappy, Zstandard और Brotli में हैं। विंडो का आकार और खोज-रणनीति संपीड़न अनुपात व गति तय करते हैं।