हफमैन फिंगर एल्गोरिथम

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

अनुवादक का नोट: एक प्रतीक द्वारा एक लेखक का अर्थ है स्रोत स्ट्रिंग का एक निश्चित दोहराव वाला तत्व - यह या तो एक मुद्रित चरित्र (चरित्र) या कोई बिट अनुक्रम हो सकता है। कोड से अभिप्राय ASCII या UTF-8 वर्ण कोड से नहीं है, बल्कि बिट्स के एन्कोडिंग अनुक्रम से है।

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

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

हम आसानी से 16-बिट चरित्र (जो कि दो मुद्रित वर्णों से मिलकर बना है) ले सकते हैं, साथ ही 10 बिट्स, 20, और इसी तरह। चरित्र आकार का चयन उस इनपुट लाइन के आधार पर किया जाता है जिसकी हम अपेक्षा करते हैं। उदाहरण के लिए, अगर मैं कच्चे वीडियो फ़ाइलों को एनकोड करने जा रहा था, तो मैं वर्ण के आकार को पिक्सेल के आकार के बराबर कर दूंगा। याद रखें कि जब आप किसी वर्ण का आकार घटाते या बढ़ाते हैं, तो प्रत्येक वर्ण के लिए कोड का आकार बदल जाता है, क्योंकि आकार जितना बड़ा होगा, उतने अधिक वर्ण इस कोड आकार के साथ एन्कोड किए जा सकते हैं। शून्य और आठ बिट के लिए उपयुक्त वाले का संयोजन सोलह से कम है। इसलिए, आपको उस सिद्धांत के आधार पर चरित्र का आकार चुनना होगा जिसके द्वारा आपके अनुक्रम में डेटा दोहराया जाता है।

इस एल्गोरिथ्म के लिए, आपको बाइनरी ट्री संरचना और प्राथमिकता कतार की न्यूनतम समझ की आवश्यकता है। स्रोत कोड में, मैंने अपने पिछले लेख से प्राथमिकता कतार कोड का उपयोग किया।

मान लें कि हमारे पास "बीप बोप बीयर!" लाइन है, जिसके लिए, अपने वर्तमान रूप में, प्रत्येक चरित्र पर एक बाइट खर्च की जाती है। इसका मतलब है कि पूरी लाइन में 15 * 8 = 120 बिट मेमोरी होती है। एन्कोडिंग के बाद, स्ट्रिंग 40 बिट्स लेगी (व्यवहार में, हमारे कार्यक्रम में हम कंसोल को 40 शून्य और इकाइयों को अनुक्रमित बिट्स का प्रतिनिधित्व करने के लिए आउटपुट देंगे। उनसे 40 बिट्स की वास्तविक स्ट्रिंग प्राप्त करने के लिए, हमें बिट अंकगणितीय का उपयोग करने की आवश्यकता है, इसलिए हम आज ऐसा नहीं करेंगे। यह करने के लिए)।

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

एक पेड़ बनाने के लिए, हम थोड़ी संशोधित प्राथमिकता कतार का उपयोग करेंगे - सबसे कम प्राथमिकता वाले तत्व और सबसे पहले नहीं निकाला जाएगा। पत्तियों से जड़ तक एक पेड़ बनाने के लिए यह आवश्यक है।

सबसे पहले, आइए सभी वर्णों की आवृत्तियों की गणना करें:

प्रतीक	आवृत्ति
'बी'	3
'ई'	4
'पी'	2
''	2
'O'	2
'आर'	1
'!'	1

आवृत्तियों की गणना करने के बाद, हम प्रत्येक वर्ण के लिए बाइनरी ट्री के नोड्स बनाएंगे और उन्हें प्राथमिकता के रूप में आवृत्ति का उपयोग करके कतार में जोड़ेंगे:


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

उसी चरणों को दोहराएं और अनुक्रम में प्राप्त करें:





खैर, अंतिम दो तत्वों को जोड़ने के बाद, हमें अंतिम पेड़ मिलता है:


अब, प्रत्येक वर्ण के लिए कोड प्राप्त करने के लिए, आपको बस पेड़ से गुजरना होगा, और प्रत्येक संक्रमण के लिए 0 जोड़ेंगे यदि हम बाईं ओर जाते हैं, और 1 यदि दाईं ओर:


यदि हम ऐसा करते हैं, तो हमें पात्रों के लिए निम्नलिखित कोड मिलते हैं:

प्रतीक	कोड
'बी'	00
'ई'	11
'पी'	101
''	011
'O'	010
'आर'	1000
'!'	1001

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

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

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

इनपुट लाइन: "बीप बोप बीयर!"
द्विआधारी रूप में इनपुट स्ट्रिंग: "0110 0010 0110 0101 0110 0101 000 0000 0000 0010 0110 0010 0111 1110 0111 11111 0000 0010 0000 0110 0110 0110 0101 0111 0010 0010 000"
कोडेड स्ट्रिंग: "0011 1110 1011 0001 0010 1010 1100 1111 1000 1001"
जैसा कि आप देख सकते हैं, एक स्ट्रिंग के एएससीआईआई संस्करण और एन्कोडेड संस्करण के बीच एक बड़ा अंतर है।

संलग्न स्रोत कोड उसी सिद्धांत पर काम करता है जैसा ऊपर वर्णित है। आप कोड में अधिक विवरण और टिप्पणियां पा सकते हैं।

सभी स्रोतों को C99 मानक का उपयोग करके संकलित और सत्यापित किया गया था। एक अच्छी प्रोग्रामिंग है!

स्रोत कोड डाउनलोड करें

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