असंपीड्य स्ट्रिंग: Difference between revisions
(Created page with "{{Short description|Concept in computing}} {{Refimprove|date=July 2019}} एक असंपीड्य स्ट्रिंग (कंप्यूटर विज्ञ...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Concept in computing}} | {{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>12349999123499991234</code>, और हम डेटा संपीड़न विधि का उपयोग कर रहे हैं जो स्ट्रिंग में विशेष वर्ण डालकर काम करती है (मान लीजिए)। <code>@</code>) के बाद मान आता है जो दोहराए गए मानों की लुकअप तालिका (या शब्दकोश) में प्रविष्टि की ओर इशारा करता है। आइए कल्पना करें कि हमारे पास एल्गोरिदम है जो 4 वर्ण खंडों में स्ट्रिंग की जांच करता है। हमारी स्ट्रिंग को देखते हुए, हमारा एल्गोरिदम अपने शब्दकोश में रखने के लिए मान 1234 और 9999 चुन सकता है। मान लीजिए कि 1234 प्रविष्टि 0 है और 9999 प्रविष्टि 1 है। अब स्ट्रिंग बन सकती है: | ||
@0@1@0@1@0 | @0@1@0@1@0 | ||
| Line 17: | Line 12: | ||
@0@0@1 | @0@0@1 | ||
यह डोरी और भी छोटी है. अब | यह डोरी और भी छोटी है. अब और स्ट्रिंग पर विचार करें: | ||
1234999988884321 | 1234999988884321 | ||
Revision as of 20:05, 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 अक्षर लंबे हैं, और जिन आइटमों को वे प्रतिस्थापित करते हैं उनकी लंबाई समान है। इसलिए, यह स्ट्रिंग हमारे एल्गोरिदम द्वारा असम्पीडित है।
संदर्भ
- ↑ V. Chandru and M.R.Rao, Algorithms and Theory of Computation Handbook, CRC Press 1999, p29-30.
