کدگذاری هافمن (Huffman Coding) برای ورودی های مرتب – راهنمای کاربردی

پیش از این، در مطلب «الگوریتم هافمن (Huffman Coding) -- به زبان ساده»، الگوریتم هافمن به طور کامل مورد بررسی قرار گرفت و پیاده‌سازی آن نیز در زبان‌های برنامه‌نویسی گوناگون انجام شد. پیچیدگی زمانی الگوریتم مورد بررسی در مطلب بیان شده، از درجه (O(nLogn است. اگر آرایه ورودی مرتب شده باشد (با مرتبه تکرار غیرنزولی)، می‌توان کد هافمن را با پیچیدگی زمانی از درجه (O(n تولید کرد. در ادامه، روش کدگذاری هافمن از درجه (O(n برای آرایه مرتب ارائه و پیاده‌سازی آن در زبان‌های برنامه‌نویسی ++C و C انجام شده است.

1. دو صف خالی بساز.
2. یک گره برگ برای هر کاراکتر یکتا بساز و آن را به اولین صف با درجه تکرار غیر نزولی اضافه کن. به صورت مقدماتی، دومین صف خالی است.
3. دو گره با کمترین تکرار را با بررسی جلوی هر دوی صف‌ها از صف خارج کن. گام‌های زیر را دو بار تکرار کن:
   • اگر صف دوم خالی است، از صف اول گره را خارج کن.
   • اگر صف اول خالی است، از صف دوم گره را خارج کن.
   • در غیر این صورت، جلوی هر دو صف را بررسی کن و کمترین مقدار را از صف خارج کن.
4. یک گره داخلی جدید با تکراری برابر با مجموعه تکرار دو گره را بساز. اولین گره خارج شده از صف را به عنوان فرزند سمت چپ و دومین گره خارج شده از صف را به عنوان فرزند سمت راست قرار بده. این گره را در دومین صف قرار بده.
5. گام ۳ و ۴ را تا زمانی که بیش از یک گره در صف قرار دارد تکرار کن. گره باقی‌مانده گره ریشه و درخت کامل است.

کدگذاری هافمن (Huffman) برای ورودی های مرتب در ++C

کدگذاری هافمن (Huffman) برای ورودی های مرتب در C

خروجی قطعه کدهای بالا، برای ورودی‌های {'a', 'b', 'c', 'd', 'e', 'f'} با تعداد تکرار  $${5, 9, 12, 13, 16, 45}$$ به صورت زیر است.

f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111

پیچیدگی زمانی این روش از درجه (O(n است. اگر ورودی مرتب شده نباشد، باید آن را پیش از پردازش، مرتب‌سازی کرد.

مرتب‌سازی می‌تواند با استفاده از «مرتب‌سازی هرمی» (Heap-Sort) یا «مرتب‌سازی ادغامی» (Merge-Sort) انجام شود که هر دو از درجه (Theta(nlogn هستند. بنابراین، پیچیدگی زمانی کلی، برای ورودی مرتب نشده از درجه (O(nlogn خواهد بود.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده
• الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
• الگوریتم پریم — به زبان ساده

^^