1 GIỚI THIỆU CHUNG VỀ MÃ HÓA HUFFMAN. - Tài Liệu Text - 123doc

1. Trang chủ >
2. Kỹ thuật >
3. Điện - Điện tử - Viễn thông >

1 GIỚI THIỆU CHUNG VỀ MÃ HÓA HUFFMAN.

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 (178.73 KB, 13 trang )

Khoa Điện Tử Viễn ThôngGVHD: Nguyễn Văn Thọ- Để 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, đượcgọ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ểudiễ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ấtcả 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àikhô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 trongtà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ấthiệ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ệnnhiề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 ướcnà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áiniệ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ệukhô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ừ "LILEE", tập các ký hiệu cần mã hóa gồm 3 chữ cái"L","I","E".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ộtchữ cái chẳng hạn "L"=00, "E"=01, "I"=10. Khi đó mã hóa của cả từ là 0010000101.Để giải mã ta đọc hai bit một và đối chiếu với bảng mã.Nếu mã hóa "L"=0, "E"=01, "I"=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ừ LILEE phải đặt dấu ngăncách vào giữa các từ mã 0.11.0.01.01SVTH: Nguyễn Hữu HùngTrang 7Khoa Điện Tử Viễn ThôngGVHD: Nguyễn Văn ThọNếu mã hóa "L"=0, "E"=10, "I"=11 thì bộ mã này là mã tiền tố. Với bộ mã tiềntố này khi mã hóa xâu "LILEE" ta có 01101010.HoặcVí 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óaxâu “PETE” ta có 01010011.CHƯƠNG 2 : GIẢI THUẬT HUFFMAN VÀXÂY DỰNG CHƯƠNG TRÌNH2.1GIẢI THUẬT HUFFMAN.Các tập tin của máy tính được lưu dưới dạng các kí tự có chiều dài không đổi là8 bits. Trong nhiều tập tin, xác suất xuất hiện các kí tự này là nhiều hơn các kí tự khác,từ đó ta thấy ngay rằng nếu chỉ dùng một vài bit để biểu diễn cho các kí tự có xác suấtSVTH: Nguyễn Hữu HùngTrang 8Khoa Điện Tử Viễn ThôngGVHD: Nguyễn Văn Thọxuất hiện lớn và dùng nhiều bit hơn để biểu diễn cho các kí tự có xác suất xuất hiệnnhỏ thì có thể tiết kiệm được độ dài tập tin một cách đáng kể.Ví dụ, để mã hoá một chuỗi như sau:"ABRACADABRA"Nếu mã hoá chuỗi trên trong dạng mã nhị phân 5 bit ta sẽ có dãy bit sau:0000100010100100000100011000010010000001000101001000001Ðể giải mã thông điệp này, chỉ đơn giản là đọc ra 5 bits ở từng thời điểm vàchuyển đổi nó tương ứng với việc mã hoá nhị phân đã được định nghĩa ở trên. Trongmã chuẩn này, chữ D xuất hiện chỉ một lần sẽ cần số lượng bit giống chữ A xuất hiệnnhiều lần.Ta có thể gán các chuỗi bit ngắn nhất cho các kí tự được dùng phổ biến nhất, giảsử ta gán: A là 0, B là 1, R là 01, C là 10 và D là 11 thì chuỗi trên được biễu diễn nhưsau:0 1 01 0 10 0 11 0 1 01 0Ví dụ này chỉ dùng 15 bits so với 55 bits như ở trên, nhưng nó không thực sự làmột mã vì phải lệ thuộc vào khoảng trống để phân cách các kí tự. Nếu không có dấuphân cách thì ta không thể giải mã được thông điệp này. Ta cũng có thể chọn các từ mãsao cho thông điệp có thể được giải mã mà không cần dấu phân cách, ví dụ như: A là11, B là 00, C là 010, D là 10 và R là 011, các từ mã này gọi là các từ mã có tính prefix(Không có từ mã nào là tiền tố của từ mã khác). Với các từ mã này ta có thể mã hoáthông điệp trên như sau:1100011110101110110001111Với chuỗi đã mã hoá này ta hoàn toàn có thể giải mã được mà không cần dấuphân cách. Nhưng bằng cách nào để tìm ra bảng mã một cách tốt nhất? Vào năm 1952,D.Huffman đã phát minh ra một cách tổng quát để tìm ra bảng mã này một cách tốtnhất.- Bước đầu tiên trong việc xây dựng mã Huffman là đếm số lần xuất hiện của mỗi kí tựtrong tập tin sẽ được mã hoá.SVTH: Nguyễn Hữu HùngTrang 9Khoa Điện Tử Viễn ThôngGVHD: Nguyễn Văn Thọ- Bước tiếp theo là xây dựng một cây nhị phân với các tần số được chứa trong các nút.Hai nút có tấn số bé nhất được tìm thấy và một nút mới được tạo ra với hai nút con làcác nút đó với giá trị tần số của nút mới bằng tổng tần suất của hai nút con. Tiếp theohai nút mới với tần số nhỏ nhất lại được tìm thấy và một nút mới nữa lại được tạo ratheo cách trên. Lặp lại như vậy cho đến khi tất cả các nút được tổ hợp thành một câyduy nhất.- Sau khi có cây nhị phân, bảng mã Huffman được phát sinh bằng cách thay thế các tầnsố ở nút đáy bằng các kí tự tương ứng.2.2XÂY DỰNG CHƯƠNG TRÌNHThuật toán này vẫn dựa trên ý tưởng của Huffman là sử dụng một vài bit (bitcode) để biểu diễn một kí tự. Độ dài “mã bit” cho các kí tự không giống nhau: Kí tự xuất hiện nhiều lần→biểu diễn bằng mã ngắn. Kí tự xuất hiện ít → biểu diễn bằng mã dài. Tạo sẵn một cây “tối thiểu” ban đầu, dữ liệu nén sẽ được cập nhật dần vào cây.2.2.1 Thuật toán nén:Bước 1: Tìm hai ký tự có trọng số nhỏ nhất ghép lại thành một, trọng số của ký tựmới bằng tổng trọng số của hai ký tự đem ghép.Bước 2: Trong khi số lượng ký tự trong danh sách còn lớn hơn một thì thực hiệnbước một, nếu không thì thực hiện bước ba.SVTH: Nguyễn Hữu HùngTrang 10Khoa Điện Tử Viễn ThôngGVHD: Nguyễn Văn ThọBước 3: Tách ký tự cuối cùng và tạo cây nhị phân với quy ước bên trái mã 0, bênphải mã 1.2.2.2 Các vấn đề trong việc xây dựng chương trình2.2.2.1 Các cấu trúc dữ liệu sử dụng trong chương trình:typedef struct node{char Data;// Kí tự alphaint TSuat;// Tần suất kí tự alphanode * Left;// Con trỏ tráinode * Right;// Con trỏ phải};typedef node * HTree;struct list{char alphaint ts;// Kí tự alpha;// 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 ứngvớ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.2.2.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à chotần số tương ứng bằng 1.2.2.2.3 Cài đặt cây Huffman và tần số (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).SVTH: Nguyễn Hữu HùngTrang 11

Xem Thêm

Tài liệu liên quan

• nghiên cứu về kỹ thuật mã hóa của huffman
  • 13
  • 2,313
  • 8
• Công văn số 127/TCT-CS về việc thời gian miễn, giảm thuế thu nhập doanh nghiệp do Tổng cục Thuế ban hành
  • 1
  • 0
  • 0
• Công văn số 1396 TCT/DNK của Tổng cục Thuế về thuế đối với chuyển quyền sử dụng đất và việc xét miễn, giảm thuế TNDN theo diện mới thành lập đối với cơ sở mua lại máy móc thiết bị đã qua sử dụng
  • 1
  • 0
  • 0

Tải bản đầy đủ (.docx) (13 trang)

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(65.55 KB) - nghiên cứu về kỹ thuật mã hóa của huffman-13 (trang) Tải bản đầy đủ ngay ×