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

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

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

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

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

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

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

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

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

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

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

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

हफमैन पेड़ निर्माण एल्गोरिथ्म

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

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

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

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

संपीड़न प्रक्रिया को गति दें

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

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

निष्कर्ष

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

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