Thuật toán nén Huffman Coding

Nén tài liệu là giải pháp vô hiệu những thông tin dư thừa trong việc trình diễn tài liệu. Nó có nhiều ứng dụng, đặc biệt quan trọng là trong việc truyền tin vì giúp rút gọn thông tin gửi đi. Có nhiều thuật toán nén tài liệu và Huffman Coding là một trong số đó. Bài viết này hầu hết bàn về ý tưởng sáng tạo của thuật toán này .

Mục lục

1. Nén dữ liệu

Hãy xem câu “ Hello ” được trình diễn dưới dạng mã ASCII như thế nào nhé :
Mỗi ký tự sử dụng 8 bit để màn biểu diễn nên tổng số sẽ dùng 64 bit .

Bảng mã ASCII mở rộng dùng 8 bit để biểu diễn 256 ký tự khác nhau. Trong khi đó thông điệp của chúng ta chỉ gồm 5 ký tự khác nhau, như vậy thực tế chỉ cần dùng 3 bit là đủ để phân biệt được 5 ký tự này.

Bạn đang đọc: Thuật toán nén Huffman Coding

Bây giờ ta sẽ liệt kê 5 ký tự phân biệt và gán cho nó một mã nhị phân 3 bit phân biệt. Lúc này ta vẫn hoàn toàn có thể trình diễn toàn vẹn thông điệp đã nén và dùng bảng giải thuật này để Phục hồi thông điệp khởi đầu .

Như vậy, chỉ cần dùng $3 \times 8 = 24$ bit để biểu diễn thông điệp trên. Mỗi ký tự đều dùng đúng một số lượng bit để biểu diễn, chúng ta gọi cách này là fixed-length encoding. Bảng các giá trị được mã hóa cũng là prefix code.

Prefix code có thể được định nghĩa khó hiểu như sau (theo Wikipedia):

A prefix code is a type of code system distinguished by its possession of the “ prefix property ”, which requires that there is no whole code word in the system that is a prefix ( initial segment ) of any other code word in the system. It is trivially true for fixed-length code, so only a point of consideration in variable-length code .

Chúng ta hiểu đơn thuần như sau : Prefix code là một tập những giá trị mã hóa mà không có thành phần nào được khởi đầu bằng một thành phần khác .

Với fix-length encoding dùng cùng một số lượng bit để mã hóa, các giá trị mã hóa đều khác nhau. Do đó, nó là prefix-code. Tuy vậy, các giá trị mã hóa với số lượng bit khác nhau (variable-length encoding) cũng là prefix code nếu thỏa mãn tính chất trên.

Ví dụ : Tập A = { 0, 10, 110, 111 } là một prefix code vì không có thành phần nào mở màn bằng thành phần khác. Nhưng B = { 0, 10, 110, 101 } không phải prefix code vì có thành phần 101 khởi đầu bằng thành phần 10 .
Prefix code hoàn toàn có thể được màn biểu diễn thành cây nhị phân mã hóa. Mỗi ký tự cần mã hóa sẽ nằm ở nút lá. Giá trị mã hóa của ký tự đó bộc lộ bằng đường đi từ nút gốc đến nút lá chứa ký tự đó. Nhánh bên trái bộc lộ giá trị 0, nhánh bên phải bộc lộ giá trị 1 .
Ví dụ cho chữ “ Hellooo ! ” được mã hóa bằng 3 – bit encoding :

Ta lại nhận thấy rằng, có những phần tử xuất hiện rất nhiều lần, nếu gắn cho chúng một mã có độ dài thấp nhất, còn các phần tử xuất ít hơn có thể có mã dài hơn, thì vẫn có thể tiết kiệm được hơn nữa.

Xem thêm: Giáo án dạy học Toán 11 theo định hướng phát triển phẩm chất năng lực – https://thomaygiat.com

Giả sử ta chọn một prefix code như ví dụ bên dưới :
Rõ ràng chỉ cần dùng 18 bit để trình diễn thông điệp trên. Cách gán mã dựa trên tần suất Open cũng chính là ý tưởng sáng tạo của thuật toán Huffman coding .

2. Thuật toán Huffman Coding

Với ý tưởng sáng tạo trên, thuật toán Huffman coding gồm 3 bước :

Bước 1: Đếm tần suất xuất hiện của các phần tử trong chuỗi đầu vào.

Bước 2: Xây dựng cây Huffman (cây nhị phân mã hóa).

Bước 3: Từ cây Huffman, ta có được các giá trị mã hóa. Lúc này, ta có thể xây dựng chuỗi mã hóa từ các giá trị này.

Quá trình kiến thiết xây dựng cây Huffman gồm những bước sau :

2.1. Tạo danh sách chứa các nút lá bao gồm phần tử đầu vào và trọng số nút là tần suất xuất hiện của nó.

2.2. Từ danh sách này, lấy ra 2 phần tử có tần suất xuất hiện ít nhất. Sau đó gắn 2 nút vừa lấy ra vào một nút gốc mới với trọng số là tổng của 2 trọng số ở nút vừa lấy ra để tạo thành một cây.

2.3. Đẩy cây mới vào lại danh sách.

2.4. Lặp lại bước 2 và 3 cho đến khi danh sách chỉ còn 1 nút gốc duy nhất của cây.

2.5. Nút còn lại chính là nút gốc của cây Huffman.

Để dễ tiếp cận những bước thực thi thiết kế xây dựng cây Huffman, tất cả chúng ta sẽ dùng lại ví dụ ở phần trước .

Bước 2.1: Sau khi đếm tần suất xuất hiện các phần tử đầu vào. Chúng ta tạo danh sách các nút lá với trọng số là tần suất xuất hiện. Danh sách sẽ có 5 phần tử như bên dưới.

Bước 2.2 và 2.3: Chọn 2 nút có trọng số thấp nhất, tạo nút gốc mới có trọng số bằng tổng 2 trọng số nút con. Sau đó gắn 2 nút con vào nút gốc và đẩy lại vào danh sách. Danh sách cần được biểu diễn đặc biệt để có thể lấy ra các nút trọng số nhỏ nhất một cách tối ưu nhất.

Bước 2.4: Lặp lại các bước 2.2 và 2.3.

Bước 2.4: Lặp lại các bước 2.2 và 2.3.

Xem thêm: TOP 5 game tư duy trí tuệ cực hấp dẫn để luyện não

Bước 2.5: Chỉ còn lại 1 nút trong danh sách, nút này chính là cây Huffman

Từ cây Huffman, ta hoàn toàn có thể suy ra những giá trị mã hóa của từng thành phần bằng cách duyệt cây nhị phân mã hóa .