असंपीड्य स्ट्रिंग: Difference between revisions
No edit summary |
No edit summary |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 25: | Line 25: | ||
<references/> | <references/> | ||
{{DEFAULTSORT:Incompressible String}} | {{DEFAULTSORT:Incompressible String}} | ||
[[Category:Created On 26/07/2023|Incompressible String]] | |||
[[Category:Lua-based templates|Incompressible String]] | |||
[[Category: Machine Translated Page]] | [[Category:Machine Translated Page|Incompressible String]] | ||
[[Category: | [[Category:Pages with script errors|Incompressible String]] | ||
[[Category:Short description with empty Wikidata description|Incompressible String]] | |||
[[Category:Templates Vigyan Ready|Incompressible String]] | |||
[[Category:Templates that add a tracking category|Incompressible String]] | |||
[[Category:Templates that generate short descriptions|Incompressible String]] | |||
[[Category:Templates using TemplateData|Incompressible String]] | |||
[[Category:दोषरहित संपीड़न एल्गोरिदम|Incompressible String]] | |||
[[Category:स्ट्रिंग (कंप्यूटर विज्ञान)|Incompressible String]] | |||
Latest revision as of 15:30, 10 August 2023
एक असंपीड्य स्ट्रिंग (कंप्यूटर विज्ञान) एक ऐसी कोलमोगोरोव जटिलता वाली स्ट्रिंग है जो इसकी लंबाई के बराबर होती है, जिससे कि इसमें कोई छोटी एनकोडिंग न हो।[1]
उदाहरण
इस प्रकार से मान लीजिए हमारे निकट स्ट्रिंग 12349999123499991234है, और हम एक संपीड़न विधि का उपयोग कर रहे हैं जो स्ट्रिंग में एक विशेष वर्ण डालकर काम करती है (मान लीजिए @) जिसके बाद एक मान होता है जो दोहराए गए मानों की लुकअप तालिका (या शब्दकोश) में एक प्रविष्टि को इंगित करता है। आइए कल्पना करें कि हमारे निकट एल्गोरिदम है जो 4 वर्ण खंडों में स्ट्रिंग की जांच करता है। अतः हमारी स्ट्रिंग को देखते हुए, हमारा एल्गोरिदम अपने शब्दकोश में रखने के लिए मान 1234 और 9999 चुन सकता है। मान लीजिए कि 1234 प्रविष्टि 0 है और 9999 प्रविष्टि 1 है। इस प्रकार से अब स्ट्रिंग बन सकती है:
@0@1@0@1@0
यह स्ट्रिंग बहुत छोटी है, यद्यपि शब्दकोश को संग्रहीत करने पर कुछ स्थान में व्यय होगी। यद्यपि, स्ट्रिंग में जितनी अधिक पुनरावृत्तियाँ होंगी, संपीड़न उतना ही ठीक होगा।
यद्यपि, हमारा एल्गोरिदम ठीक कर सकता है, यदि वह स्ट्रिंग को 4 अक्षरों से बड़े भागों में देख सके। अतः इस प्रकार से फिर यह 12349999 और 1234 को शब्दकोश में डाल सकता है, जिससे हमें यह मिलता है:
@0@0@1
इस प्रकार से यह स्ट्रिंग और भी छोटी है. अब और स्ट्रिंग पर विचार करें:
1234999988884321
अतः यह स्ट्रिंग हमारे एल्गोरिदम द्वारा असम्पीडित है। मात्र 88 और 99 ही दोहराए जाते हैं। इस प्रकार से यदि हम 88 और 99 को अपने शब्दकोश में संग्रहीत करें, तो हम उत्पादन करेंगे:
1234@1@1@0@04321
यह मूल स्ट्रिंग जितनी ही लंबी है, क्योंकि शब्दकोश में आइटमों के लिए हमारे प्लेसहोल्डर 2 अक्षर लंबे हैं, और जिन आइटमों को वे प्रतिस्थापित करते हैं उनकी लंबाई समान है। अतः इसलिए, यह स्ट्रिंग हमारे एल्गोरिदम द्वारा असम्पीडित है।
संदर्भ
- ↑ V. Chandru and M.R.Rao, Algorithms and Theory of Computation Handbook, CRC Press 1999, p29-30.
