Đồ Án Kỹ thuật nén số liệu mã hóa Số học

TÓM TẮT LUẬN VĂN TỐT NGHIỆP

Nội dung của đồ án với đề tài Kỹ thuật nén số liệu mã hóa Số học được triển khai thành hai phần chính là phần thuyết minh và phần chương trình:
* Phần thuyết minh gồm 6 chương được tổ chức như sau:
Chương I: Giới thiệu thực trạng và sự cần thiết của nén số liệu.
Chương II: Trình bày các kiến thức tổng quan, một số khái niệm và cấu trúc của quá trình nén số liệu.
Chương III: Trình bày về các vấn đề liên quan của quá trình mã hóa. Triển khai các thuật toán với cấu trúc dữ liệu phù hợp để cài đặt trên ngôn ngữ lập trình bậc cao.
Chương IV: Trình bày về cấu trúc dữ liệu và thuật toán của các mô hình từ và mô hình kí tự. Trình bày về mô hình bậc cao.
Chương V: Trình bày về kết quả thực nghiệm đã tiến hành với các mô hình đã triển khai. So sánh kết quả với phương pháp nén khác.
Chương VI: Kết luận, nêu những vấn đề đạt được, vấn đề chưa giải quyết và hướng phát triển của chương trình.
* Phần chương trình gồm càc file nguồn và tệp thực thi. Các file nguồn viết trong môi trường C ở hệ điều hành Linux. Dựa theo thuật toán trình bày trong tài liệu [3].
MỤC LỤC
TÓM TẮT LUẬN VĂN TỐT NGHIỆP 1
MỤC LỤC 2
CHƯƠNG I MỞ ĐẦU 4
CHƯƠNG II TỔNG QUAN VỀ NÉN SỐ LIỆU 6
I. GIỚI THIỆU 6
II. PHÂN LOẠI CÁC KỸ THUẬT NÉN 6
II.1. Nén tổn hao 6
II.2. Nén không tổn hao 7
III. CÁC KHÁI NIỆM LIÊN QUAN ĐẾN NÉN SỐ LIỆU 7
III.1. Sự phân bố của kí tự 7
III.2. Sự lặp lại của những kí tự 7
III.3. Độ dư thừa vị trí 7
III.4. Đơn vị đo thông tin (Entropy) và độ dài trung bình của từ mã 8
III.5. Tỷ số nén 8
IV. cấu trúc của QUÁ TRÌNH NÉN SỐ LIỆU 8
IV.1. Mô hình hoá 9
IV.1.1. Khái niệm 9
IV.1.2. Bậc của mô hình 9
IV.1.3. Phân loại mô hình 10
IV.2. Mã hoá 10
IV.2.1. Khái niệm 10
IV.2.2 Các phương pháp mã hóa . 11
CHƯƠNG III KỸ THUẬT MÃ HÓA SỐ HỌC 15
I. các vấn đề cần giải quyết 15
I.1. Mã hóa các kí tự lạ 15
I.2. Quản lý bộ nhớ 16
II. Mã hóa 16
II.1. Nguyên tắc mã hóa 16
II.2. Cấu trúc dữ liệu và giải thuật 16
III. Giải mã 19
III.1. Nguyên tắc giải mã 19
III.2. Cấu trúc dữ liệu và giải thuật 19
IV. Những hạn chế. 21
CHƯƠNG I V Xây dựng mô hình 23
I. Mô hình bậc không 23
I.1. Tính tần số xuất hiện của các kí hiệu 23
I.2. Mô hình từ 25
I.3. Mô hình kí tự . 28
II. Mô hình bậc cao 29
CHƯƠNG V chương trình và thực nghiệm 31
I. cài đặt Chương trình 31
I.1. Mã hóa 31
I.2. Mô hình 31
I.3. Các mô đun 31
I.4. Cách dùng 32
II. thực nghiệm 33
II.1. Giới thiệu 33
II.2. Kết quả thực nghiệm 33
II.2.1. Kết quả thực nghiệm với các file kiểu *.txt 33
II.2.2. Kết quả thực nghiệm với các file kiểu *.cpp 35
III. Kết luận về kết quả thực nghiệm 36
CHƯƠNG VI KẾT LUẬN 37
PHỤ LỤC Chương trình nguồn 39
I. Các file nguồn (*.c) 39
I.1. File arith.c 39
I.2. File bitio.c 44
I.3. File char.c 45
I.4. File hashtable.c 46
I.5. File main.c 50
I.6. File stats.c 57
I.7. File word.c 64
ii. các file tiêu đề (*.h) 69
II.1. File arith.h 69
II.2. File bitio.h 69
II.3. File hashtable .h 71
II.4. File main.h 72
II.5. File stats.h 73
II.6. unroll.i 73
CHƯƠNG I
MỞ ĐẦU
Ngày nay cùng với sự phát triển không ngừng của nền khoa học kỹ thuật thế giới là sự phát triển vượt bậc của ngành Công nghệ Thông tin nói chung và ngành Tin học nói riêng. Các hệ thống Tin học giúp ích rất nhiều trong công việc hàng ngày của các cơ quan, đơn vị tập thể hay mỗi cá nhân có liên quan. Các hệ thống Tin học còn giúp ta lưu trữ các thông tin cần thiết có liên quan đến công việc và đời sống hàng ngày. Mà ngày càng khối lượng thông tin cần lưu trữ tăng lên gấp bội chúng ta không còn không gian để lưu giữ chúng nữa. Một yêu cầu đặt ra là ta phải làm nhỏ lại không gian dành cho các thông tin đó.
Với xu thế toàn cầu hóa, thì mạng Internet đã ra đời. Đây là một mạng của các mạng con trên thế giới. Qua mạng Internet ta có thể ngồi ở nhà liên lạc với các công ty, các đối tác làm ăn hay với bạn bè ở trên khắp thế giới. Qua mạng này ta có thể gửi đi và nhận về các thông tin cần thiết phục vụ cho cuộc sống hàng ngày. Khi gửi các thông tin đi mà ta để nguyên như vậy gửi đi thì tốn rất nhiều thời gian kèm theo đó là sự tốn kém về tiền bạc.
Cùng với sự hoà nhập của Tin học vào các lĩnh vực đời sống thì việc xử lý các loại tập tin với các kiểu file khác nhau là điều tất yếu, và các tập tin này thường có kích thước lớn nên nhiều khi nó gây khó khăn cho công tác lưu trữ và truyền gửi. Vì vậy, khi lưu trữ hay truyền gửi người ta mong muốn giảm đến mức thấp nhất dung lượng bộ nhớ mà các tập tin này chiếm dụng để dễ tổ chức, quản lý và tiết kiệm về kinh phí.
Để đáp ứng các yêu cầu nêu trên người ta đã nghĩ ra phương pháp làm cho các thông tin đó nhỏ lại nhằm chiếm dụng bộ nhớ ít hơn. Người ta gọi đó là kỹ thuật nén số liệu. Vậy nén số liệu là gì? Ở đây chúng ta có thể giới thiệu sơ qua về nén số liệu. Nén số liệu là quá trình giảm dung lượng nhớ cần thiết dành cho các tập tin mà vẫn biểu diễn cùng một lượng thông tin như trước.
Có nhiều phương pháp nén khác nhau và chúng được thiết kế cho các loại dữ liệu khác nhau như hình ảnh, âm thanh, văn bản.v.v trong nội dung đồ án này chỉ bàn đến phương pháp dùng cho nén văn bản. Nén văn bản bao hàm thay đổi sự biểu diễn của tập tin so với không gian trống lấy được nhỏ hơn ở khối lượng dự trữ hoặc nhỏ hơn thời gian truyền tín hiệu, tuy nhiên nguyên bản chính của tập tin phải được khôi phục chính xác sau khi giải nén.
Đã có rất nhiều phương pháp nén được phát minh và sử dụng trong nhiều năm qua. Khi thực hiện giải pháp nén số liệu chúng ta cần phải xem xét đến hai vấn đề trái ngược nhau: các thuật toán nén số liệu thực hiện trước hết phải đảm bảo giảm chi phí lưu trữ mà lại không sử dụng quá nhiều thời gian. Nguyên tắc chung của các phương pháp mã hoá đều dựa trên nhận xét loại bỏ việc lưu lại các thông tin trùng lặp. Các kỹ thuật nén không tổn hao thường được áp dụng cho các tập tin văn bản vì nó chứa các ký tự xuất hiện thường xuyên hơn các ký tự khác, và các thuật toán nén tổn hao thường áp dụng cho các tập tin ảnh vì nó có thể là các vùng đồng nhất, hay cho mô tả số của âm thanh và các ký hiệu tương tự khác.
Đặc điểm của nén văn bản là dữ liệu của tệp tin gốc phải luôn luôn được khôi phục lại một cách chính xác sau khi giải nén. Một trong những phương pháp nén văn bản được biết sớm và đã thành công là nén Huffman, lần đầu tiên được phổ biến vào đầu những năm 1950. Phương pháp này tạo ra các từ mã khác nhau cho các kí hiệu đầu vào. Mã hóa Huffman được xem như một trong những phương pháp nén tốt trong nhiều thập kỷ, cho đến khi có bước đột phá về kỹ thuật nén vào cuối những năm bảy mươi là sự xuất hiện của phương pháp nén Mã hóa Số học. Mã hóa Số học ra đời vào thời gian này và được nghiên cứu phát triển bởi nhiều nhà nghiên cứu.
Trong một thời gian dài từ những năm bảy mươi đến đầu những năm tám mươi, mã hóa Số học bị coi là phương pháp khó thực hiện bởi vì nó không tạo ra từng từ mã riêng lẻ cho từng ký hiệu mà chỉ tạo ra một từ mã duy nhất cho toàn bộ nguồn số liệu. Vì vậy nó không đòi hỏi số nguyên các bít để mã hóa ký hiệu. Ví dụ, ký tự s có xác suất xuất hiện là Pr thì lượng thông tin chứa đựng trong nó là -logPr bit (biểu thức này được định nghĩa là entropy của ký tự), giả sử xác suất xuất hiện của ký tự này là 99% thì Mã hóa Số học chỉ cần sử dụng 0,015 bit để mã hóa nhưng mã hóa Huffman phải sử dụng ít nhất là 1 bit để mã hóa ký tự này vì vậy người ta nói mã hóa Số học gần với entropy. Từ đây ta có thể nghĩ đến một tỉ số nén cao hơn cho nén văn bản khi áp dụng phương pháp mã hóa Số học. Sự công bố mã nguồn cho việc mã hóa nhiều kí hiệu được viết bởi Witten,Neal và Cleary trong tập Communication of ACM (CACM ).
Với các vấn đề nêu trên và dựa vào tài liệu [3], trong đồ án này em đi sâu nghiên cứu về phương pháp mã hóa Số học. Đưa ra các mô hình khác nhau và kết quả thực tế của từng mô hình để người đọc lựa chọn. Chi tiết của các vấn đề sẽ được trình bày trong các chương tiếp theo của đồ án.