Mã như một Cây
Một mã không tiền tố ánh xạ tới một cây nhị phân: gốc đại diện cho điểm bắt đầu giải mã, các nhánh trái đại diện cho bit 0, các nhánh phải đại diện cho bit 1, và các lá đại diện cho các codeword hoàn chỉnh.
Ràng buộc hình học: mỗi lá kết thúc một đường dẫn từ gốc đến lá. Không có lá nào có thể có con cháu (nếu như vậy, codeword của nó sẽ là tiền tố của codeword của con cháu, vi phạm thuộc tính không tiền tố).
Điều này cung cấp cho bất đẳng thức Kraft một cách giải thích hình học:
Mỗi lá ở độ sâu d 'chiếm' một phân số 2^(−d) của tổng dung lượng cây. Tổng dung lượng của một cây nhị phân hoàn chỉnh ở độ sâu D là 1. Một mã không tiền tố sử dụng các lá ở các độ sâu khác nhau; tổng Kraft đo tổng chiếm dụng.
Tổng Kraft = 1: mã hoàn chỉnh (mỗi đường dẫn kết thúc ở một lá — đóng gói hoàn hảo).
Tổng Kraft < 1: mã không hoàn chỉnh (một số dung lượng cây chưa được sử dụng — có thể thêm nhiều ký hiệu hơn).
Tổng Kraft > 1: không thể có đối với các mã không tiền tố (một số đường dẫn sẽ phải chia sẻ một lá).
Lá Sâu Hơn = Mã Dài Hơn = Dung Lượng Ít Hơn
Một lá ở độ sâu 1 sử dụng nửa dung lượng cây (2^(−1) = 0,5).
Một lá ở độ sâu 3 sử dụng một phần tám (2^(−3) = 0,125).
Đặt một codeword ngắn cao trong cây chặn tất cả các con cháu của nó khỏi bị sử dụng — bạn trao đổi một mã ngắn cho nhiều mã dài tiềm năng.
Xây dựng một Cây Không Tiền tố
Hãy xem xét 5 ký hiệu có độ dài l = {1, 2, 3, 3, 3}. Tổng Kraft = 2^(−1) + 2^(−2) + 3·2^(−3) = 0,5 + 0,25 + 0,375 = 1,125 > 1.
Điều này vượt quá 1: các độ dài này không tương thích với một mã không tiền tố. Ít nhất một độ dài phải tăng.
Sửa: thay đổi l_1 từ 1 thành 2. Các độ dài mới {2, 2, 3, 3, 3}: Kraft = 2·2^(−2) + 3·2^(−3) = 0,5 + 0,375 = 0,875 < 1. Hợp lệ, nhưng không hoàn chỉnh.
Sửa: thay đổi l_1 từ 2 thành 2, thêm l_2 = 3 để sử dụng dung lượng còn lại. Kraft = 0,875; còn lại = 0,125 = 2^(−3): chỗ cho một lá độ sâu 3 nữa.
Tại sao Entropy ràng buộc Độ dài Mã
Kraft's inequality constrains code structure (lengths must fit in the tree). Shannon's entropy constrains code efficiency (average length cannot beat a theoretical floor).
Độ dài mã tối ưu. Đối với một ký hiệu có xác suất p_i, độ dài mã lý tưởng là log₂(1/p_i). Các ký hiệu hiếm xứng đáng có mã dài; các ký hiệu thường xuyên xứng đáng có mã ngắn. Điều này phản ánh sự bằng nhau Kraft: 2^(−l_i) = p_i khi l_i = log₂(1/p_i).
Nhưng log₂(1/p_i) hiếm khi là một số nguyên. Làm tròn lên thành ⌈log₂(1/p_i)⌉ cho độ dài Huffman, thỏa mãn H ≤ L < H + 1.
Đọc hình học. Vẽ biểu đồ mỗi ký hiệu như một điểm trên cây nhị phân ở độ sâu l_i. Tổng Kraft đo lường phạm vi lá toàn bộ. Entropy đo lường trung bình có trọng số độ sâu, được trọng số bằng xác suất. Định lý Shannon: độ sâu trung bình có trọng số xác suất ≥ nội dung thông tin có trọng số xác suất.
Xác minh Cận Entropy
Ví dụ đã làm: p = [1/2, 1/4, 1/8, 1/8] cho các ký hiệu {A, B, C, D}.
Độ dài tối ưu: l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3.
Đây đều là những số nguyên — một sự trùng khớp hoàn hảo. Mã Huffman: A=0, B=10, C=110, D=111.
L = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 0,5 + 0,5 + 0,375 + 0,375 = 1,75.
H = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 1,75. L = H chính xác: mã tối ưu.
Một Ví dụ Đã Làm Đầy Đủ
Đường ống đầy đủ: cho xác suất, tính toán entropy, xác minh mã đáp ứng cận.
Nguồn: p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
H = 1,75 bits (được tính toán ở trên).
Một mã khối ngây thơ: 4 ký hiệu → 2 bits mỗi → L = 2,0. Chi phí cao hơn entropy: 2,0 − 1,75 = 0,25 bits/ký hiệu = 12,5% lãng phí.
Mã độ dài biến tiết kiệm 12,5% so với mã độ dài cố định. Đối với các tin nhắn lớn, điều này rất đáng kể.
Tốc độ entropy tiếng Anh. Shannon ước tính entropy của tiếng Anh viết là khoảng 1,0 đến 1,3 bits trên mỗi ký tự, mặc dù sử dụng các mã ASCII 5 bit. Tỷ lệ 4:1 đó phản ánh sự thừa dư lớn trong ngôn ngữ tự nhiên — các chữ cái phổ biến được nhóm lại, các từ lặp lại, ngữ pháp hạn chế chuỗi.
Nén dữ liệu Không thể Vượt quá Entropy
Tỷ lệ nén: H / (độ dài mã khối). Đối với ví dụ của chúng tôi: 1,75/2,0 = 0,875 — 87,5% hiệu quả.
Bạn có thể nén thêm không? Chỉ bằng cách sử dụng ngữ cảnh: nếu bạn mã hóa các cặp hoặc bộ ba ký hiệu cùng nhau, entropy chung H(X,Y) có thể ít hơn 2·H(X) do sự phụ thuộc thống kê. Đây là mở rộng của định lý mã hóa không nhiễu thành n-gram.