AlgoVerse

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

برای هر نماد کدی دودویی می‌سازد که نمادهای پرتکرار کد کوتاه‌تری بگیرند: هر بار دو درخت سبک‌تر را زیر یک ریشه جمع می‌کند.

با کد ثابت، هر نماد از الفبای k تایی ⌈log₂ k⌉ بیت می‌گیرد. اگر بعضی نمادها خیلی پرتکرارتر باشند، بهتر است کد کوتاه‌تری بگیرند. کد باید پیشوندی باشد (هیچ کدی پیشوند کد دیگر نباشد) تا بشود بدون جداکننده خواندش؛ هر کد پیشوندی یک درخت دودویی است.

ادامه‌ی توضیح ↓
ورودی:
text="aaaaaaaaaaaa…"خروجی PDF

فراوانی‌های کتاب CLRS (a:45، b:13، c:12، d:16، e:9، f:5) در متنی به طول ۱۰۰؛ کد کل ۲۲۴ بیت می‌شود، در برابر ۳۰۰ بیت با کد ثابت ۳ بیتی.

  1. import heapq
  4. class Node:
  5. def __init__(self, key, symbol=None, left=None, right=None):
  6. self.key = key # what the picture shows: "a:5" for a leaf, the total count inside
  7. self.symbol = symbol
  8. self.left = left
  9. self.right = right
  12. def huffman(text):
  13. freq = {}
  14. for ch in text:
  15. freq[ch] = freq.get(ch, 0) + 1
  16. # A min-heap of (count, order, tree); the order breaks ties, so every run builds the same tree.
  17. heap = []
  18. for ch in sorted(freq):
  19. name = "␣" if ch == " " else ch
  20. heap.append((freq[ch], len(heap), Node(f"{name}:{freq[ch]}", ch)))
  21. heapq.heapify(heap)
  22. order = len(heap)
  23. root = None
  24. while len(heap) > 1:
  25. f1, _, a = heapq.heappop(heap)
  26. f2, _, b = heapq.heappop(heap)
  27. root = Node(str(f1 + f2), None, a, b)
  28. heapq.heappush(heap, (f1 + f2, order, root))
  29. order = order + 1
  30. root = heap[0][2] if heap else None
  31. codes = {}
  32. if root is not None:
  33. assign(root, "", codes)
  34. rows = [("␣" if ch == " " else ch, freq[ch], codes[ch]) for ch in sorted(freq)]
  35. bits = sum(freq[ch] * len(codes[ch]) for ch in freq)
  36. return bits
  39. def assign(node, prefix, codes):
  40. if node.left is None:
  41. code = prefix if prefix else "0" # a lone symbol still needs one bit
  42. codes[node.symbol] = code
  43. return
  44. assign(node.left, prefix + "0", codes)
  45. assign(node.right, prefix + "1", codes)

ناوردا: دو نماد کم‌تکرارتر در یک کد بهینه همیشه می‌توانند برادر و در پایین‌ترین سطح باشند؛ پس جمع کردن آن دو اول، به جواب بهینه می‌رسد.

شروع اجرا

∅

bits—

جدول هنوز خالی است.

درخت فراخوانی‌های بازگشتی

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

متغیرهای محلی

text'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbccccccccccccddddddddddddddddeeeeeeeeefffff'

نارنجی = در همین گام عوض شد

Call stack

  1. huffman()خط 12
گام ۱ از ۳۶۹
خط سیاه = merge · خط نارنجی = گام کلیدیcounted: 0/1 · merge: 0/5 · code: 0/6 · total_bits: 0/1
    توضیح

    ایده

    با کد ثابت، هر نماد از الفبای k تایی ⌈log₂ k⌉ بیت می‌گیرد. اگر بعضی نمادها خیلی پرتکرارتر باشند، بهتر است کد کوتاه‌تری بگیرند. کد باید پیشوندی باشد (هیچ کدی پیشوند کد دیگر نباشد) تا بشود بدون جداکننده خواندش؛ هر کد پیشوندی یک درخت دودویی است.

    الگوریتم حریصانه

    1. هر نماد یک درخت تک‌گره با وزن فراوانی‌اش است.
    2. هر بار دو درخت سبک‌تر را بردار و زیر یک ریشه‌ی تازه (با وزن جمعشان) قرار بده.
    3. وقتی یک درخت ماند، مسیر هر برگ (چپ = ۰، راست = ۱) کد آن است.

    چرا بهینه است؟

    دو نماد کم‌تکرارتر را همیشه می‌شود در عمیق‌ترین سطح و کنار هم گذاشت بی‌آنکه کد بدتر شود؛ پس جمع کردنشان اول امن است و بقیه همان مسئله با یک نماد کمتر است.

    در trace به چه چیزی نگاه کنی

    • تصویر آخرین درخت ساخته‌شده را نشان می‌دهد که مدام بزرگ‌تر می‌شود؛ جدول در پایان نماد، فراوانی و کد را دارد.