हफ़मैन कोडिंग एल्गोरिदम के साथ बनाए गए पेड़ की अधिकतम ऊंचाई क्या है, यह मानते हुए कि सभी बाइट्स इसमें स्वीकार किए जाते हैं।

मैं उत्सुक हूं क्योंकि मैंने किसी तरह 9 बिट्स का पथ प्राप्त करने में कामयाब रहा जब मैंने I फ़ाइल को संपीड़ित करने का प्रयास किया जिसे मैंने यादृच्छिक रूप से उत्पन्न किया। जिसका अर्थ है कि मैं अनिवार्य रूप से फ़ाइल का आकार बढ़ाता हूं। हालांकि कार्यक्रम में कहीं न कहीं कोई समस्या हो सकती है जिसके बारे में मुझे जानकारी नहीं है।

1
visu 11 फरवरी 2021, 23:38
2
अधिकतम ऊंचाई प्रतीकों की संख्या एक से कम है। यह तब होता है जब एक प्रतीक में शेष प्रतीकों के योग से अधिक आवृत्तियाँ होती हैं, और इसी तरह, पुनरावर्ती रूप से।
 – 
500 - Internal Server Error
12 फरवरी 2021, 00:00
रैंडम डेटा को संपीड़ित नहीं किया जा सकता क्योंकि संपीड़न डेटा में अतिरेक का शोषण करता है, और यादृच्छिक डेटा में कोई नहीं है, इसलिए आपकी खोज आश्चर्यजनक नहीं है।
 – 
500 - Internal Server Error
12 फरवरी 2021, 00:02
आप कैसे सुझाव देते हैं कि मुझे उस स्थिति को संभालना चाहिए? उच्च एन्ट्रॉपी होने पर बस एंट्रॉपी की गणना करें और फिर अधिक आवंटित करें?
 – 
visu
12 फरवरी 2021, 00:18
एक बार जब आप पेड़ का निर्माण कर लेते हैं तो आप हफ़मैन एन्कोडेड संदेश की लंबाई की गणना कर सकते हैं। यदि वह लंबाई असम्पीडित इनपुट की लंबाई से अधिक है तो डेटा को एन्कोड करने का कोई मतलब नहीं है। आपके पास प्रारंभिक ध्वज बाइट हो सकता है जो इंगित करता है कि शेष फ़ाइल हफ़मैन स्ट्रीम या असम्पीडित छवि का प्रतिनिधित्व करती है या नहीं।
 – 
500 - Internal Server Error
12 फरवरी 2021, 00:33
यदि आप यादृच्छिक डेटा को संपीड़ित करने का प्रयास कर रहे हैं तो आपको अधिक संपीड़न नहीं मिलेगा, लेकिन यह सबसे खराब स्थिति के लिए एक अच्छी परीक्षा है।
 – 
tadman
12 फरवरी 2021, 01:04

1 उत्तर

सबसे बढ़िया उत्तर

यदि "सभी बाइट्स" से आपका मतलब आपके प्रतीकों के सेट के रूप में सभी 256 संभावित बाइट मानों से है, तो इसका उत्तर यह है कि अधिकतम गहराई, और इसलिए सबसे लंबे कोड की लंबाई 255 है।

हालांकि इसे प्राप्त करने के लिए प्रतीकों की आवृत्तियों के लिए बहुत बड़ी संख्या की आवश्यकता होती है। सबसे छोटी कुल गिनती के साथ ऐसा करने वाला क्रम लुकास संख्या है, जिसमें शून्य लुकास संख्या 2 दो 1 में विभाजित है। इसलिए:

1, 1, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, ...

जहां 4 से शुरू होने वाले पद पिछले दो पदों का योग हैं, ठीक उसी तरह जैसे कि फाइबोनैचि अनुक्रम। उस क्रम में 256 प्रतीकों के लिए अंतिम पद है:

121020968315000050139390193037122554865361969834971243

53

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

0
Mark Adler 12 फरवरी 2021, 08:50