Đồ Án Kỹ thuật mã hóa Huffman với mô hình từ điển

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
CHƯƠNG 0
I. GIỚI THIỆU
Ngày nay, máy tính đã thâm nhập vào hầu hết các lĩnh vực của đời sống- xã hội. Nói đến máy tính tức là nói đến hai vấn đề lớn : lưu trữ và xử lý thông tin.
Với sự bùng nổ thông tin như hiện nay, việc lưu trữ và trao đổi thông tin đã và đang đặt ra nhiều vấn đề cần phải giải quyết, đó là làm sao để lưu trữ một cách tiết kiệm, hiệu quả và trao đổi thông tin một cách nhanh chóng nhất. Một giải pháp là tăng dung lượng của các thiết bị lưu trữ. Tuy nhiên, điều này đòi hỏi cao về mặt kỹ thuật phần cứng và chi phí khá tốn kém. Như vậy, giải pháp này là không kinh tế. Một giải pháp khác nhiều triển vọng hơn và mang tính khả thi đã được đặt ra, đó là nén dữ liệu. Vậy nén dữ liệu là gì ?
Có thể hiểu một cách nôm na rằng, nén dữ liệu là quá trình làm giảm dung lượng lưu trữ của dữ liệu mà vẫn bảo toàn được nội dung thông tin trước đó.
Như vậy, việc nén dữ liệu sẽ đem lại nhiều lợi ích thiết thực. Đó là :
· Tiết kiệm được không gian lưu trữ.
· Tăng tốc độ và giảm chi phí truyền dẫn trên mạng.
· Bảo mật được thông tin.
Mặc dù dung lượng của các thiết bị lưu trữ ngày nay đã tăng đến tốc độ chóng mặt, có thể lên đến hàng chục Gigabytes, nhưng với những lợi ích như đã nêu trên, giải pháp nén dữ liệu trước khi lưu trữ, cũng như truyền dẫn qua mạng là điều khiến chúng ta không thể không xét đến.
Nói chung, nén dữ liệu là quá trình biến đổi một luồng các kí hiệu thành một luồng các mã có kích thước nhỏ hơn ban đầu. Thông thường, một quá trình nén được tiến hành qua hai giai đoạn: (1) Mô hình hóa, là giai đoạn tiên đoán về tần suất xuất hiện của các kí tự và / hoặc chuỗi kí tự của văn bản cần nén. (2) Mã hóa, là giai đoạn dựa trên mô hình với tần suất vừa được xác định để tạo ra từ mã tương ứng.
Cùng với sự phát triển mạnh mẽ của lý thuyết thông tin, có khá nhiều phương pháp mã hóa và mô hình hóa đã ra đời. Trong các phương pháp mã hóa, đáng chú ý nhất là mã hóa Huffman và mã hóa số học. Phương pháp mã hóa Huffman được D.A Huffman công bố vào năm 1952. Phương pháp mã hóa này đơn giản, dễ xây dựng và cho thời gian mã hóa ngắn. Phương pháp mã hóa số học ra đời vào cuối những năm 70. Phương pháp này hướng đến việc tối ưu độ dài từ mã nên tương đối phức tạp hơn và vì vậy thời gian mã hóa chậm hơn.
Kỹ thuật nén xử lý từng kí tự một của luồng kí hiệu đầu vào được gọi là nén với mô hình thống kê (Statistical model). Ngược lại, kỹ thuật nén xem xét mỗi lúc một chuỗi các kí tự từ luồng nhập gọi là nén với mô hình từ điển (Dictionary-based model).
Do đặc thù của mô hình từ điển và thực tế cũng cho thấy, với cùng một phương pháp mã hóa thì việc áp dụng mô hình từ điển sẽ cho hiệu quả nén cao hơn nhiều so với mô hình thống kê. Hầu hết các chương trình nén thương mại hiện hành đều sử dụng mô hình từ điển mà điển hình là các chương trình nén nổi tiếng như NCZip, PKZip và WinZip.
Trong một thời gian ngắn, việc nghiên cứu tất cả các kỹ thuật nén dữ liệu là điều không khả thi, do vậy, trong cuốn luận văn tốt nghiệp này, tác giả chỉ đi sâu nghiên cứu về phương pháp nén dữ liệu không tổn hao dựa trên kỹ thuật mã hóa Huffman (chủ yếu là mã Huffman động) và mô hình từ điển.
Do năng lực bản thân và thời gian có hạn nên Đồ án còn khá nhiều thiếu sót. Xin nhận được những lời phê bình, góp ý quý báu của các thầy cô và bạn đọc để đề tài có thể hoàn thiện hơn trong tương lai.
Cấu trúc Đồ án
Đồ án bao gồm 6 chương và chương trình Demo trên đĩa. Nội dung như sau :
Chương 0 : Giới thiệu đề tài, vai trò và ý nghĩa của nó.
Chương I : Trình bày tổng quan về lý thuyết nén và giải nén dữ liệu, làm nền tảng cho việc giải quyết vấn đề đã đặt ra trong Đồ án.
Chương II : Trình bày phương pháp nén dữ liệu áp dụng kỹ thuật mã hóa Huffman dựa trên mô hình thống kê.
Chương III: Tìm hiểu một số phương pháp nén dựa trên mô hình từ điển.
Chương IV : Đi sâu nghiên cứu phương pháp nén dữ liệu áp dụng kỹ thuật mã hóa Huffman động, dựa trên mô hình từ điển thích ứng, làm nền tảng cho việc phát triển chương trình.
Chương V : Trình bày kết quả thực nghiệm kiểm tra tính đúng đắn, chính xác của chương trình và so sánh với một số chương trình thương mại có cùng chức năng. Trên cơ sở đó, đánh giá ưu điểm và hạn chế của phương pháp nén được sử dụng.
Chương VI : Kết luận, đánh giá những gì đã làm được, những gì chưa đạt được và nêu hướng phát triển của đề tài.