tailieunhanh - 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ý