Mã Huffman (Huffman Code)
Mã Huffman được định nghĩa là một loại mã tiền tố tối ưu (optimal prefix code) thường dùng cho nén dữ liệu không mất mát (lossless data compression).
Quy trình tìm hoặc cài đặt mã như vậy tiến hành bằng mã hóa Huffman (Huffman coding), một thuật toán được phát triển bởi David A. Huffman khi ông là sinh viên Sc.D. tại MIT, và công bố trong bài báo 1952 "A Method for the Construction of Minimum-Redundancy Codes".
Đầu ra từ thuật toán Huffman có thể hiển thị như bảng mã độ dài biến đổi (variable-length code table) để mã hóa ký hiệu nguồn (source symbol) (ví dụ: ký tự trong file). Thuật toán tạo bảng này từ xác suất ước lượng hoặc tần suất xuất hiện (trọng số) cho mỗi giá trị có thể của ký hiệu nguồn. Như các phương pháp mã hóa entropy khác, ký hiệu phổ biến hơn thường được biểu diễn bằng ít bit hơn ký hiệu hiếm hơn. Phương pháp Huffman có thể cài đặt hiệu quả, tìm mã trong thời gian tuyến tính theo số trọng số đầu vào nếu các trọng số đã được sắp xếp.
Entropy (Độ loạn/Entropy)
Trong lý thuyết thông tin, định lý mã hóa nguồn Shannon (hay định lý mã hóa không nhiễu) thiết lập giới hạn cho nén dữ liệu có thể, và ý nghĩa vận hành của entropy Shannon.
Định lý mã hóa nguồn cho thấy (trong giới hạn, khi độ dài luồng biến ngẫu nhiên độc lập đồng phân phối (i.i.d.) tiến tới vô cực) không thể nén dữ liệu sao cho tỷ lệ mã (số bit trung bình trên ký hiệu) nhỏ hơn entropy Shannon của nguồn, mà không chắc chắn làm mất thông tin. Tuy nhiên, có thể đạt tỷ lệ mã tận cận entropy Shannon, với xác suất mất mát có thể bỏ qua.
Entropy thông tin được định nghĩa là tỷ lệ trung bình mà thông tin được sản xuất bởi nguồn dữ liệu ngẫu nhiên (stochastic).
Tính Entropy cho biến ngẫu nhiên (Random Variable)
Chúng ta cũng có thể tính lượng thông tin trong một biến ngẫu nhiên.
Ví dụ: nếu muốn tính thông tin cho biến ngẫu nhiên X với phân phối xác suất p, có thể viết như hàm H(); ví dụ: H(X).
Về bản chất, tính thông tin cho biến ngẫu nhiên giống như tính thông tin cho phân phối xác suất của các sự kiện cho biến ngẫu nhiên đó.
Tính thông tin cho biến ngẫu nhiên được gọi là "entropy thông tin" (information entropy), "entropy Shannon", hoặc đơn giản là "entropy".
Nó liên quan đến ý tưởng entropy từ vật lý bằng sự tương tự, vì cả hai đều liên quan đến sự không chắc chắn (uncertainty).
Trực giác cho entropy là số bit trung bình cần để biểu diễn hoặc truyền một sự kiện rút ra từ phân phối xác suất cho biến ngẫu nhiên.
Entropy Shannon của một phân phối là lượng thông tin kỳ vọng trong một sự kiện rút ra từ phân phối đó.
Nó cung cấp ranh giới dưới (lower bound) cho số bit trung bình cần để mã hóa ký hiệu rút ra từ phân phối P.
Entropy có thể tính cho biến ngẫu nhiên X với k trong K trạng thái rời rạc như sau:
H(X) = -∑ (each k in K) p(k) * log(p(k))
Đó là âm của tổng xác suất mỗi sự kiện nhân với log xác suất mỗi sự kiện.
Giống như thông tin, hàm log() dùng cơ số 2 và đơn vị là bit. Log tự nhiên (natural logarithm) cũng có thể dùng.
Entropy thấp nhất cho biến ngẫu nhiên có một sự kiện duy nhất với xác suất 1.0 (chắc chắn). Entropy lớn nhất cho biến ngẫu nhiên sẽ xảy ra nếu tất cả sự kiện có xác suất như nhau.