Ba phần vừa qua xây từng viên gạch: entropy (bức tường), Huffman (mã theo tần suất), LZ77 (loại lặp lại). Giờ ta ghép chúng lại thành thuật toán nén phổ biến nhất hành tinh: DEFLATE. Mỗi lần trình duyệt tải một trang web nén (Content-Encoding: gzip), mỗi file .png, mỗi file .gz, mỗi commit git đều chạy qua DEFLATE. Và điều đẹp đẽ: DEFLATE không có gì mới — nó đúng là LZ77 (phần 4) chồng lên Huffman (phần 3). LZ77 loại các đoạn lặp, rồi Huffman mã hóa phần còn lại theo tần suất. Bài này (phần 5 loạt Nén) mổ xẻ định dạng gzip thật đến từng byte, phân biệt gzip/zlib/DEFLATE, và đo xem sức mạnh thực sự nằm ở đâu.

DEFLATE = LZ77 + Huffman, và ba lớp vỏ

DEFLATE hoạt động theo hai tầng bù nhau, đúng như hai phần trước gợi ý:

  • Tầng 1 — LZ77: quét dữ liệu, thay các đoạn lặp lại bằng tham chiếu ngược (distance, length), để lại một dòng gồm literal và match.
  • Tầng 2 — Huffman: mã hóa cả literal lẫn các token distance/length theo tần suất — ký hiệu phổ biến mã ngắn. (DEFLATE thực chất dùng hai bảng Huffman: một cho literal+length, một cho distance.)

Điều gây nhầm lẫn là ba cái tên hay bị lẫn — DEFLATE, zlib, gzip — thực ra chỉ khác nhau lớp vỏ quanh cùng một ruột DEFLATE:

  • DEFLATE raw: chỉ luồng bit đã nén, không header, không checksum.
  • zlib (RFC 1950): 2 byte header + DEFLATE + checksum adler32 (4 byte).
  • gzip (RFC 1952): 10 byte header + DEFLATE + CRC32 (4 byte) + kích thước gốc (4 byte).

Ảnh chụp đoạn mã nền tối minh hoạ DEFLATE gzip và zlib chính là LZ77 chồng lên Huffman DEFLATE bằng LZ77 bài 04 cộng Huffman bài 03 gzip bằng DEFLATE cộng header cộng CRC32, hai tầng bù nhau loại lặp rồi mã tần suất tầng 1 LZ77 thay đoạn lặp lại bằng tham chiếu distance length tầng 2 Huffman mã các literal và các token distance length theo tần suất ký hiệu phổ biến mã ngắn hai tầng bằng DEFLATE thuật toán của gzip zlib PNG HTTP gzip khắp nơi, ba lớp vỏ quanh cùng một DEFLATE DEFLATE raw chỉ luồng bit đã nén không header wbits -15 zlib 2 byte header cộng DEFLATE cộng adler32 4 byte checksum gzip 10 byte header cộng DEFLATE cộng CRC32 4B cộng ISIZE 4B ruột giống nhau chỉ khác lớp vỏ và kiểu checksum chọn theo ngữ cảnh, mổ header gzip bằng python không cần công cụ ngoài gz bằng gzip compress data 6 hdr bằng gz 10 byte đầu byte 0-1 magic 1f 8b byte 2 method 08 DEFLATE byte 3 flags byte 4-7 mtime byte 8 XFL byte 9 OS 8 byte cuối CRC32 4B cộng ISIZE kích thước gốc 4B little-endian, ba kiểu block trong DEFLATE stored không nén level 0 dùng khi dữ liệu không nén được fixed Huffman bằng mã cố định không lưu bảng block nhỏ dynamic Huffman bảng riêng tối ưu cho block lưu kèm thường dùng bộ mã hóa tự chọn kiểu tốt nhất cho từng block

Hình 1: DEFLATE = LZ77 (loại lặp) chồng lên Huffman (mã tần suất); ba lớp vỏ quanh cùng ruột DEFLATE — raw (không header), zlib (+adler32), gzip (+header+CRC32+kích thước); và ba kiểu block: stored (không nén), fixed Huffman (mã cố định), dynamic Huffman (bảng riêng).

Đo thật: mổ header và so ba lớp vỏ

Mình nén một khối text bằng python zlib/gzip, mổ header đến từng byte và so kích thước:

Ảnh chụp bảng kết quả chạy thật DEFLATE gzip output thật go-lab python zlib gzip round-trip OK, a 10 byte header cộng 8 byte trailer của gzip hex 1f 8b 08 00 06 26 bd 6a 00 ff magic bằng 1f 8b chữ ký gzip method bằng 08 08 bằng DEFLATE flags bằng 00 mtime bằng 06 26 bd 6a XFL OS bằng 00 ff 8 byte cuối bằng e3 a1 f9 78 gạch 84 67 00 00 CRC32 gạch ISIZE bằng 0x6784 bằng 26500 đúng kích thước gốc, b overhead ruột giống nhau khác lớp vỏ DEFLATE raw wbits -15 155 byte không header zlib header cộng adler32 161 byte cộng 6 byte bằng 2 header cộng 4 adler32 gzip header cộng CRC32 173 byte cộng 18 byte bằng 10 header cộng 8 trailer, c đóng góp của việc nén store vs deflate gốc 26500 byte gzip level 0 26523 byte stored bằng không nén chỉ xấp xỉ gốc cộng overhead gzip level 6 173 byte LZ77 cộng Huffman bằng 153.2x level 0 chứng minh bỏ tắt nén thì gzip chỉ là bao bọc sức mạnh ở DEFLATE, d round-trip gzip zlib DEFLATE raw OK cả ba giải nén ra đúng dữ liệu gốc

Hình 2: Chạy thật — (a) header gzip 1f 8b 08 00...: magic 1f 8b, method 08 (DEFLATE), trailer CRC32 + ISIZE 0x6784=26500 (đúng kích thước gốc); (b) DEFLATE raw 155B, zlib 161B (+6), gzip 173B (+18); (c) gzip level 0 (stored) 26523B vs level 6 173B (153.2x); (d) round-trip cả ba OK.

  • (a) Header gzip đọc được bằng mắt: 10 byte đầu bắt đầu bằng magic number 1f 8b (chữ ký nhận diện file gzip), rồi 08 = phương pháp nén DEFLATE, flags, mtime (thời điểm nén), XFL, OS. Cuối file là 8 byte trailer: 4 byte CRC32 (checksum để kiểm toàn vẹn) và 4 byte ISIZE — kích thước gốc, ở đây 84 67 00 00 little-endian = 0x6784 = 26500, đúng bằng kích thước dữ liệu gốc. (Chính nhờ ISIZE mà gzip -l cho biết kích thước giải nén mà không cần giải nén.)
  • (b) Ba lớp vỏ, cùng ruột: DEFLATE raw chỉ 155 byte. zlib thêm 6 byte (2 byte header + 4 byte adler32). gzip thêm 18 byte (10 byte header + 8 byte trailer). Ruột DEFLATE giống hệt nhau — khác biệt chỉ là lớp bao và kiểu checksum. Chọn cái nào tùy ngữ cảnh: HTTP dùng gzip, PNG dùng zlib, một số giao thức nhúng dùng raw để tiết kiệm từng byte.
  • (c) Sức mạnh ở DEFLATE, không phải lớp vỏ: đây là minh chứng đẹp nhất. gzip level 0 (chế độ stored — LZ77 và Huffman đều tắt) cho 26523 byte, lớn hơn cả bản gốc 26500 (chỉ thêm overhead). gzip level 6 cho 173 byte — nén 153.2x. Toàn bộ sức nén đến từ hai tầng DEFLATE; lớp vỏ gzip chỉ là bao bọc. Bỏ nén đi thì gzip chẳng nén gì.
  • (d) Round-trip đúng cả ba: gzip, zlib và DEFLATE raw đều giải nén ra đúng dữ liệu gốc — checksum (CRC32/adler32) còn giúp phát hiện nếu dữ liệu bị hỏng.

Đánh đổi cần cân nhắc

Ba kiểu block cho DEFLATE tự thích nghi. Bên trong, DEFLATE chia dữ liệu thành các block, mỗi block chọn một trong ba kiểu: stored (không nén — dùng khi dữ liệu không nén được, tránh làm to ra như ca ngẫu nhiên phần 1), fixed Huffman (dùng bảng mã cố định thỏa thuận trước — không tốn chỗ lưu bảng, hợp block nhỏ), dynamic Huffman (bảng mã riêng tối ưu cho block đó, phải lưu kèm — hợp block lớn). Bộ mã hóa tự chọn kiểu tốt nhất từng block, nên DEFLATE ít khi làm dữ liệu to hơn nhiều.

gzip vs zlib vs raw — chọn đúng theo giao thức, đừng trộn. Chúng không tương thích trực tiếp: giải nén một luồng gzip bằng bộ giải zlib sẽ lỗi vì header khác. Khi tích hợp, phải khớp đúng: HTTP Content-Encoding: gzip cần gzip, deflate (trớ trêu) thường là zlib, PNG dùng zlib. Nhầm định dạng là lỗi "invalid header" khó hiểu. Trong code, chọn wbits đúng (15+16 cho gzip, 15 cho zlib, -15 cho raw trong zlib của Python).

CRC32/adler32 là checksum, không phải mã sửa lỗi. Chúng phát hiện hỏng (một bit lật là checksum sai), nhưng không sửa được — và không phải để chống giả mạo (kẻ tấn công tính lại checksum được). adler32 (zlib) nhanh hơn nhưng yếu hơn CRC32 (gzip) trong phát hiện lỗi. Nếu cần chống giả mạo, dùng chữ ký/HMAC ngoài; nếu cần sửa lỗi, cần mã sửa lỗi (như Reed-Solomon) — đó là bài toán khác với nén.

Ba ý mang về

  1. DEFLATE = LZ77 + Huffman, không có gì mới: đo thật gzip level 6 nén 153.2x nhờ hai tầng (loại lặp rồi mã tần suất); đây là thuật toán của gzip, zlib, PNG, HTTP gzip — phổ biến nhất thế giới.
  2. gzip/zlib/DEFLATE raw chỉ khác lớp vỏ: đo thật cùng dữ liệu, raw 155B, zlib +6B (adler32), gzip +18B (header 10B + CRC32/ISIZE 8B); header gzip đọc được từng byte (magic 1f 8b, method 08, ISIZE = kích thước gốc); phải khớp đúng định dạng theo giao thức.
  3. Sức mạnh ở DEFLATE, không phải bao bọc: đo thật gzip level 0 (stored) làm 26500 byte thành 26523 (to hơn!), level 6 thành 173 — toàn bộ nén đến từ hai tầng; và DEFLATE tự chọn kiểu block (stored/fixed/dynamic) để không làm hại dữ liệu không nén được.

Nguồn

Phần sau ta xét nút chỉnh mà ai cũng gặp: mức nén (compression level) — gzip -1 tới -9 đánh đổi tốc độ lấy tỉ lệ nén thế nào, và đo thật để biết mức nào đáng.