Đồ Án Nén số liệu bằng kỹ thuật Mã hóa Huffman với Mô hình thống kê

MỞ ĐẦU
I. Giới thiệu về đề tài
Trong thời đại ngày nay với sự phát triển mạnh mẽ của khoa học công nghệ thông tin, việc ứng dụng Tin học hầu như đã vào trong tất cả mọi lĩnh vực hoạt động sản xuất của con người ở các nước phát triển trên thế giới. Ở nước ta, nhằm góp phần vào công cuộc Công nghiệp hoá-hiện đại hoá đất nước, vấn đề Tin học hoá đã và đang được triển khai. Việc ứng dụng Tin học vào công tác quản lý và điều hành tại các cơ quan xí nghiệp ngày càng cao và đem lại hiệu quả.
Bên cạnh đó, đồng nghĩa với nó là vấn đề lưu trữ và xử lý dữ liệu. Cùng với thời gian, sự cập nhật, lưu trữ dữ liệu ngày càng nhiều, điển hình là một số cơ quan hành chính nhà nước như: chi cục thống kê của các tỉnh, thành phố, trung ương . với một khối lượng lớn dữ liệu cần lưu trữ. Vì vậy, vấn đề được đặt ra là làm sao lưu trữ dữ liệu ít tốn kém nhất mà vẫn đảm bảo tính an toàn và chính xác của nó? Do đó, việc tìm ra phương pháp giảm dung lượng lưu trữ mà vẫn đáp ứng được yêu cầu trên là rất cần thiết.
Chúng ta thấy rằng: ngày nay với sự phát triển vượt trội trong công nghệ phần cứng, dung lượng đĩa cứng tăng lên một cách đáng kể và nhanh chóng. Một loạt đĩa cứng không ngừng tăng lên về dung lượng ra đời trong khi giá thành sản phẩm lại hạ. Bên cạnh đó còn có các thiết bị lưu trữ khác như băng từ, đĩa quang .cũng được sử dụng rộng rãi. Tuy nhiên, cũng chính vì lý do này mà các nhà lập trình thường sử dụng bất cứ tài nguyên nào có thể, kết quả là nhiều sản phẩm phần mềm ra đời nhưng có kích thước rất lớn, chiếm hàng trăm Mbyte. Thêm vào đó, nhiều lĩnh vực sản xuất áp dụng những phần mềm khác nhau, để đáp ứng được nhu cầu này đòi hỏi người sử dụng tiếp cận nhiều hơn và tạo thói quen lưu trữ nhiều sản phẩm phần mềm, ngoài ra là việc xử lý nhiều tập tin và nhiều loại dữ liệu khác nhau. Do vậy, nén dữ liệu vẫn là vấn đề cần thiết được thực hiện trước khi lưu trữ.
Song song với vấn đề trên, một lĩnh vực không thể không kể đến là mạng máy tính. Ngày nay, mạng máy tính mà mọi người đều nhắc đến là mạng Internet -mạng của các mạng- Có thể nói rằng: Internet là mạng thông tin toàn cầu và số người kết nối vào mạng đã lên đến vài chục triệu người. Vì vậy, nhu cầu truyền thông rất lớn. Tất cả mọi người đều muốn có thể tìm kiếm thông tin bất luận chúng ở đâu, đều muốn chia sẻ thông tin, thiết bị với người khác hoặc quản lý thông tin và thực hiện toàn bộ các tác vụ này một cách nhanh chóng, dễ dàng với độ an toàn chính xác cao. Ngoài ra, hiện nay ở nước ta nhằm đáp ứng nhu cầu trao đổi thông tin giữa các cơ quan nhà nước, việc xây dựng Mạng Hành chính Quốc Gia đã được kết nối thông suốt từ năm 1997, dẫn đến vấn đề truyền thông bằng văn bản Tiếng việt càng tăng. Do đó, bên cạnh việc cải tiến phần cứng như: Modem, đường truyền . ta còn phải tìm cách giảm dung lượng dữ liệu cần thiết trước khi truyền để giảm được thời gian truyền và bộ nhớ. Đối với mạng Internet, thực hiện tốt điều đó cho phép giảm được cước phí truy cập mạng.
Vậy nén dữ liệu là gì? Ta có thể khái quát: Nén là quá trình giảm dung lượng nhớ cần thiết mà vẫn biểu diễn cùng một dữ liệu cho trước.
Trong truyền thông số liệu, nén là một kỹ thuật được áp dụng một cách linh hoạt cho luồng thông tin đang truyền. Công nghệ bên trong về cơ bản cũng như nhau trong cả hai trường hợp là: loại bỏ thông tin dư thừa hoặc biểu thị thông tin dưới dạng chặt chẽ hơn để giảm tổng số byte phải truyền qua phương tiện truyền thông nhằm giảm đến thấp nhất thời gian chiếm phương tiện của một cuộc truyền đã cho.
Đối với nén dữ liệu trên máy PC, có nhiều thuật toán nén khác nhau được thiết kế cho nhiều loại dữ liệu khác nhau như: văn bản, hình ảnh, âm thanh . Trong phạm vi của đồ án, ta chỉ xét đến các phương pháp nén văn bản.
Nén văn bản là biểu diễn lại lượng thông tin sao cho có kích thước nhỏ hơn ban đầu và một yêu cầu không thể thiếu là dữ liệu của tập tin gốc phải luôn luôn được khôi phục lại hoàn toàn chính xác vì đối với loại văn bản này, sự mất mát thông tin dù chỉ một bit là điều không thể chấp nhận được.
Hiện nay, có nhiều phương pháp nén văn bản khác nhau trong đó ta sẽ xét đến phương pháp nén Huffman. Là một trong những phương pháp nén ra đời sớm nhất và đã thành công trong lưu trữ máy tính và viễn thông, phương pháp này thích hợp với kiểu dữ liệu văn bản. Tư tưởng chính của phương pháp như sau: Thay vì lưu trữ mỗi ký hiệu là 8 bit (mã ASCII), dựa vào xác suất (tần suất xuất hiện) của mỗi ký hiệu mà ta sẽ biểu diễn ít bit đối với ký hiệu có xác suất cao và nhiều bit để biểu diễn ký hiệu có xác suất thấp.
Ví dụ ta có luồng dữ liệu là :AABBAADCCC, với mỗi ký hiệu được lưu trữ bình thường là 8 bit thì ta phải mất 8x10=80 bit, trong khi đó với phương pháp mã hoá Huffman dựa vào xác suất xuất hiện: A= 4/10, C=3/10,B=2/10,D=1/10, giả sử ta biểu diễn cho ký hiệu A là 1 bit, C là 2 bit, B là 3 bit, D là 4 bit thì chỉ tốn lượng bit là: 1x4+2x3+3x2+4x1=20 bit. Như vậy, ta đã tiết kiệm được 60 bit lưu trữ.
Trong phạm vi đồ án, ta sẽ xét đến các phần sau:
· Phương pháp mã hoá Huffman với Mô hình thống kê tĩnh bậc 0
· Phương pháp mã hoá Huffman với Mô hình thống kê động bậc 0
· Phương pháp mã hoá Huffman với Mô hình thống kê động bậc 1
· So sánh hiệu suất nén giữa các mô hình với nhau
· So sánh hiệu suất nén giữa phương pháp mã hoá Hufman với các phương pháp nén khác trên thị trường.
Tuy nhiên cần nói thêm rằng, ở đây ta chỉ xét đến mô hình ký tự trong khi các phương pháp nén hiện có ở thị trường được thực hiện trên mô hình từ điển nên hiệu suất nén của phương pháp mã hoá trên mô hình ký hiệu sẽ thấp hơn. Do đó, mục đích của đồ án là tìm hiểu các kỹ thuật nén không tổn hao nói chung và chủ yếu là kỹ thuật nén số liệu theo phương pháp mã hoá Huffman với mô hình ký tự. Từ mô hình thống kê động bậc 0 sẽ nâng cấp lên mô hình thống kê động bậc 1 để từ đó cho thấy được hiệu suất nén của một kỹ thuật nén phụ thuộc như thế nào vào mô hình hoá?, so sánh giữa phương pháp mã hoá Huffman tĩnh và Huffman động.
Với các vấn đề trên, ta sẽ trình bày chi tiết trong các chương tiếp theo.
Cấu trúc đồ án : Gồm có 6 chương
Chương 1: - Giới thiệu đề tài
- Nêu lên mục đích ý nghĩa của đề tài
- Khái quát một số lý thuyết tổng quan về nén số liệu
Chương 2: Giới thiệu và nên lên nội dung của một bài toán nén số liệu tổng quát, so sánh một số loại mã thống kê tối ưu.
Chương 3: Làm rõ bài toán nén số liệu theo phương pháp nén Huffman với mô hình thống kê tĩnh và động bậc 0
Chương 4: Xây dựng cấu trúc dữ liệu và giải thuật cho chương trình nén theo phương pháp Huffman với mô hình thống kê tĩnh và động bậc 0. Cải tiến nâng cấp lên mô hình thống kê động bậc 1.
Chương 5: Trình bày các kết quả thực nghiệm, so sánh tỉ số nén, tốc độ nén, tốc độ giải nén đối với các chương trình nén đã được thương mại hoá.
Chương 6: Kết luận, nêu lên ưu nhược điểm của phương pháp nén Huffman. Định hướng phát triển của đồ án.