असंपीड्य स्ट्रिंग

एक असंपीड्य स्ट्रिंग (कंप्यूटर विज्ञान) एक ऐसी कोलमोगोरोव जटिलता वाली स्ट्रिंग है जो इसकी लंबाई के बराबर होती है, जिससे कि इसमें कोई छोटी एनकोडिंग न हो।

उदाहरण

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