हफमैन एन्कोडिंग का उपयोग करके डेटा को कैसे संकुचित करें: 10 चरण

हफमैन के एल्गोरिदम का उपयोग डेटा को संपीड़ित या एन्कोड करने के लिए किया जाता है. आम तौर पर, एक टेक्स्ट फ़ाइल में प्रत्येक वर्ण को आठ बिट्स (अंक, या तो 0 या 1) के रूप में संग्रहीत किया जाता है जो उस चरित्र को मानचित्र जिसे ASCII नामक एन्कोडिंग का उपयोग करके. एक हफमैन-एन्कोडेड फ़ाइल कठोर 8-बिट संरचना को तोड़ देती है ताकि सबसे अधिक उपयोग किए जाने वाले वर्ण केवल कुछ बिट्स में संग्रहीत किए जा सकें (`ए` हो सकता है "10" या "1000" ASCII के बजाय, जो है "01100001"). कम से कम आम पात्र, फिर, अक्सर 8 बिट्स से अधिक ले जाएगा (`z` हो सकता है "00100011010"), लेकिन क्योंकि वे बहुत कम ही होते हैं, पूरी तरह से हफमैन एन्कोडिंग, पूरी तरह से मूल की तुलना में बहुत छोटी फ़ाइल बनाता है.

कदम

2 का भाग 1:

एन्कोडिंग

1. फ़ाइल में प्रत्येक वर्ण की आवृत्ति को एन्कोडेड करने के लिए गिनें. फ़ाइल के अंत को चिह्नित करने के लिए एक डमी चरित्र शामिल करें - यह बाद में महत्वपूर्ण होगा. अभी के लिए, इसे ईओएफ (फ़ाइल का अंत) पर कॉल करें और इसे 1 की आवृत्ति के रूप में चिह्नित करें.

उदाहरण के लिए, यदि आप एक टेक्स्ट फ़ाइल पढ़ने को एन्कोड करना चाहते हैं "एबी एबी कैब," आपके पास फ्रीक्वेंसी 3 के साथ `ए` होगा, फ्रीक्वेंसी 3 के साथ `बी`, फ्रीक्वेंसी 2 के साथ `(स्पेस), फ्रीक्वेंसी 1 के साथ` सी `, और आवृत्ति 1 के साथ ईओएफ.

हफमैन एन्कोडिंग चरण 2 का उपयोग कर संपीड़ित डेटा शीर्षक वाली छवि

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

एक बाइनरी ट्री एक डेटा प्रारूप है जहां डेटा का प्रत्येक टुकड़ा एक नोड होता है जो एक माता-पिता और दो बच्चों तक हो सकता है. यह अक्सर एक शाखा के पेड़ के रूप में खींचा जाता है, इसलिए नाम.

एक कतार एक उपयुक्त नामांकित डेटा संग्रह है जहां कतार में जाने वाली पहली बात यह है कि बाहर आने वाली पहली बात यह है कि (जैसे लाइन में प्रतीक्षा). में वरीयता कतार, डेटा उनकी प्राथमिकता के क्रम में संग्रहीत किया जाता है, ताकि पहली चीज आने वाली सबसे जरूरी चीज है, सबसे छोटी प्राथमिकता वाली चीज़, बजाय पहली चीज़ की तुलना में.

में "एबी एबी कैब" उदाहरण, आपकी प्राथमिकता कतार इस तरह दिखेगी: {`सी`: 1, ईओएफ: 1, ``: 2, `ए`: 3, `बी`: 3}

हफमैन एन्कोडिंग चरण 3 का उपयोग कर संपीड़ित डेटा शीर्षक वाली छवि

3. अपने पेड़ का निर्माण शुरू करें. निकालें (या विपंक्ति) प्राथमिकता कतार से दो सबसे जरूरी चीजें. इन दो नोड्स के माता-पिता होने के लिए एक नया पेड़ नोड बनाएं, पहले नोड को अपने बाएं बच्चे और दूसरे के रूप में अपने दाहिने बच्चे के रूप में संग्रहीत करें. नए नोड की प्राथमिकता अपने बच्चे की प्राथमिकताओं का योग होना चाहिए. फिर इस नए नोड को प्राथमिकता कतार में रखें.

प्राथमिकता कतार अब इस तरह दिखती है: {``: 2, नया नोड: 2, `ए`: 3, `बी`: 3}

हफमैन एन्कोडिंग चरण 4 का उपयोग कर संपीड़ित डेटा शीर्षक वाली छवि

4. अपने पेड़ का निर्माण समाप्त करें: उपरोक्त चरण को तब तक दोहराएं जब तक कि कतार में केवल एक नोड न हो. ध्यान दें कि आपके द्वारा वर्णित नोड्स और उनकी आवृत्तियों के लिए आपके द्वारा बनाए गए नोड्स के अलावा, आप पेड़ों में बदलकर, पेड़ों में बदल जाएंगे, और पुन: तंत्रिका नोड्स, नोड्स जो पहले से ही पेड़ों हैं.

जब आप समाप्त कर लें, तो कतार में अंतिम नोड होगा जड़ एन्कोडिंग पेड़, अन्य सभी नोड्स से बाहर निकलने के साथ.

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

हफमैन एन्कोडिंग चरण 5 का उपयोग कर संपीड़ित डेटा शीर्षक वाली छवि

5. बनाओ एन्कोडिंग मानचित्र. प्रत्येक चरित्र तक पहुंचने के लिए पेड़ के माध्यम से चलो. हर बार जब आप एक नोड के बाएं बच्चे जाते हैं, तो यह `0` है. हर बार जब आप एक नोड के दाहिने बच्चे जाते हैं, तो यह `1` है. जब आप एक चरित्र में जाते हैं, तो चरित्र को 0s और 1 के अनुक्रम के साथ स्टोर करें जो वहां पहुंचने के लिए लिया गया था. यह अनुक्रम वह है जो चरित्र को संपीड़ित फ़ाइल में एन्कोड किया जाएगा. एक मानचित्र में पात्रों और उनके अनुक्रमों को स्टोर करें.

उदाहरण के लिए, जड़ से शुरू करें. रूट के बाएं बच्चे पर जाएं, और फिर उस नोड के बाएं बच्चे पर जाएं. चूंकि आपके पास अब आपके पास कोई बच्चा नहीं है, इसलिए आप एक चरित्र तक पहुंच गए हैं. यह है ` `. चूंकि आप यहां पहुंचने के लिए दो बार चले गए, `` के लिए एन्कोडिंग "00".

इस पेड़ के लिए, मानचित्र इस तरह दिखेगा: {``:"00", `ए`:"10", `बी`:"1 1", `सी`:"010", ईओएफ:"011"}.

हफमैन एन्कोडिंग चरण 6 का उपयोग कर संपीड़ित डेटा शीर्षक वाली छवि

6. आउटपुट फ़ाइल में, एक शीर्षलेख के रूप में एन्कोडिंग मानचित्र शामिल करें. यह फ़ाइल को डीकोड करने की अनुमति देगा.

हफमैन एन्कोडिंग चरण 7 का उपयोग कर संपीड़ित डेटा शीर्षक वाली छवि

7. फ़ाइल को एनकोड करें. फ़ाइल में प्रत्येक चरित्र के लिए एन्कोडेड होने के लिए, मानचित्र में संग्रहीत बाइनरी अनुक्रम लिखें. एक बार जब आप फ़ाइल को एन्कोड कर लेंगे, तो ईओएफ को अंत में जोड़ना सुनिश्चित करें.

फ़ाइल के लिए "एबी एबी कैब", एन्कोडेड फ़ाइल इस तरह दिखाई देगी: "1011001011000101011011".

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

2 का भाग 2:

डिकोडिंग

1. एक हफमैन-एन्कोडेड फ़ाइल में पढ़ें. सबसे पहले, हेडर पढ़ें, जो एन्कोडिंग मानचित्र होना चाहिए. एक डिकोडिंग पेड़ बनाने के लिए इसका उपयोग उसी तरह से करें जिस तरह से आपने उस पेड़ का निर्माण किया था जिसे आपने फ़ाइल को एन्कोड किया था. दो पेड़ों को समान होना चाहिए.

हफमैन एन्कोडिंग चरण 9 का उपयोग कर संपीड़ित डेटा शीर्षक वाली छवि

2. एक समय में बाइनरी एक अंक में पढ़ें. जैसा कि आप पढ़ते हैं, पेड़ को पार करें: यदि आप `0` में पढ़ते हैं, तो नोड के बाएं बच्चे पर जाएं, और यदि आप `1` में पढ़ते हैं, तो दाहिने बच्चे पर जाएं. जब आप एक पत्ती (बिना किसी बच्चों के एक नोड) तक पहुंचते हैं, तो आप एक चरित्र पर पहुंचे हैं. डिकोडेड फ़ाइल में वर्ण लिखें.

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