Định nghĩa
Mã hóa Huffman gán mã cho ký tự sao cho độ dài mã phụ thuộc vào tần suất tương đối (trọng số) của ký tự. Mã Huffman có độ dài biến đổi, không có tiền tố (không mã nào là tiền tố của mã khác). Bất kỳ mã nhị phân không tiền tố nào có thể hiển thị dưới dạng cây nhị phân với ký tự mã hóa lưu ở lá.
Cây Huffman (Huffman coding tree) định nghĩa là cây nhị phân đầy đủ (full binary tree) mà mỗi lá tương ứng với một chữ cái trong bảng chữ cái cho trước.
Cây Huffman được xem như cây nhị phân liên quan đến trọng số đường đi ngoài nhỏ nhất, tức là tổng độ dài đường đi có trọng số nhỏ nhất cho tập lá cho trước. Mục tiêu: xây dựng cây với trọng số đường đi ngoài nhỏ nhất.
Ví dụ:
Bảng tần suất chữ cái
| Chữ cái | z | k | m | c | u | d | l | e |
| Tần suất | 2 | 7 | 24 | 32 | 37 | 42 | 42 | 120 |
Mã Huffman
| Chữ cái | Tần suất | Mã | Số bit |
|---|---|---|---|
| e | 120 | 0 | 1 |
| d | 42 | 101 | 3 |
| l | 42 | 110 | 3 |
| u | 37 | 100 | 3 |
| c | 32 | 1110 | 4 |
| m | 24 | 11111 | 5 |
| k | 7 | 111101 | 6 |
| z | 2 | 111100 | 6 |
Cây Huffman (cho ví dụ trên):
