Information Theory in Data Compression
Lý thuyết thông tin trong nén file
Công ty nào đang ứng dụng Lý thuyết thông tin?
"Sao file .txt toàn chữ ‘a’ lại nhỏ hơn hẳn file toàn chữ ngẫu nhiên?" — đây là câu hỏi đánh thẳng vào bản chất của nén dữ liệu. Câu trả lời nằm trong một bài báo 1948 của Claude Shannon: mọi phân phối dữ liệu đều có một giới hạn nén lý thuyết đo bằng entropy, và không thuật toán nào vượt qua được giới hạn đó mà không mất thông tin.
Dưới đây là một bộ mã Huffman sống. Chọn một kiểu phân phối đầu vào — bạn sẽ thấy độ dài mã trung bình thay đổi, và kích thước file sau nén dịch chuyển theo thời gian thực.
Ví dụ: file toàn chữ 'a', chèn rất ít ký tự khác.
| Ký tự | Tần suất | Mã Huffman | Số bit mã | Mã cố định 3-bit |
|---|---|---|---|---|
| A | 80.0% | 0 | 1 bit | 000 (3 bit) |
| B | 8.0% | 10 | 2 bit | 001 (3 bit) |
| C | 5.0% | 110 | 3 bit | 010 (3 bit) |
| D | 4.0% | 1110 | 4 bit | 011 (3 bit) |
| E | 2.0% | 11110 | 5 bit | 100 (3 bit) |
| F | 1.0% | 11111 | 5 bit | 101 (3 bit) |
Nếu file có 1000 ký tự:
Tiết kiệm được 53% — và khoảng cách giữa mã Huffman và entropy chính là "khoảng dự phòng không thể thu hẹp thêm" mà Shannon đã chứng minh.
Vấn đề công ty cần giải quyết
Mỗi ngày internet truyền hàng exabyte dữ liệu. Không nén, băng thông sẽ sập, ổ cứng nhanh đầy, điện thoại chụp ảnh xong không còn chỗ lưu. Câu hỏi lớn: làm sao biểu diễn cùng một lượng thông tin bằng ít bit hơn?
Với nén không mất mát (lossless — ZIP), mọi bit phải giữ nguyên. Với nén có mất mát (lossy — JPEG, H.265), câu hỏi là: bỏ đến mức nào thì mắt/tai người không nhận ra? Cả hai hướng đều dùng entropy làm la bàn.
000000000000001001010
Tổng: 21 bit
00001010110
Tổng: 11 bit · tiết kiệm 48%
0), còn F (hiếm nhất) có mã dài (11111).Cách Lý thuyết thông tin giải quyết vấn đề
Đếm tần suất ký tự.Bước đầu tiên của mọi thuật toán nén: nhìn dữ liệu và đếm xem mỗi ký tự (hoặc chuỗi byte) xuất hiện bao nhiêu lần. Từ đó suy ra xác suất — càng lệch, càng có dư địa để nén. File toàn ‘a’ có xác suất 99% cho ‘a’, nghĩa là entropy ≈ 0 — gần như không có gì để "bất ngờ".
Xây cây Huffman — ký tự phổ biến được gán mã ngắn. Thuật toán bắt đầu từ sáu ký tự độc lập, ghép hai ký tự hiếm nhất thành một nút, lặp lại cho đến khi còn một gốc duy nhất. Đường đi từ gốc xuống lá cho ta mã của mỗi ký tự — đi trái = ‘0’, đi phải = ‘1’.
Bước 1: Mỗi ký tự là một láKhởi đầu: 6 ký tự A, B, C, D, E, F với tần suất biết trước. Mỗi ký tự là một lá riêng lẻ.
Huffman tiệm cận entropy Shannon.Shannon đặt giới hạn: không thể nén nhỏ hơn H(X) bit/ký tự trung bình. Huffman đạt được một giá trị rất gần với H — thường chỉ lớn hơn một chút. Đó là lý do Huffman được gọi là "tối ưu gần toàn cục" cho mã có độ dài nguyên.
ZIP = LZ77 + Huffman.LZ77 tìm chuỗi lặp lại và thay bằng tham chiếu ngược ("đi lùi N byte, copy M byte"). Huffman sau đó nén bảng chữ cái thô đã giảm dư thừa. Hai tầng bổ sung cho nhau, tiến rất gần giới hạn lý thuyết cho mọi loại văn bản.
JPEG & H.265 — nén có mất mát. Với ảnh/video, ta không cần khôi phục từng bit. JPEG chia ảnh thành khối 8×8, chuyển sang miền tần số (DCT), và lượng tử hoáthô các thành phần tần số cao mà mắt ít nhạy. H.265 làm tương tự cho video + mã hoá số học (CABAC). Cả hai đều dùng entropy để biết "bỏ được bao nhiêu mà không ai nhận ra".
Con số thật
Nếu không có Lý thuyết thông tin, app sẽ ra sao?
Không có lý thuyết thông tin của Shannon, các kỹ sư sẽ thiết kế thuật toán nén mà không biết giới hạn nằm ở đâu — như đào vàng mà không biết mỏ sâu bao nhiêu. Họ không biết khi nào đã đạt tối ưu, khi nào còn có thể cải thiện.
Entropy cho biết chính xác bao nhiêu bit là đủ và bao nhiêu là dư thừa. Nhờ vậy Huffman biết cách gán mã ngắn cho ký tự phổ biến, JPEG biết bỏ được bao nhiêu chi tiết, H.265 biết xác suất nào cần ước lượng. Internet như chúng ta biết — ảnh tải nhanh, video không giật, file gửi gọn — đều bắt nguồn từ một bài báo 78 trang năm 1948.
Một ảnh chỉ chứa 2 màu xen kẽ đều đặn (như bàn cờ). Dùng Huffman, trung bình mỗi pixel cần bao nhiêu bit?
File gốc 1 MB. Sau khi nén ZIP còn 200 KB. Tỷ lệ nén là bao nhiêu?
- Entropy Shannon = giới hạn sàn cho nén không mất mát — không thuật toán nào xuống dưới được.
- Huffman gán mã ngắn cho ký tự phổ biến, mã dài cho ký tự hiếm — tiệm cận giới hạn Shannon.
- ZIP = LZ77 (tìm chuỗi lặp) + Huffman — hai tầng bổ sung cho nhau.
- JPEG/H.265 là nén có mất mát: bỏ bớt chi tiết ít nhạy cảm với mắt/tai, vẫn dùng entropy làm chỉ dẫn.
Kiểm tra hiểu biết
Vì sao một file .txt chứa toàn chữ 'a' có thể nén nhỏ hơn hẳn so với một file toàn ký tự ngẫu nhiên?