Nén dữ liệu và giải thuật

Nén dữ liệu và các thuật toán

Trần Đức Thiện

Phần lớn, khi nghiên cứu thuật toán chúng tathường chú ý tới vấn đề thời gian chạy, tức là

càng ít tốn thờigian càng tốt. Nhưng đôi khi, việc tiết kiệm chỗ, giảm bớt lượng khônggian

sử dụng trở thành một yêu cầu cấp thiết và đem lại nhiều hiệuquả.

ở một số bài toán xử lí dữ liệu lớn, khi phảiquản lý tất cả dữ liệu thì nén lại là một yêu cầu

bắt buộc. Việcnén không có gì là cao siêu, có đôi khi ta nén mà ta không biết, vídụ như với

bài toán sau:

Cho một bảng 2x4= 8 ô, mỗi ô điền một chữ cáitừ A đến H, có một quy tắc biến đổi để

hoán vị vị trí các chữ cáitrong các ô. Hãy biến đổi bảng nhận được về bảng cơ sở như sau:

Có nhiều cách giải quyết rất hiệu quả loạitoán này. Chưa cần bàn đến thuật toán, ta hãy xét

cách lưu trữ mộttrạng thái của bảng, bình thường lưu trữ các ký tự thì phải cần tới8 byte

(nếu dùng xâu tối thiểu cũng phải 9 byte). Nhưng nếu bây giờ mỗiký tự từ A đến H ta mã

hoá bằng một chữ số từ 1 đến 8 thì mỗi trạngthái của bảng ta chỉ cần lưu trữ bằng một con

số Longint 8 chữ số vàdung lượng là 4 byte. Một việc làm không mấy phức tạp mà tiết

kiệmđược tới 50% dung lượng nhớ.

Cũngcó rất nhiều bài toán mà sau khi mã hoá (cũng là nén) khiến ta xử lýdễ dàng hơn, bởi

vì giảm bớt gánh nặng quản lý dữ liệu và việcduyệt qua dữ liệu được nhanh chóng, dù rằng

truy xuất một phần tử cóhơi phức tạp hơn nhưng sẽ chỉ tốn rất ít thời gian cho việc này.

Cáckỹ thuật nén đã được phát hiện và có hiệu quả khác nhau tuỳ thuộcvào dạng của dữ

liệu cần nén, một số kỹ thuật được sử dụng rấtrộng rãi trong công nghệ tin học. Sau đây tôi

xin giới thiệu một sốphương pháp nén có hiệu quả nhất hiện nay, có thể tiết kiệm từ 20đến

50% dung lượng và trong trường hợp lý tưởng, có thể đạt tới90%

1. Kỹ thuật mã hoá độ dài loạt (Run - Length Encoding):

Tậptin thường hay có lượng dư thừa, loại dư thừa đơn giản nhất là cácdãy dài gồm các ký

tự lặp lại. Ví dụ xét chuỗi sau:

IAAAASSSSSMMMMMMMMM

Cóthể thấy rằng chuỗi này quá dài so với lượng thông tin mà nó mang lại,ta có thể biểu

diễn một cách cô đọng hơn bằng cách thay thế nhữngchuỗi ký tự lặp lại bằng một lần ký tự

cùng số lần lặp lại liêntiếp của nó. Có nhiều cách biểu diễn tuỳ thuộc vào các đặc trưngcủa

yêu cầu và loại hình thiết bị lưu trữ; Chuỗi vừa rồi có thểđược mã hoá như sau:

I4A5S9M

Việcnén một chuỗi theo phương pháp này gọi là mã hoá độ dài loạt, ởđây 4A có nghĩa là 4

ký tự A. Chú ý là không nên mã hoá các chuỗilặp có độ dài 1 hoặc 2 vì sẽ bị phản tác dụng.

Khi có những loạtchạy dài, sẽ tiết kiệm được rất đáng kể, phương pháp này rất hiệuquả khi

áp dụng vào các tập tin nhị phân, đặc biệt các tập tin lưutrữ ảnh bitmap, các loạt lặp dài

liên tục xuất hiện. Đối với các tậptin nhị phân, ta có thể áp dụng một phiên bản được tinh

chế của phươngpháp này, đó là việc lợi dụng chuỗi chỉ gồm các ký tự 0 và 1 xenkẽ liên

tiếp nhau, vì vậy sẽ không phải lưu trữ chính các số 0 và1, mà chỉ cần lưu trữ số lần xuất