LZ77 और LZ78 - Revision history

Indicwiki: 13 revisions imported from :alpha:LZ77_और_LZ78

2023-12-18T16:14:03Z

13 revisions imported from alpha:LZ77_और_LZ78

← Older revision	Revision as of 21:44, 18 December 2023
(No difference)

alpha>Neeraja: added Category:Vigyan Ready using HotCat

2023-12-15T11:42:07Z

added Category:Vigyan Ready using HotCat

← Older revision		Revision as of 17:12, 15 December 2023
Line 142:		Line 142:
	[[Category: Machine Translated Page]]		[[Category: Machine Translated Page]]
	[[Category:Created On 07/12/2023]]		[[Category:Created On 07/12/2023]]
			[[Category:Vigyan Ready]]

alpha>Sangeeta at 08:49, 13 December 2023

2023-12-13T08:49:17Z

← Older revision		Revision as of 14:19, 13 December 2023
Line 114:		Line 114:

	==LZ78==		==LZ78==
	LZ78 एल्गोरिथम इनपुट से टोकन अनुक्रमों का डिक्शनरी बनाकर अनुक्रमिक डेटा को कंप्रेस्ड करता है, और फिर डिक्शनरी एंट्री के संदर्भ के साथ डेटा स्ट्रीम में अनुक्रम की दूसरी और ~~बाद~~ की घटना को प्रतिस्थापित करता है। अवलोकन यह है कि दोहराए गए अनुक्रमों की संख्या किसी अनुक्रम की ~~गैर~~-~~यादृच्छिक~~ प्रकृति का अच्छा माप है। एल्गोरिथम डिक्शनरी को एन-एरी ट्री के रूप में प्रस्तुत करता है जहां एन टोकन अनुक्रम बनाने के लिए उपयोग किए जाने वाले टोकन की संख्या है। प्रत्येक डिक्शनरी एंट्री ~~प्रपत्र~~ की है {{code\|1=dictionary[...] = {index, token} }}, जहां इंडेक्स डिक्शनरी एंट्री का इंडेक्स है जो ~~पहले~~ देखे गए अनुक्रम का प्रतिनिधित्व करता है, और टोकन इनपुट से ~~अगला~~ टोकन है जो इस एंट्री को डिक्शनरी में अद्वितीय बनाता है। ध्यान दें कि एल्गोरिथ्म कितना ~~लालची~~ है, और इसलिए ~~तालिका~~ में तब तक कुछ भी नहीं जोड़ा जाता है जब तक कि अद्वितीय निर्माण टोकन नहीं मिल जाता है। एल्गोरिथ्म ~~अंतिम मिलान~~ इंडेक्स = 0 और अगले उपलब्ध इंडेक्स = 1 को प्रारंभ करना है और फिर, इनपुट स्ट्रीम के प्रत्येक टोकन के लिए, डिक्शनरी मैच की सर्च करता है: {{code\|{{mset\|last matching index, token}}}}. यदि कोई ~~मिलान~~ पाया जाता है, तो ~~अंतिम मिलान~~ इंडेक्स को ~~मिलान~~ एंट्री के इंडेक्स पर सेट किया जाता है, कुछ भी आउटपुट नहीं होता है, और ~~अंतिम मिलान~~ इंडेक्स अब तक के इनपुट का प्रतिनिधित्व करने के लिए छोड़ दिया जाता है। इनपुट तब तक ~~संसाधित~~ किया जाता है जब तक कोई ~~मिलान~~ न मिल जाए। फिर नई डिक्शनरी एंट्री बनाई जाती है, {{code\|1=dictionary[next available index] = {last matching index, token} }}, और एल्गोरिथम ~~अंतिम मिलान~~ इंडेक्स को आउटपुट करता है, उसके ~~बाद~~ टोकन देता है, फिर ~~अंतिम मिलान~~ इंडेक्स = 0 को रीसेट करता है और अगले उपलब्ध इंडेक्स को बढ़ाता है। उदाहरण के ~~तौर पर~~ टोकन के अनुक्रम ~~पर विचार करें~~ {{samp\|AABBA}} जो डिक्शनरी को ~~इकट्ठा~~ करेगा;		LZ78 एल्गोरिथम इनपुट से टोकन अनुक्रमों का डिक्शनरी बनाकर अनुक्रमिक डेटा को कंप्रेस्ड करता है, और फिर डिक्शनरी एंट्री के संदर्भ के साथ डेटा स्ट्रीम में अनुक्रम की दूसरी और पश्चात की घटना को प्रतिस्थापित करता है। अवलोकन यह है कि दोहराए गए अनुक्रमों की संख्या किसी अनुक्रम की नॉन-रैंडम प्रकृति का अच्छा माप है। एल्गोरिथम डिक्शनरी को n-एरी ट्री के रूप में प्रस्तुत करता है जहां n टोकन अनुक्रम बनाने के लिए उपयोग किए जाने वाले टोकन की संख्या है। प्रत्येक डिक्शनरी एंट्री डिक्शनरी फॉर्म की होती है {{code\|1=dictionary[...] = {index, token} }}, जहां इंडेक्स डिक्शनरी एंट्री का इंडेक्स है जो पूर्व में देखे गए अनुक्रम का प्रतिनिधित्व करता है, और टोकन इनपुट से नेक्स्ट टोकन है जो इस एंट्री को डिक्शनरी में अद्वितीय बनाता है। ध्यान दें कि एल्गोरिथ्म कितना ग्रीडी है, और इसलिए टेबल में तब तक कुछ भी नहीं जोड़ा जाता है जब तक कि अद्वितीय निर्माण टोकन नहीं मिल जाता है। एल्गोरिथ्म लास्ट मैचिंग इंडेक्स = 0 और अगले उपलब्ध इंडेक्स = 1 को प्रारंभ करना है और फिर, इनपुट स्ट्रीम के प्रत्येक टोकन के लिए, डिक्शनरी मैच की सर्च करता है: {{code\|{{mset\|last matching index, token}}}}। यदि कोई मैच पाया जाता है, तो लास्ट मैचिंग इंडेक्स को मैचिंग एंट्री के इंडेक्स पर सेट किया जाता है, कुछ भी आउटपुट नहीं होता है, और लास्ट मैचिंग इंडेक्स अब तक के इनपुट का प्रतिनिधित्व करने के लिए छोड़ दिया जाता है। इनपुट तब तक प्रोसेस्ड किया जाता है जब तक कोई मैच न मिल जाए। फिर नई डिक्शनरी एंट्री बनाई जाती है, {{code\|1=dictionary[next available index] = {last matching index, token} }}, और एल्गोरिथम लास्ट मैचिंग इंडेक्स को आउटपुट करता है, उसके पश्चात टोकन देता है, फिर लास्ट मैचिंग इंडेक्स = 0 को रीसेट करता है और अगले उपलब्ध इंडेक्स को बढ़ाता है। उदाहरण के रूप में टोकन के अनुक्रम{{samp\|AABBA}}पर विचार करें जो डिक्शनरी को एकत्र करेगा;
	{{pre\|		{{pre\|
	0 {0,_}		0 {0,_}

alpha>Sangeeta at 08:36, 13 December 2023

2023-12-13T08:36:43Z

← Older revision		Revision as of 14:06, 13 December 2023
Line 114:		Line 114:

	==LZ78==		==LZ78==
	LZ78 एल्गोरिथम इनपुट से टोकन अनुक्रमों का डिक्शनरी बनाकर अनुक्रमिक डेटा को कंप्रेस्ड करता है, और फिर डिक्शनरी ~~प्रविष्टि~~ के संदर्भ के साथ डेटा स्ट्रीम में अनुक्रम की दूसरी और बाद की घटना को प्रतिस्थापित करता है। अवलोकन यह है कि दोहराए गए अनुक्रमों की संख्या किसी अनुक्रम की गैर-यादृच्छिक प्रकृति का अच्छा माप है। एल्गोरिथम डिक्शनरी को एन-एरी ट्री के रूप में प्रस्तुत करता है जहां एन टोकन अनुक्रम बनाने के लिए उपयोग किए जाने वाले टोकन की संख्या है। प्रत्येक डिक्शनरी ~~प्रविष्टि~~ प्रपत्र की है {{code\|1=dictionary[...] = {index, token} }}, जहां इंडेक्स डिक्शनरी ~~प्रविष्टि~~ का इंडेक्स है जो पहले देखे गए अनुक्रम का प्रतिनिधित्व करता है, और टोकन इनपुट से अगला टोकन है जो इस ~~प्रविष्टि~~ को डिक्शनरी में अद्वितीय बनाता है। ध्यान दें कि एल्गोरिथ्म कितना लालची है, और इसलिए तालिका में तब तक कुछ भी नहीं जोड़ा जाता है जब तक कि अद्वितीय निर्माण टोकन नहीं मिल जाता है। एल्गोरिथ्म अंतिम मिलान इंडेक्स = 0 और अगले उपलब्ध इंडेक्स = 1 को प्रारंभ करना है और फिर, इनपुट स्ट्रीम के प्रत्येक टोकन के लिए, डिक्शनरी मैच की सर्च करता है: {{code\|{{mset\|last matching index, token}}}}. यदि कोई मिलान पाया जाता है, तो अंतिम मिलान इंडेक्स को मिलान ~~प्रविष्टि~~ के इंडेक्स पर सेट किया जाता है, कुछ भी आउटपुट नहीं होता है, और अंतिम मिलान इंडेक्स अब तक के इनपुट का प्रतिनिधित्व करने के लिए छोड़ दिया जाता है। इनपुट तब तक संसाधित किया जाता है जब तक कोई मिलान न मिल जाए। फिर नई डिक्शनरी ~~प्रविष्टि~~ बनाई जाती है, {{code\|1=dictionary[next available index] = {last matching index, token} }}, और एल्गोरिथम अंतिम मिलान इंडेक्स को आउटपुट करता है, उसके बाद टोकन देता है, फिर अंतिम मिलान इंडेक्स = 0 को रीसेट करता है और अगले उपलब्ध इंडेक्स को बढ़ाता है। उदाहरण के तौर पर टोकन के अनुक्रम पर विचार करें {{samp\|AABBA}} जो डिक्शनरी को इकट्ठा करेगा;		LZ78 एल्गोरिथम इनपुट से टोकन अनुक्रमों का डिक्शनरी बनाकर अनुक्रमिक डेटा को कंप्रेस्ड करता है, और फिर डिक्शनरी एंट्री के संदर्भ के साथ डेटा स्ट्रीम में अनुक्रम की दूसरी और बाद की घटना को प्रतिस्थापित करता है। अवलोकन यह है कि दोहराए गए अनुक्रमों की संख्या किसी अनुक्रम की गैर-यादृच्छिक प्रकृति का अच्छा माप है। एल्गोरिथम डिक्शनरी को एन-एरी ट्री के रूप में प्रस्तुत करता है जहां एन टोकन अनुक्रम बनाने के लिए उपयोग किए जाने वाले टोकन की संख्या है। प्रत्येक डिक्शनरी एंट्री प्रपत्र की है {{code\|1=dictionary[...] = {index, token} }}, जहां इंडेक्स डिक्शनरी एंट्री का इंडेक्स है जो पहले देखे गए अनुक्रम का प्रतिनिधित्व करता है, और टोकन इनपुट से अगला टोकन है जो इस एंट्री को डिक्शनरी में अद्वितीय बनाता है। ध्यान दें कि एल्गोरिथ्म कितना लालची है, और इसलिए तालिका में तब तक कुछ भी नहीं जोड़ा जाता है जब तक कि अद्वितीय निर्माण टोकन नहीं मिल जाता है। एल्गोरिथ्म अंतिम मिलान इंडेक्स = 0 और अगले उपलब्ध इंडेक्स = 1 को प्रारंभ करना है और फिर, इनपुट स्ट्रीम के प्रत्येक टोकन के लिए, डिक्शनरी मैच की सर्च करता है: {{code\|{{mset\|last matching index, token}}}}. यदि कोई मिलान पाया जाता है, तो अंतिम मिलान इंडेक्स को मिलान एंट्री के इंडेक्स पर सेट किया जाता है, कुछ भी आउटपुट नहीं होता है, और अंतिम मिलान इंडेक्स अब तक के इनपुट का प्रतिनिधित्व करने के लिए छोड़ दिया जाता है। इनपुट तब तक संसाधित किया जाता है जब तक कोई मिलान न मिल जाए। फिर नई डिक्शनरी एंट्री बनाई जाती है, {{code\|1=dictionary[next available index] = {last matching index, token} }}, और एल्गोरिथम अंतिम मिलान इंडेक्स को आउटपुट करता है, उसके बाद टोकन देता है, फिर अंतिम मिलान इंडेक्स = 0 को रीसेट करता है और अगले उपलब्ध इंडेक्स को बढ़ाता है। उदाहरण के तौर पर टोकन के अनुक्रम पर विचार करें {{samp\|AABBA}} जो डिक्शनरी को इकट्ठा करेगा;
	{{pre\|		{{pre\|
	0 {0,_}		0 {0,_}
Line 121:		Line 121:
	3 {0,B}		3 {0,B}
	}}		}}
	और कंप्रेस्ड डेटा का आउटपुट अनुक्रम ~~होगा~~ {{samp\|0A1B0B}}. ध्यान दें कि अंतिम A का अभी तक प्रतिनिधित्व नहीं किया गया है क्योंकि एल्गोरिथम यह नहीं जान सकता कि आगे क्या होगा। ~~व्यवहार~~ में EOF मार्कर को इनपुट में जोड़ा जाता है - {{samp\|AABBA$}} ~~उदाहरण के लिए।~~ यह भी ध्यान दें कि इस ~~मामले~~ में आउटपुट {{samp\|0A1B0B1$}} मूल इनपुट से अधिक लंबा है, किन्तु जैसे-जैसे डिक्शनरी बढ़ता है, कम्प्रेशन अनुपात में ~~काफी~~ सुधार होता है, और बाइनरी में इंडेक्स को न्यूनतम संख्या से अधिक बिट्स द्वारा प्रस्तुत करने की आवश्यकता नहीं होती है।<ref>https://math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf {{Bare URL PDF\|date=March 2022}}</ref>		और कंप्रेस्ड डेटा का आउटपुट अनुक्रम{{samp\|0A1B0B}}होगा। ध्यान दें कि अंतिम A का अभी तक प्रतिनिधित्व नहीं किया गया है क्योंकि एल्गोरिथम यह नहीं जान सकता कि आगे क्या होगा। प्रैक्टिस में EOF मार्कर को इनपुट में जोड़ा जाता है - उदाहरण के लिए {{samp\|AABBA$}} है। यह भी ध्यान दें कि इस स्थिति में आउटपुट {{samp\|0A1B0B1$}} मूल इनपुट से अधिक लंबा है, किन्तु जैसे-जैसे डिक्शनरी बढ़ता है, कम्प्रेशन अनुपात में अधिक सुधार होता है, और बाइनरी में इंडेक्स को न्यूनतम संख्या से अधिक बिट्स द्वारा प्रस्तुत करने की आवश्यकता नहीं होती है।<ref>https://math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf {{Bare URL PDF\|date=March 2022}}</ref>
	डीकंप्रेसन में कंप्रेस्ड अनुक्रम से डिक्शनरी का पुनर्निर्माण सम्मिलित है। ~~क्रम से~~ {{samp\|0A1B0B1$}} ~~पहली प्रविष्टि~~ सदैव टर्मिनेटर ~~होती है~~ {{samp\|0 {...} }}, और अनुक्रम से ~~पहला होगा~~ {{samp\|1 {0,A} }}~~. वह~~ {{samp\|A}} आउटपुट में जोड़ा जाता है। इनपुट से दूसरी जोड़ी है {{samp\|1B}} और डिक्शनरी ~~में प्रविष्टि संख्या 2 में परिणाम~~, {{samp\|{{mset\|1,B}}}}. टोकन बी आउटपुट है, जिसके ~~पहले~~ डिक्शनरी ~~प्रविष्टि~~ 1 द्वारा दर्शाया गया अनुक्रम है। ~~प्रविष्टि~~ 1 'ए' है (~~प्रविष्टि~~ 0 के ~~बाद -~~ कुछ भी नहीं) इसलिए {{samp\|AB}} आउटपुट में जोड़ा जाता है। अगला {{samp\|0B}} को डिक्शनरी में ~~अगली प्रविष्टि के रूप में जोड़ा गया है,~~ {{samp\|3 {0,B} }}, और बी (~~पहले~~ कुछ नहीं) को आउटपुट में जोड़ा जाता है। अंत में ~~शब्दकोष प्रविष्टि~~ {{samp\|1$}} ~~बनाया गया~~ है और {{samp\|A$}} ~~परिणामी~~ आउटपुट है {{samp\|A AB B A$}} या {{samp\|AABBA}}रिक्त ~~स्थान~~ और EOF मार्कर को ~~हटाना।~~
			डीकंप्रेसन में कंप्रेस्ड अनुक्रम से डिक्शनरी का पुनर्निर्माण सम्मिलित है। अनुक्रम {{samp\|0A1B0B1$}} फर्स्ट एंट्री सदैव टर्मिनेटर {{samp\|0 {...} }}होती है, और अनुक्रम से फर्स्ट एंट्री {{samp\|1 {0,A} }}होगी।{{samp\|A}} को आउटपुट में जोड़ा जाता है। इनपुट से दूसरी जोड़ी{{samp\|1B}} और इसकी परिणाम डिक्शनरी, {{samp\|{{mset\|1,B}}}}एंट्री नंबर में होता है। टोकन "B" आउटपुट है, जिसके पूर्व डिक्शनरी एंट्री 1 द्वारा दर्शाया गया अनुक्रम है। एंट्री 1 'A' है (एंट्री 0 के पश्चात कुछ भी नहीं है।) इसलिए {{samp\|AB}} आउटपुट में जोड़ा जाता है। अगला {{samp\|0B}} को डिक्शनरी में नेक्स्ट एंट्री {{samp\|3 {0,B} }}के रूप में जोड़ा गया है, और B (पूर्व कुछ नहीं) को आउटपुट में जोड़ा जाता है। अंत में {{samp\|1$}}के लिए डिक्शनरी एंट्री बनाई जाती है और {{samp\|A$}} आउटपुट होता है जिसके परिणामस्वरूप {{samp\|A AB B A$}} या {{samp\|AABBA}}रिक्त स्पेस और EOF मार्कर को रिमूव कर देता है।

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

	[[BTLZ]] LZ78-आधारित एल्गोरिथम है जिसे रियल-टाइम कम्युनिकेशन्स सिस्टम्स (मूल रूप से मॉडेम) में उपयोग के लिए विकसित किया गया था और CCITT/ITU द्वारा V.42bis के रूप में मानकीकृत किया गया था। जब ट्री-स्ट्रक्चर्ड डिक्शनरी फुल हो जाती है, तो यह सुनिश्चित करने के लिए सरल रियूज़/रिकवरी एल्गोरिथम का उपयोग किया जाता है कि डिक्शनरी परिवर्तित डेटा के अनुसार अनुकूलन कंटिन्यू रख सकता है। काउंटर डिक्शनरी के माध्यम से घूमता है। जब नई ~~प्रविष्टि~~ की आवश्यकता होती है, तो काउंटर डिक्शनरी के माध्यम से तब तक स्टेप लेता है जब तक कि लीफ नोड नहीं मिल जाता (कोई आश्रित नोड नहीं)। इसे डिलीट कर दिया गया है और नई एंट्री के लिए स्पेस का रियूज़ किया गया है। LRU या LFU की समानता में इसे इम्प्लीमेंट करना सरल है और एक्विवैलेन्ट परफॉरमेंस प्राप्त होता है।		[[BTLZ]] LZ78-आधारित एल्गोरिथम है जिसे रियल-टाइम कम्युनिकेशन्स सिस्टम्स (मूल रूप से मॉडेम) में उपयोग के लिए विकसित किया गया था और CCITT/ITU द्वारा V.42bis के रूप में मानकीकृत किया गया था। जब ट्री-स्ट्रक्चर्ड डिक्शनरी फुल हो जाती है, तो यह सुनिश्चित करने के लिए सरल रियूज़/रिकवरी एल्गोरिथम का उपयोग किया जाता है कि डिक्शनरी परिवर्तित डेटा के अनुसार अनुकूलन कंटिन्यू रख सकता है। काउंटर डिक्शनरी के माध्यम से घूमता है। जब नई एंट्री की आवश्यकता होती है, तो काउंटर डिक्शनरी के माध्यम से तब तक स्टेप लेता है जब तक कि लीफ नोड नहीं मिल जाता (कोई आश्रित नोड नहीं)। इसे डिलीट कर दिया गया है और नई एंट्री के लिए स्पेस का रियूज़ किया गया है। LRU या LFU की समानता में इसे इम्प्लीमेंट करना सरल है और एक्विवैलेन्ट परफॉरमेंस प्राप्त होता है।

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

alpha>Sangeeta at 08:14, 13 December 2023

2023-12-13T08:14:54Z

← Older revision		Revision as of 13:44, 13 December 2023
Line 114:		Line 114:

	==LZ78==		==LZ78==
	LZ78 एल्गोरिथम इनपुट से टोकन अनुक्रमों का डिक्शनरी बनाकर अनुक्रमिक डेटा को कंप्रेस्ड करता है, और फिर डिक्शनरी प्रविष्टि के संदर्भ के साथ डेटा स्ट्रीम में अनुक्रम की दूसरी और बाद की घटना को प्रतिस्थापित करता है। अवलोकन यह है कि दोहराए गए अनुक्रमों की संख्या किसी अनुक्रम की गैर-यादृच्छिक प्रकृति का अच्छा माप है। एल्गोरिथम डिक्शनरी को एन-एरी ट्री के रूप में प्रस्तुत करता है जहां एन टोकन अनुक्रम बनाने के लिए उपयोग किए जाने वाले टोकन की संख्या है। प्रत्येक डिक्शनरी प्रविष्टि प्रपत्र की है {{code\|1=dictionary[...] = {index, token} }}, जहां ~~सूचकांक~~ डिक्शनरी प्रविष्टि का ~~सूचकांक~~ है जो पहले देखे गए अनुक्रम का प्रतिनिधित्व करता है, और टोकन इनपुट से अगला टोकन है जो इस प्रविष्टि को डिक्शनरी में अद्वितीय बनाता है। ध्यान दें कि एल्गोरिथ्म कितना लालची है, और इसलिए तालिका में तब तक कुछ भी नहीं जोड़ा जाता है जब तक कि अद्वितीय निर्माण टोकन नहीं मिल जाता है। एल्गोरिथ्म अंतिम मिलान ~~सूचकांक~~ = 0 और अगले उपलब्ध ~~सूचकांक~~ = 1 को प्रारंभ करना है और फिर, इनपुट स्ट्रीम के प्रत्येक टोकन के लिए, डिक्शनरी मैच की सर्च करता है: {{code\|{{mset\|last matching index, token}}}}. यदि कोई मिलान पाया जाता है, तो अंतिम मिलान ~~सूचकांक~~ को मिलान प्रविष्टि के ~~सूचकांक~~ पर सेट किया जाता है, कुछ भी आउटपुट नहीं होता है, और अंतिम मिलान ~~सूचकांक~~ अब तक के इनपुट का प्रतिनिधित्व करने के लिए छोड़ दिया जाता है। इनपुट तब तक संसाधित किया जाता है जब तक कोई मिलान न मिल जाए। फिर नई डिक्शनरी प्रविष्टि बनाई जाती है, {{code\|1=dictionary[next available index] = {last matching index, token} }}, और एल्गोरिथम अंतिम मिलान ~~सूचकांक~~ को आउटपुट करता है, उसके बाद टोकन देता है, फिर अंतिम मिलान ~~सूचकांक~~ = 0 को रीसेट करता है और अगले उपलब्ध ~~सूचकांक~~ को बढ़ाता है। उदाहरण के तौर पर टोकन के अनुक्रम पर विचार करें {{samp\|AABBA}} जो डिक्शनरी को इकट्ठा करेगा;		LZ78 एल्गोरिथम इनपुट से टोकन अनुक्रमों का डिक्शनरी बनाकर अनुक्रमिक डेटा को कंप्रेस्ड करता है, और फिर डिक्शनरी प्रविष्टि के संदर्भ के साथ डेटा स्ट्रीम में अनुक्रम की दूसरी और बाद की घटना को प्रतिस्थापित करता है। अवलोकन यह है कि दोहराए गए अनुक्रमों की संख्या किसी अनुक्रम की गैर-यादृच्छिक प्रकृति का अच्छा माप है। एल्गोरिथम डिक्शनरी को एन-एरी ट्री के रूप में प्रस्तुत करता है जहां एन टोकन अनुक्रम बनाने के लिए उपयोग किए जाने वाले टोकन की संख्या है। प्रत्येक डिक्शनरी प्रविष्टि प्रपत्र की है {{code\|1=dictionary[...] = {index, token} }}, जहां इंडेक्स डिक्शनरी प्रविष्टि का इंडेक्स है जो पहले देखे गए अनुक्रम का प्रतिनिधित्व करता है, और टोकन इनपुट से अगला टोकन है जो इस प्रविष्टि को डिक्शनरी में अद्वितीय बनाता है। ध्यान दें कि एल्गोरिथ्म कितना लालची है, और इसलिए तालिका में तब तक कुछ भी नहीं जोड़ा जाता है जब तक कि अद्वितीय निर्माण टोकन नहीं मिल जाता है। एल्गोरिथ्म अंतिम मिलान इंडेक्स = 0 और अगले उपलब्ध इंडेक्स = 1 को प्रारंभ करना है और फिर, इनपुट स्ट्रीम के प्रत्येक टोकन के लिए, डिक्शनरी मैच की सर्च करता है: {{code\|{{mset\|last matching index, token}}}}. यदि कोई मिलान पाया जाता है, तो अंतिम मिलान इंडेक्स को मिलान प्रविष्टि के इंडेक्स पर सेट किया जाता है, कुछ भी आउटपुट नहीं होता है, और अंतिम मिलान इंडेक्स अब तक के इनपुट का प्रतिनिधित्व करने के लिए छोड़ दिया जाता है। इनपुट तब तक संसाधित किया जाता है जब तक कोई मिलान न मिल जाए। फिर नई डिक्शनरी प्रविष्टि बनाई जाती है, {{code\|1=dictionary[next available index] = {last matching index, token} }}, और एल्गोरिथम अंतिम मिलान इंडेक्स को आउटपुट करता है, उसके बाद टोकन देता है, फिर अंतिम मिलान इंडेक्स = 0 को रीसेट करता है और अगले उपलब्ध इंडेक्स को बढ़ाता है। उदाहरण के तौर पर टोकन के अनुक्रम पर विचार करें {{samp\|AABBA}} जो डिक्शनरी को इकट्ठा करेगा;
	{{pre\|		{{pre\|
	0 {0,_}		0 {0,_}
Line 125:		Line 125:

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

	[[BTLZ]] LZ78-आधारित एल्गोरिथम है जिसे ~~वास्तविक समय संचार प्रणालियों~~ (मूल रूप से मॉडेम) में उपयोग के लिए विकसित किया गया था और CCITT/ITU द्वारा V.42bis के रूप में मानकीकृत किया गया था। जब ~~त्रि~~-~~संरचित~~ डिक्शनरी ~~भर जाता~~ है, तो यह सुनिश्चित करने के लिए सरल ~~पुन: उपयोग~~/~~पुनर्प्राप्ति~~ एल्गोरिथम का उपयोग किया जाता है कि डिक्शनरी ~~बदलते~~ डेटा के अनुसार अनुकूलन ~~जारी~~ रख सकता है। काउंटर ~~शब्दकोष~~ के माध्यम से घूमता है। जब नई प्रविष्टि की आवश्यकता होती है, तो काउंटर ~~शब्दकोष~~ के माध्यम से तब तक ~~कदम उठाता~~ है जब तक कि लीफ नोड नहीं मिल जाता (कोई आश्रित नोड नहीं)। इसे ~~हटा~~ दिया गया है और नई ~~प्रविष्टि~~ के लिए ~~स्थान~~ का ~~पुन: उपयोग~~ किया गया है। ~~एलआरयू~~ या ~~एलएफयू~~ की ~~तुलना~~ में इसे ~~लागू~~ करना ~~आसान~~ है और ~~समकक्ष प्रदर्शन~~ प्राप्त होता है।		[[BTLZ]] LZ78-आधारित एल्गोरिथम है जिसे रियल-टाइम कम्युनिकेशन्स सिस्टम्स (मूल रूप से मॉडेम) में उपयोग के लिए विकसित किया गया था और CCITT/ITU द्वारा V.42bis के रूप में मानकीकृत किया गया था। जब ट्री-स्ट्रक्चर्ड डिक्शनरी फुल हो जाती है, तो यह सुनिश्चित करने के लिए सरल रियूज़/रिकवरी एल्गोरिथम का उपयोग किया जाता है कि डिक्शनरी परिवर्तित डेटा के अनुसार अनुकूलन कंटिन्यू रख सकता है। काउंटर डिक्शनरी के माध्यम से घूमता है। जब नई प्रविष्टि की आवश्यकता होती है, तो काउंटर डिक्शनरी के माध्यम से तब तक स्टेप लेता है जब तक कि लीफ नोड नहीं मिल जाता (कोई आश्रित नोड नहीं)। इसे डिलीट कर दिया गया है और नई एंट्री के लिए स्पेस का रियूज़ किया गया है। LRU या LFU की समानता में इसे इम्प्लीमेंट करना सरल है और एक्विवैलेन्ट परफॉरमेंस प्राप्त होता है।

	==यह भी देखें==		==यह भी देखें==
	* लेम्पेल-ज़िव-स्टैक (~~एलजेडएस~~)		* लेम्पेल-ज़िव-स्टैक (LZS)

	==संदर्भ==		==संदर्भ==

alpha>Sangeeta at 07:52, 13 December 2023

2023-12-13T07:52:45Z

Show changes

alpha>Sangeeta at 07:20, 13 December 2023

2023-12-13T07:20:32Z

← Older revision		Revision as of 12:50, 13 December 2023
Line 64:		Line 64:
	यह न केवल स्वीकार्य है यद्यपि प्रायः उपयोगी भी होता है कि लंबाई-दूरी के पेअर को ऐसी लंबाई निर्दिष्ट करने की अनुमति दी जाए जो वास्तव में दूरी से अधिक हो। कॉपी कमांड के रूप में, यह हैरान करने वाला है: चार करैक्टर पीछे जाएं और उस स्थिति से दस करैक्टर वर्तमान स्थिति में कॉपी करें। दस करैक्टर की कॉपी कैसे बनाई जा सकती है जबकि उनमें से केवल चार ही वास्तव में बफ़र में हैं? एक समय में एक बाइट के निवारण पर, इस अनुरोध को पूर्ण करने में कोई समस्या नहीं होती है, क्योंकि जैसे ही बाइट कॉपी की जाती है, इसे कॉपी कमांड में इनपुट के रूप में फिर से फीड किया जा सकता है। जब कॉपी-फ़्रॉम पोजीशन इनिशियल डेस्टिनेशन पोजीशन पर पहुंचती है, तो इसके परिणामस्वरूप उसे वह डेटा फीड किया जाता है जो कॉपी-फ़्रॉम पोजीशन के प्रारम्भ में पेस्ट किया गया था। इस प्रकार यह ऑपरेशन उस कथन के समतुल्य है जो आपको दिया गया डेटा कॉपी करता है और इसे फिट होने तक बार-बार पेस्ट करता है। चूंकि इस प्रकार की जोड़ी डेटा की ही कॉपी को कई बार रिपीट करती है, इसलिए इसका उपयोग [[रन-लेंथ एन्कोडिंग]] के फ्लेक्सिबल और सरल रूप को सम्मिलित करने के लिए किया जा सकता है।		यह न केवल स्वीकार्य है यद्यपि प्रायः उपयोगी भी होता है कि लंबाई-दूरी के पेअर को ऐसी लंबाई निर्दिष्ट करने की अनुमति दी जाए जो वास्तव में दूरी से अधिक हो। कॉपी कमांड के रूप में, यह हैरान करने वाला है: चार करैक्टर पीछे जाएं और उस स्थिति से दस करैक्टर वर्तमान स्थिति में कॉपी करें। दस करैक्टर की कॉपी कैसे बनाई जा सकती है जबकि उनमें से केवल चार ही वास्तव में बफ़र में हैं? एक समय में एक बाइट के निवारण पर, इस अनुरोध को पूर्ण करने में कोई समस्या नहीं होती है, क्योंकि जैसे ही बाइट कॉपी की जाती है, इसे कॉपी कमांड में इनपुट के रूप में फिर से फीड किया जा सकता है। जब कॉपी-फ़्रॉम पोजीशन इनिशियल डेस्टिनेशन पोजीशन पर पहुंचती है, तो इसके परिणामस्वरूप उसे वह डेटा फीड किया जाता है जो कॉपी-फ़्रॉम पोजीशन के प्रारम्भ में पेस्ट किया गया था। इस प्रकार यह ऑपरेशन उस कथन के समतुल्य है जो आपको दिया गया डेटा कॉपी करता है और इसे फिट होने तक बार-बार पेस्ट करता है। चूंकि इस प्रकार की जोड़ी डेटा की ही कॉपी को कई बार रिपीट करती है, इसलिए इसका उपयोग [[रन-लेंथ एन्कोडिंग]] के फ्लेक्सिबल और सरल रूप को सम्मिलित करने के लिए किया जा सकता है।

	~~चीजों~~ को देखने ~~का दूसरा तरीका~~ इस प्रकार है: एन्कोडिंग करते समय, सर्च पॉइंटर को सर्च विंडो के अंत से प्रथम मैच्ड पेअर को सर्च करने के लिए, ऑफसेट D पर फर्स्ट मैच से लेकर सर्च विंडो के अंत तक सभी करैक्टर का मैच होना चाहिए इनपुट, और ये (पूर्व में देखे गए) करैक्टर हैं जिनमें लंबाई ''L''<sub>R</sub> की एकल रन ~~इकाई~~ सम्मिलित है, जो D के समान होनी चाहिए। फिर जैसे ही सर्च पॉइंटर सर्च विंडो से आगे बढ़ता है और आगे बढ़ता है, जहां तक रन पैटर्न इनपुट में रिपीट किया जाता है, रन पैटर्न बाधित होने तक सर्च और इनपुट पॉइंटर्स सिंक में रहेंगे और करैक्टर का मिलान करेंगे। फिर कुल मिलाकर L करैक्टर का मिलान किया गया है, L > D, और कोड [D, L, c] है।		वस्तुओं को देखने की दूसरी स्थिति इस प्रकार है: एन्कोडिंग करते समय, सर्च पॉइंटर को सर्च विंडो के अंत से प्रथम मैच्ड पेअर को सर्च करने के लिए, ऑफसेट D पर फर्स्ट मैच से लेकर सर्च विंडो के अंत तक सभी करैक्टर का मैच होना चाहिए इनपुट, और ये (पूर्व में देखे गए) करैक्टर हैं जिनमें लंबाई ''L''<sub>R</sub> की एकल रन यूनिट सम्मिलित है, जो D के समान होनी चाहिए। फिर जैसे ही सर्च पॉइंटर सर्च विंडो से आगे बढ़ता है और आगे बढ़ता है, जहां तक रन पैटर्न इनपुट में रिपीट किया जाता है, रन पैटर्न बाधित होने तक सर्च और इनपुट पॉइंटर्स सिंक में रहेंगे और करैक्टर का मिलान करेंगे। फिर कुल मिलाकर L करैक्टर का मिलान किया गया है, L > D, और कोड [D, L, c] है।

	[डी, एल, सी] को डिकोड करने पर, फिर से, D= एल<sub>R</sub>. जब प्रथम एल<sub>R</sub> करैक्टर को आउटपुट में पढ़ा जाता है, यह आउटपुट बफ़र से जुड़ी ल रन ~~इकाई~~ से ~~मेल खाता~~ है। इस बिंदु पर, ~~पढ़े गए~~ पॉइंटर को केवल int(L/L~~) वापस करने की आवश्यकता के रूप में सोचा जा सकता है~~<sub>R</sub>) + (1 यदि ~~एल मोडएल~~<sub>R</sub> ≠ 0) ~~उस ल बफ़र्ड रन यूनिट~~ की ~~शुरुआत से पहले~~, ~~एल पढ़ें~~<sub>R</sub> करैक्टर (या ~~शायद~~ अंतिम रिटर्न पर कम), और तब तक दोहराएँ जब तक कि कुल L करैक्टर न पढ़ लिए जाएँ। ~~लेकिन~~ एन्कोडिंग प्रक्रिया को प्रतिबिंबित करते हुए, चूंकि पैटर्न ~~दोहराव वाला~~ है, रीड पॉइंटर को केवल रन लेंथ एल के समान निश्चित दूरी तक राइट पॉइंटर के साथ सिंक करने की आवश्यकता होती ~~है।<sub>R</sub>~~ जब तक L करैक्टर कुल मिलाकर आउटपुट में कॉपी नहीं ~~हो जाते।~~		[D, L, c] को डिकोड करने पर, फिर से, D = L<sub>R</sub> है। जब प्रथम L<sub>R</sub> करैक्टर को आउटपुट में पढ़ा जाता है, यह आउटपुट बफ़र से जुड़ी एकल रन यूनिट से ऍपेन्डेड है। इस बिंदु पर, रीड पॉइंटर को केवल उस एकल बफ़र्ड रन यूनिट के प्रारम्भ में int(L/L<sub>R</sub>) + (1 यदि L mod L<sub>R</sub> ≠ 0) लौटाने की आवश्यकता है, L<sub>R</sub> करैक्टर पढ़ें (या संभवतः अंतिम रिटर्न पर कम), और तब तक दोहराएँ जब तक कि कुल L करैक्टर न पढ़ लिए जाएँ। किन्तु एन्कोडिंग प्रक्रिया को प्रतिबिंबित करते हुए, चूंकि पैटर्न रेपेटेटिव है, रीड पॉइंटर को केवल रन लेंथ L<sub>R</sub> के समान निश्चित दूरी तक राइट पॉइंटर के साथ सिंक करने की आवश्यकता होती है, जब तक कि L करैक्टर को कुल मिलाकर आउटपुट में कॉपी नहीं किया जाता है।

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

	===स्यूडोकोड===		===स्यूडोकोड===
Line 121:		Line 121:
	3 {0,B}		3 {0,B}
	}}		}}
	और संपीड़ित डेटा का आउटपुट अनुक्रम होगा {{samp\|0A1B0B}}. ध्यान दें कि अंतिम A का अभी तक प्रतिनिधित्व नहीं किया गया है क्योंकि एल्गोरिथम यह नहीं जान सकता कि आगे क्या होगा। व्यवहार में EOF मार्कर को इनपुट में जोड़ा जाता है - {{samp\|AABBA$}} उदाहरण के लिए। यह भी ध्यान दें कि इस मामले में आउटपुट {{samp\|0A1B0B1$}} मूल इनपुट से अधिक लंबा है, ~~लेकिन~~ जैसे-जैसे डिक्शनरी बढ़ता है, कम्प्रेशन अनुपात में काफी सुधार होता है, और बाइनरी में इंडेक्स को न्यूनतम संख्या से अधिक बिट्स द्वारा प्रस्तुत करने की आवश्यकता नहीं होती है।<ref>https://math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf {{Bare URL PDF\|date=March 2022}}</ref>		और संपीड़ित डेटा का आउटपुट अनुक्रम होगा {{samp\|0A1B0B}}. ध्यान दें कि अंतिम A का अभी तक प्रतिनिधित्व नहीं किया गया है क्योंकि एल्गोरिथम यह नहीं जान सकता कि आगे क्या होगा। व्यवहार में EOF मार्कर को इनपुट में जोड़ा जाता है - {{samp\|AABBA$}} उदाहरण के लिए। यह भी ध्यान दें कि इस मामले में आउटपुट {{samp\|0A1B0B1$}} मूल इनपुट से अधिक लंबा है, किन्तु जैसे-जैसे डिक्शनरी बढ़ता है, कम्प्रेशन अनुपात में काफी सुधार होता है, और बाइनरी में इंडेक्स को न्यूनतम संख्या से अधिक बिट्स द्वारा प्रस्तुत करने की आवश्यकता नहीं होती है।<ref>https://math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf {{Bare URL PDF\|date=March 2022}}</ref>
	डीकंप्रेसन में संपीड़ित अनुक्रम से डिक्शनरी का पुनर्निर्माण सम्मिलित है। क्रम से {{samp\|0A1B0B1$}} पहली प्रविष्टि सदैव टर्मिनेटर होती है {{samp\|0 {...} }}, और अनुक्रम से पहला होगा {{samp\|1 {0,A} }}. वह {{samp\|A}} आउटपुट में जोड़ा जाता है। इनपुट से दूसरी जोड़ी है {{samp\|1B}} और डिक्शनरी में प्रविष्टि संख्या 2 में परिणाम, {{samp\|{{mset\|1,B}}}}. टोकन बी आउटपुट है, जिसके पहले डिक्शनरी प्रविष्टि 1 द्वारा दर्शाया गया अनुक्रम है। प्रविष्टि 1 'ए' है (प्रविष्टि 0 के बाद - कुछ भी नहीं) इसलिए {{samp\|AB}} आउटपुट में जोड़ा जाता है। अगला {{samp\|0B}} को डिक्शनरी में अगली प्रविष्टि के रूप में जोड़ा गया है, {{samp\|3 {0,B} }}, और बी (पहले कुछ नहीं) को आउटपुट में जोड़ा जाता है। अंत में शब्दकोष प्रविष्टि {{samp\|1$}} बनाया गया है और {{samp\|A$}} परिणामी आउटपुट है {{samp\|A AB B A$}} या {{samp\|AABBA}}रिक्त स्थान और EOF मार्कर को हटाना।		डीकंप्रेसन में संपीड़ित अनुक्रम से डिक्शनरी का पुनर्निर्माण सम्मिलित है। क्रम से {{samp\|0A1B0B1$}} पहली प्रविष्टि सदैव टर्मिनेटर होती है {{samp\|0 {...} }}, और अनुक्रम से पहला होगा {{samp\|1 {0,A} }}. वह {{samp\|A}} आउटपुट में जोड़ा जाता है। इनपुट से दूसरी जोड़ी है {{samp\|1B}} और डिक्शनरी में प्रविष्टि संख्या 2 में परिणाम, {{samp\|{{mset\|1,B}}}}. टोकन बी आउटपुट है, जिसके पहले डिक्शनरी प्रविष्टि 1 द्वारा दर्शाया गया अनुक्रम है। प्रविष्टि 1 'ए' है (प्रविष्टि 0 के बाद - कुछ भी नहीं) इसलिए {{samp\|AB}} आउटपुट में जोड़ा जाता है। अगला {{samp\|0B}} को डिक्शनरी में अगली प्रविष्टि के रूप में जोड़ा गया है, {{samp\|3 {0,B} }}, और बी (पहले कुछ नहीं) को आउटपुट में जोड़ा जाता है। अंत में शब्दकोष प्रविष्टि {{samp\|1$}} बनाया गया है और {{samp\|A$}} परिणामी आउटपुट है {{samp\|A AB B A$}} या {{samp\|AABBA}}रिक्त स्थान और EOF मार्कर को हटाना।

alpha>Sangeeta at 06:59, 13 December 2023

2023-12-13T06:59:27Z

← Older revision		Revision as of 12:29, 13 December 2023
Line 64:		Line 64:
	यह न केवल स्वीकार्य है यद्यपि प्रायः उपयोगी भी होता है कि लंबाई-दूरी के पेअर को ऐसी लंबाई निर्दिष्ट करने की अनुमति दी जाए जो वास्तव में दूरी से अधिक हो। कॉपी कमांड के रूप में, यह हैरान करने वाला है: चार करैक्टर पीछे जाएं और उस स्थिति से दस करैक्टर वर्तमान स्थिति में कॉपी करें। दस करैक्टर की कॉपी कैसे बनाई जा सकती है जबकि उनमें से केवल चार ही वास्तव में बफ़र में हैं? एक समय में एक बाइट के निवारण पर, इस अनुरोध को पूर्ण करने में कोई समस्या नहीं होती है, क्योंकि जैसे ही बाइट कॉपी की जाती है, इसे कॉपी कमांड में इनपुट के रूप में फिर से फीड किया जा सकता है। जब कॉपी-फ़्रॉम पोजीशन इनिशियल डेस्टिनेशन पोजीशन पर पहुंचती है, तो इसके परिणामस्वरूप उसे वह डेटा फीड किया जाता है जो कॉपी-फ़्रॉम पोजीशन के प्रारम्भ में पेस्ट किया गया था। इस प्रकार यह ऑपरेशन उस कथन के समतुल्य है जो आपको दिया गया डेटा कॉपी करता है और इसे फिट होने तक बार-बार पेस्ट करता है। चूंकि इस प्रकार की जोड़ी डेटा की ही कॉपी को कई बार रिपीट करती है, इसलिए इसका उपयोग [[रन-लेंथ एन्कोडिंग]] के फ्लेक्सिबल और सरल रूप को सम्मिलित करने के लिए किया जा सकता है।		यह न केवल स्वीकार्य है यद्यपि प्रायः उपयोगी भी होता है कि लंबाई-दूरी के पेअर को ऐसी लंबाई निर्दिष्ट करने की अनुमति दी जाए जो वास्तव में दूरी से अधिक हो। कॉपी कमांड के रूप में, यह हैरान करने वाला है: चार करैक्टर पीछे जाएं और उस स्थिति से दस करैक्टर वर्तमान स्थिति में कॉपी करें। दस करैक्टर की कॉपी कैसे बनाई जा सकती है जबकि उनमें से केवल चार ही वास्तव में बफ़र में हैं? एक समय में एक बाइट के निवारण पर, इस अनुरोध को पूर्ण करने में कोई समस्या नहीं होती है, क्योंकि जैसे ही बाइट कॉपी की जाती है, इसे कॉपी कमांड में इनपुट के रूप में फिर से फीड किया जा सकता है। जब कॉपी-फ़्रॉम पोजीशन इनिशियल डेस्टिनेशन पोजीशन पर पहुंचती है, तो इसके परिणामस्वरूप उसे वह डेटा फीड किया जाता है जो कॉपी-फ़्रॉम पोजीशन के प्रारम्भ में पेस्ट किया गया था। इस प्रकार यह ऑपरेशन उस कथन के समतुल्य है जो आपको दिया गया डेटा कॉपी करता है और इसे फिट होने तक बार-बार पेस्ट करता है। चूंकि इस प्रकार की जोड़ी डेटा की ही कॉपी को कई बार रिपीट करती है, इसलिए इसका उपयोग [[रन-लेंथ एन्कोडिंग]] के फ्लेक्सिबल और सरल रूप को सम्मिलित करने के लिए किया जा सकता है।

	चीजों को देखने का दूसरा तरीका इस प्रकार है: एन्कोडिंग करते समय, ~~खोज सूचक~~ को ~~खोज~~ विंडो के अंत से ~~पहले मिलान जोड़े~~ को ~~ढूंढना जारी रखने~~ के लिए, ऑफसेट डी पर ~~पहले मिलान~~ से लेकर ~~खोज~~ विंडो के अंत तक सभी करैक्टर का ~~मिलान~~ होना चाहिए इनपुट, और ये (~~पहले~~ देखे गए) करैक्टर हैं जिनमें लंबाई ~~एल की ल रन इकाई सम्मिलित है~~<sub>R</sub>, जो डी के समान ~~होना~~ चाहिए। फिर जैसे ही ~~खोज सूचक खोज~~ विंडो से आगे बढ़ता है और आगे बढ़ता है, जहां तक रन पैटर्न इनपुट में ~~दोहराता~~ है, ~~खोज~~ और इनपुट ~~सूचक~~ सिंक में ~~होंगे~~ और ~~रन पैटर्न बाधित होने तक~~ करैक्टर का मिलान करेंगे। फिर कुल मिलाकर L करैक्टर का मिलान किया गया है, L > D, और कोड है [D, L, c]।		चीजों को देखने का दूसरा तरीका इस प्रकार है: एन्कोडिंग करते समय, सर्च पॉइंटर को सर्च विंडो के अंत से प्रथम मैच्ड पेअर को सर्च करने के लिए, ऑफसेट D पर फर्स्ट मैच से लेकर सर्च विंडो के अंत तक सभी करैक्टर का मैच होना चाहिए इनपुट, और ये (पूर्व में देखे गए) करैक्टर हैं जिनमें लंबाई ''L''<sub>R</sub> की एकल रन इकाई सम्मिलित है, जो D के समान होनी चाहिए। फिर जैसे ही सर्च पॉइंटर सर्च विंडो से आगे बढ़ता है और आगे बढ़ता है, जहां तक रन पैटर्न इनपुट में रिपीट किया जाता है, रन पैटर्न बाधित होने तक सर्च और इनपुट पॉइंटर्स सिंक में रहेंगे और करैक्टर का मिलान करेंगे। फिर कुल मिलाकर L करैक्टर का मिलान किया गया है, L > D, और कोड [D, L, c] है।

	[डी, एल, सी] को डिकोड करने पर, फिर से, डी = एल<sub>R</sub>. जब प्रथम एल<sub>R</sub> करैक्टर को आउटपुट में पढ़ा जाता है, यह आउटपुट बफ़र से जुड़ी ल रन इकाई से मेल खाता है। इस बिंदु पर, पढ़े गए पॉइंटर को केवल int(L/L) वापस करने की आवश्यकता के रूप में सोचा जा सकता है<sub>R</sub>) + (1 यदि एल मोडएल<sub>R</sub> ≠ 0) उस ल बफ़र्ड रन यूनिट की शुरुआत से पहले, एल पढ़ें<sub>R</sub> करैक्टर (या शायद अंतिम रिटर्न पर कम), और तब तक दोहराएँ जब तक कि कुल L करैक्टर न पढ़ लिए जाएँ। लेकिन एन्कोडिंग प्रक्रिया को प्रतिबिंबित करते हुए, चूंकि पैटर्न दोहराव वाला है, रीड पॉइंटर को केवल रन लेंथ एल के समान निश्चित दूरी तक राइट पॉइंटर के साथ सिंक करने की आवश्यकता होती है।<sub>R</sub> जब तक L करैक्टर कुल मिलाकर आउटपुट में कॉपी नहीं हो जाते।		[डी, एल, सी] को डिकोड करने पर, फिर से, D= एल<sub>R</sub>. जब प्रथम एल<sub>R</sub> करैक्टर को आउटपुट में पढ़ा जाता है, यह आउटपुट बफ़र से जुड़ी ल रन इकाई से मेल खाता है। इस बिंदु पर, पढ़े गए पॉइंटर को केवल int(L/L) वापस करने की आवश्यकता के रूप में सोचा जा सकता है<sub>R</sub>) + (1 यदि एल मोडएल<sub>R</sub> ≠ 0) उस ल बफ़र्ड रन यूनिट की शुरुआत से पहले, एल पढ़ें<sub>R</sub> करैक्टर (या शायद अंतिम रिटर्न पर कम), और तब तक दोहराएँ जब तक कि कुल L करैक्टर न पढ़ लिए जाएँ। लेकिन एन्कोडिंग प्रक्रिया को प्रतिबिंबित करते हुए, चूंकि पैटर्न दोहराव वाला है, रीड पॉइंटर को केवल रन लेंथ एल के समान निश्चित दूरी तक राइट पॉइंटर के साथ सिंक करने की आवश्यकता होती है।<sub>R</sub> जब तक L करैक्टर कुल मिलाकर आउटपुट में कॉपी नहीं हो जाते।

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

	===स्यूडोकोड===		===स्यूडोकोड===
Line 114:		Line 114:

	==LZ78==		==LZ78==
	LZ78 एल्गोरिथम इनपुट से टोकन अनुक्रमों का डिक्शनरी बनाकर अनुक्रमिक डेटा को संपीड़ित करता है, और फिर डिक्शनरी प्रविष्टि के संदर्भ के साथ डेटा स्ट्रीम में अनुक्रम की दूसरी और बाद की घटना को प्रतिस्थापित करता है। अवलोकन यह है कि दोहराए गए अनुक्रमों की संख्या किसी अनुक्रम की गैर-यादृच्छिक प्रकृति का अच्छा माप है। एल्गोरिथम डिक्शनरी को एन-एरी ट्री के रूप में प्रस्तुत करता है जहां एन टोकन अनुक्रम बनाने के लिए उपयोग किए जाने वाले टोकन की संख्या है। प्रत्येक डिक्शनरी प्रविष्टि प्रपत्र की है {{code\|1=dictionary[...] = {index, token} }}, जहां सूचकांक डिक्शनरी प्रविष्टि का सूचकांक है जो पहले देखे गए अनुक्रम का प्रतिनिधित्व करता है, और टोकन इनपुट से अगला टोकन है जो इस प्रविष्टि को डिक्शनरी में अद्वितीय बनाता है। ध्यान दें कि एल्गोरिथ्म कितना लालची है, और इसलिए तालिका में तब तक कुछ भी नहीं जोड़ा जाता है जब तक कि अद्वितीय निर्माण टोकन नहीं मिल जाता है। एल्गोरिथ्म अंतिम मिलान सूचकांक = 0 और अगले उपलब्ध सूचकांक = 1 को प्रारंभ करना है और फिर, इनपुट स्ट्रीम के प्रत्येक टोकन के लिए, डिक्शनरी मैच की ~~खोज~~ करता है: {{code\|{{mset\|last matching index, token}}}}. यदि कोई मिलान पाया जाता है, तो अंतिम मिलान सूचकांक को मिलान प्रविष्टि के सूचकांक पर सेट किया जाता है, कुछ भी आउटपुट नहीं होता है, और अंतिम मिलान सूचकांक अब तक के इनपुट का प्रतिनिधित्व करने के लिए छोड़ दिया जाता है। इनपुट तब तक संसाधित किया जाता है जब तक कोई मिलान न मिल जाए। फिर नई डिक्शनरी प्रविष्टि बनाई जाती है, {{code\|1=dictionary[next available index] = {last matching index, token} }}, और एल्गोरिथम अंतिम मिलान सूचकांक को आउटपुट करता है, उसके बाद टोकन देता है, फिर अंतिम मिलान सूचकांक = 0 को रीसेट करता है और अगले उपलब्ध सूचकांक को बढ़ाता है। उदाहरण के तौर पर टोकन के अनुक्रम पर विचार करें {{samp\|AABBA}} जो डिक्शनरी को इकट्ठा करेगा;		LZ78 एल्गोरिथम इनपुट से टोकन अनुक्रमों का डिक्शनरी बनाकर अनुक्रमिक डेटा को संपीड़ित करता है, और फिर डिक्शनरी प्रविष्टि के संदर्भ के साथ डेटा स्ट्रीम में अनुक्रम की दूसरी और बाद की घटना को प्रतिस्थापित करता है। अवलोकन यह है कि दोहराए गए अनुक्रमों की संख्या किसी अनुक्रम की गैर-यादृच्छिक प्रकृति का अच्छा माप है। एल्गोरिथम डिक्शनरी को एन-एरी ट्री के रूप में प्रस्तुत करता है जहां एन टोकन अनुक्रम बनाने के लिए उपयोग किए जाने वाले टोकन की संख्या है। प्रत्येक डिक्शनरी प्रविष्टि प्रपत्र की है {{code\|1=dictionary[...] = {index, token} }}, जहां सूचकांक डिक्शनरी प्रविष्टि का सूचकांक है जो पहले देखे गए अनुक्रम का प्रतिनिधित्व करता है, और टोकन इनपुट से अगला टोकन है जो इस प्रविष्टि को डिक्शनरी में अद्वितीय बनाता है। ध्यान दें कि एल्गोरिथ्म कितना लालची है, और इसलिए तालिका में तब तक कुछ भी नहीं जोड़ा जाता है जब तक कि अद्वितीय निर्माण टोकन नहीं मिल जाता है। एल्गोरिथ्म अंतिम मिलान सूचकांक = 0 और अगले उपलब्ध सूचकांक = 1 को प्रारंभ करना है और फिर, इनपुट स्ट्रीम के प्रत्येक टोकन के लिए, डिक्शनरी मैच की सर्च करता है: {{code\|{{mset\|last matching index, token}}}}. यदि कोई मिलान पाया जाता है, तो अंतिम मिलान सूचकांक को मिलान प्रविष्टि के सूचकांक पर सेट किया जाता है, कुछ भी आउटपुट नहीं होता है, और अंतिम मिलान सूचकांक अब तक के इनपुट का प्रतिनिधित्व करने के लिए छोड़ दिया जाता है। इनपुट तब तक संसाधित किया जाता है जब तक कोई मिलान न मिल जाए। फिर नई डिक्शनरी प्रविष्टि बनाई जाती है, {{code\|1=dictionary[next available index] = {last matching index, token} }}, और एल्गोरिथम अंतिम मिलान सूचकांक को आउटपुट करता है, उसके बाद टोकन देता है, फिर अंतिम मिलान सूचकांक = 0 को रीसेट करता है और अगले उपलब्ध सूचकांक को बढ़ाता है। उदाहरण के तौर पर टोकन के अनुक्रम पर विचार करें {{samp\|AABBA}} जो डिक्शनरी को इकट्ठा करेगा;
	{{pre\|		{{pre\|
	0 {0,_}		0 {0,_}

alpha>Sangeeta at 06:44, 13 December 2023

2023-12-13T06:44:08Z

Show changes

alpha>Sangeeta at 05:11, 13 December 2023

2023-12-13T05:11:36Z

← Older revision		Revision as of 10:41, 13 December 2023
Line 45:		Line 45:

	== सैद्धांतिक दक्षता ==		== सैद्धांतिक दक्षता ==
	इन एल्गोरिथम को ~~पेश~~ करने वाले दो पेपरों में से दूसरे में उनका विश्लेषण ~~परिमित~~-~~राज्य~~ मशीनों द्वारा ~~परिभाषित~~ एनकोडर के रूप में किया गया है। [[सूचना एन्ट्रापी]] के अनुरूप माप ~~व्यक्तिगत अनुक्रमों के लिए विकसित किया गया है~~ (संभाव्य संयोजनों के विपरीत)। यह माप [[डेटा संपीड़न अनुपात\|डेटा कम्प्रेशन ~~अनुपात~~]] पर ~~सीमा~~ देता है जिसे ~~हासिल~~ किया जा सकता है। फिर यह ~~दिखाया~~ गया है कि प्रत्येक ~~अनुक्रम~~ के लिए ~~परिमित दोषरहित~~ एनकोडर ~~मौजूद~~ हैं जो इस ~~सीमा~~ को प्राप्त करते हैं क्योंकि ~~अनुक्रम~~ की ~~लंबाई अनंत~~ तक ~~बढ़ती~~ है। इस अर्थ में इस ~~योजना~~ पर आधारित एल्गोरिथम असममित रूप से ~~इष्टतम~~ एन्कोडिंग उत्पन्न करता है। इस परिणाम को ~~अधिक सीधे तौर पर~~ सिद्ध किया जा सकता है, उदाहरण के लिए [[पीटर शोर]] के नोट्स ~~में।~~<ref>{{cite web		इन एल्गोरिथम को प्रस्तुत करने वाले दो पेपरों में से दूसरे में उनका विश्लेषण फाइनाइट-स्टेट मशीनों द्वारा डिफाइन एनकोडर के रूप में किया गया है। [[सूचना एन्ट्रापी\|इनफार्मेशन एन्ट्रापी]] के अनुरूप माप इंडिविजुअल सीक्वेन्सों (संभाव्य संयोजनों के विपरीत) के लिए विकसित किया गया है। यह माप [[डेटा संपीड़न अनुपात\|डेटा कम्प्रेशन रेश्यो]] पर बाउंड देता है जिसे प्राप्त किया जा सकता है। फिर यह दर्शाया गया है कि प्रत्येक सीक्वेंस के लिए फाइनाइट लॉसलेस एनकोडर उपस्थित हैं जो इस बाउंड को प्राप्त करते हैं क्योंकि सीक्वेंस की लेंथ इंफिनिटी तक जाती है। इस अर्थ में इस स्कीम पर आधारित एल्गोरिथम असममित रूप से ऑप्टीमल एन्कोडिंग उत्पन्न करता है। इस परिणाम को प्रत्यक्ष रूप से सिद्ध किया जा सकता है, उदाहरण के लिए इसे [[पीटर शोर]] के नोट्स में दर्शाया गया है।<ref>{{cite web
	\| url=http://www-math.mit.edu/~shor/PAM/lempel_ziv_notes.pdf		\| url=http://www-math.mit.edu/~shor/PAM/lempel_ziv_notes.pdf
	\| title=Lempel-Ziv notes		\| title=Lempel-Ziv notes
Line 58:		Line 58:

	== LZ77 ==		== LZ77 ==
	LZ77 एल्गोरिथम ~~असम्पीडित~~ डेटा स्ट्रीम में ~~पहले~~ से ~~मौजूद~~ डेटा की ~~प्रति~~ के ~~संदर्भ~~ के साथ डेटा की ~~बार-बार~~ होने वाली ~~घटनाओं~~ को प्रतिस्थापित करके कम्प्रेशन प्राप्त करते हैं। मैच को ~~संख्याओं की जोड़ी~~ द्वारा एन्कोड किया जाता है जिसे ~~लंबाई~~-~~दूरी की जोड़ी~~ कहा जाता है, जो इस ~~कथन~~ के ~~बराबर~~ है कि ~~अगली लंबाई~~ के प्रत्येक ~~अक्षर असम्पीडित~~ स्ट्रीम में उसके पीछे के सटीक दूरी वाले अक्षरों के बराबर हैं। (दूरी को कभी-कभी ऑफसेट भी कहा जाता है।)		LZ77 एल्गोरिथम अनकम्प्रेस्सड डेटा स्ट्रीम में पूर्व से उपस्थित डेटा की कॉपी के रिफरेन्स के साथ डेटा की रिपीट होने वाली ओकरेन्स को प्रतिस्थापित करके कम्प्रेशन प्राप्त करते हैं। मैच को नंबर्स के पेयर द्वारा एन्कोड किया जाता है जिसे लेंथ-डिस्टेंस पेयर कहा जाता है, जो इस स्टेटमेंट के समान है कि नेक्स्ट लेंथ के प्रत्येक कैरेक्टर अनकम्प्रेस्सड स्ट्रीम में उसके पीछे के सटीक दूरी वाले अक्षरों के बराबर हैं। (दूरी को कभी-कभी ऑफसेट भी कहा जाता है।)

	मिलान का पता लगाने के लिए, एनकोडर को नवीनतम डेटा की कुछ मात्रा पर नज़र रखनी होगी, जैसे कि अंतिम 2 [[किलोबाइट]], 4 केबी, या 32 केबी। जिस संरचना में यह डेटा रखा जाता है उसे स्लाइडिंग विंडो कहा जाता है, यही कारण है कि LZ77 को कभी-कभी स्लाइडिंग-विंडो कम्प्रेशन भी कहा जाता है। एनकोडर को मैचों को देखने के लिए इस डेटा को रखने की आवश्यकता होती है, और डिकोडर को एनकोडर द्वारा संदर्भित मैचों की व्याख्या करने के लिए इस डेटा को रखने की आवश्यकता होती है। स्लाइडिंग विंडो जितनी बड़ी होगी, एनकोडर संदर्भ बनाने के लिए उतनी ही देर तक खोज कर सकता है।		मिलान का पता लगाने के लिए, एनकोडर को नवीनतम डेटा की कुछ मात्रा पर नज़र रखनी होगी, जैसे कि अंतिम 2 [[किलोबाइट]], 4 केबी, या 32 केबी। जिस संरचना में यह डेटा रखा जाता है उसे स्लाइडिंग विंडो कहा जाता है, यही कारण है कि LZ77 को कभी-कभी स्लाइडिंग-विंडो कम्प्रेशन भी कहा जाता है। एनकोडर को मैचों को देखने के लिए इस डेटा को रखने की आवश्यकता होती है, और डिकोडर को एनकोडर द्वारा संदर्भित मैचों की व्याख्या करने के लिए इस डेटा को रखने की आवश्यकता होती है। स्लाइडिंग विंडो जितनी बड़ी होगी, एनकोडर संदर्भ बनाने के लिए उतनी ही देर तक खोज कर सकता है।