Chương I

PHẦN MỞ ĐẦU

1.1 - TẠI SAO PHẢI NÉN DỮ LIỆU

1.1.1 Khái niệm về dữ liệu

Trong một bài toán, dữ liệu bao gồm một tập các phần tử cơ sở mà ta gọi là dữ liệu nguyên tử (atoms). Nó có thể là một chữ số, một ký tự... nhưng cũng có thể là một con số, hay một từ..., điều đó tuỳ thuộc vào từng bài toán.

1.1.2. Mục đích của việc nén dữ liệu

Một trong những chức năng chính của máy tính là xử lý dữ liệu và lưu trữ. Bên cạnh việc xử lý nhanh, người ta còn quan tâm đến việc lưu trữ được nhiều dữ liệu nhưng lại tiết kiệm được vùng nhớ và giảm chi phí lưu trữ. Về mặt lý thuyết thì các thiết bị lưu trữ là không có giới hạn nhưng ngày nay do nhu cầu xử lý nhiều tập tin, nhiều loại dữ liệu trong cùng một tệp do vậy mà kích thước tệp trở nên khá lớn.

Trong nhiều năm gần đây, mạng máy tính đã trở nên phổ biến trên thế giới. Sự ra đời của mạng đã thực hiện được ước mơ chinh phục khoảng cách giữa con người. Những lợi ích mà mạng cung cấp rất đa dạng và phong phú trên các lĩnh vực khác nhau của xã hội như cung cấp, trao đổi thông tin giữa các máy tính, giữa máy tính với server hoặc giữa các server với nhau. Điều này dẫn đến phải làm như thế nào để giảm thiểu thời gian, chi phí sử dụng để trao đổi dữ liệu trên mạng. Nó cũng đồng nghĩa với việc bên cạnh nâng cao chất lượng của các thiết bị truyền dữ liệu trên mạng thì mặt khác chúng ta phải nghĩ ra một phương pháp nào không để sao cho việc truyền dữ liệu có hiệu quả hơn.

Tất cả những vấn đề trên nảy sinh ra khái niệm nén dữ liệu. Một trong những hình thức nén dữ liệu đầu tiên là hệ chữ Braille, là một hệ chữ dùng phương pháp mã hoá ký hiệu cho người mù có thể đọc và viết. Ngày nay, nén dữ liệu mang lại rất nhiều lợi ích khác nhau mà điển hình là :

+ Đối với việc tìm kiếm thì đôi khi ta tìm kiếm thông tin trên dữ liệu nén lại nhanh hơn so với việc tìm kiếm thông tin trên dữ liệu không nén vì do dữ liệu lưu trữ ít nên số phép toán để tìm kiếm giảm và lượng thông tin cao.

+ Nén dữ liệu đặc biệt hiệu quả với việc truyền dữ liệu trên mạng. Khi nén dữ liệu thì chi phí cho việc truyền dữ liệu trên mạng sẽ giảm mặt khác tốc độ đường truyền sẽ tăng lên bởi vì cùng một lượng thông tin đó thời gian truyền dữ liệu sẽ giảm.

Với những ưu điểm trên thì do đó, nén dữ liệu là giải pháp hợp lý nhất nhằm mục đích giảm chi phí cho người sử dụng.

Tóm lại những lợi ích mà nén dữ liệu mang lại xoay quanh vấn đề tiết kiệm tối đa chi phí cho việc mua các thiết bị lưu trữ dữ liệu và cho việc luân chuyển thông tin trên mạng.

* Một số vấn đề gặp phải khi nén dữ liệu là :

+ Các thuật toán thực hiện trước hết phải giảm chi phí lưu trữ.

+ Các thuật toán được thực hiện nhanh, hiệu quả.

Với nhiều loại thông tin khác nhau mà ta có các kỹ thuật nén khác nhau, có hiệu quả khác nhau, ví dụ như nén tệp văn bản thường tiết kiệm 20% - 50%, còn đối với tập tin nhị phân khoảng 50% - 90% tuy nhiên đối với các tập tin ngẫu nhiên thì lượng không gian tiết kiệm được rất ít hoặc hầu như không tiết kiệm được (chẳng hạn như tệp *.exe, ...). Do các dữ liệu có độ dư thừa khác nhau nên mỗi phương pháp nén nếu áp dụng đúng sẽ trở nên không cần thiết, không có độ linh hoạt.

I.2- NÉN BẢO TOÀN

Đó là mô hình nén dữ liệu mà nó cho phép người sử dụng bảo toàn thông tin trong suốt quá trình nén. Điều này được giải thích như sau:

Giả sử ta có dữ liệu nguồn là D và dữ liệu nén là D'. Sau khi ta giải nén D' thì được tập D'' mà tập D'' hoàn toàn giống với tập D ban đầu khi được giải nén. Thông thường, kỹ thuật này được áp dụng với các loại dữ liệu như văn bản vì độ chính xác của văn bản. Nếu hiểu theo ngôn ngữ toán học thì đó là một ánh xạ 1 - 1 từ 1 tập X -> Y mà ở đó mỗi phần tử Xi  X tương ứng với một phần tử Yi  Y.

1.3 - NÉN KHÔNG BẢO TOÀN

Trong kỹ thuật nén, bên cạnh nén bảo toàn thì người ta còn đưa ra khái niệm nén không bảo toàn. Nén không bảo toàn là mô hình nén dữ liệu mà tính bảo toàn của dữ liệu không được coi trọng. Nó có nghĩa là nếu ta có tập dữ liệu D, tập nén D' thì sau khi giải nén ta thu được tập D'' khác tập D ban đầu. Kỹ thuật này thường áp dụng cho việc nén dữ liệu là các loại tệp ảnh vì nói chung nó cũng không ảnh hưởng gì nhiều đến hình dạng ảnh. Nếu biểu diễn bằng toán học, chúng có mô hình sau:

F(x)  { y1¬, y2, ...}

1.4 - QUÁ TRÌNH NÉN VÀ GIẢI NÉN

Quá trình nén dữ liệu là một quá trình gồm 2 công đoạn:

1) Công đoạn nén.

2) Công đoạn giải nén.

Chúng ta có thể minh hoạ như sau:

a) Công đoạn nén:

Dữ liệu  Mã hoá  Đóng gói  Dữ liệu nén.

b) Công đoạn giải nén:

Dữ liệu nén  Giải mã  Mã hoá  Dữ liệu gốc.

Hai công đoạn trên là 2 điển hình trái ngược nhau. Đối với tiến trình nén thì module mã hoá thực hiện việc cắt văn bản nguồn thành các đoạn và gán cho chúng ký hiệu để xác định chúng. Ngược lại đối với tiến trình giải nén thì module giải mã sẽ dựa vào các mã mà module mã hoá ở tiến trình nén sinh ra để tìm đoạn tương ứng. Quá trình tìm đoạn tương ứng đó được thực hiện trên rất nhiều đoạn trong tiến trình nén, giải nén sinh ra. Tập hợp các đoạn đó chúng ta gọi là từ điển.