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
hiện của chúng, với quy ước kýtự đầu luôn là 1, nếu không có thì nó sẽ xuất hiện 0
lần, với xâu0010001111 ta có thể mã hoá như sau:
0 2 1 3 4
Mở rộng phươngpháp này, không chỉ cho 1 ký tự mà áp dụng với 1 đoạn xâu lặp
lại,tức là khi chính trong sâu sau khi mã hoá có sự lặp lại nhiều lần củamột chuỗi
dài nào đó, ta phải dùng tới cặp ngoặc đơn và số lầnxuất hiện của chuỗi trong
ngoặc đi theo sau, xâu chứa ngoặc gọi là xâunén cấp cao. Thực tế ít gặp các trường hợp thế
này, nhưng tuy nhiêntrong bài tập thì lại có. Có những bài tập mà xâu ngoặc vào chỉ
giớihạn 255 ký tự, nhưng xâu giải nén ra có thể dài tới mức tràn bộ nhớ.
Phương pháp này rất đơn giản, dễcài đặt, nhưng có nhược là kém hiệu quả với các tập tin
có các kýtự lặp lại nhiều lần không xuất hiện liên tiếp, và không nén đượctập tin có chứa
ký tự số, việc khắc phục là thực hiện được tuynhiên sẽ phức tạp và hiệu quả phương pháp
bị giảm xuống. Chúng tasẽ xem xét một phương pháp khác có phạm vi áp dụng rộng hơn.
2. Mã hoá độ dài biến động (Variable - Length Encoding):
Trong cách thông thường, mỗi ký tự được mã hoá với số bít bằng nhauđể lưu trữ, khi đó
dung lượng tiêu dùng tỷ lệ với số lượng ký tựcó trong tập tin, không kể đến việc có một số
ký tự nào đó có mặttrong tập tin gấp rất nhiều lần các ký tự khác. Điều này thực sự gâylãng
phí. Vì vậy ý tưởng cơ bản của phương pháp này là mã hoá mỗiký tự bởi một lượng bít
nhất định khác nhau, ký tự nào xuất hiệnnhiều lần hơn thì sẽ được mã hoá bởi lượng bít ít
hơn, lúc nàycác ký tự không cần phải xuất hiện liền nhau mà vẫn có thể nénđược do ta tiết
kiệm được đáng kể không gian trong việc lưu trữ cácký tự xuất hiện nhiều lần.
Một cách trực quan, chúng ta hãy xét ví dụ với xâu 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

xây dựng dần dần như sau(số trong ô tròn là tần số của ký tự):
Tiếp tục quá trình trên ta được một cây hoànchỉnh ở dạng tần số (như hình).
Thay các nút trái bởi số 0, nút phảibởi số 1 ta được cây nhị phân, từ đó ta sẽ biết
được mã của từnglá tương ứng( N-11, O-10, E-00000,D-0011).
Có đôi khi mã hoá và nén lại là một, có thể dùng nén dữ liệu để mãhoá có hiệu
quả, tuy có nhược điểm là độ bảo mật không cao nhưnglại rất thuận lợi với các
tập tin lớn cần truyền tải nhanh. Nếu biếtkết hợp nén để mã hoá thì sẽ đem lại rất
nhiều hiệu quả không ngờ.
Cácbạn có thể cho rằng các kỹ thuật nén tập tin không mấy quan trọng bởigiá cả
của các thiết bị lưu trữ trên máy tính hiện nay đã giảm rấtnhiều và người sử dụng có nhiều
bộ nhớ hơn so với trước đây. Nhưngcũng có thể nói rằng việc nén hiệu quả mang lại rất
nhiều thuận lợi,bởi vì công nghệ càng phát triển, càng có quá nhiều bộ nhớ đangtrong tình
trạng sử dụng, việc tiết kiệm là cần thiết, nhất là trongviệc truyền tải thông tin hiện nay,
tình trạng tải thông tin và truy cậpmạng còn rất chậm, nếu nén được tập tin nhỏ gọn lại thì
hiệu quảnó mang lại không phải là ít, cho cả người sản xuất và người sử dụng.Các kỹ thuật
nén cũng thích hợp cho các thiết bị lưu trữ cho phéptruy xuất với tốc độ cao vượt bực (bởi
vì thiết bị tương đốiđắt và thường là phải nhỏ gọn).
Trongbài viết này, tôi không chú trọng việc áp dụng cũng như giải các bàitoán cụ thể, chỉ
nêu khái quát các phương pháp. Cuối cùng, rất hyvọng các bạn áp dụng tốt vào các bài tập
cần thiết và có được mộtchương trình nén, bung nén cho riêng mình (khi đó có thể chèn,
thêm,xoá, sửa theo ý mình), và nhất là có thể sáng tạo được một kỹthuật nén có hiệu quả
hơn, sẽ rất thú vị đấy; Chào thân ái và hẹngặp lại.