Tại sao Chiến lược Tham lam là Tối ưu
Thuật toán Huffman là một thuật toán tham lam: ở mỗi bước, nó đưa ra lựa chọn tối ưu cục bộ (hợp nhất hai nút rẻ nhất) mà không nhìn trước. Các thuật toán tham lam không phải lúc nào cũng tối ưu toàn cục — nhưng ở đây thì có.
Lập luận về Tính Tối ưu
Giả sử một mã C có độ dài trung bình tối thiểu L. Xét hai ký hiệu có xác suất thấp nhất, gọi là p_a và p_b. Trong bất kỳ mã tối ưu nào, hai ký hiệu này phải xuất hiện như các lá anh em tại mức sâu nhất của cây. Tại sao?
Nếu chúng không có chung cha mẹ, bạn có thể hoán đổi ký hiệu sâu hơn với một mã ngắn hơn — giảm L. Do đó, các lá sâu nhất phải là các ký hiệu có xác suất thấp nhất.
Bây giờ, nếu bạn kết hợp a & b thành một ký hiệu siêu ab (với p_ab = p_a + p_b), bất kỳ mã tối ưu nào cho bảng chữ cái giảm trừ một ký hiệu chính xác là mã Huffman trên bài toán giảm. Quy nạp hoàn thành lập luận.
Góc nhìn Hình học
Thuật toán Huffman xây dựng cây nhị phân từ dưới lên, đặt các ký hiệu ít xác suất nhất ở độ sâu lớn nhất. Điều này giảm thiểu Σ p_i · depth(i) = L.
Một góc nhìn tương đương: bạn đang gán nhãn cho các lá cây để giảm thiểu độ dài đường đi có trọng số, trong đó trọng số của mỗi lá là xác suất của nó.
Thực hiện các Bước Tham lam
Xác suất: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1. Tổng = 1.0 ✓
Bước 1: Hai xác suất thấp nhất: C(0.2), D(0.1). Hợp nhất → CD(0.3). Danh sách: A(0.4), B(0.3), CD(0.3).
Bước 2: Hai xác suất thấp nhất: B(0.3), CD(0.3) (hòa — bất kỳ cái nào cũng hợp lệ). Hợp nhất → BCD(0.6). Danh sách: A(0.4), BCD(0.6).
Bước 3: Hợp nhất A(0.4), BCD(0.6) → gốc(1.0). Gán A=0, BCD=1.
Quay lại: BCD → B=10 (l=2), CD=11 → C=110 (l=3), D=111 (l=3).
L = 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 0.4+0.6+0.6+0.3 = 1.9 bit.
Phương sai Độ dài Mã
Hai mã Huffman có thể đạt được cùng một L nhưng có các phân phối độ dài mã khác nhau. Phương sai của độ dài mã đo lường sự lan truyền này:
Var(l) = E[l²] − (E[l])²
trong đó E[l] = L (độ dài mã trung bình) & E[l²] = Σ p_i · l_i².
Tại sao phương sai quan trọng:
1. Yêu cầu bộ đệm. Trong giải mã thời gian thực, mỗi ký hiệu chiếm một số bit biến đổi. Phương sai cao có nghĩa là một số ký hiệu chiếm nhiều bit — bạn cần bộ đệm đầu vào lớn hơn để đảm bảo bạn luôn có thể đọc một ký hiệu hoàn chỉnh.
2. Độ trễ giải mã. Các mã phương sai cao có đường dẫn giải mã trường hợp xấu nhất dài. Các mã phương sai thấp (cây rậm) ràng buộc trường hợp xấu nhất chặt hơn.
3. Độ bền vững. Một bit bị mất trong mã phương sai cao gây ra nhiều thiệt hại đồng bộ hóa hơn vì các mã từ dài phải được đọc lại hoàn toàn.
Khuyến nghị của Hamming: khi tồn tại nhiều mã Huffman hợp lệ (các lựa chọn phá vòng), hãy ưa thích cái có phương sai thấp hơn — cây rậm.
Tính Phương sai cho Hai Cây
Sử dụng p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1 & mã A=0, B=10, C=110, D=111:
E[l] = L = 1.9
E[l²] = 0.4·1² + 0.3·2² + 0.2·3² + 0.1·3² = 0.4+1.2+1.8+0.9 = 4.3
Var = 4.3 − 1.9² = 4.3 − 3.61 = 0.69
Mã Huffman 3 ký hiệu Từ đầu đến cuối
Một ví dụ hoàn chỉnh từ đầu đến cuối: xây dựng mã Huffman, tính L, tính H, xác minh L ≥ H, tính Var.
Nguồn: p(X)=0.6, p(Y)=0.3, p(Z)=0.1.
Xây dựng Huffman:
Bước 1: Sắp xếp: X(0.6), Y(0.3), Z(0.1). Hai xác suất thấp nhất: Y(0.3), Z(0.1).
Hợp nhất → YZ(0.4). Danh sách: X(0.6), YZ(0.4).
Bước 2: Hợp nhất X(0.6), YZ(0.4) → gốc(1.0). Gán X=0, YZ=1.
YZ → Y=10, Z=11.
Mã: X=0 (l=1), Y=10 (l=2), Z=11 (l=2).
L = 0.6·1 + 0.3·2 + 0.1·2 = 0.6 + 0.6 + 0.2 = 1.4 bit.
Entropy: H = −0.6·log₂(0.6) − 0.3·log₂(0.3) − 0.1·log₂(0.1)
log₂(0.6) ≈ −0.737, log₂(0.3) ≈ −1.737, log₂(0.1) ≈ −3.322
H = 0.6·0.737 + 0.3·1.737 + 0.1·3.322 = 0.442 + 0.521 + 0.332 = 1.295 bit.
L = 1.4 ≥ H = 1.295 ✓. L/H = 1.4/1.295 ≈ 1.081. 8.1% trên entropy.
Phương sai: E[l²] = 0.6·1 + 0.3·4 + 0.1·4 = 0.6+1.2+0.4 = 2.2. Var = 2.2 − 1.4² = 2.2 − 1.96 = 0.24.
Lượt của Bạn: Một Đường Ống Hoàn chỉnh
Các giá trị log₂ để tham khảo: log₂(0.5)=−1.000, log₂(0.25)=−2.000, log₂(0.125)=−3.000, log₂(0.375)≈−1.415, log₂(0.625)≈−0.678.