Bài 8: File ZIP nén dữ liệu như thế nào? Mã Huffman, LZ77 và thuật toán DEFLATE

Bạn nén một thư mục 100 MB thành file ZIP chỉ còn vài chục MB, gửi qua Zalo, người nhận giải nén ra y nguyên từng byte. Dữ liệu không mất đi đâu cả – chỉ là được "viết lại" ngắn gọn hơn. Bí quyết nằm ở một ý tưởng tham lam rất đẹp của một sinh viên năm 1951.

Bài thứ tám của chuyên mục "Thuật toán trong đời sống". Thuật toán Huffman là ví dụ kinh điển của chiến lược tham lam và hàng đợi ưu tiên (heap) – hai chủ đề quen thuộc trong chương trình chuyên Tin.

1. Ý tưởng: chữ hay gặp thì viết ngắn

Máy tính thường lưu mỗi ký tự bằng 8 bit (mã ASCII). Nhưng trong văn bản, có chữ xuất hiện rất nhiều, có chữ hiếm khi gặp. Vậy tại sao không dùng mã ngắn cho chữ hay gặp, mã dài cho chữ hiếm? Mã Morse cũng dựa trên ý tưởng này: chữ E – chữ phổ biến nhất tiếng Anh – chỉ là một dấu chấm.

Khó khăn: mã có độ dài khác nhau thì làm sao biết một mã kết thúc ở đâu? Lời giải là mã tiền tố – không mã nào là phần đầu của mã khác. Khi đó chỉ cần đọc lần lượt từng bit là giải mã được duy nhất.

2. Câu chuyện của David Huffman

Năm 1951, David Huffman là nghiên cứu sinh tại MIT. Thầy Robert Fano cho lớp lý thuyết thông tin chọn: làm bài tiểu luận hoặc thi cuối kỳ. Đề tiểu luận là tìm cách mã hóa nhị phân hiệu quả nhất – cách mã hóa mà Fano và Claude Shannon đề xuất trước đó vẫn chưa phải là tối ưu.

Theo bài viết của tạp chí Scientific American (1991), Huffman loay hoay nhiều tháng, đến lúc định vứt ghi chép vào thùng rác để ôn thi thì lời giải chợt lóe lên. Ông gọi đó là khoảnh khắc "lightning of sudden realization". Năm 1952, ông công bố bài báo "A Method for the Construction of Minimum-Redundancy Codes" – và học trò đã vượt thầy.

Điểm mấu chốt của Huffman: thay vì chia từ trên xuống như cách của Shannon–Fano, ông xây cây từ dưới lên: luôn ghép hai nhóm hiếm nhất lại với nhau. Cách làm này được chứng minh là tối ưu trong các mã tiền tố.

3. Thuật toán Huffman

1. Đếm tần suất mỗi ký tự; mỗi ký tự là một nút lá.
2. Lấy ra hai nút có tần suất nhỏ nhất, ghép thành một nút cha có tần suất bằng tổng.
3. Lặp lại đến khi chỉ còn một nút – đó là gốc cây.
4. Đi từ gốc xuống: rẽ trái ghi 0, rẽ phải ghi 1. Đường đi tới mỗi lá là mã của ký tự đó.

Dùng hàng đợi ưu tiên, thuật toán chạy trong O(k log k) với k là số ký tự khác nhau. Ví dụ với chuỗi "abracadabra":

Ký tự	Số lần	Mã cố định 3 bit	Mã Huffman
a	5	000	0
b	2	001	110
r	2	010	111
c	1	011	100
d	1	100	101
Tổng	11	33 bit	23 bit

Chữ "a" xuất hiện 5 lần chỉ tốn 1 bit. Tổng cộng 23 bit, so với 33 bit của mã cố định 3 bit và 88 bit của ASCII.

Code C++ và Python

#include <bits/stdc++.h>
using namespace std;
struct Node { int freq; char ch; Node *l, *r; };
map<char, string> codes;
void build(Node* t, string s){
    if(!t->l){ codes[t->ch] = s.empty() ? "0" : s; return; }
    build(t->l, s + "0"); build(t->r, s + "1");
}
int main(){
    string text = "abracadabra";
    map<char, int> cnt; for(char c : text) cnt[c]++;
    // Hàng đợi ưu tiên: luôn lấy ra 2 nút có tần suất nhỏ nhất để ghép
    auto cmp = [](Node* a, Node* b){ return a->freq > b->freq; };
    priority_queue<Node*, vector<Node*>, decltype(cmp)> pq(cmp);
    for(auto [c, f] : cnt) pq.push(new Node{f, c, nullptr, nullptr});
    while(pq.size() > 1){
        Node* a = pq.top(); pq.pop();
        Node* b = pq.top(); pq.pop();
        pq.push(new Node{a->freq + b->freq, 0, a, b});
    }
    build(pq.top(), "");
    int bits = 0;
    for(auto [c, s] : codes){ cout << c << " (" << cnt[c] << " lan): " << s << "\n"; bits += cnt[c] * s.size(); }
    cout << "Huffman: " << bits << " bit, ASCII 8 bit/ky tu: " << text.size() * 8 << " bit\n";
}

import heapq
from collections import Counter

def huffman(text):
    cnt = Counter(text)
    # mỗi phần tử: (tần suất, thứ tự, {ký tự: mã})
    heap = [(f, i, {c: ""}) for i, (c, f) in enumerate(cnt.items())]
    heapq.heapify(heap)
    k = len(heap)
    while len(heap) > 1:
        f1, _, a = heapq.heappop(heap)   # hai nhóm hiếm nhất
        f2, _, b = heapq.heappop(heap)
        merged = {c: "0" + s for c, s in a.items()}
        merged.update({c: "1" + s for c, s in b.items()})
        heapq.heappush(heap, (f1 + f2, k, merged)); k += 1
    return cnt, heap[0][2]

text = "abracadabra"
cnt, codes = huffman(text)
for c in sorted(codes):
    print(c, cnt[c], codes[c])
encoded = "".join(codes[c] for c in text)
print("Huffman:", len(encoded), "bit | ASCII:", len(text) * 8, "bit")

4. Bên trong file ZIP: DEFLATE = LZ77 + Huffman

Huffman chỉ khai thác việc chữ nào hay gặp. Văn bản thật còn có những đoạn lặp lại (từ, câu, đoạn code giống nhau). Năm 1977, Abraham Lempel và Jacob Ziv công bố thuật toán LZ77: thay một đoạn đã từng xuất hiện bằng cặp số "lùi lại bao xa, chép bao nhiêu ký tự". Viện IEEE ghi nhận LZ77 là một cột mốc giúp truyền dữ liệu qua Internet hiệu quả.

Định dạng DEFLATE – được dùng trong file ZIP – kết hợp cả hai. Theo tài liệu chuẩn RFC 1951, DEFLATE "nén dữ liệu bằng sự kết hợp của thuật toán LZ77 và mã Huffman", và người thiết kế định dạng là Phil Katz – người sáng lập công ty PKWARE năm 1989.

Huffman còn ở khắp nơi

• Ảnh PNG: theo đặc tả của W3C, PNG nén bằng DEFLATE.
• Ảnh JPEG: theo ITU, mã Huffman là phương pháp bắt buộc trong chuẩn JPEG cơ bản (T.81).
• File .gz, .docx, .xlsx (thực chất là file ZIP) cũng dùng DEFLATE.

Vì sao file ZIP chứa ảnh JPG hầu như không nhỏ đi? Vì JPG đã được nén rồi – dữ liệu gần như không còn "dư thừa" để khai thác. Không thuật toán nén không mất dữ liệu nào có thể làm nhỏ mọi file.

5. Bạn học được gì từ đây?

• Tham lam + hàng đợi ưu tiên giải được bài toán tối ưu thật sự – nhưng cần chứng minh, không phải tham lam nào cũng đúng.
• Một bài tiểu luận sinh viên đã trở thành thuật toán chạy trên hàng tỷ thiết bị.
• Bài toán ghép hai phần tử nhỏ nhất xuất hiện rất nhiều trong đề thi, ví dụ bài "nối dây" với tổng chi phí nhỏ nhất.

Bài tập luyện tập

• CSES – Stick Divisions (chính là thuật toán Huffman)

Thử thách: hãy chạy code với tên của bạn (ví dụ "laptrinhthuattoan") và cho biết mã Huffman tiết kiệm được bao nhiêu bit so với ASCII. Chia sẻ trong phần bình luận nhé!

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 9: Xếp lịch thi sao cho không ai bị trùng giờ? Bài toán tô màu đồ thị trong đời sống

Đọc tiếp: xếp lịch thi & tô màu đồ thị →

← Bài trước: giao hàng & bài toán TSPXem tất cả 27 bài →

Nguồn tham khảo

• Huffman (1952) – A Method for the Construction of Minimum-Redundancy Codes (lịch sử, NMSU)
• Wikipedia – Huffman coding
• IETF – RFC 1951: DEFLATE Compressed Data Format
• Ziv & Lempel (1977) – A Universal Algorithm for Sequential Data Compression
• IEEE Milestone – Lempel-Ziv Data Compression Algorithm, 1977
• W3C – PNG Compression
• ITU – JPEG (T.81)
• Computerworld (2000) – ZIP compression inventor dies