Cách Huffman Xây dựng Mã Tối ưu
Hamming trình bày mã hóa Huffman như một thuật toán tham lam xây dựng mã tiền tố có độ dài trung bình tối thiểu. Ý tưởng chính: xây dựng cây từ dưới lên, luôn gộp hai ký hiệu có xác suất thấp nhất.
Lượt Thuận (Xây dựng)
1. Sắp xếp tất cả các ký hiệu theo xác suất, từ cao đến thấp.
2. Lấy hai ký hiệu có xác suất thấp nhất. Kết hợp chúng thành một siêu ký hiệu mới với xác suất = tổng của hai ký hiệu.
3. Chèn siêu ký hiệu vào vị trí được sắp xếp của nó.
4. Lặp lại cho đến khi chỉ còn hai ký hiệu.
5. Gán 0 và 1 cho hai ký hiệu còn lại.
Lượt Ngược (Gán Mã)
Hoàn tác các lần gộp theo thứ tự ngược lại: ở mỗi lần tách, hai ký hiệu được gộp nhận cùng các bit tiền tố với cha gộp của chúng, cộng với một 0 bổ sung (một con) hoặc 1 (con khác). Phép gán 0/1 là tùy ý — cả hai đều hợp lệ.
Tại sao điều này là tối ưu: nếu bất kỳ mã nào khác có độ dài trung bình L' nhỏ hơn, áp dụng cùng quy trình giảm thuận sẽ cuối cùng tạo ra hai ký hiệu có độ dài trung bình nhỏ hơn 1 bit — điều không thể đối với mã 2 ký hiệu. Mâu thuẫn.
Theo dõi Thuật toán
Ví dụ từ Hamming: bốn ký hiệu A, B, C, D với p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125.
Lượt thuận:
Bước 1: Sắp xếp: A(0.5), B(0.25), C(0.125), D(0.125). Hai thấp nhất: C, D.
Bước 2: Gộp CD với p=0.25. Danh sách mới: A(0.5), B(0.25), CD(0.25).
Bước 3: Hai thấp nhất: B(0.25), CD(0.25). Gộp BCD với p=0.5.
Bước 4: Hai ký hiệu còn lại: A(0.5), BCD(0.5). Gán A=0, BCD=1.
Lượt ngược:
BCD → B được 10, CD được 11. CD → C được 110, D được 111.
Mã cuối cùng: A=0 (l=1), B=10 (l=2), C=110 (l=3), D=111 (l=3).
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 bit.
Nhiều Mã Huffman Hợp lệ
Hamming lưu ý hai nguồn không duy nhất:
1. Phép gán 0/1 tùy ý. Ở mỗi lần tách, bạn có thể cho 0 cho bất kỳ con nào. Hoán đổi 0 & 1 xuyên suốt mang lại mã khác với L giống hệt.
2. Tiebreak. Khi hai nút có xác suất bằng nhau, bất kỳ nút nào cũng có thể được đặt 'cao hơn' (được gộp trước). Các lựa chọn tiebreak khác nhau có thể tạo ra các cây có cấu trúc khác — 'dài' so với 'rậm' — với cùng L nhưng phân bố độ dài mã khác nhau.
Cây Dài so với Rậm
Cây dài (lệch). một ký hiệu ở mỗi mức độ sâu (cấu trúc giống Fibonacci). Độ dài mã thay đổi rộng: một ký hiệu nhận mã ngắn, các ký hiệu khác dòng chảy đến mã dài hơn.
Cây rậm (cân bằng): các ký hiệu trải rộng đều trên các mức độ sâu. Độ dài mã cụm gần trung bình. Phương sai thấp hơn.
Khuyến nghị của Hamming: khi được lựa chọn, ưa chuộng cây rậm. Cùng L, nhưng phương sai nhỏ hơn trong độ dài mã → thời gian giải mã đồng đều hơn → yêu cầu bộ đệm nhỏ hơn trong các ứng dụng thời gian thực.
Tính toán Phương sai Độ dài Mã
Phương sai độ dài mã: Var = E[l²] − (E[l])²
Đối với mã {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3} với p=[0.5, 0.25, 0.125, 0.125]:
E[l] = L = 1.75
E[l²] = 0.5·1² + 0.25·2² + 0.125·3² + 0.125·3² = 0.5 + 1.0 + 1.125 + 1.125 = 3.75
Var = 3.75 − 1.75² = 3.75 − 3.0625 = 0.6875
Một mã rậm thay thế cho các ký hiệu có xác suất bằng nhau sử dụng tất cả mã độ dài 2: L=2, Var=0.
Lợi Nhuận Nén so với Phân bố Ký hiệu
Quy tắc của Hamming: mã hóa Huffman chỉ trả tiền khi xác suất ký hiệu khác nhau đáng kể.
Xác suất bằng nhau. Nếu tất cả 2^k ký hiệu có xác suất bằng 1/2^k, Huffman tạo ra mã khối: mỗi ký hiệu nhận độ dài k. L = H = k. Không lợi so với mã khối đơn giản.
Xác suất lệch. Nếu một ký hiệu chiếm ưu thế (p >> 1/2^k cho những ký hiệu khác), Huffman gán cho nó mã rất ngắn (độ dài 1 hoặc 2), giảm đáng kể L.
Mã dấu phẩy (thuật ngữ của Hamming). Khi mỗi xác suất vượt quá 2/3 của tổng còn lại, Huffman tự nhiên tạo ra: p(s1)→0, p(s2)→10, p(s3)→110, ..., xuống đến hai mã độ dài bằng nhau ở cuối. Đây là 'mã dấu phẩy': dấu 0 ở cuối một dòng 1s hoạt động như một dấu phẩy.
Hamming lưu ý: nén dữ liệu thực tế (sao lưu, lưu trữ tệp) có thể cắt giảm lưu trữ hơn một nửa khi nguồn có xác suất lệch — văn bản tiếng Anh là ví dụ chính.
Huffman so với Mã Khối: So sánh Số lượng
Ví dụ thứ hai của Hamming: p(s1)=1/3, p(s2)=1/5, p(s3)=1/6, p(s4)=1/10, p(s5)=1/12, p(s6)=1/20, p(s7)=1/30, p(s8)=1/30.
Mã khối: 8 ký hiệu → 3 bit mỗi → L_block = 3.
Hamming tính toán mã Huffman & báo cáo L_Huffman ≈ 2.58 bit.
Tiết kiệm: (3 − 2.58)/3 ≈ 14% nén so với mã khối.
Khi xác suất ký hiệu khác nhau rất lớn (1/3 so với 1/30 ở đây, tỷ lệ 10:1), mã độ dài biến trả tiền đáng kể.
Các Chương Trình Tự Biên dịch
Hamming kết thúc Chương 11 với một ý tưởng ngoạn mục: một bộ mã hóa Huffman có thể mã hóa chính nó. Cây giải mã (cho biết bộ giải mã cách đọc thông báo nén) được truyền cùng với dữ liệu nén. Người nhận không cần biết trước mã.
Bộ mã hóa: lấy mẫu dữ liệu, ước tính xác suất, xây dựng mã Huffman, mã hóa cây giải mã dưới dạng tiêu đề, sau đó mã hóa dữ liệu.
Bộ giải mã: đọc tiêu đề để xây dựng lại cây, sau đó giải mã dữ liệu bằng nó.
Điểm của Hamming: toàn bộ đường dẫn này có thể chạy dưới dạng hàm thư viện mà không cần sự can thiệp của con người. Bạn gọi nó, nó nén & giải nén tự động. Các định dạng lưu trữ hiện đại (ZIP, gzip, bzip2) triển khai chính xác mẫu này.
Nguyên tắc sâu hơn: trí tuệ nằm trong thuật toán, không phải trong bảng mã cố định. Thuật toán thích ứng với bất kỳ dữ liệu nào nó nhận được. Đây là mẫu Hamming thấy xuyên suốt tất cả các hệ thống kỹ thuật tuyệt vời: khả năng thích ứng được xây dựng sẵn, không bị bắt bằng lực.