Mã Huffman: nén tham lam bằng heap
Xây cây mã tiền tố tối ưu từ tần suất ký tự bằng thuật toán tham lam bottom-up với min-heap.
Trung bìnhThuật toán ~60 phút
Ôn lại trước khi học
Giới thiệu
Bài này học cách nén chữ theo tần suất. Bạn cho chữ hay gặp mã ngắn.
Kiến thức cần nhớ
Ý tưởng gán mã theo tần suất
- Chữ gặp nhiều thì mã ngắn, hiếm thì mã dài.
- Văn bản toàn A thì A chỉ tốn 1 bit.
- Đầu ra là bảng chữ sang dãy bit.
- Ví dụ đời thường: phím tắt cho việc hay làm.
Vòng gộp 2 nút nhỏ nhất
- Bắt đầu từ mỗi chữ và số lần gặp.
- Mỗi lượt gộp 2 nút nhỏ nhất thành cha.
- Tần suất cha bằng tổng 2 con.
- Ví dụ đời thường: gộp 2 đống nhỏ nhất trước.
- Lặp tới khi còn 1 gốc là xong cây.
Min-heap và mã tiền tố
- Min-heap lấy 2 nút nhỏ nhanh .
- Trái là 0, phải là 1, đường đi là mã.
- Không mã nào là đầu của mã khác.
- Ví dụ đời thường: mã vùng không lẫn nhau.
- Nhờ đó giải mã khỏi cần dấu cách.
| Chữ mẫu | Tần suất | Mã |
|---|---|---|
| A | 0.6 | Ngắn nhất |
| B | 0.2 | Trung bình |
| F, E | 0.02, 0.05 | Dài nhất |
Ví dụ
- Input: A 5 lần, B 2 lần, C 1 lần. Output: A mã ngắn nhất, C dài nhất.
- Giải thích: gộp C với B trước vì nhỏ nhất.
💻 Bài tập
Ngôn ngữ: C++. Được dùng std::priority_queue. Nộp vào day-027/.
Bài 1: Dựng cây và bảng mã
struct HNode { long long freq; unsigned char ch; HNode *left = nullptr, *right = nullptr; };
std::array<long long, 256> countFreq(const std::string &text);
HNode *buildTree(const std::array<long long, 256> &freq);
std::unordered_map<unsigned char, std::string> buildCodes(const HNode *root); // trái '0', phải '1'
void freeTree(HNode *root);
Ràng buộc
- Hòa tần suất thì nút có ký tự nhỏ hơn ra trước. Nhờ vậy kết quả tất định, dễ test.
- Văn bản chỉ có 1 loại ký tự: mã của ký tự đó là
"0". - Văn bản rỗng: trả bảng mã rỗng.
"AAAAABBC" -> freq A=5 B=2 C=1; len(code[A]) = 1, len(code[C]) = 2
"AAAA" -> code[A] = "0"
Không mã nào là tiền tố của mã khác (viết hàm isPrefixFree để kiểm)
Bài 2: Mã hóa và giải mã
| Hàm | Yêu cầu |
|---|---|
std::string encode(const std::string &text, const Codes &c) | Trả chuỗi '0'/'1' |
std::string decode(const std::string &bits, const HNode *root) | Đi từ gốc theo bit, gặp lá thì xuất ký tự |
double avgBits(const std::string &text, const Codes &c) | Số bit trung bình mỗi ký tự |
decode(encode(t)) == t với mọi t (test 100 chuỗi ngẫu nhiên)
"abracadabra": avgBits ~ 2.09, so với 8 bit ASCII
Bài 3: Nén file thật (nâng cao)
Viết 2 lệnh: huff c input.txt out.huf và huff d out.huf back.txt.
File .huf gồm: 256 số tần suất (mỗi số 8 byte), tổng số ký tự gốc (8 byte), rồi các bit đã đóng gói 8 bit vào 1 byte.
Test: back.txt giống hệt input.txt (so bằng cmp hoặc diff)
In: kích thước gốc, kích thước nén, tỉ lệ nén
Chạy trên 3 file: văn bản tiếng Việt, file toàn chữ a, file byte ngẫu nhiên. Giải thích vì sao file ngẫu nhiên không nén được.
✅ Tiêu chí hoàn thành
- Test mẫu pass,
decode(encode(t)) == tvới 100 chuỗi ngẫu nhiên. - Trường hợp 1 ký tự và chuỗi rỗng không crash.
- Bài 3 nén rồi giải nén trả lại file giống hệt.
- Sanitizer sạch, cây được giải phóng.
❓ Câu hỏi ôn tập
- Vì sao chữ hay gặp được mã ngắn?
- Mỗi lượt Huffman gộp mấy nút nào?
- Min-heap giúp gì ở đây?
- Mã tiền tố nghĩa là gì?
🌕 Bạn đã hoàn thành ngày 27. Làm hết bài tập phía trên rồi sang ngày tiếp theo.