Huffman Coding

Thuật toán Huffman Coding

• Thuật toán Huffman coding giúp nén chuỗi đầu vào thành 1 chuỗi có dung lượng nhỏ hơn, sao cho dữ liệu không bị mất mát.

• Nó hoạt động bằng cách xây dựng một cây nhị phân dựa trên tần suất xuất hiện của các ký tự trong dữ liệu đầu vào, từ đó tạo ra mã nhị phân có độ dài ngắn hơn cho những ký tự có tần suất xuất hiện cao hơn.

Cách hoạt động

Để hiểu hơn về thuật toán nén dữ liệu này, hãy xem xét ví dụ cụ thể. Giả sử có chuỗi như sau 'BCAADDDCCACACAC', mỗi kí tự chiếm 8 bit. Tổng có 15 kí tự do đó chuỗi trên chiếm 15 x 8 = 120 bit.

Các bước thực hiện như sau:

• Tính toán tần suất xuất hiện của từng kí tự

  

• Sắp xếp các kí tự theo thứ tự tăng dần của tần suất

  

• Định nghĩa các node trong cây là node(character, frequency, left child, right child). Trong đó character là kí tự, frequency là tần suất xuất hiện, left child, right child là các node con. Đối với node lá thì sẽ chỉ có (character, frequency).

• Ta tạo từng kí tự trong bảng tần suất trên thành từng nút lá: (B, 1), (D, 3), (A, 5), (C, 6).

• Tiếp theo ta tạo 1 empty node, ta sẽ gán left child chính là node có tần suất xuất hiện ít nhất, và right child là node có tần suất xuất hiện ít thứ hai. Frequency của node cha sẽ là tổng của frequency 2 node con.

  

• Tiếp đến ta loại bỏ 2 node con vừa rồi khỏi dãy tần suất, thêm vào dãy node vừa tạo và sắp xếp lại dãy theo thứ tự tăng dần tần suất.

• Lặp lại các thủ tục vừa rồi cho đến khi dãy ban đầu chỉ còn 1 node duy nhất, đó chính là node gốc của cây.

  

  

• Sau khi hoàn thành việc tạo cây, ta sẽ gán cho các cạnh trái có giá trị 0, cạnh phải có giá trị 1

  

• Từ cây trên, ta có thể build ra một Hashmap(character, compressed code). ví dụ (C, '0'), (B, '100'), (A, '11'), (D, '101')

Ta thu được bảng kết quả mapping kí tự

Dữ liệu sau khi nén còn 28 bit so với 120 bit ban đầu.

Decode về chuỗi ban đầu

• Để decode từng mã code, ta có thể duyệt cây lại để tìm ra giá trị gốc ban đầu. Ví dụ với code '101', ta sẽ duyệt cây theo hình dưới đây để cho ra kí tự 'D'

  

Độ phức tạp

• Time complexity để mã hóa mỗi ký tự duy nhất dựa trên tần suất xuất hiện của nó là O(nlog⁡n)

Ứng dụng

• Huffman coding được sử dụng trong các định dạng nén thông thường như GZIP, BZIP2, PKZIP, v.v.

• Dùng cho việc truyền văn bản và fax.

Note

• github của mình: https://github.com/huynguyen411/HuffmanCoding