در این پست به شما نشان می‌دهم که الگوریتم هافمن چگونه کار می‌کند. همچنین در پایان کد پایتون الگوریتم هافمن را نیز تقدیم خواهم کرد.

تکنیک کدگذاری هافمن برای فشرده‌سازی داده‌ها و کاهش حجم(اندازه) آنها بدون از دست رفتن جزییات استفاده می‌شود. این تکنیک اولین بار توسط دیوید هافمن ارائه و توسعه داده شده است. به طور معمول این شیوه کدگذاری برای فشرده‌سازی داده‌هایی مناسب است که کاراکترهای تکراری داشته باشد.

کد گذاری هافمن چگونه کار می‌کند؟

فرض کنید که قصد داریم رشته‌ی زیر را به یک شبکه ارسال کنیم:

الگوریتم هافمن - رشته اولیه
رشته اولیه

هر کاراکتر این رشته ۸ بیت فضا را اشغال می‌کند. این رشته نیز دارای ۱۵ کاراکتر است. لذا برای ارسال این رشته به ۱۲۰ بیت فضا نیاز است. اما با استفاده از تکنیک کدگذاری هافمن می‌توانیم این رشته را با سایز کوچکتری ارسال کرد.

در شیوه کدگذاری هافمن ابتدا درختی با استفاده از تعداد تکرار کاراکترها ایجاد می‌شود سپس کد مربوط به هر کاراکتر تولید می‌شود. زمانی‌که داده‌ها توسط این درخت کدگذاری می‌شوند برای رمزگشایی آنها نیز از همین درخت استفاده خواهد شد. در این شیوه‌ی کدگذاری هیچ کدام از رمزها پیشوند یکسانی ندارند؛ پس در رمزگشایی کاراکترها نیز ابهامی نخواهد بود. درخت تکرار هافمن از ایجاد پیشوندهای تکراری جلوگیری می‌کند.

گام‌های کدگذاری هافمن

کدگذاری هافمن به کمک گامهای زیر انجام می‌شود:

  1. ابتدا تعداد تکرار هر کاراکتر در رشته را محاسبه کنید.
کد پایتون الگوریتم هافمن - شمارش تکرارها
تعداد تکرار کاراکترها
  1. کاراکترها را براساس تعداد تکرار آنها به صورت صعودی مرتب کنید. آنها را در صف اولویت Q ذخیره کنید.
کد پایتون الگوریتم هافمن - مرتب سازی
مرتب سازی لیست تعداد تکرارها
  1. هر کاراکتر را به عنوان یک برگ در نظر بگیرید.
  2. یک نود(گره) خالی به عنوان z ایجاد کنید. کمترین تکرار را به عنوان فرزند چپ و دومین تکرار(از نظر کوچکی) را به عنوان فرزند راست z در نظر بگیرید. مقدار z نیز برابر با حاصل‌جمع دو فرزند چپ و راست آن می‌باشد.
کد پایتون الگوریتم هافمن - ساخت گره ها
محاسبه جمع کوچکترین تکرارها
  1. دو مقدار استفاده شده در گام ۴ را از صف(فهرست) Q حذف کنید و جمع آن دو را به فهرست تکرار اضافه کنید.(به شکل بالا توجه کنید.)
  2. نود z را درون درخت قرار دهید.
  3. گام‌های ۳ تا ۵ را برای تمامی کاراکترها تکرار کنید.
کد پایتون الگوریتم هافمن - تکرار الگوریتم
تکرار گام‌های ۳ تا ۵ برای تمامی کاراکترها
کد پایتون الگوریتم هافمن - تکرار گامها
تکرار گام‌های ۳ تا ۵ برای تمامی کاراکترها
  1. در پایان برای کدگذاری کاراکترها، از ریشه درخت حرکت می‌کنیم به سمت برگ متعلق به آن کاراکتر، در صورتی که به سمت چپ رفتیم عدد 0و اگر به سمت راست رفتیم عدد 1را نسبت می‌دهیم.(به یال چپ 0 و به یال راست 1 دهید.)
کد پایتون الگوریتم هافمن - شماره گذاری یالها
به یالهای سمت چپ عدد صفر و یالهای راست عدد یک داده می‌شود

جدول زیر کاراکتر، تعداد تکرار، کد هافمن و سایز را مشخص می‌کند.

اندازهکدتعداد تکرارکاراکتر
5*2=1011۵A
1*3=3100۱B
6*1=60۶C
3*3=9101۳D
28bits15bits4*8=32bits

مشاهده کردید که بدون فشرده‌سازی برای ارسال این رشته ۱۲۰ بیت نیاز بود، اما پس از فشرده‌سازی با الگوریتم هافمن برای ارسال این رشته تنها به 32+15+28 = 75بیت نیاز است.

رمزگشایی کد هافمن

برای رمزگشایی کد هافمن از پیمایش همان درخت کدگذاری استفاده می‌شود. برای مثال فرض کنید که میخواهیم در مثال بالا کد ۱۰۱ را رمزگشایی کنیم؛ در این صورت باید درخت را به صورت زیر پیمایش کنیم تا به کاراکتر D برسیم.

کد پایتون الگوریتم هافمن - رمزگشایی
رمزگشایی کد هافمن ۱۰۱ با استفاده از درخت کدگذاری

الگوریتم هافمن

با توجه به توضیحات بالا الگوریتم هافمن را می‌توان به صورت زیر بیان کرد:

create a priority queue Q consisting of each unique character.
sort then in ascending order of their frequencies.
for all the unique characters:
    create a newNode
    extract minimum value from Q and assign it to leftChild of newNode
    extract minimum value from Q and assign it to rightChild of newNode
    calculate the sum of these two minimum values and assign it to the value of newNode
    insert this newNode into the tree
return rootNode

کد پایتون الگوریتم هافمن نیز به صورت زیر است:

پیچیدگی زمانی الگوریتم هافمن

استخراج حداقل تکرارها از صف اولویت 2(n-1) بار انجام می‌شود که مرتبه‌ی زمانی آن lg(n) است. بنابراین مرتبه زمانی کل الگوریتم هافمن nlg(n) می‌باشد.

امیدوارم این پست از webpy برای شما مفید بوده باشد. این کد از طریق سایت گیت هاب نیز قابل دسترس و توسعه دادن است. نظرات و انتقادات شما را برای بهتر شدن به دیده منت می‌گذارم.

برچسب گذاری شده در:

,