Mã hóa chuỗi ký tự bằng thuật toán huffman năm 2024

Giải thuật Huffman được sử dụng trong việc nén các dữ liệu dạng ký tự bằng việc sử dụng ít bit nhất có thể. Ví dụ như chúng ta có chuỗi “ABC” cần phải mã hóa. Nếu sử dụng mã ASCII với 8 bit cho mỗi ký tự thì với chuỗi “ABC” trên, chúng ta phải sử dụng là: 8 x 3 = 24 bit. Tuy nhiên, nếu sử dụng giải thuật Huffman để nén chuỗi trên thì chúng ta chỉ cần sử dụng: 5 bit. Trong đó, mỗi ký tự sẽ được lưu theo các bit như sau (Không phải là duy nhất, có thể có các cách đánh mã khác cho các ký tự này):

A: 11 B: 10 C: 0

Để biết chi tiết về giải thuật Huffman cũng như cách cài đặt tổng quát thì mọi người có thể xem tại http://vi.wikipedia.org/wiki/M%C3%A3_Huffman. Phần này chúng ta sẽ chỉ tìm cách cài đặt giải thuật Huffman cụ thể bằng ngôn ngữ C#.

Các lớp được sử dụng trong phần này bao gồm:

1. Lớp FreqTable: Đây là lớp được sử dụng để lưu trữ thông tin về tỉ lệ xuất hiện của các ký tự trong chuỗi. Lớp này có constructor nhận một chuỗi để nén và sử dụng một HashTable để lưu dữ liệu

2. Lớp HuffmanTree: Lớp này được dùng để lưu trữ câu Huffman, khai báo của lớp này như sau:

class HuffmanTree : IComparable {

public string c;
public int frequency;
public HuffmanTree left=null, right=null;

# region IComparable Members

public int CompareTo(object obj)
{
    return frequency.CompareTo(((HuffmanTree)(obj)).frequency);
}

# endregion }

– c là biến dùng để lưu trữ ký tự (nếu là nút lá) và để lưu chuỗi kết hợp của hai nút con (nếu là nút trung gian)

– frequency: lưu trữ tỉ lệ xuất hiện của c (nếu là nút là) hoặc lưu tổng số lần xuất hiện của hai nút con (nếu là nút trung gian)

– left, right: hai biến kiểu HuffmanTree được sử dụng để có thể lưu hai nút con, nếu là lá thì left và right sẽ bằng null

– Ngoài ra, lớp này còn thực thi interface IComparable để có thể thực hiện được phép so sánh hai nút (sử dụng khi chúng ta sắp xếp các nút từ nhỏ đến lớn). Việc so sánh này thật ra chính là việc so sánh tỉ lệ xuất hiện của hai nút này.

3. Lớp HuffmanCoding: Lớp này sẽ chứa các lớp kia và cài đặt các phương thức chính như: Encode, Decode. Trong lớp này, chúng ta có sử dụng một List để làm một hàng đợi ưu tiên các nút kiểu HuffmanTree (sau khi thêm một nút vào list này thì chúng ta gọi ngay phương thức Sort để sắp xếp)

Các bước thực hiện trong phương thức Encode(string input) như sau

• Xây dựng bảng thống kê tỉ lệ xuất hiện của các ký tự trong chuỗi input
• Duyệt qua danh sách các ký tự có trong chuỗi và thực hiện việc tạo một đối tượng HuffmanTree mới với giá trị c là ký tự đang xét. Sau đó thêm đối tượng này vào hàng đợi ưu tiên
• Sắp xếp hàng đợi theo thứ tự xuất hiện từ nhỏ đến lớn
• Trong khi có hơn 1 nút còn nằm trong hàng đợi thì thực hiện các việc sau:- Ghép hai phần tử đầu tiên trong hàng đợi thành một phần tử mới

– Bỏ hai phần tử đầu tiên trong hàng đợi ra khỏi hàng đợi và thêm phần tử mới tạo vào hàng đợi

– Sắp xếp lại hàng đợi

• Cuối cùng, sau khi đã xây dựng xong cây Huffman thì chúng ta sẽ thực hiện duyệt qua mỗi ký tự trong chuỗi input. Với mỗi ký tự đó thì sinh ra mã (codeword) tương ứng bằng cách duyệt cây Huffman từ gốc. Cách duyệt cho ký tự c như sau:- khởi tạo chuỗi s là rỗng, gán nút bắt đầu tìm là nút gốc

– Kiểm tra nếu thấy nút trái có chứa c thì gán nút tiếp theo là nút trái, đồng thời s = s + “0”. Nếu nút phải chứa c thì gán nút tiếp theo là nút phải, đồng thời s = s + “1”

– Nếu như nút đang xét có left, right bằng null thì đó là nút lá, dừng duyệt và trả về chuỗi s (chính là codeword của c)

Để thực hiện việc decode theo cây Huffman đã xây dựng thì chúng ta thực hiện theo các bước sau (Luôn bắt đầu từ nút gốc):

• * Đọc một ký tự, nếu ký tự này bằng 0 thì đi qua nhánh trái, nếu ký tự này bằng 1 thì đi qua nhánh phải.
  • Nếu nút đang xét là nút lá thì lấy giá trị c của nút đó, gán nút bắt đầu là gốc và quay trở lại bước đầu tiên
  • Nếu nút đang xét không phải nút lá thì quay lại giống như bước đầu (nếu 0, đi qua trái, nếu 1, đi qua phải….)

Chương trình Demo giải thuật Huffman (sử dụng .NET 3.0, C#): https://drive.google.com/file/d/0B5iZPOjOn1osLTdrNjc3NllXbDQ/view?usp=sharing&resourcekey=0-mBhpuSyqYItoo45m1Ld6FQ

1.Giới thiệu về thuật toán Huffman: - Trong khoa học máy tính và lý thuyết thông tin, mã Huffman là một thuật toán mã hóa dùng để nén dữ liệu. Nó dựa trên bảng tần suất xuất hiện các kí tự cần mã hóa để xây dựng một bộ mã nhị phân cho các kí tự đó sao cho dung lượng (số bít) sau khi mã hóa là nhỏ nhất. - Thuật toán được đề xuất bởi David A. Huffman khi ông còn là sinh viên Ph.D. tại MIT, và công bố năm 1952 trong bài báo "A Method for the Construction of Minimum-Redundancy Codes". Sau này Huffman đã trở thành một giảng viên ở MIT và sau đó ở khoa Khoa học máy tính của Đại học California, Santa Cruz, Trường Kỹ nghệ Baskin (Baskin School of Engineering). - Mã Huffman là một mã tiền tố. Sau đây là khái niệm về mã tiền tố: 2. Mã tiền tố (prefix-free binary code) - Để mã hóa các kí hiệu (kí tự, chữ số, .) ta thay chúng bằng các xâu nhị phân, được gọi là từ mã của kí hiệu đó. Chẳng hạn bộ mã ASCII, mã hóa cho 256 kí hiệu là biểu diễn nhị phân của các số từ 0 đến 255, mỗi từ mã gồm 8 bít. Trong ASCII từ mã của kí tự "a" là 1100001, của kí tự "A" là 1000001. Trong cách mã hóa này các từ mã của tất cả 256 kí hiệu có độ dài bằng nhau (mỗi từ mã 8 bít). Nó được gọi là mã hóa với độ dài không đổi. - Khi mã hóa một tài liệu có thể không sử dụng đến tất cả 256 kí hiệu. Hơn nữa trong tài liệu chữ cái "a" chỉ có thể xuất hiện 1000000 lần còn chữ cái "A" có thể chỉ xuất hiện 2, 3 lần. Như vậy ta có thể không cần dùng đủ 8 bít để mã hóa cho một ký hiệu, hơn nữa độ 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. Như vậy ta có việc mã hóa với độ dài thay đổi. Tuy nhiên, nếu mã hóa với độ dài thay đổi, 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 (",") hoặc một kí hiệu quy ước nào đó để 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ã. Một cách giải quyết khác dẫn đến khái niệm mã tiền tố - 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ỤC LỤC I. Thuật toán Huffman II. Khái quát về chương trình III. Các vấn đề chung trong xây dựng chương trình

6 trang | Chia sẻ: | Lượt xem: 3621 | Lượt tải: 0

Bạn đang xem nội dung tài liệu Tài liệu Cấu trúc dữ liệu và giải thuật 2: Huffman code, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên

ĐỒ ÁN MÔN HỌC Môn: Cấu Trúc Dữ Liệu Và Giải Thuật 2 Đề Tài: Huffman Code Giảng Viên: Phạm Thi Vương Thành viên nhóm 4: 1. Lê Xuân Bình 08050135 2. Ngô Trường Hải 08050099 3. Lại Duy Thanh 08050131 4. Nguyễn Văn Chính 08050165 I. Thuật toán Huffman: 1.Giới thiệu về thuật toán Huffman: - Trong khoa học máy tính và lý thuyết thông tin, mã Huffman là một thuật toán mã hóa dùng để nén dữ liệu. Nó dựa trên bảng tần suất xuất hiện các kí tự cần mã hóa để xây dựng một bộ mã nhị phân cho các kí tự đó sao cho dung lượng (số bít) sau khi mã hóa là nhỏ nhất. - Thuật toán được đề xuất bởi David A. Huffman khi ông còn là sinh viên Ph.D. tại MIT, và công bố năm 1952 trong bài báo "A Method for the Construction of Minimum-Redundancy Codes". Sau này Huffman đã trở thành một giảng viên ở MIT và sau đó ở khoa Khoa học máy tính của Đại học California, Santa Cruz, Trường Kỹ nghệ Baskin (Baskin School of Engineering). - Mã Huffman là một mã tiền tố. Sau đây là khái niệm về mã tiền tố: 2. Mã tiền tố (prefix-free binary code) - Để mã hóa các kí hiệu (kí tự, chữ số, ...) ta thay chúng bằng các xâu nhị phân, được gọi là từ mã của kí hiệu đó. Chẳng hạn bộ mã ASCII, mã hóa cho 256 kí hiệu là biểu diễn nhị phân của các số từ 0 đến 255, mỗi từ mã gồm 8 bít. Trong ASCII từ mã của kí tự "a" là 1100001, của kí tự "A" là 1000001. Trong cách mã hóa này các từ mã của tất cả 256 kí hiệu có độ dài bằng nhau (mỗi từ mã 8 bít). Nó được gọi là mã hóa với độ dài không đổi. - Khi mã hóa một tài liệu có thể không sử dụng đến tất cả 256 kí hiệu. Hơn nữa trong tài liệu chữ cái "a" chỉ có thể xuất hiện 1000000 lần còn chữ cái "A" có thể chỉ xuất hiện 2, 3 lần. Như vậy ta có thể không cần dùng đủ 8 bít để mã hóa cho một ký hiệu, hơn nữa độ 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. Như vậy ta có việc mã hóa với độ dài thay đổi. Tuy nhiên, nếu mã hóa với độ dài thay đổi, 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 (",") hoặc một kí hiệu quy ước nào đó để 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ã. Một cách giải quyết khác dẫn đến khái niệm mã tiền tố - 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ã ấy. - Đương nhiên mã hóa với độ dài không đổi là mã tiền tố. - Ví dụ: Giả sử mã hóa từ "ARRAY", tập các ký hiệu cần mã hóa gồm 3 chữ cái "A","R","Y". 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 chữ cái chẳng hạn "A"=00, "R"=01, "Y"=10. Khi đó mã hóa của cả từ là 0001010010. Để giải mã ta đọc hai bit một và đối chiếu với bảng mã. Nếu mã hóa "A"=0, "R"=01, "Y"=11 thì bộ từ mã này không là mã tiền tố ví từ mã của "A" là tiền tố của từ mã của "R". Để mã hóa cả từ ARRAY phải đặt dấu ngăn cách vào giữa các từ mã 0,01,01,0,11 Nếu mã hóa "A"=0, "R"=11, "Y"=10 thì bộ mã này là mã tiền tố. Với bộ mã tiền tố này khi mã hóa xâu "ARRAY" ta có 01111010. 3. Biểu diễn mã tiền tố trên cây nhị phân: - Nếu có một cây nhị phân n lá ta có thể tạo một bộ mã tiền tố cho n ký hiệu bằng cách đặt mỗi ký hiệu vào một lá. Từ mã của mỗi kí hiệu được được tạo ra khi đi từ gốc tới lá chứa ký hiệu đó, nếu đi qua cạnh trái thì ta thêm số 0, đi qua cạnh phải thì thêm số 1. - Ví dụ: Cây 3 lá sau đây biểu diễn bộ mã của A,R,Y trong ví dụ trên * 0/ \1 A * 0/ \1 Y R Từ mã của "A" là 0, của "R" là 11, của "Y" là 10. 4. Giải thuật Huffman - Thành lập cây nhị phân từ tập hợp các kí hiệu trong thông báo, mỗi kí hiệu là một nút lá của cây. Cách thành lập cây như sau: - Chọn hai nút a,b có xác suất nhỏ nhất trong tập hợp các nút, giả sử xác suất nút a nhỏ hơn hoặc bằng xác suất nút b. Thành lập cây nhị phân có nút gốc x, con trái là a, con phải là b. Nút x có xác suất bằng tổng xác suất của a và b. - Tập hợp các nút bây giờ là các nút còn lại (đã loại bỏ a, và nút b). Lặp lại một cách đệ qui quá trình trên tập hợp đang xét cho đến khi tập này chỉ còn lại một nút.  - Mã của a, b sẽ tìm được bằng cách lấy mã của x nối thêm 0 cho a và 1 cho b. Mã của nút gốc là rỗng. - Như vậy thực chất quá trình trên là ta xây dựng một cây nhị phân từ tập hợp các ký tự muốn mã hoá, cuối cùng ta được một cây nhị phân có lá là các ký tự đó. Mã của một ký tự là một đường đi trên cây từ gốc đến lá chứa kí tự, với 0 đi sang trái còn 1 đi sang phải. Yï tưởng của giải thuật mã hoá cũng hết sức đơn giản, ta tìm bộ mã cho các kí tự sao cho các kí tự có tần suất xuất hiện cao (xác suất xuất hiện là lớn) sẽ được mã ngắn (gần với gốc) để độ dài trung bình để mã hoá một kí tự là nhỏ nhất. Ví dụ: Cho bảng tần suất của 5 chữ cái A,B,C,D,E như sau tương ứng là 0.10; 0.15; 0.30; 0.16; 0.29 A B C D E 0.10 0.15 0.30 0.16 0.29 Như vậy bộ mã tối ưu tương ứng là: A B C D E 010 011 11 00 10 II. Khái quát về chương trình: 1. Bài toán: Cho một dòng văn bản nhập từ bàn phím: - Xây dựng cây Huffman để giải mã dòng văn bản - Hiển thị cây Huffman và bảng mã Huffman ra màn hình - Thực hiện mã hóa dòng văn bản và dải mã - Mở rộng mã hóa và giải mã một file văn bản. Kết quả giải mã và mã hóa được ghi vào 2 file văn bản khác. 2. Cấu trúc chương trình: EnStr(): Mã hóa chuỗi. DeStr(): Giải mã chuỗi. EnFile(): Mã hóa file. DeFile(): Giải mã file. CreateHuffman(): Cài đặt cây Huffman, được sử dụng trong các hàm trên. Duyet(): Tạo bảng mã cho các ký tự, được sử dụng trong các hàm mã hóa. III. Các vấn đề chung trong xây dựng chương trình: 1. Các cấu trúc dữ liệu sử dụng trong chương trình: Code: typedef struct node { char Data ;// Kí tự alpha int TSuat ;// Tần suất kí tự alpha node * Left ;// Con trỏ trái node * Right ;// Con trỏ phải }; typedef node * HTree ; struct list { char alpha ;// Kí tự alpha int ts ;// Tần suất char code[max] ;// Mảng lưu trữ mã nhị phân }; - Kiểu dữ liệu của mảng node[] dùng để cài đặt cây Huffman. Các node tương ứng với ký tự (node.alph nếu có). node.Left, node.Right, tương ứng là chỉ số của nút con trái, con phải, Node.TSuat chứa tổng tần số các nút lá thuộc nhánh của nó. 2. Lập bộ ký tự (a[i].alph) và tần số tương ứng (a[i].ts) từ một xâu ký tự (s): - Đọc ký tự đầu tiên của xâu cho vào a[0].alpha tương ứng là a[0].ts bằng 1. - Duyệt từng ký tự còn lại của xâu, nếu gặp ký tự nào đã có trong mảng a[i].alph thì tăng a[i].ts lên 1, nếu chưa có ký tự đó thì thêm phần tử mới vào mảng và cho tần số tương ứng bằng 1. 3. Cài đặt cây Huffman từ tập ký tự và tần số cho trước (chứa trong mảng a[]). - Sắp xếp lại các a - Khởi tạo các node, node.alph và node.TSuat tương ứng với a.alph và a.ts sau khi đã sắp xếp. Các thành phần còn lại có giá trị là NULL (chưa xác định). - Tạo cây Huffman bằng cách chèn thêm nút mới đồng thời sắp xếp lại theo thứ tự tần số tăng dần. 4. Mã hóa: - Đọc từng ký tự của chuỗi (hoặc file), gặp phần tử nào thì hiển thị xâu mã hóa tương ứng hoặc ghi thêm xâu mã hóa tương ứng của ký tự đó vào file đã mã hóa (fileout). 5. Giải mã: - Duyệt cây Huffman từ trên xuống, gặp 0 thì nhảy xuống con trái, gặp 1 thì nhảy xuống con phải, cho tới khi gặp node có thành phần alph khác NULL. - Nếu gặp node có thành phần alph khác NULL thì hiển thị ký tự của node đó và nhảy về gốc End