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:

ABTACADABTA
Có 5 loại ký tự xuất hiện, để mã hoá phân biệt 5 ký tự này với sốbit bằng nhau, cần tối
thiểu 3 bít cho mỗi ký tự, vậy cần 33 bit. Nhưngnếu ta mã hoá A là 0, B là 1, T là 01, C là
10 và D là 11, như thế xâuđã cho được mã hoá thành:
0 1 01 0 10 0 11 0 1 01 0
Như vậy chúng ta chỉ dùng 15 bit, giảm đi rất nhiều. Nhưng lại nảy sinh vấnđề là xuất hiện
các dấu phân cách. Nếu không có phân cách thì việcgiải mã ngược lại sẽ không đúng với
xâu ban đầu và không duy nhất.Các khoảng trống này có thể bỏ được nếu trong cách mã
hoá, khôngcó mã ký tự nào là phần đầu của một mã khác. Ví dụ nếu mã hoáA là 1, B là 00,
C là 0101, D là 0100 và T là 011, sẽ có duy nhất mộtcách giải mã xâu 23 bít sau:
10001110101101001000111
Việc mã hoá và giảimã chưa được rõ ràng, hẳn các bạn sẽ đưa ra câu hỏi, vậy làm thếnào
để mã hoá các ký tự để không có mã nào là phần đầu của mộtmã khác mà vẫn đảm bảo
việc mã hoá đó là tối ưu. Trước hếtđể biểu diễn cách mã hoá, chúng ta dùng cây, trong
trường hợp nàyđể mã hoá bit các ký tự ta dùng một cây nhị phân mà trên các nútcủa nó, trừ
nút gốc ra ta sẽ điền 0 nếu sang trái và 1 nếu sang phải,và mỗi nút lá sẽ tương ứng với 1 ký
tự. Mã của ký tự là chuỗi cácbít trên đường đi từ gốc qua các nút con đến lá tương ứng.
Trongví dụ trên ta có cây biểu diễn như sau:
Việcbiểu diễn theo cây đảm bảo rằng không có ký tự nào là đoạn đầucủa mã ký tự khác.
Nhưng xây dựng cây như thế nào để chuỗi saukhi mã hoá có số bít tối thiểu. Một thuật
toán tổng quát đã đượcD.Huffman tìm ra vào năm 1952.
3. Xây dựng mã HuffMan:
Bước đầu tiên chúng ta sẽ đếm số lần xuất hiện(tần số) của mỗi ký tựtrong toàn bộ tập tin.
Sau đó, bỏ qua các ký tự có tần số bằng 0, cácký tự còn lại tạo thành 1 rừng.
Ta sẽ lặp công việc : tìm ra hai nútcó tần số nhỏ nhất, một nút mới được tạo
thành nhận hai nút nàylàm hai nút con và có tần số bằng tổng 2 tần số, nút
mới này sẽthay thế cho hai nút con trong các bước tiếp theo. Như vậy mỗi
bước rừngsẽ giảm đi một cây, cuối cùng tất cả các nút được kết hợp lạithành
1 cây duy nhất.
Với xâu : NOI DONGNAU OC NOI DAT NAU ECH Thì cây mã hoá được