Thuật toán nén dữ liệu | Lý thuyết nén dữ liệu Huffman (phần 1: ý tưởng)

[sonhn]

Bài này trình bày ý tưởng thuật toán mã hóa Huffman dùng trong nén thông tin. Các bạn có thể gặp nó trong lĩnh vực xử lý ảnh, hoặc trong kỳ thi lấy chứng chỉ… chuẩn kỹ sư CNTT Nhật Bản.

Mã Huffman là cái gì?

Đã khi nào bạn đặt câu hỏi: tại sao Winzip nén tập tin “nhatky.doc” 1MB của mình xuống chỉ còn 10KB chưa? Bài viết này giới thiệu khái niệm mã Huffman, một kỹ thuật nén thông tin kinh điển và khá phổ biến trước đây.

Mã hóa dữ liệu

Ai cũng biết, để lưu trữ dữ liệu trong máy tính, ta phải mã hóa chúng. Ví dụ, trong bộ mã ASCII nổi tiếng ra đời năm 1967, người ta dùng 8 bit để mã hóa 1 ký tự, cụ thể như:

“a” = 01100001
“A” = 01000001

Người ta gọi dãy số nhị phân trên là từ mã (codeword) của ký tự tương ứng.
Vậy, với bộ mã ASCII, chúng ta có thể mã hóa 2^8 = 256 ký tự, với mỗi từ mã dài 8 bit.


Và vấn đề phát sinh từ đây!

Năm 1952 (lúc đó chưa có ASCII à nghen!), anh sinh viên Huffman nhìn thấy sự lãng phí trong cách lưu trữ dạng này. Ví dụ, để lưu trữ file text có nội dung:

“Con ca kiem kiem con ca kiem can con ca kiem con”

Ta thấy trong file trên, chỉ có 8 ký tự được dùng là: C,O,N,A,K,I,M,E
Vậy, nếu mã hóa bằng mã ASCII, ta phải dùng đến 8 bit chỉ để mã hóa 8 ký tự. Thế thì “giết gà dùng dao mổ trâu” rồi!

Ý tưởng

Này nhé, nếu chỉ xét trong nội bộ tập tin, ta thấy: 8 ký tự = 2^3. Như vậy thì chỉ cần 3 bit là đủ để mã hóa chúng rồi. Từ đó, chúng ta tự lập ra 1 bảng mã riêng như vầy:
“C” = 000
“O” = 001
“N” = 010
“A” = 011
“K” = 100
“I” = 101
“M” = 110
“E” = 111
Tuyệt! nếu sử dụng bảng mã “đời mới” này, kích thước tập tin sẽ giảm đi hơn 1 nữa!

Đơn giản vậy đó hả?

Chưa đâu, nếu chỉ nhiêu đó thì… level của Huffman chỉ dừng lại ở mức thường thường bậc trung thôi. Ông còn phát hiện thêm điều khác. Quay lại câu “con cá kiếm” lúc nãy, ta nhận thấy ký tự “C” xuất hiện khá nhiều trong câu (8 lần), còn ký tự “M” xuất hiện ít hơn (4 lần). Vậy, nếu ta dùng 1 bit để mã hóa ký tự “C”, và 5 bit để mã hóa ký tự “M”, đại loại như vầy:

“C” = 0
“M” = 11111

Thì khi đó ta sẽ tiết kiệm được thêm: (3 x 8 + 3 x 4) – (1 x 8 + 5 x 4) = 36 – 28 = 8 bít.

Như vậy, ý tưởng chính ở đây là ta có thể không cần dùng đủ 8 bít để mã hóa cho một ký hiệu. Cần lập bảng mã sao cho độ dài (số bít) dành cho mỗi kí hiệu có thể khác nhau, kí hiệu nào xuất hiện nhiều lần thì nên dùng số bít ít, ký hiệu nào xuất hiện ít thì có thể mã hóa bằng từ mã dài hơn. Tuy nhiên, nếu mã hóa với độ dài thay đổi, thì khi giải mã ta làm thế nào phân biệt được xâu bít nào là mã hóa của ký hiệu nào? Một trong các giải pháp là dùng các dấu phẩy (“,”) để tách từ mã của các kí tự đứng cạnh nhau. Nhưng như thế số các dấu phẩy sẽ chiếm một không gian đáng kể trong bản mã. Và mã tiền tố là giải pháp phù hợp trong trường hợp này.

Mã tiền tố là cái gì vậy?

Mã tiền tố là bộ các từ mã của một tập hợp các kí hiệu sao cho từ mã của mỗi ký hiệu không là tiền tố (phần đầu) của từ mã một ký hiệu khác trong bộ mã đó.

Ví dụ, muốn mã hóa từ "PETE", với 3 ký tự “E”, “P”, “T”. Ta có:

- Nếu mã hóa bằng các từ mã có độ dài bằng nhau, ta dùng ít nhất 2 bit cho một ký tự. Chẳng hạn “E”=00, “P”=01, “T”=10. Khi đó mã hóa của cả từ là 0001010010.

- Nếu mã hóa “E”=0, “P”=01, “T”=11 thì bộ từ mã này không là mã tiền tố. Vì từ mã của “E” là tiền tố của từ mã của “P”.

- Nếu mã hóa “E”=0, “P”=10, “T”=11 thì bộ mã này là mã tiền tố. Khi đó, để mã hóa xâu “PETE” ta có 01010011.

Biểu diễn mã tiền tố bằng cây nhị phân

Một bộ mã tiền tố gồm n lá sẽ được biểu diễn bằng cây nhị phân n lá. Với qui ước, khi duyệt từ nút gốc đến lá, nếu rẽ sang phải là 1, và rẽ sang trái là 0. Ví dụ, bộ từ mã ở trên có thể được biểu diễn như sau:

    (*)
 0   |    1
  ---------
 |         |
(E)       (*)
      0    |   1
       --------
      |        |
     (P)      (T)

Thuật toán xây dựng mã tiền tố

Bây giờ chúng ta cùng nghiên cứu thuật toán xây dựng cây mã tiền tố. Đây là bước đầu để xây dựng một bảng mã bảng mã tiền tố tối ưu cho nội dung thông tin mà ta muốn nén.

Cây mã tiền tố là cây nhị phân. Mỗi nút có thể là nút lá hoặc nút trong (*), kèm theo một con số chứa tần số xuất hiện (trọng số) của nó. Nút lá chứa ký hiệu của chính nó và trọng số, kèm một liên kết đến nút cha. Nút trong chứa trọng số, kèm hai liên kết đến hai nút con, và một liên kết đến nút cha.

- Bước 0: Khởi tạo một rừng n cây, mỗi cây chỉ có 1 nút gốc và 1 nút lá. Nút lá chứa ký tự, và nút gốc chứa tần số xuất hiện của ký tự đó.

- Bước 1: Chọn hai cây có trọng số ở gốc nhỏ nhất hợp thành một cây bằng cách thêm một gốc mới nối với hai gốc đã chọn. Trọng số của gốc mới bằng tổng trộng số của hai gốc tạo thành nó.

- Bước 2: Lặp lại quá trình này đến khi rừng chỉ còn một cây (cây này là kết quả luôn đó!).

Ví dụ: cho xác xuất của 5 chữ cái a, b, c, d, e tương ứng là 0.10, 0.15, 0.30, 0.16, 0.29. Quá trình xây dựng cây Huffman diễn ra như hình sau:

(sao hổng chèn hình được vầy nè, mod nào hướng dẫn giùm đi!)

Khi đó, ta có bảng mã tiền tố cho các ký tự là:

a = 000
b = 001
d = 01
c = 10
e = 11

Và giải thuật nén file

Giả sử đã xây dựng được bộ mã Huffman cho tất cả các ký tự, chúng ta có thể nén file theo giải thuật sau:
- Đọc từng byte của file cần nén cho đến khi hết tệp
- Chuyển theo bộ mã thành xâu nhị phân
- Ghép với xâu nhị phân còn dư từ bước trước
- Nếu có đủ 8 bit trong xâu thì cắt ra 8 bít đầu ghi vào tệp nén
- Nếu đã hết tệp cần nén thì dừng

(còn tiếp)

[hailoc12]

Bài viết này hay lắm sonhn cứ tiếp tục đi. Sau này mình sẽ chuyển vào mục Nén tập tin trong [CTDL&GT] cùng các phương pháp khác. Lúc đó tìm hiểu có hệ thống có lẽ sẽ nhiều nguời quan tâm tới đề tài này hơn.

[rox_rook]

Đế tiếp tục bài viết của Sonhn, mình có sưu tầm được 1 đoạn code khá hay và cô đúc, không quá lườm thườm nhưng vẫn thể hiện được ý tưởng. Phần ý tưởng thì như Sonhn đã nêu, sau đây là toàn bộ code viết bằng C++, mình giữ tên nguyên tên tác giả và ko chỉnh sữa gì để tôn trọng công sức của người viết.

//------------------------------------------------------//  //  this coding is about huffman algorithm.//  in this coding, i assume that all of you know about //  huffman algorithm////  Author: Andy Gunawan//------------------------------------------------------- #include<iostream.h> struct tree{   int value;    char ch;    tree *left;    tree *right;}; struct input {   int frequency;    char character;    tree *address;}; void postorder(tree *root,int node,char *temp_bit){   node++;    if(root!=0)    {   temp_bit[node-1]='0';        postorder(root->left,node,temp_bit);        temp_bit[node-1]='\0';                temp_bit[node-1]='1';        postorder(root->right,node,temp_bit);        temp_bit[node-1]='\0';         if(root->ch!='\0')            cout<<root->ch<<" : "<<temp_bit<<endl;     }    node--;}    tree *inputTree(input num_input1,input num_input2){   tree *leftnode = new tree;    tree *rightnode = new tree;    tree *root=new tree;        if(num_input1.address=='\0')    {   leftnode->value = num_input1.frequency;        leftnode->ch = num_input1.character;        leftnode->left = '\0';        leftnode->right = '\0';    }    else    {   leftnode = num_input1.address;  }        if(num_input2.address=='\0')    {   rightnode->ch=num_input2.character;        rightnode->value=num_input2.frequency;        rightnode->left='\0';        rightnode->right='\0';    }    else    {   rightnode = num_input2.address; }     root->value=num_input1.frequency+num_input2.frequency;    root->ch='\0';    root->left=leftnode;    root->right=rightnode;     return root;} void bubble(input *number_input,int counter){   for(int i=0;i<counter-1;i++)        for(int j=i+1;j<counter;j++)            if(number_input[i].frequency > number_input[j].frequency)            {   input *temp = new input;                 temp->address = number_input[i].address;                temp->character = number_input[i].character;                temp->frequency = number_input[i].frequency;                number_input[i].address = number_input[j].address;                number_input[i].character = number_input[j].character;                number_input[i].frequency = number_input[j].frequency;                number_input[j].address = temp->address;                number_input[j].character = temp->character;                number_input[j].frequency = temp->frequency;                                delete temp;            }} int main(void){           int number,node=0;     cout<<"How many character will you input? ";    cin>>number;        char *temp_bit = new char[number];    input *num_input = new input[number];     for(int p=0;p<number;p++)    {   num_input[p].address='\0';        num_input[p].frequency=0;        num_input[p].character='\0';    }        for(int i=0;i<number;i++)    {   cout<<"\nEnter character: ";        cin>>num_input[i].character;        cout<<"Enter frequency: ";        cin>>num_input[i].frequency;    }     for(int j=0;j<number-1;j++)    {   bubble(num_input,number);         num_input[j+1].address=inputTree(num_input[j],num_input[j+1]);          num_input[j+1].frequency += num_input[j].frequency;        num_input[j+1].character = '\0';    }        cout<<endl;    postorder(num_input[number-1].address,node,temp_bit);    cout<<endl;     delete temp_bit;    delete num_input;    return 0;}

[thanhtien]

Vậy còn văn bản có dấu thì làm sao xác định tần số xuất hiện?
-xuống dòng...

[anaconda875]

Ví dụ, muốn mã hóa từ "PETE", với 3 ký tự “E”, “P”, “T”. Ta có:

- Nếu mã hóa bằng các từ mã có độ dài bằng nhau, ta dùng ít nhất 2 bit cho một ký tự. Chẳng hạn “E”=00, “P”=01, “T”=10. Khi đó mã hóa của cả từ là 0001010010.

- Nếu mã hóa “E”=0, “P”=01, “T”=11 thì bộ từ mã này không là mã tiền tố. Vì từ mã của “E” là tiền tố của từ mã của “P”.

- Nếu mã hóa “E”=0, “P”=10, “T”=11 thì bộ mã này là mã tiền tố. Khi đó, để mã hóa xâu “PETE” ta có 01010011.

Ai giải thích giúp em chỗ đổi chuỗi "PETE" sang nhị phân với. Quy luật thế nào nhỉ? Trường hợp 1 sao lại dùng 10 bít trong khi "PETE" có 4 chữ thôi (lẽ ra 8 bit 01001000 mới đúng chứ. Còn trường hợp 3 thì ngu luôn! Số bit lẻ trong khi "PETE" chẵn 4 ký tự

[logweb176]

..Bạn có thể cho mình link để tải giáo trình Kỹ thuật nén dữ liệu được k, mình cảm ơn Bạn nhiều nhiều

[dungdv1986]

Đang tìm hiểu vấn đề này, gặp chủ đề của bạn học được khá nhiều điều. Cám ơn bạn