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

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.