کد Huffman با پایتون؛ درختِ پیشوندی، هزینهٔ بیت و رمزگشایی

در ثبتِ رویدادهای مهندسی، همهٔ نمادها الزاماً به یک اندازه تکرار نمی‌شوند. کدِ طول‌متغیر می‌تواند برای نمادِ پرتکرار مسیرِ کوتاه‌تری بسازد، اما صرفِ کوتاه شدنِ یک رشته، قالبِ فایلِ کامل یا گیرندهٔ قابل اعتماد نمی‌سازد. این درس کد Huffman را با فراوانی‌های تألیفی، مرجع مستقلِ هزینه و رمزگشای بیت‌های دقیق می‌سنجد؛ هیچ دادهٔ محصول یا نسبتِ فشرده‌سازیِ اندازه‌گیری‌شدهٔ واقعی نداریم.

۱. فراوانیِ نماد و هزینهٔ بیت

چهار برچسبِ A، B، C و D را با تعدادهای پنج، دو، یک و یک می‌گیریم. این اعداد شمارِ رخدادند، نه ولتاژ یا احتمالِ تخمین‌زده‌شدهٔ فرایند. برای چهار نماد، کدِ ثابتِ دوبیتی به نه رخداد، هجده بیتِ محموله می‌دهد. هدفِ مورد مقایسه، مجموعِ تعدادِ هر نماد ضرب‌در طولِ کدِ همان نماد است؛ هزینهٔ جدول و قالبِ انتقال هنوز در آن نیست.

بخشِ ساختِ درختِ Huffman در درس Cornell، ادغامِ دو وزنِ کمینه را توضیح می‌دهد. وزنِ یک گرهٔ داخلی برابر مجموعِ وزنِ دو فرزند است. با تکرارِ ادغام، یک درخت باقی می‌ماند و مسیرهای ریشه تا برگ، کدِ نمادها می‌شوند. اینجا نمونه، زبانِ اجرا و قراردادِ رمزگشای خودمان را داریم؛ فایل‌ها یا مثالِ درسِ آن دانشگاه را بازسازی نمی‌کنیم.

برای حداقل دو نماد با وزنِ مثبت، معیارِ بهینگی به کدهای دودوییِ پیشوندی برای همین الفبا و همین وزن‌ها مربوط است. از آن کمینه بودنِ فایلِ نهایی، برتری بر هر روشِ فشرده‌سازی یا بهترین نمایشِ هر پیامِ تازه نتیجه نمی‌گیریم. اگر فراوانیِ کاربرد عوض شود، میانگینِ طولِ دیده‌شده نیز می‌تواند تغییر کند؛ این کد مدلِ تطبیقیِ جریانی نیست.

نماد در رابطِ ما یک برچسبِ رشته‌ایِ غیرخالی است و می‌تواند چند نویسه داشته باشد. فهرستِ نمادها را می‌گیریم، نه متنی که مرزِ واژه‌هایش حدس زده شود. ترتیبِ یونیکد برای قطعی کردنِ ساخت کافی است و مقایسهٔ زبانیِ فارسی نیست. تعدادِ مقدارهای یک بایت را نیز با تعریفِ ASCII یکی نمی‌گیریم؛ این برنامه به الفبای بایتیِ خاص محدود نشده است.

۲. درختِ پیشوندی و تساویِ وزن‌ها

پیشوندی بودن یعنی کدِ هیچ نمادی، آغازِ کدِ نمادِ دیگری نیست. بخش‌های ۳٫۲٫۱ و ۳٫۲٫۲ در RFC 1951، رمزگشاییِ مسیرهای درخت و قواعدِ افزودهٔ قالبِ DEFLATE را جدا توضیح می‌دهند. برنامهٔ حاضر قواعدِ کدِ متعارف و قالبِ DEFLATE را پیاده نمی‌کند؛ دانستنِ طول‌ها، به‌تنهایی جدولِ اختصاصیِ ما را جایگزین نمی‌کند.

در صفِ اولویت، کلیدِ نخست وزن و کلیدِ دوم شمارهٔ ساختِ یکتاست. برگ‌ها ابتدا با ترتیبِ نامِ نماد وارد می‌شوند و گره‌های تازه شماره‌های بعدی می‌گیرند. نخستین گرهٔ برداشته‌شده فرزندِ صفر و دومی فرزندِ یک می‌شود. با این سیاست، ترتیبِ درج در دیکشنری نتیجه را عوض نمی‌کند. این سیاستِ خودمان است؛ وجودِ چند کدِ هم‌هزینه را انکار نمی‌کند.

در مثال، ابتدا C و D با وزنِ یک ادغام می‌شوند. سپس B با وزنِ دو، پیش از گرهٔ تازهٔ هم‌وزن قرار می‌گیرد و آن دو ترکیب می‌شوند. سرانجام وزنِ چهار با A دارای وزنِ پنج ادغام می‌شود. کدها به ترتیب A برابر یک، B برابر صفرصفر، C برابر صفر‌یک‌صفر و D برابر صفر‌یک‌یک‌اند؛ جای شاخه‌های صفر و یک را نباید از یک تصویرِ مفهومی حدس زد.

سهمِ هزینه‌ها پنج، چهار، سه و سه بیت است؛ جمع پانزده و میانگین پنج‌سوم بیت بر نماد می‌شود. برای این چهار کد، مجموعِ دو به توانِ منفیِ طول‌ها برابر یک است و بررسیِ جداگانهٔ هر جفت نیز نبودِ رابطهٔ پیشوند را تأیید می‌کند. تساویِ هزینه، الزاماً تساویِ بیت‌های کد با یک پیاده‌سازیِ دیگر نیست؛ برای تبادل باید جدولِ مشترک معلوم باشد.

۳. کد کاملِ کدگذار و رمزگشا

سازنده، دیکشنریِ غیرخالیِ برچسب‌های رشته‌ای و وزن‌های صحیحِ مثبت می‌خواهد؛ وزنِ صفر یا منفی، بولی و float رد می‌شوند. وزن‌ها به احتمال تبدیل یا گرد نمی‌شوند. سقفِ کوچکِ دلخواه برای شمارِ نمادها نداریم، اما نگه‌داریِ درخت و رشته‌های کد هزینهٔ حافظه دارد؛ این اجرای آموزشی، فشرده‌سازِ صنعتی یا آزمونِ مصرفِ حافظه نیست.

کدگذار، فهرست یا تاپلِ کاملِ نمادهای شناخته‌شده را به رشتهٔ دقیقِ صفر و یک تبدیل می‌کند. رمزگشا همان جدول را می‌گیرد و تا پایانِ هر کلمهٔ کد پیش می‌رود. ورودیِ غیرِ دودویی یا پایان در میانهٔ کد رد می‌شود. پیشوندِ سالمِ یک قابِ خراب به‌عنوان نتیجهٔ جزئی برگردانده نمی‌شود؛ این رابط، رمزگشای جریانی با حالتِ ادامه نیست.

"""Logical Huffman bitstrings with explicit codebook; not a packed-file format."""
from functools import lru_cache
from fractions import Fraction
from itertools import count,product
import heapq
import json
import platform


def build_code(frequencies):
    if type(frequencies)is not dict or not frequencies:
        raise ValueError('nonempty dict of positive integer symbol weights required')
    if any(type(s)is not str or not s for s in frequencies):
        raise ValueError('nonempty exact string symbol labels required')
    if any(type(w)is not int or w<=0 for w in frequencies.values()):
        raise ValueError('positive actual integer weights, not bool')
    serial=count();heap=[]
    for symbol in sorted(frequencies):
        heapq.heappush(heap,(frequencies[symbol],next(serial),(symbol,None,None)))
    while len(heap)>1:
        wa,_,left=heapq.heappop(heap);wb,_,right=heapq.heappop(heap)
        heapq.heappush(heap,(wa+wb,next(serial),(None,left,right)))
    codes={};stack=[(heap[0][2],'')]
    while stack:
        node,prefix=stack.pop();symbol,left,right=node
        if symbol is not None:codes[symbol]=prefix or '0'
        else:stack.extend([(right,prefix+'1'),(left,prefix+'0')])
    return {s:codes[s] for s in sorted(codes)}


def checked_code(codes):
    if type(codes)is not dict or not codes:raise ValueError('nonempty codebook dict required')
    if any(type(s)is not str or not s or type(bits)is not str or not bits or set(bits)-{'0','1'} for s,bits in codes.items()):
        raise ValueError('nonempty symbol strings and binary nonempty codewords required')
    words=sorted(codes.values())
    if any(b.startswith(a) for a,b in zip(words,words[1:])):
        raise ValueError('duplicate codeword or prefix ambiguity')
    return dict(codes)


def encode(symbols,codes):
    table=checked_code(codes)
    if type(symbols)not in (list,tuple):raise ValueError('whole symbol list/tuple required')
    if any(type(s)is not str or s not in table for s in symbols):raise ValueError('unknown symbol or invalid symbol type')
    return ''.join(table[s] for s in symbols)


def decode(bits,codes):
    table=checked_code(codes)
    if type(bits)is not str or set(bits)-{'0','1'}:raise ValueError('exact binary string required')
    reverse={word:symbol for symbol,word in table.items()}
    prefixes={word[:i] for word in reverse for i in range(1,len(word))}
    result=[];pending=''
    for bit in bits:
        pending+=bit
        if pending in reverse:
            result.append(reverse[pending]);pending=''
        elif pending not in prefixes:raise ValueError('not a valid codeword prefix')
    if pending:raise ValueError('frame ends inside a codeword')
    return tuple(result)


def weighted_bits(frequencies,codes):
    return sum(weight*len(codes[symbol]) for symbol,weight in frequencies.items())


def partition_optimum(weights):
    """All proper root splits of leaves; no greedy merge/heap/code construction."""
    @lru_cache(None)
    def cost(mask):
        if mask & (mask-1)==0:return 0
        total=sum(w for i,w in enumerate(weights) if mask>>i&1)
        anchor=mask & -mask;best=None;subset=(mask-1)&mask
        while subset:
            if subset & anchor and subset!=mask:
                value=cost(subset)+cost(mask^subset)
                best=value if best is None else min(best,value)
            subset=(subset-1)&mask
        return total+best
    if len(weights)<2:raise ValueError('oracle excludes single-symbol empty-code convention')
    return cost((1<<len(weights))-1)


def fails(function,*args):
    try:function(*args)
    except ValueError:return True
    return False


def run():
    checks={}
    def check(name,passed):checks[name]=bool(passed);assert checks[name],name
    frequencies={'A':5,'B':2,'C':1,'D':1};codes=build_code(frequencies)
    check('literal_codewords_with_declared_serial_ties',codes=={'A':'1','B':'00','C':'010','D':'011'})
    message=('A',)*5+('B',)*2+('C','D');bits=encode(message,codes)
    check('literal_payload_and_weighted_cost',bits=='111110000010011' and len(bits)==weighted_bits(frequencies,codes)==15 and 2*len(message)==18)
    kraft=sum(Fraction(1,2**len(word)) for word in codes.values())
    check('pairwise_prefix_independence_and_Kraft_sum',all(not b.startswith(a) for i,a in enumerate(codes.values()) for j,b in enumerate(codes.values()) if i!=j) and kraft==1)
    cases=0
    for n in range(2,6):
        alphabet=tuple(chr(65+i) for i in range(n))
        for weights in product((1,2,3),repeat=n):
            data=dict(zip(alphabet,weights,strict=True));book=build_code(data)
            assert weighted_bits(data,book)==partition_optimum(weights)
            cases+=1
    check('subset_partition_optimum_360_weight_sets_ONE_group',cases==360)
    roundtrips=0
    for n in range(6):
        for symbols in product(tuple(frequencies),repeat=n):
            assert decode(encode(symbols,codes),codes)==symbols;roundtrips+=1
    check('whole_frame_roundtrips_1365_messages_ONE_group',roundtrips==1365)
    single=build_code({'idle':7})
    check('single_symbol_has_one_bit_not_empty_word',single=={'idle':'0'} and encode(('idle',)*3,single)=='000' and decode('000',single)==('idle',)*3 and fails(decode,'1',single))
    check('empty_frame_valid_but_empty_alphabet_invalid',encode((),codes)=='' and decode('',codes)==() and fails(build_code,{}))
    reversed_weights=dict(reversed(tuple(frequencies.items())))
    check('dictionary_insertion_order_does_not_set_ties',build_code(reversed_weights)==codes and build_code({'b':1,'a':1})=={'a':'0','b':'1'})
    triple={s:3*w for s,w in frequencies.items()}
    check('common_weight_scale_keeps_code_and_scales_cost',build_code(triple)==codes and weighted_bits(triple,codes)==45)
    check('same_codebook_frame_concatenation_at_codeword_boundary',encode(('A','C'),codes)+encode(('B','D'),codes)==encode(('A','C','B','D'),codes))
    check('unknown_symbols_and_input_types_rejected',fails(encode,('missing',),codes) and fails(encode,('A',False),codes) and fails(encode,'AB',codes))
    check('invalid_frequency_types_and_signs_rejected',all(fails(build_code,v) for v in ({'A':0},{'A':-1},{'A':True},{'A':1.0},{'':1},{1:1},[('A',1)])))
    check('nonprefix_duplicate_and_empty_codebooks_rejected',all(fails(decode,'',book) for book in ({'A':'0','B':'01'},{'A':'0','B':'0'},{'A':''},{'A':'2'},{})))
    check('malformed_bits_and_incomplete_last_codeword_rejected',all(fails(decode,b,codes) for b in ('0','01','10x',b'1',True)))
    padded=decode('11000000',codes)
    check('zero_padding_without_bit_length_can_add_valid_symbols',decode('11',codes)==('A','A') and padded==('A','A','B','B','B'))
    check('bit_flip_can_be_valid_but_wrong_symbol',decode('010',codes)==('C',) and decode('011',codes)==('D',))
    before=dict(frequencies);before_codes=dict(codes);encode(message,codes);decode(bits,codes)
    check('inputs_not_mutated_and_new_codebooks_are_fresh',frequencies==before and codes==before_codes and build_code(frequencies)is not codes)
    return {'python':platform.python_version(),'dependencies':'stdlib only','weights_are_occurrence_counts':frequencies,'codebook':codes,'logical_bitstring':bits,'logical_payload_bits':len(bits),'fixed_four_symbol_payload_bits':18,'weighted_average_bits_per_symbol':str(Fraction(15,9)),'Kraft_sum':str(kraft),'single_symbol_codebook':single,'padding_counterexample_decoded':padded,'format':'Exact logical 01 string with separately shared codebook; no byte packing/padding/header/EOF/DEFLATE format','independent_optimum_weight_sets_in_ONE_group':cases,'roundtrip_messages_in_ONE_group':roundtrips,'checks':checks}


if __name__=='__main__':print(json.dumps(run(),ensure_ascii=False,indent=2,allow_nan=False))

برای الفبای تک‌نمادی، به‌طور قراردادی کدِ صفر می‌دهیم؛ پس سه رخدادِ idle رشتهٔ سه‌صفر می‌سازند. کدِ تهی نمی‌دهیم، چون بدون شمارندهٔ بیرونی، تعدادِ رخدادها در آن گم می‌شود. ادعای بهینه بودنِ هزینهٔ درخت برای دو نماد و بیشتر را بی‌تغییر به این قراردادِ تک‌نمادی تعمیم نمی‌دهیم؛ انتخابِ کدِ تهی با طولِ پیامِ بیرونی مسئلهٔ دیگری است.

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

۴. مرجعِ تقسیمِ مجموعه و هزینهٔ بهینه

رفت‌وبرگشت به‌تنهایی کافی نیست، چون دو تابع می‌توانند اشتباهِ مشترک داشته باشند. مرجعِ مستقلِ هزینه، به‌جای ادغامِ حریصانه، همهٔ تقسیم‌های ممکنِ مجموعهٔ برگ‌ها به دو زیرمجموعهٔ ناتهی را بررسی می‌کند. برای هر تقسیم، هزینهٔ بهینهٔ دو زیر‌درخت به‌اضافهٔ مجموعِ وزنِ همهٔ برگ‌ها محاسبه می‌شود؛ یک بیتِ افزوده برای هر مسیر، همین جملهٔ آخر را می‌سازد.

این بازگشت با حافظه‌گذاری فقط برای fixtureهای کوچک اجرا می‌شود و جایگزینِ پیشنهادیِ الگوریتمِ اصلی برای الفبای بزرگ نیست. سیصدوشصت بردارِ وزنِ مثبت با دو تا پنج نماد، در یک گروه با هزینهٔ Huffman مقایسه شده‌اند. مرجع از heap، ترتیبِ ادغامِ تابع یا جدولِ ساخته‌شده برای تعیینِ جوابِ بهینه استفاده نمی‌کند؛ همهٔ هزینه‌ها صحیح و بدون تلورانسِ شناورند.

شاهدِ بیتِ دقیق نیز داریم: پنج A، دو B، سپس C و D رشتهٔ پانزده‌بیتیِ ثبت‌شده را می‌دهند. هزاروسیصدوشصت‌وپنج پیام با طولِ صفر تا پنج روی همین چهار نماد، در یک گروه رفت‌وبرگشت شده‌اند. کنترلِ پیشوندِ جفتی و مرجعِ هزینه، شاهدهای جدا از سازنده و گیرندهٔ مشترک‌اند؛ هیچ‌کدام پوششِ همهٔ خطاهای برنامه یا همهٔ پیام‌های ممکن معرفی نمی‌شود.

{
  "python": "3.14.5",
  "dependencies": "stdlib only",
  "weights_are_occurrence_counts": {
    "A": 5,
    "B": 2,
    "C": 1,
    "D": 1
  },
  "codebook": {
    "A": "1",
    "B": "00",
    "C": "010",
    "D": "011"
  },
  "logical_bitstring": "111110000010011",
  "logical_payload_bits": 15,
  "fixed_four_symbol_payload_bits": 18,
  "weighted_average_bits_per_symbol": "5/3",
  "Kraft_sum": "1",
  "single_symbol_codebook": {
    "idle": "0"
  },
  "padding_counterexample_decoded": [
    "A",
    "A",
    "B",
    "B",
    "B"
  ],
  "format": "Exact logical 01 string with separately shared codebook; no byte packing/padding/header/EOF/DEFLATE format",
  "independent_optimum_weight_sets_in_ONE_group": 360,
  "roundtrip_messages_in_ONE_group": 1365,
  "checks": {
    "literal_codewords_with_declared_serial_ties": true,
    "literal_payload_and_weighted_cost": true,
    "pairwise_prefix_independence_and_Kraft_sum": true,
    "subset_partition_optimum_360_weight_sets_ONE_group": true,
    "whole_frame_roundtrips_1365_messages_ONE_group": true,
    "single_symbol_has_one_bit_not_empty_word": true,
    "empty_frame_valid_but_empty_alphabet_invalid": true,
    "dictionary_insertion_order_does_not_set_ties": true,
    "common_weight_scale_keeps_code_and_scales_cost": true,
    "same_codebook_frame_concatenation_at_codeword_boundary": true,
    "unknown_symbols_and_input_types_rejected": true,
    "invalid_frequency_types_and_signs_rejected": true,
    "nonprefix_duplicate_and_empty_codebooks_rejected": true,
    "malformed_bits_and_incomplete_last_codeword_rejected": true,
    "zero_padding_without_bit_length_can_add_valid_symbols": true,
    "bit_flip_can_be_valid_but_wrong_symbol": true,
    "inputs_not_mutated_and_new_codebooks_are_fresh": true
  }
}

هفده گروهِ نام‌دار با Python 3.14.5 و کتابخانهٔ استاندارد اجرا شده‌اند. کدِ بایتیِ Cornell، قالبِ RFC یا کتابخانهٔ فشرده‌سازی اجرا نشده است. رشتهٔ پایتونیِ صفر و یک، در حافظه واقعاً یک بیت برای هر نویسه مصرف نمی‌کند؛ عددِ پانزده، طولِ منطقیِ محموله است. هزینهٔ جدول، پایانِ پیام، چیدمانِ بایت‌ها و سربارِ یک فایل هنوز باید در قالبی جدا تعریف شوند.

تفاوت با کدِ تصحیحِ تک‌بیتِ Hamming بنیادی است: اینجا هدف کوتاه‌کردنِ نمایشِ منبع است. تغییرِ آخرین بیتِ کدِ C، کدِ معتبرِ D می‌سازد و رمزگشا خطا نمی‌دهد. بررسیِ CRC بستهٔ حسگر نیز مسئلهٔ تشخیصِ خطای بایت را جدا دنبال می‌کند؛ پیشوندی بودن جانشینِ آن بررسی نیست.

۵. چهار پرسش و مرزِ بسته‌بندی

پرسش اول: چرا پاسخ پانزده است و نه هجده؟ پاسخ: طول‌ها یک، دو، سه و سه بیت‌اند؛ ضرب در تعدادهای پنج، دو، یک و یک، پانزده می‌دهد. هجده مربوط به نه نماد با کدِ ثابتِ دوبیتی است. هیچ‌یک، اندازهٔ فایلِ کامل با جدول و سربار را به‌تنهایی مشخص نمی‌کنند.

پرسش دوم: اگر همهٔ وزن‌ها سه برابر شوند چه می‌شود؟ پاسخ: ترتیبِ وزن‌ها و سیاستِ تساوی ثابت می‌ماند، پس همین جدول ساخته می‌شود؛ هزینهٔ وزن‌دار چهل‌وپنج و میانگین همچنان پنج‌سوم است. این آزمون از ثابت بودنِ شمارِ رخدادهای پیامِ تازه خبر نمی‌دهد؛ فقط تغییرِ مشترکِ وزن‌های ورودی را بررسی می‌کند.

پرسش سوم: می‌توان بیتِ اضافیِ صفر را برای پُر کردن بایت نادیده گرفت؟ پاسخ: خیر؛ دو A برابر دو بیتِ یک‌اند. با افزودنِ شش صفر، رمزگشا دو A و سه B معتبر تحویل می‌دهد. پس طولِ واقعیِ بیت‌ها یا قراردادِ پایان باید بیرون از این رشته معلوم باشد؛ رمزگشای حاضر padding یا EOF ضمنی ندارد.

پرسش چهارم: کدِ متفاوت یعنی پیاده‌سازیِ غلط؟ پاسخ: لزوماً خیر؛ تساویِ وزن‌ها و انتخابِ شاخه‌ها می‌توانند جدولِ هم‌هزینهٔ دیگری بسازند. اما گیرنده نمی‌تواند آن جدول را حدس بزند و باید همان قرارداد را داشته باشد. منابع در ۲۶ مهر ۱۴۰۵ خوانده شده‌اند؛ این آموزش ادعای قالبِ DEFLATE، تصحیحِ خطا، احرازِ هویت یا نسبتِ فشرده‌سازیِ محصول ندارد.

منابع و مطالعهٔ بیشتر

• Cornell؛ ساخت درخت و کدِ Huffman
• RFC 1951؛ بخشِ کدهای پیشوندی و قواعدِ کدِ Huffman

بررسی منابع: ۲۶ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.