TAILIEUCHUNG - Tài liệu hướng dẫn thực hành môn Cấu trúc dữ liệu và giải thuật - Bài 6: Nén Huffman

Trong bài 6 sinh viên sẽ thực hành các thao tác về nén Huffman. Sau khi hoàn thành bài thực hành này, sinh viên có thể nắm rõ các bước của thuật toán nén huffman tĩnh. . | NÉN HUFFMAN M C TIÊU Hoàn thành bài thực hành này, sinh viên có thể: - Nắm rõ các bước của thuật toán nén huffman tĩnh. TH I GIAN TH C HÀNH Từ 120 phút đến 400 phút TÓM T T Nén Huffman là phương pháp mã hóa bằng mã có độ dài thay đổi (variable length encoding) trong đó chỉ sử dụng vài bit để biểu diễn 1 ký tự và độ dài mã bit cho các ký tự không giống nhau (ký tự xuất hiện nhiều lần được biểu diễn bằng mã ngắn và ngược lại). Thuật toán nén Huffman bao gồm 5 bước: - B1: Lập bảng thống kê tần số xuất hiện của các ký tự. B2: Xây dựng cây Huffman dựa vào bảng thống kê tần số xuất hiện. B3: Phát sinh bảng mã bit cho từng ký tự tương ứng. B4: Duyệt tập tin, thay thế các ký tự trong tập tin bằng mã bit tương ứng. B5: Lưu lại thông tin của cây Huffman cho giải nén. N I DUNG TH C HÀNH Cài đặt thuật toán nén Huffman. Dữ liệu được nhập từ file “”. Xuất ra màn hình chuỗi bit tương ứng với nội dung nhập. Ví dụ Với file có nội dung: ABBCCCDDDD Chuỗi bit tương ứng khi xuất ra sẽ là 10010110 11111110 000 Trong đó A (100) B (101) C(11) và D(0) PHÂN TÍCH Để biễu diễn một nút trong cây huffman, ta dùng: struct NODE { unsigned char c; int freq; bool used; int int nLeft; nRight; // // // // // // ký t c a node s l n xu t hi n ñánh d u node có thu c b ng th ng kê ko used = true: ko thu c b ng th ng kê ch s nút con n m bên trái ch s nút con n m bên ph i }; Cây Huffman được lưu trữ dưới dạng mảng NODE huffTree[MAX_NODE]; Trong đó MAX_NODE là 1 số nguyên > số lượng nút tối đa của cây Huffman. (Ta có thể thấy số lượng nút tối đa của cây Huffman sẽ 0) • Tạo node mới của cây Huffman có 2 nút con i, j Thêm node được tạo vào cuối mảng, sử dụng nLeft và nRight để lưu vị trí 2 nút con. huffTree[nNode].freq = huffTree[i].freq + huffTree[j].freq; huffTree[nNode].nLeft = i; huffTree[nNode].nRight = j; • Loại phần tử x, y khỏi bảng thống kê. Để loại x, y khỏi bảng thống kê, gán huffTree[i].used = true; huffTree[j].used = true; • Thêm phần tử nNode vào bảng .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu
• Nén Huffman
• Thuật toán nén huffman tĩnh
• Xây dựng cây Huffman
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp