हफ़मैन के एल्गोरिथ्म का उपयोग डेटा को संपीड़ित या एन्कोड करने के लिए किया जाता है। आम तौर पर, टेक्स्ट फ़ाइल में प्रत्येक वर्ण को आठ बिट्स (अंक, या तो 0 या 1) के रूप में संग्रहीत किया जाता है जो ASCII नामक एन्कोडिंग का उपयोग करके उस वर्ण को मैप करता है। एक हफ़मैन-एन्कोडेड फ़ाइल कठोर 8-बिट संरचना को तोड़ देती है ताकि सबसे अधिक उपयोग किए जाने वाले वर्ण केवल कुछ बिट्स में संग्रहीत हों ('ए' ASCII के बजाय "10" या "1000" हो सकता है, जो "01100001" है।) फिर, कम से कम सामान्य वर्ण, अक्सर 8 बिट्स से अधिक ('z' "00100011010" हो सकता है) ले लेंगे, लेकिन क्योंकि वे बहुत कम होते हैं, हफ़मैन एन्कोडिंग, कुल मिलाकर, मूल की तुलना में बहुत छोटी फ़ाइल बनाता है।
कदम
2 का भाग 1: एन्कोडिंग
चरण 1. एन्कोड की जाने वाली फ़ाइल में प्रत्येक वर्ण की आवृत्ति की गणना करें।
फ़ाइल के अंत को चिह्नित करने के लिए एक डमी वर्ण शामिल करें - यह बाद में महत्वपूर्ण होगा। अभी के लिए, इसे EOF (फ़ाइल का अंत) कहें और इसे 1 की आवृत्ति के रूप में चिह्नित करें।
उदाहरण के लिए, यदि आप "ab ab कैब" पढ़ने वाली टेक्स्ट फ़ाइल को एन्कोड करना चाहते हैं, तो आपके पास आवृत्ति 3 के साथ 'a', फ़्रीक्वेंसी 3 के साथ 'b', फ़्रीक्वेंसी 2 के साथ '' (स्पेस), फ़्रीक्वेंसी 1 के साथ 'c' होगा।, और ईओएफ आवृत्ति के साथ 1
चरण 2. वर्णों को ट्री नोड्स के रूप में संग्रहीत करें और उन्हें प्राथमिकता कतार में रखें।
आप पत्ते के रूप में प्रत्येक चरित्र के साथ एक बड़ा बाइनरी पेड़ बना रहे होंगे, इसलिए आपको पात्रों को प्रारूप में स्टोर करना चाहिए ताकि वे पेड़ के नोड बन सकें। इन नोड्स को प्रत्येक वर्ण की आवृत्ति के साथ अपनी नोड की प्राथमिकता के रूप में प्राथमिकता कतार में रखें।
- एक बाइनरी ट्री एक डेटा प्रारूप है जहां डेटा का प्रत्येक टुकड़ा एक नोड होता है जिसमें एक माता-पिता और दो बच्चे हो सकते हैं। इसे अक्सर एक शाखा वाले पेड़ के रूप में खींचा जाता है, इसलिए नाम।
- एक कतार एक उपयुक्त नामित डेटा संग्रह है जहां कतार में जाने वाली पहली चीज भी बाहर आने वाली पहली चीज है (जैसे लाइन में प्रतीक्षा करना)। प्राथमिकता कतार में, डेटा को उनकी प्राथमिकता के क्रम में संग्रहीत किया जाता है, ताकि पहली चीज जो सबसे जरूरी चीज है, वह सबसे छोटी प्राथमिकता वाली चीज है, न कि पहली चीज जो कतार में है।
- "अब अब कैब" उदाहरण में, आपकी प्राथमिकता कतार इस तरह दिखेगी: {'c':1, EOF:1, ' ':2,'a':3, 'b':3}
चरण 3. अपना पेड़ बनाना शुरू करें।
प्राथमिकता कतार से दो सबसे जरूरी चीजों को हटा दें (या हटा दें)। इन दो नोड्स के माता-पिता बनने के लिए एक नया ट्री नोड बनाएं, पहले नोड को उसके बाएं बच्चे के रूप में और दूसरे को उसके दाहिने बच्चे के रूप में संग्रहीत करें। नए नोड की प्राथमिकता उसके बच्चे की प्राथमिकताओं का योग होना चाहिए। फिर इस नए नोड को प्राथमिकता कतार में संलग्न करें।
प्राथमिकता कतार अब इस तरह दिखती है: {' ':2, नया नोड:2,'a':3, 'b':3}
चरण 4. अपना पेड़ बनाना समाप्त करें:
उपरोक्त चरण को तब तक दोहराएं जब तक कि कतार में केवल एक नोड न हो। ध्यान दें कि आपके द्वारा वर्णों और उनकी आवृत्तियों के लिए बनाए गए नोड्स के अलावा, आप भी dequeuing, पेड़ों में बदल रहे हैं, और माता-पिता नोड्स, नोड्स जो पहले से ही पेड़ हैं, को फिर से संलग्न करेंगे।
- जब आप समाप्त कर लें, तो कतार में अंतिम नोड एन्कोडिंग ट्री की जड़ होगी, जिसमें अन्य सभी नोड्स इससे अलग होंगे।
- सबसे अधिक उपयोग किए जाने वाले वर्ण पेड़ के शीर्ष के सबसे नज़दीकी पत्ते होंगे, जबकि दुर्लभ रूप से उपयोग किए जाने वाले वर्ण पेड़ के नीचे, जड़ से दूर स्थित होंगे।
चरण 5. एक एन्कोडिंग मानचित्र बनाएँ। प्रत्येक चरित्र तक पहुँचने के लिए पेड़ के माध्यम से चलो। हर बार जब आप नोड के बाएं बच्चे पर जाते हैं, तो वह '0' होता है। हर बार जब आप नोड के दाहिने बच्चे पर जाते हैं, तो वह '1' होता है। जब आप किसी पात्र पर पहुँचते हैं, तो उस वर्ण को 0 और 1 के अनुक्रम के साथ संग्रहीत करें जो उसे वहाँ पहुँचने में लगा। यह अनुक्रम वह है जो चरित्र को संपीड़ित फ़ाइल के रूप में एन्कोड किया जाएगा। पात्रों और उनके अनुक्रमों को मानचित्र में संग्रहित करें।
- उदाहरण के लिए, जड़ से शुरू करें। रूट के बाएँ बच्चे पर जाएँ, और फिर उस नोड के बाएँ बच्चे पर जाएँ। चूंकि आप जिस नोड पर हैं, उसके कोई बच्चे नहीं हैं, आप एक चरित्र पर पहुंच गए हैं। यह है ' '। चूँकि आप यहाँ पहुँचने के लिए दो बार बायीं ओर चले थे, '' ' के लिए एन्कोडिंग "00" है।
- इस पेड़ के लिए, नक्शा इस तरह दिखेगा: {' ':"00", 'a':"10", 'b':"11", 'c':"010", EOF:"011"}।
चरण 6. आउटपुट फ़ाइल में, एन्कोडिंग मैप को हेडर के रूप में शामिल करें।
यह फ़ाइल को डीकोड करने की अनुमति देगा।
चरण 7. फ़ाइल को एन्कोड करें।
फ़ाइल में प्रत्येक वर्ण को एन्कोड करने के लिए, मानचित्र में आपके द्वारा संग्रहीत बाइनरी अनुक्रम लिखें। एक बार जब आप फ़ाइल को एन्कोड करना समाप्त कर लेते हैं, तो ईओएफ को अंत में जोड़ना सुनिश्चित करें।
- फ़ाइल "अब अब कैब" के लिए, एन्कोडेड फ़ाइल इस तरह दिखेगी: "1011001011000101011011"।
- फ़ाइलें बाइट्स (8 बिट, या 8 बाइनरी अंक) के रूप में संग्रहीत की जाती हैं। चूंकि हफ़मैन एन्कोडिंग एल्गोरिथम 8-बिट प्रारूप का उपयोग नहीं करता है, इसलिए एन्कोडेड फ़ाइलों की लंबाई अक्सर 8 के गुणकों में नहीं होती है। शेष अंक 0s से भरे जाएंगे। इस स्थिति में, फ़ाइल के अंत में दो 0 जोड़े जाएंगे, जो किसी अन्य स्थान की तरह दिखता है। यह एक समस्या हो सकती है: डिकोडर को कैसे पता चलेगा कि कब पढ़ना बंद करना है? हालाँकि, क्योंकि हमने एक एंड-ऑफ-फाइल कैरेक्टर शामिल किया है, डिकोडर इसे प्राप्त करेगा और फिर रुक जाएगा, इसके बाद जो कुछ भी जोड़ा गया है उसे अनदेखा कर देगा।
2 का भाग 2: डिकोडिंग
चरण 1. हफ़मैन-एन्कोडेड फ़ाइल में पढ़ें।
सबसे पहले, हेडर पढ़ें, जो एन्कोडिंग मैप होना चाहिए। इसका उपयोग डिकोडिंग ट्री बनाने के लिए उसी तरह करें जैसे आपने उस ट्री को बनाया था जिसका उपयोग आपने फ़ाइल को एन्कोड करने के लिए किया था। दो पेड़ समान होने चाहिए।
चरण 2. बाइनरी में एक बार में एक अंक पढ़ें।
जैसा कि आप पढ़ते हैं, पेड़ को पार करें: यदि आप '0' में पढ़ते हैं, तो आप जिस नोड पर हैं, उसके बाएं बच्चे पर जाएं, और यदि आप '1' में पढ़ते हैं, तो दाएं बच्चे पर जाएं। जब आप एक पत्ते (बिना बच्चों के एक नोड) तक पहुँचते हैं, तो आप एक चरित्र पर पहुँच जाते हैं। डिकोड की गई फाइल में कैरेक्टर लिखें।
ट्री में वर्णों को संग्रहीत करने के तरीके के कारण, प्रत्येक वर्ण के कोड में एक उपसर्ग गुण होता है, ताकि किसी भी वर्ण की बाइनरी एन्कोडिंग किसी अन्य वर्ण के एन्कोडिंग की शुरुआत में कभी भी न हो। प्रत्येक वर्ण के लिए एन्कोडिंग पूरी तरह से अद्वितीय है। यह डिकोडिंग को बहुत आसान बनाता है।
चरण 3. ईओएफ तक पहुंचने तक दोहराएं।
बधाई हो! आपने फ़ाइल को डीकोड कर लिया है।
