दबाव उदाहरण

Question

मेरी एल्गोरिदम पाठ्यपुस्तक से:

वार्षिक काउंटी घुड़दौड़ तीन thoroughbreds जो एक दूसरे के विरुद्ध कभी नहीं हिस्सा लिया है में ला रही है। उत्साहित, आप अपने पिछले 200 दौड़ों का अध्ययन करते हैं और इन परिणामों को चार परिणामों में संभाव्यता वितरण के रूप में सारांशित करते हैं: पहला ("पहला स्थान"), दूसरा, तीसरा, और अन्य।

     Outcome  Aurora Whirlwind Phantasm 
         first  0.15  0.30   0.20 

         second  0.10  0.05   0.30 

         third  0.70  0.25   0.30 

         other  0.05  0.40   0.20 

कौन सा घोड़ा सबसे उम्मीद के मुताबिक है? इस सवाल का एक मात्रात्मक दृष्टिकोण संपीड़न को देखना है। प्रत्येक घोड़े के इतिहास को 200 मानों की एक स्ट्रिंग के रूप में लिखें (पहला, दूसरा, तीसरा, अन्य)। इन ट्रैक-रिकॉर्ड स्ट्रिंग को एन्कोड करने के लिए आवश्यक बिट्स की कुल संख्या को हफमैन के एल्गोरिदम का उपयोग करके गणना की जा सकती है। यह अरोड़ा के लिए 2 9 0 बिट्स, वाइरविंड के लिए 380, और फेंटासम के लिए 420 (इसे जांचें!) के लिए काम करता है। अरोड़ा में सबसे छोटा एन्कोडिंग है और इसलिए यह एक मजबूत अर्थ में सबसे अनुमानित है।

उन्हें फ़ैंटसम के लिए 420 कैसे मिले? मैं 400 बाइट्स प्राप्त करता रहता हूं, जैसे:

पहले, अन्य = 0.4, दूसरे, तीसरे = 0.6 को मिलाएं। प्रत्येक स्थिति एन्कोडिंग 2 बिट्स के साथ समाप्त करें।

क्या कुछ ऐसा है जो मैंने हफमैन एन्कोडिंग एल्गोरिदम के बारे में गलत समझा है?

यहां उपलब्ध पाठ्यपुस्तक: http://www.cs.berkeley.edu/~vazirani/algorithms.html (पृष्ठ 156)।

Answer 1

मुझे लगता है कि आप सही हैं: फ़ैंटसम के 200 परिणामों का प्रतिनिधित्व 400 बिट्स (बाइट्स नहीं) का उपयोग करके किया जा सकता है। ऑरोरा के लिए 2 9 0 और वाइरविंड के लिए 380 सही हैं।

सही Huffman कोड निम्नलिखित तरीके से उत्पन्न होता है:

1. कम्बाइन दो कम से कम संभावित परिणामों: 0.2 और 0.2। 0.4 प्राप्त करें।
2. अगले दो कम से कम संभावित परिणामों को जोड़ें: 0.3 और 0.3। 0.6 प्राप्त करें।
3. 0.4 और 0.6 जोड़ें। 1.0 प्राप्त करें।

आप 420 बिट्स मिलेगा अगर आप इस बजाय किया:

1. कम्बाइन दो कम से कम संभावित परिणामों: 0.2 और 0.2। 0.4 प्राप्त करें।
2. 0.4 और 0.3 जोड़ो। (गलत!) 0.7 प्राप्त करें।
3. 0.7 और 0.3 जोड़ें। 1.0