Nén dữ liệu: LZ77 và định dạng nâng cao

Giới thiệu

Bài này học nén không mất mát với Huffman và LZ77. Bạn dùng nó để lưu log gọn và tải nhanh hơn.

Kiến thức cần nhớ

Nén mất mát và không mất mát

• Nén không mất mát: giải nén ra đúng từng bit gốc.
• Nén mất mát: bỏ bớt chi tiết mắt khó nhận thấy.
• Ví dụ đời thường: file văn bản như cất giấy tờ gốc, video như ảnh chụp mờ vẫn xem được.
• Hợp đồng và code phải dùng không mất mát.
• Video 4K nên dùng mất mát cho nhẹ.

Mã Huffman biến dài

• Định nghĩa: chữ hay gặp cho mã bit ngắn, chữ hiếm cho mã dài.
• Không mã nào là tiền tố của mã khác nên giải mã duy nhất.
• Ví dụ đời thường: như gán số điện thoại ngắn cho người gọi nhiều.
• Mạnh khi tần suất chữ lệch nhau nhiều.
• Yếu khi văn bản toàn đoạn lặp dài.

LZ77 cửa sổ trượt

• Định nghĩa: nhìn lại đoạn vừa qua, gặp lặp thì ghi vị trí thay vì ghi chữ.
• Mỗi lần lặp ghi 3 số: lùi bao xa, dài bao nhiêu, ký tự tiếp theo.
• Ví dụ đời thường: như ghi "copy 5 chữ ở trên" thay vì viết lại.
• Mạnh với log và HTML nhiều đoạn lặp.
• Cửa sổ càng lớn càng bắt lặp xa nhưng tốn nhớ.

# Ví dụ ý tưởng LZ77
text = "abababab"
# gặp "abab" lần 2 -> ghi (lùi 4, dài 4)
print(("lùi", 4, "dài", 4))  # thay vì ghi lại chữ

Ví dụ

• Input: abababab. Output: lần đầu ghi abab, lần sau ghi (lùi 4, dài 4).
• Giải thích: LZ77 không ghi lại chữ lặp mà chỉ ghi vị trí.
• Input: log 100 dòng giống nhau. Output: Huffman giảm 20%, LZ77 giảm 80%.
• Giải thích: đoạn lặp hợp với từ điển của LZ77 hơn.

💻 Bài tập

Ngôn ngữ: C++ (hoặc Python). Dùng Huffman ngày 27. Nộp vào day-061/.

Bài 1: LZ77

struct Token { uint16_t offset; uint8_t length; char next; };   // (lùi, dài, ký tự kế)
std::vector<Token> lz77Encode(const std::string &s, int window = 4096, int maxLen = 255);
std::string lz77Decode(const std::vector<Token> &tokens);

Ràng buộc

• Tìm đoạn khớp dài nhất trong cửa sổ, hòa thì chọn offset nhỏ nhất.
• Đoạn khớp được phép chồng lên phần đang mã hóa (offset < length).
• Không có khớp thì token là (0, 0, c).

"abababab" -> (0,0,a) (0,0,b) (2,5,b)   (khớp chồng lấn, lùi 2 chép 5 ký tự)
decode(encode(s)) == s với mọi s (test 1000 chuỗi ngẫu nhiên, gồm chuỗi rỗng)

Bài 2: So Huffman và LZ77

Chạy trên 4 file: văn bản tiếng Việt, log server có nhiều dòng lặp, file HTML, file byte ngẫu nhiên.

file        gốc(byte)   huffman   lz77(ước lượng 4 byte/token)   gzip
text.txt    ...
server.log  ...

Viết 4 câu: loại dữ liệu nào hợp thuật toán nào và vì sao.

Bài 3: LZ77 + Huffman kiểu DEFLATE (nâng cao)

1. Mã hóa LZ77 trước, rồi Huffman riêng cho luồng offset, luồng length, luồng next.
2. Ghi file nhị phân tự định dạng. Giải nén lại đúng từng byte.
3. Tăng tốc tìm khớp bằng bảng băm 3 ký tự đầu (hash chain). So thời gian với tìm tuyến tính trên file 5 MB.

✅ Tiêu chí hoàn thành

• Test mẫu và test ngẫu nhiên pass.
• Bảng so sánh 4 file có số thật, có cột gzip để đối chiếu.
• Bài 3 nén rồi giải nén ra file giống hệt (cmp).
• Phân biệt được nén mất mát và không mất mát bằng ví dụ.

❓ Câu hỏi ôn tập

• Khi nào dùng nén mất và không mất mát?
• Huffman gán mã ngắn dài theo nguyên tắc nào?
• LZ77 dùng cửa sổ trượt để làm gì?
• Khi nào chọn LZ77 thay vì Huffman?

🌕 Bạn đã hoàn thành ngày 61. Làm hết bài tập phía trên rồi sang ngày tiếp theo.