একটি সহজ অ্যালগরিদম
- nটি ইনিশিয়াল হাফম্যান ট্রির একটি কালেকশন প্রস্তুত করা হয়, যেকোনো একটি একটি সিঙ্গেল লিফ নোড। nটি ট্রিকে একটি প্রায়রিটি কিউতে রাখা হয় ওয়েট (ফ্রিকোয়েন্সি) দ্বারা অর্গানাইজড।
- এই নতুন ট্রি প্রায়রিটি কিউতে রাখা হয়।
- স্টেপ ২-৩ রিপিট করা হয় যতক্ষণ না সমস্ত পার্শ্ববর্তী হাফম্যান ট্রি একে একসাথে জয়েন করা হয়।
প্রথম দুটি ট্রি রিমুভ বা ডিলিট করা হয় (সাবচেয়ে ছোট ওয়েটের)। এই দুটি ট্রি কম্বাইন করা হয় একটি নতুন ট্রি তৈরি করতে যার রুট দুটি ট্রি সাথে চাইল্ড হিসেবে অ্যাসোসিয়েটেড, এবং যার ওয়েট দুটি চাইল্ড ট্রির ওয়েটের যোগফল।
এটি একটি লোভী অ্যালগরিদম: প্রতিটি ইটারেশনে, অ্যালগরিদম একটি "লোভী" সিদ্ধান্ত নেয় দুটি সাবট্রি মার্জ করতে যাদের সবচেয়ে ছোট ওয়েট। কি অ্যালগরিদমটি ডিজায়ারড রেজাল্ট দিতে পারে?
- লেমা: x এবং y হোক দুটি সবচেয়ে কম ফ্রিকোয়েন্ট ক্যারেক্টার। একটি অপ্টিমাল কোড ট্রি আছে যেখানে x এবং y সিবলিং যাদের ডেপথ মিনিমাম যেকোনো অন্য লিফ নোডের চেয়ে ট্রিতে।
- থিওরেম: হাফম্যান কোডগুলো অপ্টিমাল প্রিফিক্স-ফ্রি বাইনারি কোড হিসেবে বিবেচিত হয় (লোভী অ্যালগরিদম দেওয়া সেট অফ লেটারের জন্য মিনিমাম এক্সটার্নাল পাথ ওয়েটের হাফম্যান ট্রি কনস্ট্রাক্ট করে)।
