Kỹ thuật mã hóa Huffman với mô hình từ điển (Trần Quang Minh) (Thuyết minh + Chương trình) Full
12 thg 12, 2024 | 20:41

Kỹ thuật mã hóa Huffman với mô hình từ điển (Trần Quang Minh) (Thuyết minh + Chương trình) Full



Mục đích của Đồ án là đi sâu nghiên cứu về phương pháp nén dữ liệu áp dụng kỹ thuật mã hóa Huffman với mô hình từ điển. Trên cơ sở đó, đi xây dựng chương trình nén dữ liệu áp dụng phương pháp đã nghiên cứu.

Do vậy, nhìn chung, Đồ án bao gồm hai phần chính: phần đầu là tìm hiểu chung về lý thuyết nén và giải nén dữ liệu; đi sâu tìm hiểu một số phương pháp nén khác đã có; phần tiếp theo, đi vào nghiên cứu kỹ thuật mã hóa Huffman và mô hình từ điển, phân tích các giải thuật để xây dựng các cấu trúc dữ liệu phù hợp, cần thiết cho việc phát triển chương trình. Sau cùng, tiến hành thực nghiệm với chương trình đã cài đặt nhằm kiểm chứng tính đúng của chương trình và so sánh với một số chương trình nén thương mại khác để đánh giá ưu điểm và nhược điểm của phương pháp nén đã nghiên cứu.




NỘI DUNG:



CHƯƠNG 0.  GIỚI THIỆU 3
CHƯƠNG I. LÝ THUYẾT TỔNG QUAN VỀ NÉN DỮ LIỆU 5
I. KHÁI NIệM Về NÉN Dữ LIệU 5
II. MộT Số KHÁI NIệM CƠ BảN 5
II.1. Tỉ lệ nén (compression ratio) 5
II.2. Độ dư thừa số liệu 6
a. Sự lặp lại của những kí tự 6
b. Sự phân bố các kí tự 6
c. Độ dư thừa vị trí 6
d. Những mẫu sử dụng mật độ cao 6
II.3. Độ dài trung bình từ mã 7
II.4. Nén tổn hao và nén không tổn hao 7
a. Nén tổn hao (lossy compression) 7
b. Nén không tổn hao (lossless compression) 7
II.5. Nén số liệu = Mô hình hóa + Mã hóa 7
III. LÝ THUYếT Về MÃ HÓA 8
III.1. Định nghĩa mã hóa 8
III.2. Một số khái niệm cơ bản 8
a. Chiều dài từ mã 8
b. Trọng lượng từ mã 9
c. Khoảng cách mã 9
III.3. Phân loại mã 9
III.4. Một số phương pháp biểu diễn mã thông dụng 9
a. Phương pháp liệt kê 9
b. Phương pháp đồ hình kết cấu 10
c. Phương pháp cây 10
III.5. Điều kiện để mã phân tách được 11
III.6. Mã có tính tiền tố (prefix) 12
III.7. Định lý về độ dài trung bình từ mã 12
IV. MÃ THốNG KÊ TốI ƯU 14
IV.1. Mã Shannon-Fano 14
IV.2. Mã số học 16
IV.3. Mã Huffman 18
V. MÔ HÌNH HÓA NGUồN Số LIệU 18
V.1. Mô hình thống kê 18
V.2. Mô hình từ điển 20
CHƯƠNG II. PHƯƠNG PHÁP MÃ HÓA HUFFMAN VỚI MÔ HÌNH THỐNG KÊ 21
I. PHƯƠNG PHÁP MÃ HÓA HUFFMAN 21
I.1. Mã Huffman tĩnh 21
a. Cở sở nén số liệu của phương pháp mã hóa Huffman tĩnh 21
b. Phương pháp tạo mã Huffman tĩnh 21
c. Phương pháp giải mã Huffman tĩnh 26
d. Ưu và nhược điểm của phương pháp mã hóa Huffman tĩnh với mô hình thống kê 27
CHƯƠNG III.  CÁC PHƯƠNG PHÁP NÉN THEO MÔ HÌNH TỪ ĐIỂN 28
I. MÔ HÌNH Từ ĐIểN TĨNH VÀ MÔ HÌNH Từ ĐIểN ĐộNG 29
II. CÁC PHƯƠNG PHÁP NÉN LEMPEL VÀ ZIV 31
II.1. Phương pháp nén LZ77 31
II.2. Phương pháp nén LZ78 34
CHƯƠNG IV.  KỸ THUẬT MÃ HÓA HUFFMAN ĐỘNG VỚI MÔ HÌNH TỪ ĐIỂN THÍCH ỨNG 38
I. MÃ HÓA HUFFMAN ĐỘNG 38
II. MÔ HÌNH TỪ ĐIỂN THÍCH ỨNG 38
II.1. Kỹ thuật nén với một cửa sổ hạn chế 39
II.2. Các cấu trúc dữ liệu hỗ trợ 39
a. Bộ đệm quay vòng 39
b. Bảng băm (Hash table) 40
III. TIếN TRÌNH NÉN 42
III.1. Quá trình mô hình hóa 42
III.2. Quá trình mã hóa 43
a. Cấu trúc dữ liệu mô tả cây mã Huffman động 43
b. Thủ tục mã hóa 45
IV. TIếN TRÌNH GIảI NÉN 46
IV.1. Quá trình giải mã theo cây mã Huffman động 46
a. Khởi tạo cây mã đầu tiên 46
b. Thủ tục giải mã 46
IV.2. Quá trình giải nén 47
V. NHậN XÉT 48
CHƯƠNG V.  THỰC NGHIỆM 49
I. SO SÁNH Tỉ Số NÉN 49
I.1. Bảng so sánh tỉ số nén 50
I.2. Biểu đồ so sánh tỉ số nén 50
I.3. Nhận xét 51
II. SO SÁNH TốC Độ NÉN 51
II.1. Bảng so sánh tốc độ nén 51
II.2. Biểu đồ so sánh tốc độ nén 51
II.3. Nhận xét 52
III. SO SÁNH TốC Độ GIảI NÉN 52
III.1. Bảng so sánh tốc độ giải nén 52
III.2. Biểu đồ so sánh tốc độ giải nén 53
III.3. Nhận xét 53
IV. KếT LUậN 53
CHƯƠNG VI.  KẾT LUẬN 54
 






Mục đích của Đồ án là đi sâu nghiên cứu về phương pháp nén dữ liệu áp dụng kỹ thuật mã hóa Huffman với mô hình từ điển. Trên cơ sở đó, đi xây dựng chương trình nén dữ liệu áp dụng phương pháp đã nghiên cứu.

Do vậy, nhìn chung, Đồ án bao gồm hai phần chính: phần đầu là tìm hiểu chung về lý thuyết nén và giải nén dữ liệu; đi sâu tìm hiểu một số phương pháp nén khác đã có; phần tiếp theo, đi vào nghiên cứu kỹ thuật mã hóa Huffman và mô hình từ điển, phân tích các giải thuật để xây dựng các cấu trúc dữ liệu phù hợp, cần thiết cho việc phát triển chương trình. Sau cùng, tiến hành thực nghiệm với chương trình đã cài đặt nhằm kiểm chứng tính đúng của chương trình và so sánh với một số chương trình nén thương mại khác để đánh giá ưu điểm và nhược điểm của phương pháp nén đã nghiên cứu.




NỘI DUNG:



CHƯƠNG 0.  GIỚI THIỆU 3
CHƯƠNG I. LÝ THUYẾT TỔNG QUAN VỀ NÉN DỮ LIỆU 5
I. KHÁI NIệM Về NÉN Dữ LIệU 5
II. MộT Số KHÁI NIệM CƠ BảN 5
II.1. Tỉ lệ nén (compression ratio) 5
II.2. Độ dư thừa số liệu 6
a. Sự lặp lại của những kí tự 6
b. Sự phân bố các kí tự 6
c. Độ dư thừa vị trí 6
d. Những mẫu sử dụng mật độ cao 6
II.3. Độ dài trung bình từ mã 7
II.4. Nén tổn hao và nén không tổn hao 7
a. Nén tổn hao (lossy compression) 7
b. Nén không tổn hao (lossless compression) 7
II.5. Nén số liệu = Mô hình hóa + Mã hóa 7
III. LÝ THUYếT Về MÃ HÓA 8
III.1. Định nghĩa mã hóa 8
III.2. Một số khái niệm cơ bản 8
a. Chiều dài từ mã 8
b. Trọng lượng từ mã 9
c. Khoảng cách mã 9
III.3. Phân loại mã 9
III.4. Một số phương pháp biểu diễn mã thông dụng 9
a. Phương pháp liệt kê 9
b. Phương pháp đồ hình kết cấu 10
c. Phương pháp cây 10
III.5. Điều kiện để mã phân tách được 11
III.6. Mã có tính tiền tố (prefix) 12
III.7. Định lý về độ dài trung bình từ mã 12
IV. MÃ THốNG KÊ TốI ƯU 14
IV.1. Mã Shannon-Fano 14
IV.2. Mã số học 16
IV.3. Mã Huffman 18
V. MÔ HÌNH HÓA NGUồN Số LIệU 18
V.1. Mô hình thống kê 18
V.2. Mô hình từ điển 20
CHƯƠNG II. PHƯƠNG PHÁP MÃ HÓA HUFFMAN VỚI MÔ HÌNH THỐNG KÊ 21
I. PHƯƠNG PHÁP MÃ HÓA HUFFMAN 21
I.1. Mã Huffman tĩnh 21
a. Cở sở nén số liệu của phương pháp mã hóa Huffman tĩnh 21
b. Phương pháp tạo mã Huffman tĩnh 21
c. Phương pháp giải mã Huffman tĩnh 26
d. Ưu và nhược điểm của phương pháp mã hóa Huffman tĩnh với mô hình thống kê 27
CHƯƠNG III.  CÁC PHƯƠNG PHÁP NÉN THEO MÔ HÌNH TỪ ĐIỂN 28
I. MÔ HÌNH Từ ĐIểN TĨNH VÀ MÔ HÌNH Từ ĐIểN ĐộNG 29
II. CÁC PHƯƠNG PHÁP NÉN LEMPEL VÀ ZIV 31
II.1. Phương pháp nén LZ77 31
II.2. Phương pháp nén LZ78 34
CHƯƠNG IV.  KỸ THUẬT MÃ HÓA HUFFMAN ĐỘNG VỚI MÔ HÌNH TỪ ĐIỂN THÍCH ỨNG 38
I. MÃ HÓA HUFFMAN ĐỘNG 38
II. MÔ HÌNH TỪ ĐIỂN THÍCH ỨNG 38
II.1. Kỹ thuật nén với một cửa sổ hạn chế 39
II.2. Các cấu trúc dữ liệu hỗ trợ 39
a. Bộ đệm quay vòng 39
b. Bảng băm (Hash table) 40
III. TIếN TRÌNH NÉN 42
III.1. Quá trình mô hình hóa 42
III.2. Quá trình mã hóa 43
a. Cấu trúc dữ liệu mô tả cây mã Huffman động 43
b. Thủ tục mã hóa 45
IV. TIếN TRÌNH GIảI NÉN 46
IV.1. Quá trình giải mã theo cây mã Huffman động 46
a. Khởi tạo cây mã đầu tiên 46
b. Thủ tục giải mã 46
IV.2. Quá trình giải nén 47
V. NHậN XÉT 48
CHƯƠNG V.  THỰC NGHIỆM 49
I. SO SÁNH Tỉ Số NÉN 49
I.1. Bảng so sánh tỉ số nén 50
I.2. Biểu đồ so sánh tỉ số nén 50
I.3. Nhận xét 51
II. SO SÁNH TốC Độ NÉN 51
II.1. Bảng so sánh tốc độ nén 51
II.2. Biểu đồ so sánh tốc độ nén 51
II.3. Nhận xét 52
III. SO SÁNH TốC Độ GIảI NÉN 52
III.1. Bảng so sánh tốc độ giải nén 52
III.2. Biểu đồ so sánh tốc độ giải nén 53
III.3. Nhận xét 53
IV. KếT LUậN 53
CHƯƠNG VI.  KẾT LUẬN 54
 





M_tả /a> M_tả

Chuyên mục:

Không có nhận xét nào: