असंपीड्य स्ट्रिंग: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Short description|Concept in computing}}एक असंपीड्य [[स्ट्रिंग (कंप्यूटर विज्ञान)]] [[कोलमोगोरोव जटिलता]] वाली स्ट्रिंग है जो इसकी लंबाई के बराबर होती है, ताकि इसमें कोई छोटी एनकोडिंग न हो।<ref>V. Chandru and  M.R.Rao, '' Algorithms and Theory of Computation Handbook'', CRC Press 1999, p29-30.</ref>
{{Short description|Concept in computing}}एक '''असंपीड्य [[स्ट्रिंग (कंप्यूटर विज्ञान)|स्ट्रिंग]]''' [[स्ट्रिंग (कंप्यूटर विज्ञान)|(कंप्यूटर विज्ञान)]] एक ऐसी [[कोलमोगोरोव जटिलता]] वाली स्ट्रिंग है जो इसकी लंबाई के बराबर होती है, ताकि इसमें कोई छोटी एनकोडिंग न हो।<ref>V. Chandru and  M.R.Rao, '' Algorithms and Theory of Computation Handbook'', CRC Press 1999, p29-30.</ref>
==उदाहरण==
==उदाहरण==


मान लीजिए हमारे पास स्ट्रिंग है <code>12349999123499991234</code>, और हम डेटा संपीड़न विधि का उपयोग कर रहे हैं जो स्ट्रिंग में विशेष वर्ण डालकर काम करती है (मान लीजिए)। <code>@</code>) के बाद मान आता है जो दोहराए गए मानों की लुकअप तालिका (या शब्दकोश) में प्रविष्टि की ओर इशारा करता है। आइए कल्पना करें कि हमारे पास एल्गोरिदम है जो 4 वर्ण खंडों में स्ट्रिंग की जांच करता है। हमारी स्ट्रिंग को देखते हुए, हमारा एल्गोरिदम अपने शब्दकोश में रखने के लिए मान 1234 और 9999 चुन सकता है। मान लीजिए कि 1234 प्रविष्टि 0 है और 9999 प्रविष्टि 1 है। अब स्ट्रिंग बन सकती है:
मान लीजिए हमारे निकट स्ट्रिंग <code>12349999123499991234</code>है, और हम एक संपीड़न विधि का उपयोग कर रहे हैं जो स्ट्रिंग में एक विशेष वर्ण डालकर काम करती है (मान लीजिए <code>@</code>) जिसके बाद एक मान होता है जो दोहराए गए मानों की लुकअप तालिका (या शब्दकोश) में एक प्रविष्टि को इंगित करता है। आइए कल्पना करें कि हमारे निकट एल्गोरिदम है जो 4 वर्ण खंडों में स्ट्रिंग की जांच करता है। हमारी स्ट्रिंग को देखते हुए, हमारा एल्गोरिदम अपने शब्दकोश में रखने के लिए मान 1234 और 9999 चुन सकता है। मान लीजिए कि 1234 प्रविष्टि 0 है और 9999 प्रविष्टि 1 है। अब स्ट्रिंग बन सकती है:


   @0@1@0@1@0
   @0@1@0@1@0


यह स्ट्रिंग बहुत छोटी है, हालाँकि शब्दकोश को संग्रहीत करने में कुछ जगह खर्च होगी। हालाँकि, स्ट्रिंग में जितनी अधिक पुनरावृत्तियाँ होंगी, संपीड़न उतना ही बेहतर होगा।
यह स्ट्रिंग बहुत छोटी है, यद्यपि शब्दकोश को संग्रहीत करने पर कुछ स्थान में व्यय होगी। यद्यपि, स्ट्रिंग में जितनी अधिक पुनरावृत्तियाँ होंगी, संपीड़न उतना ही ठीक होगा।


हालाँकि, हमारा एल्गोरिदम बेहतर कर सकता है, अगर वह स्ट्रिंग को 4 अक्षरों से बड़े टुकड़ों में देख सके। फिर यह 12349999 और 1234 को शब्दकोश में डाल सकता है, जिससे हमें यह मिलता है:
यद्यपि, हमारा एल्गोरिदम ठीक कर सकता है, यदि वह स्ट्रिंग को 4 अक्षरों से बड़े भागों में देख सके। फिर यह 12349999 और 1234 को शब्दकोश में डाल सकता है, जिससे हमें यह मिलता है:


   @0@0@1
   @0@0@1


यह डोरी और भी छोटी है. अब और स्ट्रिंग पर विचार करें:
यह स्ट्रिंग और भी छोटी है. अब और स्ट्रिंग पर विचार करें:


   1234999988884321
   1234999988884321


यह स्ट्रिंग हमारे एल्गोरिदम द्वारा असम्पीडित है। केवल 88 और 99 ही दोहराए जाते हैं। यदि हम 88 और 99 को अपने शब्दकोश में संग्रहीत करें, तो हम उत्पादन करेंगे:
यह स्ट्रिंग हमारे एल्गोरिदम द्वारा असम्पीडित है। मात्र 88 और 99 ही दोहराए जाते हैं। यदि हम 88 और 99 को अपने शब्दकोश में संग्रहीत करें, तो हम उत्पादन करेंगे:


   1234@1@1@0@04321
   1234@1@1@0@04321

Revision as of 20:40, 1 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 अक्षर लंबे हैं, और जिन आइटमों को वे प्रतिस्थापित करते हैं उनकी लंबाई समान है। इसलिए, यह स्ट्रिंग हमारे एल्गोरिदम द्वारा असम्पीडित है।

संदर्भ

  1. V. Chandru and M.R.Rao, Algorithms and Theory of Computation Handbook, CRC Press 1999, p29-30.