ডাটা স্ট্রাকচারে হাফম্যান ট্রিস

সংজ্ঞা

হাফম্যান কোডিং অক্ষরগুলিতে কোড সরবরাহ করে যাতে কোডের দৈর্ঘ্য সংশ্লিষ্ট অক্ষরের আপেক্ষিক ফ্রিকোয়েন্সি বা ওজনের উপর নির্ভর করে। হাফম্যান কোডগুলি পরিবর্তনশীল-দৈর্ঘ্যের, এবং কোনো উপসর্গ ছাড়াই (এর মানে কোনো কোড অন্য কোনো উপসর্গ নয়)। যে কোনো উপসর্গ-মুক্ত বাইনারি কোড পাতায় সংরক্ষিত এনকোড করা অক্ষর সহ একটি বাইনারি ট্রি হিসাবে প্রদর্শিত বা ভিজ্যুয়ালাইজ করা যেতে পারে।

হাফম্যান ট্রি বা হাফম্যান কোডিং ট্রি একটি সম্পূর্ণ বাইনারি গাছ হিসাবে সংজ্ঞায়িত করে যেখানে গাছের প্রতিটি পাতা প্রদত্ত বর্ণমালার একটি অক্ষরের সাথে মিলে যায়৷

হাফম্যান গাছটিকে ন্যূনতম বাহ্যিক পথের ওজনের সাথে যুক্ত বাইনারি গাছ হিসাবে বিবেচনা করা হয় যার অর্থ, প্রদত্ত পাতার সেটের জন্য ওজনযুক্ত পথের দৈর্ঘ্যের ন্যূনতম যোগফলের সাথে যুক্ত। তাই লক্ষ্য হল ন্যূনতম বাহ্যিক পথের ওজন সহ একটি গাছ তৈরি করা।

নিচে একটি উদাহরণ দেওয়া হল-

অক্ষরের ফ্রিকোয়েন্সি টেবিল

হাফম্যান কোড

হাফম্যান গাছ (উপরের উদাহরণের জন্য) নীচে দেওয়া হল -