एक सरल एल्गोरिदम (A Simple Algorithm)
- n प्रारंभिक हफमैन ट्रीज़ का एक संग्रह तैयार किया जाता है, जिनमें से प्रत्येक एक सिंगल लीफ नोड (Single Leaf Node) है। n ट्रीज़ को वजन (आवृत्ति) द्वारा व्यवस्थित प्रायोरिटी क्यू (Priority Queue) पर रखें।
- पहले दो ट्रीज़ को हटाएं (सबसे छोटे वजन वाले)। इन दो ट्रीज़ को मिलाकर एक नई ट्री बनाएं जिसका रूट उन दो ट्रीज़ को बच्चों के रूप में जोड़ता है, और जिसका वजन दोनों बच्चों ट्रीज़ के वजन का योग होता है।
- इस नई ट्री को प्रायोरिटी क्यू में रखें।
- चरण 2-3 को तब तक दोहराएं जब तक कि सभी आंशिक हफमैन ट्रीज़ एक में जुड़ न जाएं।
यह एक लालची एल्गोरिदम (Greedy Algorithm) है: प्रत्येक पुनरावृत्ति पर, एल्गोरिदम सबसे छोटे वजन वाले दो सबट्रीज़ को मर्ज करने का "लालची" निर्णय लेता है। क्या एल्गोरिदम वांछित परिणाम दे सकता है?
- लेम्मा (Lemma): मान लीजिए x और y दो सबसे कम आवृत्ति वाले वर्ण हैं। एक इष्टतम कोड ट्री मौजूद है जिसमें x और y भाई (Siblings) हैं जिनकी गहराई ट्री में किसी अन्य लीफ नोड की तुलना में न्यूनतम है।
- थ्योरम (Theorem): हफमैन कोड को इष्टतम प्रीफिक्स-फ्री बाइनरी कोड (Optimal Prefix-free Binary Codes) माना जाता है (लालची एल्गोरिदम दिए गए अक्षरों के सेट के लिए न्यूनतम बाहरी पथ वजन के साथ हफमैन ट्री का निर्माण करता है)।
