Lesson 21 — Huffman Encoding

Greedy xây cây nhị phân tối ưu để nén dữ liệu. Ba module: (1) xây cây từng bước, (2) gán mã 0/1, (3) encode/decode + tỉ lệ nén.

① Build tree — ghép 2 node nhẹ nhất từng bước

Văn bản:

Min-heap hiện tại (nhỏ nhất bên trái):

Nhập văn bản rồi bấm Đếm & khởi tạo heap.

Dùng cây vừa xây ở Module ①. DFS gán mã từ gốc: rẽ trái thêm 0, rẽ phải thêm 1; tới lá thì chuỗi bit là mã của ký tự.

Xây cây ở Module ① trước, rồi bấm Gán 1 lá.

Dùng bảng mã từ Module ②. So sánh với fixed-length (đủ bit để phân biệt các ký tự trong văn bản).

Bit stream Huffman (màu xen kẽ theo ký tự):

—

Decode (đi theo cây):

—

Fixed-length: — Huffman: — Tiết kiệm: —

Hoàn tất Module ① và ② trước, rồi bấm Encode.