HUFFMAN CODE - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.doc) (6 trang)

Trang chủ

Luận Văn - Báo Cáo

Công nghệ thông tin

HUFFMAN CODE

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (140.02 KB, 6 trang )

Nhóm 4: Huffman CodePage 1http:// ww w.eboo k. ed u.v n ĐỒ ÁN MÔN HỌCMôn: Cấu Trúc Dữ Liệu VàGiải Thuật 2Đề Tài: Huffman CodeGiảng Viên: Phạm Thi VươngThành viên nhóm 4:1. Lê Xuân Bình 080501352. Ngô Trường Hải080500993. Lại Duy Thanh 080501314. Nguyễn Văn Chính 08050165 Page 2http:// ww w.eboo k. ed u.v nNhóm 4: Huffman Code 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ậttoá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ầnmã 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ênPh.D. tại MIT, và công bố năm 1952 trong bài báo "A Method for the Constructionof 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 256kí 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. TrongASCII từ mã của kí tự "a" là 1100001, của kí tự "A" là 1000001. Trong cách mã hóanà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óacho 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. Tuynhiê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 đượcxâ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ấuphẩy (",") hoặc một kí hiệu quy ước nào đó để tách từ mã của các kí tự đứngcạ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 Page 3http:// ww w.eboo k. ed u.v nNhóm 4: Huffman Code 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ăncách vào giữa các từ mã 0,01,01,0,11Nế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/ \1A *0/ \1Y RTừ 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ệulà 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ấtnú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ạimộ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 Page 4http:// ww w.eboo k. ed u.v nNhóm 4: Huffman Code 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 chob. 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ậphợ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 đisang 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.29A B C D E0.10 0.15 0.30 0.16 0.29Như vậy bộ mã tối ưu tương ứng là: A B C D E010 011 11 00 10II. 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ự alphaint TSuat;// Tần suất kí tự alpha node * Left;// Con trỏ tráinode * Right;// Con trỏ phải};typedef node * HTree;struct list{ char alpha;// Kí tự alpha int ts;// Tần suấtchar 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útcon 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].alphthì 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ài liệu liên quan

Code SQL.doc
- 141
- 883
- 2
Source code Server.doc
- 6
- 1
- 2
SOURCE CODECLIENT.doc
- 13
- 551
- 0
Rate-Distortion Analysis and Traffic Modelling of Scalable Video Coders
- 172
- 470
- 0
Demo Google Code
- 40
- 323
- 1
Huffman Code
- 6
- 2
- 32
nghiên cứu thuật toán của các loại mã nén Shannon-Fano và Huffman
- 61
- 1
- 5
bài toán CODE ANSYS - MATLAB
- 14
- 515
- 1
Code và giao diện chương trình
- 13
- 371
- 0
ĐỀ tài cây mã HUFFMAN (TOÁN ỨNG DỤNG)
- 24
- 362
- 6