Ngôn ngữ HTML
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (2.46 MB, 35 trang )
ĐỒ ÁN MÔN HỌC
Môn: Cấu Trúc Dữ Liệu Và
Giải Thuật 2
Đề Tài: Huffman Code
Giảng Viên: Phạm Thi Vương
Nhóm 4:
1. Nguyễn Văn Chính 08050165
2. Lê Xuân Bình 08050135
3. Ngô Trường Hải 08050099
4. Lại Duy Thanh 08050131
1Nhóm 44/24/13
2Nhóm 44/24/13
I. Thuật toán Huffman:
1. Giới thiệu về thuật toán Huffman:
Trong khoa học máy tính và lý thuyết thông tin,
mã Huffman là một thuật toán mã hóa dùng để
nén dữ liệu.
Nó dựa trên bảng tần suất xuất hiện các kí tự cần
mã hóa để xây dựng một bộ mã nhị phân cho các
kí tự đó sao cho dung lượng (số bít) sau khi mã
hóa là nhỏ nhất.
3Nhóm 44/24/13
4
Mã nén Huffman
Mã Huffman được sử dụng rộng rãi và là một
kỹ thuật rất hiệu quả đối với việc nén dữ liệu.
nó có thể tiết kiệm được tới 20% − 90% tùy
theo từng file bị nén.
Huffman đề xuất một thuật toán tham lam sử
dụng một bảng tần suất xuất hiện của các ký tự
để xây dựng lên một sơ đồ tốt nhất biểu diễn
các ký tự bằng một xâu nhị phân.
David A. Huffman
4/24/13
Nhóm 4 5
Thuật toán được đề xuất bởi David A. Huffman
khi ông còn là sinh viên Ph.D. tại MIT, và công bố
năm 1952 trong bài báo "A Method for the
Construction of Minimum-Redundancy Codes".
Sau này Huffman đã trở thành một giảng viên ở
MIT và sau đó ở khoa Khoa học máy tính của Đại
học California, Santa Cruz, Trường Kỹ nghệ
Baskin (Baskin School of Engineering).
Mã Huffman là một mã tiền tố. Sau đây là khái
niệm về mã tiền tố:
6Nhóm 4
- Để mã hóa các kí hiệu (kí tự, chữ số, ...) ta
thay chúng bằng các xâu nhị phân, được gọi là
từ mã của kí hiệu đó.
Chẳng hạn bộ mã ASCII, mã hóa cho 256 kí
hiệu là biểu diễn nhị phân của các số từ 0 đến
255, mỗi từ mã gồm 8 bít.
Trong ASCII từ mã của kí tự "a" là 1100001,
của kí tự "A" là 1000001.
2. Mã tiền tố (prefix-free binary code)
7Nhóm 44/24/13
