Định nghĩa
Mã hóa Huffman cung cấp mã cho các ký tự sao cho độ dài của mã phụ thuộc vào tần suất tương đối hoặc trọng lượng của ký tự tương ứng. Mã Huffman có độ dài thay đổi và không có bất kỳ tiền tố nào (điều đó có nghĩa là không có mã nào là tiền tố của bất kỳ mã nào khác). Bất kỳ mã nhị phân không có tiền tố nào đều có thể được hiển thị hoặc hình dung dưới dạng cây nhị phân với các ký tự được mã hóa được lưu trữ ở các lá.
Cây Huffman hoặc cây mã hóa Huffman được định nghĩa là một cây nhị phân đầy đủ, trong đó mỗi lá của cây tương ứng với một chữ cái trong bảng chữ cái đã cho.
Cây Huffman được coi là cây nhị phân được liên kết với trọng số đường đi bên ngoài tối thiểu có nghĩa là cây được liên kết với tổng chiều dài đường dẫn có trọng số tối thiểu cho tập hợp các lá đã cho. Vì vậy, mục tiêu là tạo một cây với trọng lượng đường dẫn bên ngoài tối thiểu.
Một ví dụ được đưa ra dưới đây-
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ã | Bits |
|---|---|---|---|
| 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 (ví dụ trên) được đưa ra bên dưới -
