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.
Nội dung trích xuất từ tài liệu:
Bài giảng Giải thuật nén HuffmanGiả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 CuuDuongThanCong.com https://fb.com/tailieudientucntt Nén tĩnh (Static Huffman) om .c ng co an th o ng du ucuCuuDuongThanCong.com https://fb.com/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 CuuDuongThanCong.com https://fb.com/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 duKý 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 cuB 001 B 15 B 1 B 11C 010 C 10 C 01 C 01D 011 D 6 D 011 D 100E 100 E 7 E 100 E 101 CuuDuongThanCong.com https://fb.com/tailieudientucntt Cây Huffman om .cLà 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 coMỗi ký tự được biểu diễn bằng 1 nút lá (tính tiền tố). an thNút cha có tổng ký tự, tổng trọng số của 2 nút con. o ng duCác nút có trọng số, ký tự tăng dần từ trái sang phải. u cuCá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. CuuDuongThanCong.com https://fb.com/tailieudientucntt Mã Huffman omLà chuỗi nhị phân được sinh ra dựa trên cây Huffman. .c ...