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

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

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

यसको मतलब यो नम्बर पदनाम अनुरूप हुनेछ "सबैभन्दा सानो संख्या जसको लागि अस्सी अक्षरहरू पर्याप्त छैनन्", जसमा मात्र ७८ अक्षरहरू छन्! एकातिर, यो संख्या अवस्थित हुनुपर्छ; अर्कोतर्फ, यदि यो संख्या अवस्थित छ भने, यसको पदनाम यो संग मेल खाँदैन। विरोधाभास!

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

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

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

हामी पहिलेको जस्तै तरिकामा तर्क गर्नेछौं: त्यहाँ 2561024 किलोबाइट पाठहरू छन्, जसको मतलब 2561024 भन्दा बढी संख्याहरू किलोबाइट प्रोग्रामहरूद्वारा आउटपुट हुन सक्दैन। यसको मतलब 2561024 भन्दा ठूलो कुनै निश्चित संख्या यस तरिकाले प्राप्त गर्न सकिँदैन।

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

अब के छ पकड? यसलाई अब नोटेशनको अनौपचारिकतालाई श्रेय दिन सकिँदैन!

यदि तपाइँ यस तथ्यबाट भ्रमित हुनुहुन्छ कि हाम्रो कार्यक्रमलाई काम गर्नको लागि मेमोरीको एक खगोलीय मात्रा चाहिन्छ - 2561024 तत्वहरूको शब्दकोश (वा बिट एरे) - तब तपाइँ यसलाई बिना पनि उही कुरा गर्न सक्नुहुन्छ: प्रत्येक 2561024 नम्बरहरूको लागि, बदलामा। , सबै 2561024 सम्भावित कार्यक्रमहरू मार्फत जानुहोस्, त्यहाँ कुनै उपयुक्त नभएसम्म। यसले फरक पार्दैन कि यस्तो खोज धेरै लामो समय सम्म रहन्छ: नम्बर र कार्यक्रमबाट (2561024) 2 जोडीहरू भन्दा कम जाँच गरेपछि, यो समाप्त हुनेछ र त्यो धेरै प्यारो नम्बर फेला पार्नेछ।

वा यो समाप्त हुँदैन? वास्तवमा, प्रयास गरिने सबै कार्यक्रमहरू मध्ये, त्यहाँ हुनेछ while True: pass (र यसको कार्यात्मक analogues) - र मामला यस्तो कार्यक्रम परीक्षण भन्दा अगाडि जानेछैन!

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

स्रोत: www.habr.com