ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

BÀI TẬP LỚN
MÔN HỌC: MẬT MÃ VÀ AN TOÀN DỮ LIỆU
ĐỀ TÀI: Nén dữ liệu Huffman
Họ tên: Nguyễn Thị Thu Hà
Lớp: Cao học K20 - HTTT
Mã học viên: 13025079
Giảng viên hướng dẫn: PGS.TS. Trịnh Nhật Tiến
Hà Nội - 2014
MỤC LỤC
MỤC LỤC 2
1. Giới thiệu chung về nén và giải nén 3
2. Ý tưởng Nén dữ liệu Hu!man 3
3. Xây dựng cây hu!man 6
4. Nén và giải nén Hu!man 10
4.1. Nén tập -n 10
4.2. Giải nén tập -n: 10
5. Cài đặt chương trình 16
1. Giới thiệu chung về nén và giải nén
 Giới thiệu chung:
− Hầu hết các tập tin trong máy tính có nhiều thông tin dư thừa
− Nén tập tin thực chất là mã hóa lại thông tin dư thừa
 Tầm quan trọng:
* Giảm kích thước dữ liệu:
− Để lưu trữ.
− Truyền dữ liệu.
* Tăng tính bảo mật.
2. Ý tưởng Nén dữ liệu Huffman
 Tác giả:

đứ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ảng
mã.
Và mã tiền tố là giải pháp phù hợp trong trường hợp này.
 Mã tiền tố là gì?
− Nếu mã hóa “A”=0, “B”=01, “C”=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 “B”.
− Nếu mã hóa “A”=0, “B”=10, “C”=11 thì bộ mã này là mã tiền tố. Khi
đó, để mã hóa xâu “ACB” ta có 01110.
 Xây dựng và biểu diễn mã tiền tố
− Được xây dựng và biểu diễn bằng cây nhị phân gọi là cây Huffman
3. Xây dựng cây huffman
 Ví dụ: Giả sử ta có dữ liệu như sau: “ma huffman”
− Tạo 1 cây mới với cây con trái và cây con phải là hai cây từ mảng cây
có tần suất nhỏ nhất, tức là 2 cây ở vị trí 0 và 1
− Khóa của cây cha là chuỗi gồm chuỗi cây con trái và cây con phải
− Tần suất của cây cha là của 2 cây con trái và phải cộng lại
− Sắp xếp lại mảng cây theo tần suất tăng dần, nếu bằng nhau ưu tiên
theo kí tự đầu của khóa
- Tiếp tục chọn 2 phần tử đầu của mảng cây để tạo cây cha mới
− Sắp xếp lại mảng cây
− Tiếp tục tạo cây mới từ 2 cây 0 và 1 của mảng cây
− Tiếp tục sắp xếp lại
− Tiếp tục xây dựng cây mới
− Tiếp tục sắp xếp
− Tiếp tục xây dựng cây mới
− Tiếp tục xây dựng cây mới
− Tiếp tục đến khi mảng cây chỉ còn 1 phần tử, ta được cây Huffman
hoàn chỉnh.
4. Nén và giải nén Huffman