Nếu bạn đang suy nghĩ mà không cần viết, thì bạn chỉ nghĩ là bạn đang nghĩ. Linus Torvalds
STDIO Trong quá trình lưu trữ cũng như truyền dữ liệu, việc nén dữ liệu là điều không thể thiếu. Bài viết này sẽ khái quát tổng quan về nén dữ liệu và trình bày về thuật toán nén dữ liệu đơn giản - RLE (Run-Length Encoding).
Nội dung bài viết

Giới thiệu

Trong quá trình lưu trữ cũng như truyền dữ liệu, việc nén dữ liệu là điều không thể thiếu. Bài viết này sẽ khái quát tổng quan về nén dữ liệu và trình bày về thuật toán nén dữ liệu đơn giản - RLE (Run-Length Encoding).

Tổng quan về nén dữ liệu

Trong xử lí dữ liệu, nén dữ liệu là việc mã hoá thông tin sử dụng ít bit hơn cách thể hiện ở dữ liệu gốc.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: Đây là phương pháp nén mà sau khi giải nén ta 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: Dây 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 tính chất của mắt người 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. Từ đó, 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. Trong bài viết này, tôi sẽ 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 với dữ liệu, chúng ta thường thấy 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’, 6 kí tự ‘T’, 3 kí tự ‘D’, 3 kí tự ‘I’ và 2 kí tự 'O'.

Kết quả của thuật toán nén RLE đoạn văn bản trên là:

S3T6D3I3O2

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

Đây là cách mà tôi hiện thực thuật toán nén RLE:

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 cực kì phù hợp. Nó 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 thì việc sử dụng RLE không thật sự hiệu quả. Nó tạo ra dữ liệu sau khi nén có dung lượng lớn ơn cả dữ liệu "nguyên thuỷ". Đâ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

Download mã nguồn

Download

Bạn cần hỗ trợ các dự án kết nối không dây?

Quí doanh nghiệp, cá nhân cần hỗ trợ, hợp tác các dự án IoT, kết nối không dây. Vui lòng liên hệ, hoặc gọi trực tiếp 0942.111912.

  • TỪ KHÓA
  • Arduino
  • ESP32
  • ESP8266
  • Wifi
  • Bluetooth
  • Zigbee
  • Raspberry Pi
THẢO LUẬN
ĐÓNG