STDIO
Tìm kiếm gần đây
    • Nội dung
    • QR Code
    • 0
    • 0
    • Sao chép

    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.

    Đề xuất

    Mã Hóa Base64
    Base64 không phải là một thuật toán mã hóa và trong mọi trường hợp, nó ...
    SHA-1 - Secure Hash Algorithm 1
    SHA-1 là một trong những thuật toán băm mã hóa, được dùng trong việc ...

    Khám phá

    MD5
    MD5 (MD5 Message-Digest Algorithm) là một thuật toán tóm tắt thông điệp, ...
    Heap Sort - Thuật Toán Sắp Xếp Vun Đống
    Với độ phức tạp trong trường hợp xấu nhất bằng O (n log n), giải thuật ...
    Giải Thuật Là Gì?
    Giải thuật - thuật toán là một tập hợp hữu hạn các thao tác được thực ...
    Thuật Toán PID trong Điều Khiển Tự Động
    Chi tiết về thuật toán PID, các ví dụ thực tế và hướng đưa thuật toán ...
    Xử Lý Ảnh Với OpenCV: Các Phép Toán Hình Thái Học
    Giới thiệu những thuật toán cơ sở trong xử lý hình thái học, những thuật ...
    Trích Xuất Dữ Liệu từ File Excel bằng Python - Phần 1: Đọc Dữ Liệu
    Hướng dẫn cách để trích xuất dữ liệu từ file excel bằng python.
    18/03/2015
    Học Lập Trình Nên Bắt Đầu Từ Đâu?
    Học lập trình nên bắt đầu từ đâu? Lựa chọn học từ nền tảng có phải luôn ...
    Little Endian và Big Endian
    Thuật ngữ “big endian” và “little endian” diễn tả sự khác nhau về cách ...
    26/07/2015
    Khi bạn nhấn vào liên kết sản phẩm do STDIO đề xuất và mua hàng, STDIO có thể nhận được hoa hồng. Điều này hỗ trợ STDIO tạo thêm 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 - 2020