परिभाषा
हफमैन कोडिंग वर्णों को कोड प्रदान करता है जैसे कि कोड की लंबाई संबंधित वर्ण की सापेक्ष आवृत्ति या वजन पर निर्भर करती है। हफ़मैन कोड चर-लंबाई के होते हैं, और बिना किसी उपसर्ग के (अर्थात कोई भी कोड किसी अन्य का उपसर्ग नहीं होता है)। किसी भी उपसर्ग-मुक्त बाइनरी कोड को पत्तियों पर संग्रहीत एन्कोडेड वर्णों के साथ बाइनरी ट्री के रूप में प्रदर्शित या विज़ुअलाइज़ किया जा सकता है।
हफ़मैन ट्री या हफ़मैन कोडिंग ट्री एक पूर्ण बाइनरी ट्री के रूप में परिभाषित करता है जिसमें पेड़ का प्रत्येक पत्ता दिए गए वर्णमाला के एक अक्षर से मेल खाता है।
हफ़मैन ट्री को न्यूनतम बाहरी पथ भार से जुड़े बाइनरी ट्री के रूप में माना जाता है, जिसका अर्थ है कि पत्तियों के दिए गए सेट के लिए न्यूनतम भारित पथ लंबाई के साथ जुड़ा हुआ है। तो लक्ष्य न्यूनतम बाहरी पथ भार के साथ एक पेड़ का निर्माण करना है।
एक उदाहरण नीचे दिया गया है-
अक्षर आवृत्ति तालिका
| पत्र | 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 |
हफ़मैन ट्री (उपरोक्त उदाहरण के लिए) नीचे दिया गया है -
