परिभाषा
हफमैन कोडिंग कैरेक्टर को कोड प्रदान करती है जैसे कि कोड की लंबाई संबंधित कैरेक्टर की सापेक्ष आवृत्ति या वजन पर निर्भर करती है। हफमैन कोड वेरिएबल-लेंथ के होते हैं, और बिना किसी प्रीफिक्स के (यानी कोई कोड किसी अन्य का प्रीफिक्स नहीं होता)। किसी भी प्रीफिक्स-फ्री बाइनरी कोड को एन्कोडेड कैरेक्टर के साथ लीव्स पर संग्रहीत बाइनरी ट्री के रूप में प्रदर्शित या विज़ुअलाइज़ किया जा सकता है।
हफमैन ट्री या हफमैन कोडिंग ट्री को एक फुल बाइनरी ट्री के रूप में परिभाषित किया जाता है जिसमें ट्री का प्रत्येक लीफ दिए गए अल्फाबेट में एक अक्षर से मेल खाता है।
हफमैन ट्री को मिनिमम एक्सटर्नल पाथ वेट से जुड़े बाइनरी ट्री के रूप में माना जाता है, यानी दिए गए लीव्स के सेट के लिए वेटेड पाथ लंबाई के न्यूनतम योग से जुड़ा हुआ। इसलिए लक्ष्य न्यूनतम एक्सटर्नल पाथ वेट वाला ट्री बनाना है।
एक उदाहरण नीचे दिया गया है -
अक्षर आवृत्ति तालिका
| अक्षर | z | k | m | c | u | d | l | e |
| आवृत्ति | 2 | 7 | 24 | 32 | 37 | 42 | 42 | 120 |
हफमैन कोड
| अक्षर | आवृत्ति | कोड | बिट्स |
|---|---|---|---|
| e | 120 | 0 | 1 |
| d | 42 | 101 | 3 |
| l | 42 | 110 | 3 |
| u | 37 | 100 | 3 |
| c | 32 | 1110 | 4 |
| m | 24 | 11111 | 5 |
| k | 7 | 111101 | 6 |
| z | 2 | 111100 | 6 |
उपरोक्त उदाहरण के लिए हफमैन ट्री नीचे दिया गया है -
