एंट्रोपी और विनरार - विस्तृत जवाब

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

मैं एक साधारण से शुरू करूँगा - चित्र "विभिन्न डेटा के संपीड़न की डिग्री।" यहाँ यह है:



आश्चर्यजनक रूप से, संख्याओं का एक यादृच्छिक अनुक्रम मूल मात्रा के 60% तक कहीं सिकुड़ता है। मुझे याद है कि अपनी युवावस्था में मैंने jpg में संकुचित वीडियो और तस्वीरों को जिप करने की कोशिश की थी। अभिलेखागार मूल के रूप में लगभग एक ही मात्रा में प्राप्त किए गए थे, और कभी-कभी कुछ प्रतिशत अधिक! दुर्भाग्य से, लेख के लेखक ने विस्तार से वर्णन नहीं किया कि उसे अपना परिणाम कैसे मिला। यादृच्छिक संख्याओं के इसके अनुक्रम का संपीड़न अनुपात संदिग्ध रूप से 10/16 = 0.625 के अनुपात के समान है।

मैंने अपने दम पर प्रयोग को फिर से शुरू करने की कोशिश की। मैंने यादृच्छिक वर्णों के साथ एक फ़ाइल बनाई, और फिर उसे उसी हैडर के साथ शीर्षक में उल्लिखित किया। परिणाम यह है:

फ़ाइल का आकार	पुरालेख का आकार
1,000,000 बाइट्स	1 002 674 बाइट्स
100,000 बाइट्स	100 414 बाइट्स
10,000 बाइट्स	10 119 बाइट्स

जैसा कि आप देख सकते हैं, डेटा के बेतरतीब ढंग से उत्पन्न अनुक्रम के साथ, संग्रह का आकार मूल फ़ाइल के आकार से बड़ा है, जैसा कि आप उम्मीद करेंगे।

मजेदार अवलोकन: फ़ाइल बनाने के लिए मैंने जावा में एक छोटा कार्यक्रम लिखा। वास्तविक पीढ़ी को टीम द्वारा किया गया था

dataOutputStream.writeChar((int) (Math.random() * 65536));


मुझे समझाने दो: यूनिकोड जावा में समर्थित है, इसलिए चार प्रकार के बाइट्स लगते हैं। यही है, यह 0 से 65535 तक की संख्या है। Math.random () 0 से 1 तक की संख्या देता है, गुणांक से गुणा करने पर हमें एक यादृच्छिक चरित्र मिलता है, जो कि समान संभावना के साथ कोई भी उपलब्ध चरित्र हो सकता है।

मजेदार अवलोकन: पहले कार्यक्रम में 65536 के बजाय एक त्रुटि के साथ लिखा गया था, यह 16536 था। परिणामस्वरूप, यादृच्छिक वर्णों वाली फ़ाइल को मूल के 95% तक संकुचित किया गया था। सिद्धांत रूप में, यह अपेक्षित परिणाम भी है। हम इसे सूत्र द्वारा जाँचते हैं।
मैं मूल लेख में दिए गए सूत्र का उपयोग करूंगा:



हम मानते हैं कि हमारी फ़ाइल के वर्ण स्वतंत्र रूप से दिखाई देते हैं। प्रत्येक स्थिति में 16536 विभिन्न प्रतीक संभव हैं, प्रत्येक परिणाम की संभावना समान और समान है। तो राशि की गणना इस प्रकार है:

एच = - (1/16536 * लॉग (1/16536)) * 16536 = 14

इसके बाद, आधार 2 पर लघुगणक लिया जाता है।

हालाँकि, संग्रहकर्ता आपको प्रत्येक 2 बाइट्स के लिए सभी 65536 मानों का उपयोग करने की अनुमति देता है। आर्काइव प्रतीक के लिए एंट्रॉपी है

H = - (1/65536 * लॉग (1/65536)) * 65536 = 16

14/16 = 0.875 में एंट्रोपियों का अनुपात - संग्रह के परिणामस्वरूप प्राप्त 0.95 से थोड़ा कम - भी काफी स्वाभाविक परिणाम है।

मुझे संदेह है कि मूल लेख के लेखक ने दशमलव में संख्याएं उत्पन्न कीं, और संपीड़न के बाद, इन संख्याओं को हेक्साडेसिमल में एन्कोड किया गया था। यह अभिलेखागार को उस अनुपात में डेटा को संपीड़ित करने की अनुमति देता है जो 10/16 तक जाता है।

दूसरा बिंदु जिस पर मैं टिप्पणी करना चाहूंगा। जैसा कि आपने देखा है, एन्ट्रापी फार्मूले में एक मात्रा है जैसे कि एक या दूसरे मूल्य को प्राप्त करने की संभावना। यह मुझे लगता है कि इस संभावना के साथ, सब कुछ इतना स्पष्ट नहीं है, और यह एक अलग बड़े लेख के योग्य है। मैंने सबसे सरल मामले पर विचार किया जब हमारे संदेश के सभी पात्र एक-दूसरे से स्वतंत्र होते हैं, प्रत्येक मान अनियमित रूप से प्रकट होता है। इस मामले में, सब कुछ सरल है: हम प्रत्येक मूल्य की उपस्थिति की संभावना के बारे में बात कर सकते हैं। यदि फ़ाइल उत्पन्न होती है, तो हम इस संभावना को निर्धारित कर सकते हैं। यदि फ़ाइल बाहर से आती है - हम प्रत्येक वर्ण की घटना की आवृत्ति को माप सकते हैं और, पर्याप्त रूप से लंबे संदेश के साथ, यह संभावना की ओर बढ़ेगा।

हालांकि, वास्तव में, सब कुछ इतना सरल नहीं है। उदाहरण के लिए, मानव भाषा में जुड़े वाक्यों का पाठ लें। यदि हम इसे स्वतंत्र पत्रों की एक धारा के रूप में मानते हैं, तो आप देख सकते हैं कि अक्षरों में अलग-अलग आवृत्तियाँ हैं, वे संभावना से मेल खा सकते हैं और एक निश्चित डिग्री संपीड़न प्राप्त कर सकते हैं। हालांकि, प्राकृतिक भाषा में, कुछ जोड़े और पत्रों के ट्रिपल लगभग कभी नहीं पाए जाते हैं - यह काम के लिए आधार है, उदाहरण के लिए, प्रसिद्ध पुंटोस्विच द्वारा। यानी वर्तमान पत्र दिखने की संभावना इस बात पर निर्भर करती है कि इसके पहले क्या आया था। यह अनिश्चितता को कम करता है और अधिक से अधिक संपीड़न को प्राप्त करता है। आप आगे बढ़ सकते हैं: पाठ में शब्द शामिल हैं। पाठ के लेखक की शब्दावली संभवतः 4096 शब्दों से अधिक नहीं है, जो प्रति शब्द 12 बिट देगा। यहां आपको लगभग 8 मामलों या संयुग्मों के लिए 3 बिट्स जोड़ने की आवश्यकता है - कुल 15 बिट्स। रूसी भाषा के मध्य शब्द में 6 अक्षर हैं - यह ASCII में 48 बिट्स या यूनिकोड में 96 बिट्स है। वैसे, कुछ शब्द दूसरों की तुलना में अधिक सामान्य होते हैं, मामलों के साथ समान - जिसका अर्थ है कि प्रति शब्द बिट्स की औसत संख्या और भी कम होगी (दुर्लभ शब्दों को बिट्स के एक लंबे अनुक्रम के साथ एन्कोड किया जा सकता है, और एक छोटे से लगातार वाले)।

लेकिन यह सब नहीं है। हम वाक्यों के स्तर पर जा सकते हैं - इससे यह अनुमान लगाना संभव हो जाएगा कि कौन सा शब्द सबसे अधिक पिछले वाले का अनुसरण करेगा, और, इस प्रकार, संदेश में प्रवेश को कम कर सकता है।

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

[संख्या पाई के वर्णों की गणना के लिए सूत्र] [वर्णों की संख्या]

जैसा कि आप देख सकते हैं, इस रिकॉर्ड की लंबाई मूल अनुक्रम की लंबाई के संबंध में बड़े पैमाने पर बढ़ेगी (999 वर्णों के लिए आपको सूत्र + 3 दशमलव अंक लिखने की आवश्यकता है, और 9999 वर्णों को एन्कोडिंग करने के लिए यह 1 दशमलव अंक अधिक है, "9999" लिखने के लिए एक अतिरिक्त वर्ण आवश्यक है)। संपीड़न अनुपात प्राप्त करने के लिए मूल अनुक्रम की लंबाई से "संग्रह" की लंबाई को विभाजित करें और प्रति वर्ण एन्ट्रापी का अनुमान लगाएं। यह अनुपात प्रारंभिक अनुक्रम की बढ़ती लंबाई के साथ शून्य हो जाएगा, क्योंकि यह गैर-आयामी प्रारंभिक डेटा के लिए होना चाहिए। हां, इस तरह के संग्रह को अनपैक करने के लिए कुछ कंप्यूटिंग संसाधनों की आवश्यकता होगी, लेकिन साधारण अभिलेखागार स्वयं द्वारा भी अनपैक नहीं किए जाते हैं।

उपरोक्त सभी एन्ट्रापी की गणना के फार्मूले का खंडन नहीं करते हैं, लेकिन केवल यह दर्शाते हैं कि अक्षर p के पीछे क्या तरकीबें छिपाई जा सकती हैं, जो संभाव्यता को इंगित करती हैं।