हफमैन कोड: उदाहरण, अनुप्रयोग

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

एल्गोरिदम का इतिहास

एक प्रभावी के लिए पहला एल्गोरिदमइलेक्ट्रॉनिक जानकारी का कोडिंग बीसवीं शताब्दी के मध्य में हफमैन द्वारा प्रस्तावित कोड था, अर्थात् 1 9 52 में। यह वर्तमान में सूचना को संपीड़ित करने के लिए बनाए गए अधिकांश कार्यक्रमों का मुख्य मूल तत्व है। फिलहाल, इस कोड का उपयोग करने वाले सबसे लोकप्रिय स्रोतों में से एक ज़िप, एआरजे, आरएआर अभिलेखागार और कई अन्य हैं।

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

कुशल कोडिंग का सिद्धांत

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

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

हफमैन का कोड, उदाहरण

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

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

ऐसी अवधारणा भी है, जो कोड में शामिल हैएक पेड़ के पत्ते की तरह हफमैन। यह एक नोड है जिससे कोई चाप नहीं बचाना चाहिए। यदि दो नोड्स एक चाप से जुड़े होते हैं, तो उनमें से एक माता-पिता, दूसरा बच्चा होता है, इस पर निर्भर करता है कि किस नोड से आ रहा है, और यह किस में है। यदि दो नोड्स में एक ही पैरेंट नोड होता है, तो उन्हें आमतौर पर भाई नोड कहा जाता है। यदि, पत्तियों के अलावा, नोड्स में कई आर्क हैं, इस पेड़ को बाइनरी कहा जाता है। यह वास्तव में हफमैन का पेड़ है। इस निर्माण के नोड्स की विशिष्टता यह है कि प्रत्येक माता-पिता का वजन उसके सभी नोडल बच्चों के वजन के बराबर होता है।

हफमैन के अनुसार एक पेड़ बनाने के लिए एल्गोरिदम

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

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

संपीड़न दक्षता में सुधार

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

संपीड़न प्रक्रिया का त्वरण

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

इसके अलावा, इस मोड में गतिशील, गतिशीलहफमैन कोड, या बल्कि एल्गोरिदम स्वयं, किसी भी बदलाव के अधीन नहीं है। यह मुख्य रूप से इस तथ्य के कारण है कि संभावनाएं आवृत्तियों के लिए सीधे आनुपातिक हैं। इस तथ्य पर विशेष ध्यान देने योग्य है कि फ़ाइल का अंतिम वजन या तथाकथित रूट नोड ऑब्जेक्ट में संसाधित होने वाले अक्षरों की संख्या के योग के बराबर होगा।

निष्कर्ष

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

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