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

الگوریتم کدگذاری هافمن (Huffman Coding Algorithm) یک روش موثر برای فشرده‌سازی داده‌ها است. این الگوریتم در سال 1952 توسط دیوید هافمن، دانشجوی دکتری دانشگاه MIT، ابداع شد. اصلی‌ترین کاربرد آن در فشرده‌سازی داده‌ها و ارتباطات دیجیتال است. در اینجا به توضیح کامل این الگوریتم می‌پردازیم:

مفهوم اصلی

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

مراحل الگوریتم

۱. شمارش فراوانی:

• ابتدا، فراوانی هر کاراکتر در داده‌ها شمرده می‌شود.

۲. ساخت درخت هافمن:

• برای هر کاراکتر یک گره درخت ایجاد می‌شود.
• گره‌ها بر اساس فراوانی‌هایشان مرتب می‌شوند.
• دو گره با کمترین فراوانی انتخاب شده و یک گره جدید ایجاد می‌کنند که فراوانی آن برابر با مجموع فراوانی‌های دو گره فرزند است.
• این فرآیند تا زمانی که تنها یک گره باقی بماند (ریشه درخت) ادامه می‌یابد.
  

۳. تولید کدهای هافمن:

• از ریشه درخت شروع کرده، به هر گره فرزند یک بیت اختصاص می‌دهیم (معمولاً 0 برای چپ و 1 برای راست).
• هر کاراکتر با مسیری از ریشه تا گره مربوط به خود کدگذاری می‌شود.
  

مثال

بیایید یک مثال ساده از پیاده‌سازی الگوریتم هافمن را بررسی کنیم. فرض کنید متنی داریم که می‌خواهیم آن را با استفاده از الگوریتم هافمن فشرده‌سازی کنیم. متن ما این است: "BACADAEAFABBBAGAH"

ابتدا فراوانی هر کاراکتر را محاسبه می‌کنیم:

• A: 7 بار
• B: 4 بار
• C: 1 بار
• D: 1 بار
• E: 1 بار
• F: 1 بار
• G: 1 بار
• H: 1 بار

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

در نهایت، کد هر کاراکتر با توجه به مسیری که از ریشه درخت تا گره مربوط به آن کاراکتر طی می‌کند، تعیین می‌شود. برای سادگی، فرض می‌کنیم که رفتن به سمت چپ در درخت نشان‌دهنده 0 و رفتن به سمت راست نشان‌دهنده 1 است.

فرض کنید که درخت هافمن ما به این شکل باشد (این تنها یکی از چندین روش ممکن برای ساخت درخت است):

در این مثال، کد هر کاراکتر به شکل زیر خواهد بود:

• A: 0
• B: 10
• C: 1100
• D: 1101
• E: 1110
• F: 1111

بنابراین، متن اصلی "BACADAEAFABBAAAGAH" با استفاده از کدهای هافمن به شکل زیر فشرده‌سازی می‌شود:

این مثال نشان می‌دهد که چگونه الگوریتم هافمن می‌تواند برای فشرده‌سازی داده‌ها استفاده شود. البته، در عمل، پیاده‌سازی‌های واقعی این الگوریتم ممکن است پیچیده‌تر باشند و شامل جزئیات بیشتری برای مدیریت انواع داده‌ها و شرایط مختلف باشند.

کد پایتون

ابتدا، کلاس‌های لازم برای نمایش گره‌های درخت و خود درخت هافمن را تعریف می‌کنیم:

import heapq
import collections


class Node:
 def __init__(self, char, freq):
 self.char = char
 self.freq = freq
 self.left = None
 self.right = None

 # برای استفاده در heapq، تعریف مقایسه بر اساس فرکانس
 def __lt__(self, other):
 return self.freq < other.freq


def calculate_frequencies(text):
 return collections.Counter(text)


def build_huffman_tree(text):
    frequencies = calculate_frequencies(text)
    priority_queue = [Node(char, freq) for char, freq in frequencies.items()]
    heapq.heapify(priority_queue)

 while len(priority_queue) > 1:
        left = heapq.heappop(priority_queue)
        right = heapq.heappop(priority_queue)

        merged = Node(None, left.freq + right.freq)
        merged.left = left
        merged.right = right

        heapq.heappush(priority_queue, merged)

 return priority_queue[0]


def build_codes(node, prefix=&quot&quot, codebook={}):
 if node is not None:
 if node.char is not None:
            codebook[node.char] = prefix
        build_codes(node.left, prefix + &quot0&quot, codebook)
        build_codes(node.right, prefix + &quot1&quot, codebook)
 return codebook


def huffman_encoding(text):
    root = build_huffman_tree(text)
    codebook = build_codes(root)
 return ''.join(codebook[char] + '-' for char in text)


# متن مورد نظر برای کدگذاری
text = &quotBACADAEAFABBAAAGAH&quot
encoded_text = huffman_encoding(text)
print(&quotEncoded Text:&quot, encoded_text)

این کد ابتدا فرکانس هر کاراکتر در متن را محاسبه می‌کند، سپس یک درخت هافمن بر اساس این فرکانس‌ها می‌سازد. در نهایت، با استفاده از این درخت، متن را کدگذاری می‌کند.

توجه داشته باشید که کدهای تولید شده برای هر کاراکتر ممکن است با مثال قبلی متفاوت باشد، زیرا ساختار دقیق درخت هافمن می‌تواند بسته به نحوه پیاده‌سازی متفاوت باشد. خروجی کد بالا برای مثال قبل:

ویژگی‌ها و مزایا

• کدگذاری متغیر طول: در مقابل کدگذاری ثابت طول (مانند ASCII)، هافمن کدگذاری متغیر طول ارائه می‌دهد که باعث می‌شود کاراکترهای پرتکرار با کدهای کوتاه‌تر و کاراکترهای کمتکرار با کدهای بلندتر نمایش داده شوند.
• بهینه‌سازی فضای ذخیره‌سازی: با استفاده از این روش، می‌توان حجم داده‌ها را بدون از دست دادن اطلاعات کاهش داد.
• بدون از دست دادن داده: این یک روش فشرده‌سازی بدون از دست دادن داده است، به این معنی که داده‌های اصلی می‌توانند دقیقاً بازیابی شوند.

کاربردها

• فشرده‌سازی فایل‌ها: در فرمت‌های فشرده‌سازی مانند ZIP و GZIP.
• ارتباطات دیجیتال: برای کاهش پهنای باند مورد نیاز.
• پردازش تصویر و صدا: به خصوص در فرمت‌هایی که از فشرده‌سازی بدون از دست دادن داده استفاده می‌کنند.

محدودیت‌ها

• کارایی با داده‌های با فراوانی متغیر: اگر فراوانی کاراکترها در داده‌ها به طور قابل توجهی تغییر کند، کدگذاری هافمن ممکن است بهینه نباشد.
• نیاز به پیش‌پردازش: برای ساخت درخت هافمن، ابتدا باید تمام داده‌ها پردازش شوند.