کدگذاریِ هافمن برای نمادهای پرتکرار کدِ کوتاه‌تر و برای بعضی نمادهای کم‌تکرار کدِ بلندتر می‌سازد. کدها پیشوندآزادند؛ یعنی کدِ یک نماد ابتدای کدِ نمادِ دیگر نیست و می‌توان جریانِ بیت را بدون جداکنندهٔ میان هر دو نماد خواند. این صفحه یک پیامِ ساختگی را به بیت تبدیل و دوباره دقیقاً بازسازی می‌کند؛ صرفِ دیدنِ رشتهٔ صفر و یک را فشرده‌سازیِ فایلِ واقعی نمی‌نامد.
پیامِ۱۳نمادیِ ما
رشتهٔ آموزشی AAAAAAABBBCCD از A با فراوانی۷، B با۳، C با۲ و D با۱ ساخته شده است. ترتیبِ پیام در بازسازی مهم است، اما برای ساخت درخت، فراوانیِ هر نماد را می‌شماریم. این شمارش آمار زبان، تماس مشتری یا عملکردِ مدلِ هوش مصنوعی نیست.
چهار نماد را اگر همگی با دو بیت کد کنیم، بدنهٔ همین پیام۲۶بیت می‌شود. هافمن به‌جای طولِ یکسان، از ساختارِ درخت و فراوانی‌ها استفاده می‌کند؛ اما گیرنده باید درخت یا قراردادِ معادلِ کد را هم بشناسد. آن هزینه را در مقایسهٔ بدنه پنهان نمی‌کنیم.
سه ادغامِ صفِ کمینه
هر نماد یک برگ با وزنِ فراوانی است. هر بار دو درختِ با کمترین وزن از heap برداشته و با وزنِ مجموع به صف برمی‌گردند. در تساوی، شمارندهٔ ورود انتخاب را قطعی نگه می‌دارد. برای این داده، وزن‌های۱و۲ به۳، سپس۳و۳ به۶ و در پایان۶و۷ به۱۳ می‌رسند.
| نماد | فراوانی | کد در قراردادِ این فایل | سهم در بدنه |
|---|---|---|---|
| A | ۷ | ۱ | ۷بیت |
| B | ۳ | ۰۰ | ۶بیت |
| C | ۲ | ۰۱۱ | ۶بیت |
| D | ۱ | ۰۱۰ | ۳بیت |
روی یالِ چپ۰ و راست۱ می‌نویسیم؛ مسیرِ ریشه تا برگ، کدِ همان نماد است. جابه‌جاکردنِ دو فرزند می‌تواند بیت‌های کد را عوض کند، بدون اینکه طول‌ها و هزینه عوض شوند. بنابراین جدولِ یک اجرای معتبرِ دیگر ممکن است دقیقاً همین صفر و یک‌ها را نداشته باشد.
پیشوندآزاد یعنی رمزگشاییِ بی‌ابهامِ این قرارداد
در این جدول، هیچ کدی ابتدای کدِ دیگری نیست؛ فایل این شرط را برای همهٔ جفت‌های متفاوت کنترل می‌کند. رمزگشا از ریشه شروع می‌کند، با هر بیت به یک فرزند می‌رود و پس از رسیدن به برگ، نماد را خروجی می‌دهد و به ریشه بازمی‌گردد. برای پیامِ ما، رشتهٔ بیتِ تولیدشده دقیقاً همان۱۳نماد را بازمی‌سازد.
ورودیِ دارای نویسهٔ غیر از۰و۱ رد می‌شود. رشتهٔ «۰۱» نیز درخت را در میانهٔ کدِ یک نماد رها می‌کند و واقعاً خطا می‌دهد؛ نباید آخرِ آن را دلخواه با صفر پر کنیم و بازسازی موفق اعلام کنیم. نمونهٔ تک‌نمادیِ جدا هم قراردادِ صریحِ کد۰ دارد؛ چهار Z با۰۰۰۰ بازمی‌گردد. انتخابِ تک‌نمادی را بدون ثبت قرارداد به همهٔ قالب‌ها تعمیم ندهید.
قراردادِ ورودیِ خالی هم جدا آزموده شده است: ساختِ درخت از جدولِ فراوانیِ خالی رد می‌شود، ولی با درختِ معلوم، پیامِ خالی به بدنهٔ خالی کد و دوباره خالی خوانده می‌شود. رمزگذارِ دارای فرهنگِ ثابت، نمادِ ناشناختهٔ X را واقعاً رد می‌کند؛ بی‌خبر فرهنگِ تازه نمی‌سازد. این سه حالت در خروجیِ اجرا ثبت‌اند.
۲۲بیت را چگونه کنترل کردیم؟
جمعِ فراوانی ضرب در طولِ کد، ۷×۱+۳×۲+۲×۳+۱×۳=۲۲است. طولِ بدنهٔ تولیدشده هم۲۲بیت است. یک تابعِ مستقل برای همین چهار نماد، هزینهٔ همهٔ تقسیم‌های دودوییِ درختِ کامل را با برنامه‌ریزی پویا بررسی می‌کند؛ کمترین هزینه۲۲ می‌شود. این کنترل از همان heap هافمن استفاده نمی‌کند.
بهینگیِ شناخته‌شدهٔ هافمن دربارهٔ کدِ دودوییِ پیشوندآزادِ نمادبه‌نماد با فراوانی‌های داده‌شده است؛ به معنی کمترین حجم میان همهٔ روش‌های فشرده‌سازیِ ممکن نیست. خودِ فرهنگ کد، سرآیند، هم‌ترازی بایتی و متادیتای فایل در عدد۲۲ حساب نشده‌اند. پس اختلاف با۲۶بیت، درصدِ صرفه‌جوییِ یک فایلِ کامل یا فایل صوتی نیست.
با توکنایزر و کاهش عمقِ صوت اشتباه نکنیم
BPE واحدهای توکن را با ادغام جفت‌ها می‌سازد؛ اینجا نمادهای موجود را با طولِ بیتِ متفاوت کد کردیم. در کاهش عمقِ بیت ممکن است مقدارهای نمونه حذف شوند؛ کدگذاریِ حاضر روی همین رشته، بازگشتِ دقیق را کنترل کرده است. رمزگذاری برای محرمانگی هم انجام نشده؛ دانستنِ درخت برای خواندن پیام کافی است.
برای تحویل صوت به اپرانگار، مشخصاتِ فایلِ واقعی و ورودیِ قابل‌پذیرش را بررسی کنید. این فایلِ آموزشی صدای واقعی را فشرده نمی‌کند و دربارهٔ کدکِ داخلی، تعرفه یا دقتِ محصول چیزی ثابت نمی‌کند.
فایل تمرین و منبع
کد کامل Python؛ محاسبه و کنترل‌های مستقل · ورودیِ ساخته‌شده، مراحل و خروجیِ اجرای واقعی
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.