algorithm हफ़मैन कोड का उपयोग करके शब्दों को कैसे एन्कोड करना चाहिए




encoding compression (4)

हफ़मैन कोड जैसे कि NEED के उपयोग से आप शब्दों को कैसे एनकोड करते हैं


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

आमतौर पर दो विशेष टोकन, एस्केप और एंड-स्ट्रीम हैं

एन्कोडिंग एक शब्दकोश बनाए रखता है जो मूल रूप से टोकन पाने के लिए बिट अनुक्रमों का एक लुकअप है। प्रारंभ में इसमें केवल दो विशेष टोकन शामिल हैं

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

इसलिए आपका 'एन' आउटपुट स्ट्रीम में हो सकता है:

0 xxxxxxxx
| +- token code for N
+--- ESCAPE

और नया शब्दकोश:

ESCAPE:00
END-STREAM:01
N:1

तब आपका 'ई' आउटपुट स्ट्रीम में हो सकता है:

0 xxxxxxxx 0 yyyyyyyy
             +- token code for E

और नया शब्दकोश:

ESCAPE:00
END-STREAM:01
N:10
E:11

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

जब डी आता है, तो आउटपुट स्ट्रीम बन जाती है:

0 xxxxxxxx 0 yyyyyyyy 11 0 zzzzzzzz
                      |    +- token code for D
                      +------ second E

और नया शब्दकोश:

ESCAPE:00
END-STREAM:011
N:010
E:11
D:10

तो आप देख सकते हैं, जितना अधिक वर्ण आते हैं, आम लोगों की थोड़ी लंबाई कम हो जाती है और एक असामान्य वृद्धि के साथ, आपको अपना संपीड़न दे। इस मामले में एन (या डी) को 3-अंकीय कोड मिलता है, जबकि ई 2-अंकीय कोड के साथ चिपक जाता है क्योंकि उनमें से अधिक हैं

सुंदरता यह है कि आपको फ़ाइल के साथ डिक्शनरी को स्टोर करने की आवश्यकता नहीं है क्योंकि एस्कैप वर्गों को डी-कॉम्प्रेशन के लिए गतिशील रूप से भी बढ़ाना है।

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

एक (8-बिट एएससीआईआई) इनपुट स्ट्रीम का सबसे अच्छा मामला एक ऐसी फाइल है, जिसमें लाखों एक ही चरित्र नहीं हैं। यह पहले अक्षर के लिए 9 बिट की लागत है, फिर प्रत्येक अतिरिक्त चरित्र के लिए 1 बिट तो स्ट्रीम के अंत के लिए 2 बिट्स। यह तेज़ एक 1-के -8 संपीड़न अनुपात (97.5%) तक पहुंचता है।

सबसे बुरा मामला वाकई प्रत्येक चरित्र में से एक है जिसमें 9 बिट प्रति चरित्र और स्ट्रीम का अंत होता है - यह वास्तव में धारा 12.5% ​​तक फैलता है।



एफ # के साथ हफ़मान कोडिंग पर एक नज़र डालें, एक ब्लॉग पोस्ट जो एफ # में लिखा हफ़मान सांकेतिक शब्दों में बदलनेवाला / डिकोडर प्रस्तुत करता है। यह छोटा और स्पष्ट है


मुझे लगता है कि आपको हफ़मान कोडिंग का मतलब है यह नुकसान के बिना डेटा को संक्षिप्त करने के लिए एक एल्गोरिथ्म है बस रखो, आप सबसे छोटी और सबसे अधिक दोहराव वाले छोटे-छोटे प्रतिरूपों को प्रतिस्थापित करते हैं जो कि सबसे छोटी संभव प्रतिनिधित्व (जो कि सबसे संपीड़न कैसे काम करता है) को बदलता है उदाहरण के लिए, एक एचटीएमएल पृष्ठ बाइनरी नंबर 01 को बहुत ही आम <DIV को निर्दिष्ट कर सकता है जिसमें से प्रत्येक के 32 बीट्स को कम किया जाता है।

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





huffman-code