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 năm 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 đi 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 khi 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%. 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, ví dụ ZIP), mọi bit phải giữ nguyên. Với nén có mất mát (lossy, ví dụ JPEG hay H.265), câu hỏi là: bỏ đến mức nào thì mắt và 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. Phân phối 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 là ‘0’, đi phải là ‘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 cho mỗi 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 và H.265: nén có mất mát. Với ảnh và 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), rồi 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, kèm thêm 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, giống 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 mà bạn đang dùng (ả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 là 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) cộng với Huffman. Hai tầng bổ sung cho nhau.
- JPEG và 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 và 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?