ONE is preparing: 01 / INITIALIZING MODEL ROUTER. Evaluating routing across providers.
Current state
01 / INITIALIZING MODEL ROUTER.

Evaluating routing across providers.

Start learning
← ML cơ bản

AI Foundation

Lý thuyết thông tin trong nén file

Vietnamese onlyThe learning content is available in Vietnamese only. The surrounding interface follows your language.

Vì sao file .txt toàn chữ 'a' nén rất nhỏ còn file ngẫu nhiên gần như không nén được? Entropy Shannon đặt giới hạn — Huffman tiến gần nó.

lesson46 minML cơ bảnAI Foundation

Giới thiệu

“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 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 vượt qua được giới hạn đó mà không mất thông tin.

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 hoặc tai người không nhận ra? Cả hai hướng đều dùng entropy làm la bàn.

Kiểm tra nhanh

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?

Huffman — mã ngắn cho ký tự phổ biến

Shannon đặt giới hạn: không thể nén nhỏ hơn H(X) bit mỗi ký tự trung bình. Huffman là thuật toán gán mã ngắn cho ký tự phổ biến và mã dài cho ký tự hiếm, đạt giá trị rất gần giới hạn đó.

Đếm tần suất ký tự. Bước đầu tiên của mọi thuật toán nén là đế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. Thuật toán bắt đầu từ các ký tự độc lập, ghép hai ký tự (hoặc nú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. Đi từ gốc xuống mỗi lá — đi trái là ‘0’, đi phải là ‘1’ — ta có mã của ký tự đó.

Ví dụ với sáu ký tự A–F

1 / 3
  1. 1. Bước 1: mỗi ký tự là một lá

    Khởi đầu với A, B, C, D, E, F và tần suất biết trước. Mỗi ký tự là một lá riêng lẻ.

Bảng tần suất đầy đủ của sáu ký tự không có trong nguồn bài, nên không tính được độ dài mã trung bình hay số bit tiết kiệm ở đây. Với file 1000 ký tự, mã cố định 3 bit/ký tự tốn 3000 bit — đó là mốc so sánh.

Huffman tiệm cận entropy Shannon. Shannon đặt giới hạn: không thể nén nhỏ hơn H(X) bit mỗi ký tự trung bình. Huffman đạ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, 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 và 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.

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. 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.

4 điều rút ra

  • 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) + 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.

Quay lại lý thuyết: Entropy, cross-entropy và KL divergence — hiểu sâu hơn ba thước đo mà mọi thuật toán nén và mọi loss phân loại đều dùng làm chuẩn.

Continue the path

Lesson 43 of 106