एक सरल एल्गोरिथम
- n प्रारंभिक हफ़मैन पेड़ों का एक संग्रह तैयार किया गया है, जिनमें से प्रत्येक एक एकल पत्ती नोड है। n पेड़ों को वज़न (आवृत्ति) द्वारा व्यवस्थित प्राथमिकता वाली कतार में रखें।
- पहले दो पेड़ों को हटाएं या हटाएं (जिन पेड़ों का वजन सबसे छोटा है)। इन दो पेड़ों को मिलाकर एक नया पेड़ बनाएं जिसकी जड़ बच्चों के रूप में दो पेड़ों से जुड़ी हो और जिसका वजन दो बच्चों के पेड़ों के वजन का योग हो।
- इस नए पेड़ को प्राथमिकता कतार में रखें।
- चरण 2-3 तब तक दोहराएं जब तक कि सभी आंशिक हफ़मैन पेड़ एक में शामिल न हो जाएं।
यह एक लालची एल्गोरिथ्म है:प्रत्येक पुनरावृत्ति पर, एल्गोरिथ्म दो उपप्रकारों को सबसे छोटे वजन के साथ मिलाने के लिए एक "लालची" निर्णय बनाता है। क्या एल्गोरिथम के लिए वांछित परिणाम देना संभव है?
- लेम्मा:मान लीजिए x और y दो सबसे कम बारंबार होने वाले वर्ण हैं। एक इष्टतम कोड ट्री है जिसमें x और y भाई-बहन हैं जिनकी गहराई पेड़ में किसी भी अन्य लीफ नोड्स की तरह न्यूनतम है।
- प्रमेय:हफ़मैन कोड को इष्टतम उपसर्ग-मुक्त बाइनरी कोड के रूप में माना जाता है (लालची एल्गोरिथम अक्षरों के दिए गए सेट के लिए न्यूनतम बाहरी पथ भार के साथ हफ़मैन ट्री का निर्माण करता है)।