STDIO
Tìm kiếm gần đây
    Nội dung
    0
    0
    Chia sẻ

    Thuật Toán Nén Dữ Liệu RLE

    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 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).
    05/12/2016
    03/09/2020
    4 phút đọc
    Thuật Toán Nén Dữ Liệu RLE

    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

    0 Bình luận
    Giải Thuật Lập Trình

    Giải Thuật Lập Trình

    STDIO Training - Chia sẻ các giải thuật lập trình từ cổ điển đến hiện đại.

    Khi bạn nhấn vào sản phẩm do chúng tôi đề xuất và mua hàng, chúng tôi sẽ nhận được hoa hồng. Điều này hỗ trợ chúng tôi có thêm kinh phí tạo nhiều nội dung hữu ích. Tìm hiểu thêm.
    STDIO

    Trang chính

    Công ty TNHH STDIO

    • 30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
      +84 28.36205514 - +84 942.111912
      developer@stdio.vn
    • 383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
      Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012
    ©STDIO, 2013 - 2021