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