TAILIEUCHUNG - Bài giảng Giải thuật nén Huffman

Bài giảng "Giải thuật nén Huffman" có nội dung trình bày về nén tĩnh (Static Huffman); Nén động (Adaptive Huffman); Cây Huffman; Mã hóa Huffman. Để hiểu rõ hơn mời các bạn cùng tham khảo nội dung chi tiết của bài giảng này. | Giải thuật nén Huffman om .c Nén tĩnh Static Huffman ng co an Nén động Adaptive Huffman th o ng du u cu https tailieudientucntt Nén tĩnh Static Huffman om .c ng co an th o ng du u cu https tailieudientucntt Giới thiệu om Mã hóa Huffman David A. Huffman là một .c thuật toán mã hóa dùng để nén dữ liệu. ng co Dựa trên bảng tần suất xuất hiện các kí tự an cần mã hóa để xây dựng một bộ mã nhị th phân cho các kí tự đó sao cho dung lượng o ng số bit sau khi mã hóa là nhỏ nhất. du u cu https tailieudientucntt Trong bản mã ASCII mỗi ký tự được biểu diễn bằng chuỗi 8 bit. Ký tự Mã bit om Ý tưởng A 01000001 Giảm số bit để biểu diễn 1 ký tự .c B 01000010 ng Dùng chuỗi bit ngắn hơn để biểu diễn ký tự xuất hiện nhiều C 01000011 D 01000100 co Sử dụng mã tiền tố để phân cách các ký tự E 01000101 an th o ng du Ký tự Mã bit Ký tự Tần suất Ký tự Mã bit Ký tự Mã tiền tố A 000 A 9 A 000 A 00 u cu B 001 B 15 B 1 B 11 C 010 C 10 C 01 C 01 D 011 D 6 D 011 D 100 E 100 E 7 E 100 E 101 https tailieudientucntt Cây Huffman om .c Là cây nhị phân mỗi nút chứa ký tự và trọng số tần suất của ký tự đó . ng co Mỗi ký tự được biểu diễn bằng 1 nút lá tính tiền tố . an th Nút cha có tổng ký tự tổng trọng số của 2 nút con. o ng du Các nút có trọng số ký tự tăng dần từ trái sang phải. u cu Các nút có trọng số lớn nằm gần nút gốc. Các nút có trọng số nhỏ nằm xa nút gốc hơn. https tailieudientucntt Mã Huffman om Là chuỗi nhị phân được sinh ra dựa trên cây Huffman. .c ng Mã Huffman của ký tự là đường dẫn từ nút gốc đến nút lá đó. co Sang trái ta được bit 0 an Sang phải ta được bit 1 th ng Có độ dài biến đổi tối ưu bảng mã . o du Các ký tự có tần suất lớn có độ dài ngắn. u cu Các ký tự có tần suất nhỏ có độ dài dài hơn. https tailieudientucntt Thuật toán nén tĩnh Static Huffman om B1 Duyệt file lập bảng thống kê tuần suất xuất hiện của mỗi ký

• Kỹ thuật lập trình
• Bài giảng Giải thuật nén Huffman
• Nén tĩnh Static Huffman
• Nén động Adaptive Huffman
• Mã hóa Huffman
• Thuật toán nén 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
• Nén dữ liệu
• Giải thuật nén Huffman tĩnh
• Thuật toán nén
• Nén RLE trên PCX
• Nén RLE trên BMP
• Tính chất cây Huffman động
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Giải thuật nén RLE
• Giải thuật nén Huffman
• Nén bảo toàn thông tin
• Thuật toán giải nén
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu và giải thuật
• Nguyên tắc nén dữ liệu
• Bài toán giải thuật
• Thuật ngữ nén dữ liệu
• Khái niệm nén dữ liệu
• Tạo cây Huffman
• Phát sinh mã bit
• Nén Run Length Encoding
• Nén Huffman tĩnh