ساختن یه کمپرسور از صفر با Huffman coding
خلاصهٔ کامل‌تر
نویسندهٔ این پست می‌خواد نشون بده فشرده‌سازی اصلاً جادو نیست. ایدهٔ پایه اینه که همون اطلاعات رو با بایت‌های کمتر بنویسی. مثالش یه آرایهٔ ۸تایی از booleanهاست: اگه به شکل JSON ذخیره‌ش کنی ۵۲ بایت جا می‌گیره، ولی اگه هر true رو 1 و هر false رو 0 بنویسی، کل آرایه تو یه بایت جا میشه. یعنی ۵۲ برابر کوچیک‌تر، بدون اینکه چیزی از دست بره.
این روش فقط برای آرایهٔ boolean کار می‌کنه، ولی ابزاری مثل gzip باید هر نوع داده‌ای رو فشرده کنه. نویسنده چند تا نمونه آورده: یه کتاب متنی از 622KB به 234KB رسیده، یه باینری Rust از 90MB به 30MB، ولی یه فایل MP3 همون 54MB مونده. دلیلش اینه که MP3 از قبل فشرده شده و فشرده‌سازی هم یه حدی داره.
الگوریتم gzip اسمش DEFLATE هست و دو تا ترفند داره. اولی (که اسمش LZ77 هست) تکه‌های تکراری رو پیدا می‌کنه و جاشون یه نشونهٔ کوتاه می‌ذاره، مثلاً «اینجا ۱۵ بایت از موقعیت 2397 رو کپی کن». دومی Huffman coding هست، یعنی شمردن تعداد تکرار هر بایت و دادن کد کوتاه‌تر به بایت‌های پرتکرار و کد بلندتر به بایت‌های کم‌تکرار. اینجوری معمولاً حجم کل کم میشه.
به گفتهٔ نویسنده، Huffman بخش «جادویی» و جذاب ماجراست و کمپرسور خودش فقط از همین استفاده می‌کنه. مراحلش ساده‌ست: تعداد تکرار هر بایت رو بشمار، از روی اون برای هر بایت یه دنبالهٔ بیتی بساز، داده رو با این جدول کد کن و خود جدول رو هم اول فایل بنویس. decompressor هم برعکس همین کار رو می‌کنه: جدول رو می‌خونه و بیت‌ها رو دوباره به بایت برمی‌گردونه.
اسم این کمپرسور ABC (Adolfo's Basic Compressor) هست و کلاً ۵۸۰ خط کد Rust بدون هیچ وابستگیه. همون کتاب رو از 622KB به 366KB می‌رسونه و باینری Rust رو از 90MB به 73MB. از gzip ضعیف‌تره چون فقط یکی از دو ترفند رو داره، ولی نویسنده می‌گه هنوزم براش حس جادو داره. آخر پست هم از David MacKay یاد کرده که درس‌هاش دربارهٔ information theory بالاخره کمکش کرد این موضوع رو بفهمه.
نکات کلیدی:
- آرایهٔ ۸تایی boolean به شکل JSON ۵۲ بایته ولی به شکل بیتی فقط ۱ بایت.
- الگوریتم gzip اسمش DEFLATE هست و از LZ77 و Huffman coding با هم استفاده می‌کنه.
- Huffman coding به بایت‌های پرتکرار کد کوتاه‌تر می‌ده و جدول کدها رو اول فایل ذخیره می‌کنه.
- کمپرسور ABC فقط با Huffman، یه کتاب 622KB رو به 366KB می‌رسونه؛ gzip به 234KB می‌رسونه.
- کل پیاده‌سازی ABC ۵۸۰ خط Rust بدون وابستگیه.
- فایل‌های از قبل فشرده مثل MP3 با gzip کوچیک‌تر نمی‌شن.
