डेटा संपीड़न के बारे में विरोधाभास

डेटा संपीड़न की समस्या, अपने सरलतम रूप में, संख्याओं और उनके अंकन से संबंधित हो सकती है। संख्याओं को अंकों द्वारा दर्शाया जा सकता है ("ग्यारह" संख्या 11 के लिए), गणितीय अभिव्यक्ति ("बीसवीं में दो" 1048576 के लिए), स्ट्रिंग एक्सप्रेशन ("पांच नौ" 99999 के लिए), उचित नाम ("जानवर की संख्या" 666 के लिए, "ट्यूरिंग की मृत्यु का वर्ष" 1954 के लिए), या उसके मनमाने संयोजन। कोई भी पदनाम उपयुक्त है जिसके द्वारा वार्ताकार स्पष्ट रूप से यह निर्धारित कर सके कि हम किस संख्या के बारे में बात कर रहे हैं। जाहिर है, अपने वार्ताकार को बताएं "आठ का भाज्य" समतुल्य अंकन से अधिक कुशल "चालीस हजार तीन सौ बीस". यहां एक तार्किक प्रश्न उठता है: किसी दी गई संख्या के लिए सबसे छोटा अंकन क्या है?

दार्शनिक बर्ट्रेंड रसेल ने 1908 में प्रकाशित किया "बेरी का विरोधाभास", जो विपरीत दिशा से संख्या अंकन के मुद्दे को छूता है: वह सबसे छोटी संख्या कौन सी है जिसमें अस्सी अक्षरों की आवश्यकता नहीं है?
ऐसी संख्या मौजूद होनी चाहिए: अस्सी रूसी अक्षरों और रिक्त स्थानों से आप केवल 3480 पदनाम बना सकते हैं, जिसका अर्थ है कि अस्सी अक्षरों का उपयोग करके आप 3480 से अधिक संख्याएँ निर्दिष्ट नहीं कर सकते हैं। इसका मतलब यह है कि इस तरह से 3480 से अधिक किसी निश्चित संख्या को निर्दिष्ट करना असंभव है।

इसका मतलब यह है कि यह संख्या पदनाम के अनुरूप होगी "वह सबसे छोटी संख्या जिसके लिए अस्सी अक्षर पर्याप्त नहीं हैं", जिसमें केवल 78 अक्षर हैं! एक ओर, यह संख्या मौजूद होनी चाहिए; दूसरी ओर, यदि यह संख्या मौजूद है, तो इसका पदनाम इसके अनुरूप नहीं है। विरोधाभास!

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

क्या संख्याओं पर क्रियाओं के अनुक्रम (एल्गोरिदम) का वर्णन करने के कोई औपचारिक तरीके हैं? हैं, और बहुतायत में - उन्हें प्रोग्रामिंग भाषाएं कहा जाता है। मौखिक नोटेशन के बजाय, हम प्रोग्राम का उपयोग करेंगे (उदाहरण के लिए, पायथन में) जो आवश्यक संख्याएँ प्रदर्शित करते हैं। उदाहरण के लिए, पाँच नौ के लिए कार्यक्रम उपयुक्त है print("9"*5). किसी दिए गए नंबर के लिए सबसे छोटे कार्यक्रम में हमारी रुचि बनी रहेगी। ऐसे प्रोग्राम की लंबाई कहलाती है कोलमोगोरोव जटिलता संख्याएँ; यह वह सैद्धांतिक सीमा है जिस तक किसी दी गई संख्या को संपीड़ित किया जा सकता है।

बेरी के विरोधाभास के बजाय, अब हम एक समान विरोधाभास पर विचार कर सकते हैं: वह कौन सी सबसे छोटी संख्या है जिसे आउटपुट करने के लिए एक किलोबाइट प्रोग्राम पर्याप्त नहीं है?

हम पहले की तरह ही तर्क देंगे: 2561024 किलोबाइट टेक्स्ट हैं, जिसका अर्थ है कि किलोबाइट प्रोग्राम द्वारा 2561024 से अधिक संख्याएँ आउटपुट नहीं की जा सकती हैं। इसका मतलब यह है कि 2561024 से अधिक की एक निश्चित संख्या इस तरह से प्राप्त नहीं की जा सकती है।

लेकिन आइए पायथन में एक प्रोग्राम लिखें जो सभी संभावित किलोबाइट टेक्स्ट उत्पन्न करता है, उन्हें निष्पादन के लिए चलाता है, और यदि वे एक संख्या आउटपुट करते हैं, तो इस संख्या को पहुंच योग्य लोगों के शब्दकोश में जोड़ता है। सभी 2561024 संभावनाओं की जाँच करने के बाद, चाहे इसमें कितना भी समय लगे, प्रोग्राम शब्दकोश से गायब सबसे छोटी संख्या की तलाश करता है और उस संख्या को प्रिंट करता है। यह स्पष्ट प्रतीत होता है कि ऐसा प्रोग्राम एक किलोबाइट कोड में फिट होगा - और वही संख्या आउटपुट करेगा जो एक किलोबाइट प्रोग्राम द्वारा आउटपुट नहीं किया जा सकता है!

अब क्या दिक्कत है? इसे अब अंकन की अनौपचारिकता के लिए जिम्मेदार नहीं ठहराया जा सकता है!

यदि आप इस तथ्य से भ्रमित हैं कि हमारे प्रोग्राम को काम करने के लिए बड़ी मात्रा में मेमोरी की आवश्यकता होगी - 2561024 तत्वों का एक शब्दकोश (या बिट सरणी) - तो आप इसके बिना भी वही काम कर सकते हैं: 2561024 संख्याओं में से प्रत्येक के लिए, बदले में , सभी 2561024 संभावित कार्यक्रमों से गुजरें, जब तक कि कोई उपयुक्त कार्यक्रम न हो। इससे कोई फर्क नहीं पड़ता कि ऐसी खोज बहुत लंबे समय तक चलेगी: संख्या और कार्यक्रम से (2561024)2 से कम जोड़े की जांच करने के बाद, यह समाप्त हो जाएगी और वह बहुत ही पोषित संख्या मिल जाएगी।

या ख़त्म नहीं होगा? दरअसल, जिन सभी कार्यक्रमों को आजमाया जाएगा, उनमें से एक होगा while True: pass (और इसके कार्यात्मक एनालॉग्स) - और मामला ऐसे कार्यक्रम के परीक्षण से आगे नहीं बढ़ेगा!

बेरी के विरोधाभास के विपरीत, जहां समस्या अंकन की अनौपचारिकता में थी, दूसरे मामले में हमारे पास एक अच्छी तरह से प्रच्छन्न सुधार है "समस्याओं को रोकना". तथ्य यह है कि किसी प्रोग्राम से एक सीमित समय में उसका आउटपुट निर्धारित करना असंभव है। विशेष रूप से, कोलमोगोरोव जटिलता बेशुमार: ऐसा कोई एल्गोरिदम नहीं है जो किसी दिए गए नंबर के लिए, इस नंबर को प्रिंट करने वाले सबसे छोटे प्रोग्राम की लंबाई ज्ञात करने की अनुमति दे; जिसका अर्थ है कि बेरी की समस्या का कोई समाधान नहीं है - किसी दी गई संख्या के लिए सबसे छोटे मौखिक पदनाम की लंबाई ज्ञात करना।

स्रोत: www.habr.com