Nén dữ liệu là gì?
Trong xử lí dữ liệu, nén dữ liệu là việc mã hoá thông tin sử dụng sao cho giảm được không gian lưu trữ nhưng vẫn giữ được thông tin gốc hoặc ít mất mát thông tin. Dựa vào sự thay đổi dữ liệu trước và sau khi nén, người ta chia thành 2 loại: nguyên vẹn (lossless) và bị mất dữ liệu (lossy).
- Lossless Compression: là phương pháp nén mà sau khi giải nén thu được thông tin nguyên thuỷ, tuy nhiên hiệu suất nén không cao, chỉ đạt khoảng 10% - 60%. Một số giải thuật nén tiêu biểu như: RLE, Huffman, LZ77, ...
- Lossy Compression: là phương pháp nén mà sau khi giải nén thông tin nguyên thuỷ bị mất mát. Hiệu suất nén cao từ 40% - 90%. Trong nén ảnh, dựa vào trải nghiệm người dùng chấp nhận một số vặn xoắn trong ảnh khi khôi phục lại – phương pháp “tâm lí thị giác”. Tuy nhiên, phương pháp này có hiệu quả ở một mức độ nhất định mắt thường chấp nhận được hay với dung sai nào đó. Một số thuật toán nén tiêu biểu như: JPEG, MP3, MP4, ...
Việc này giúp giảm được dung lượng dữ liệu, giảm được dung lượng lưu trữ, tăng tính bảo mật đồng thời tăng tốc độ đường truyền. Trong thực tế, có nhiều thuật toán nén dữ liệu khác nhau. Mỗi thuật toán có ưu nhược điểm khác nhau. Vì vậy, đối với các loại dữ liệu khác nhau cần phải có sự lựa chọn giải thuật nén phù hợp để đạt hiểu quả cao nhất. Bài viết này giới thiệu về thuật toán nén dữ liệu lossless RLE (Run-Length Encoding).
Thuật toán RLE (Run-Length Encoding)
Ý tưởng
Trong quá trình thao tác dữ liệu, sự lặp đi lặp lại các dữ liệu có sự tương đồng hay trùng lặp nhau, liên tiếp hay không liên tiếp. Dễ thấy nhất là tập tin văn bản, hay trong các tập tin đồ họa dạng bitmap, ...
Nén dữ liệu hàng loạt RLE là phương pháp nén không mất dữ liệu. RLE hoạt động bằng cách tìm loạt dữ liệu liền nhau, lặp lại trong chuỗi dữ liệu thành một dữ liệu đại diện khác, mục đích là để giảm kích thước dữ liệu gốc.
Xét dữ liệu là đoạn văn bản sau:
SSSTTTTTTDDDIIIOO
Thuật toán RLE để nén đoạn văn bản trên bằng việc thay thế chuỗi ký tự được lặp lại nhiều lần bằng một ký tự duy nhất và kèm theo sau là một số chỉ số lần ký tự đó được lặp lại liên tục. Nói cách khác, với chuỗi trên xuất hiện liên tục:
- 3 ký tự S (giá trị 123)
- 6 ký tự T (giá trị 124)
- 3 ký tự D (giá trị 104)
- 3 ký tự I (giá trị 111)
- 2 ký tự O (giá trị 117)
Kết quả của thuật toán nén RLE đoạn văn bản trên là 3S 6T 3D 3I 2O hay chính xác hơn dưới dạng nhị phân là:
3 123 6 124 3 104 3 111 2 117
Trong thực tế, việc lưu trữ hình ảnh là dưới dạng nhị phân chứ không phải ASCII kí tự như trên nhưng nguyên tắc vẫn giống nhau. Việc nén 1 chuỗi theo phương pháp này được gọi là mã hoá độ dài loạt. Khi có nhưng loạt dài thì việc tiết kiệm là rất đáng kể.
Hiện thực
void compressFile(char* fileData, long fileSize, unsigned char* &compressFileData, long &compressFileSize)
{
compressFileSize = fileSize > 0 ? 2 : 0;
for (int i = 0; i < fileSize - 1; i++)
if (fileData[i] != fileData[i + 1])
compressFileSize += 2;
compressFileData = new unsigned char[compressFileSize];
int temp = 1;
int index = 0;
for (int i = 0; i < fileSize; i++)
{
if (fileData[i] == fileData[i + 1])
{
temp++;
}
else
{
compressFileData[index] = temp;
compressFileData[index + 1] = fileData[i];
index += 2;
temp = 1;
}
}
}
Đánh giá
Ưu điểm
Đối với các dữ liệu có sự lặp đi lặp lại nhiều lần của một ký tự thì thuật toán này rất phù hợp, giảm được đáng kể dung lượng của dữ liệu.
Nhược điểm
Với những loại dữ liệu mà thông tin ít lặp, việc sử dụng RLE không thật sự hiệu quả, tạo ra dữ liệu sau khi nén có dung lượng lớn hơn dữ liệu gốc, đây được gọi là hiệu ứng ngược. Xét ví dụ sau:
Cho đoạn dữ liệu: abcdefgh #8byte
Sau khi nén bằng RLE sẽ là: a1b1c1d1e1f1g1h1 #16 byte
