STDIO
Tìm kiếm gần đây

    Nội dung

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

    05/12/2016
    27/03/2020
    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).

    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ài viết liên quan

    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ó không nên được sử dụng để băm mật khẩu hoặc dữ liệu nhạy cảm, bởi vì đây là thuật toán có thể được ...

    Bugs19/10/2019

    Tìm Hiểu Về Thuật Toán

    ­­­­Thuật toán là một tập hợp hữu hạn các thao tác được thực hiện liên tục nhằm đạt được một mục đích xác định trước. Trong bài viết này, tôi sẽ trình bày lại những hiểu ...

    @ TOMBSTONE25/08/2015

    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 kiểm tra tính toàn vẹn của dữ liệu ở phía người nhận. SHA-1 checksum được so sánh giữa người cung cấp ...

    Bugs04/05/2019

    Little Endian Và Big Endian

    Một bộ máy có thể đọc và xử lý dữ liệu được tạo ra bởi nó một cách bình thường. Vấn đề xảy ra khi một bộ máy “khác loại” cố gắng đọc dữ liệu đó. Thuật ngữ Big Endian và ...

    Rye Nguyen26/07/2015

    MD5

    MD5 (MD5 Message-Digest Algorithm) là một thuật toán tóm tắt thông điệp, là một hàm băm mã hóa được dùng để chứng thực sự toàn vẹn của nội dung. Nội dung sau khi băm qua ...

    Bugs13/08/2018

    Trích Xuất Dữ Liệu Từ File Excel Bằng Python - Phần 1: Đọc Dữ Liệu

    Đọc và ghi dữ liệu từ các file là điều chắc chắn bạn sẽ gặp phải trong quá trình học tập và làm việc. Thông qua bài viết này tôi muốn gửi đến các bạn đọc một cách để ...

    Ryan Lê18/03/2015

    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 sắp xếp vung đống Heapsort vẫn thường được sử dụng do có tốc độ chạy nhanh và không quá phức tạp. ...

    Nguyễn Hoàng Vinh04/09/2017

    Thuật Toán Vẽ Đường Thẳng DDA - Digital Differential Analyzer

    Thuật toán DDA - Digital Differential Analyzer được dùng để xác định các điểm ảnh được vẽ của đường thẳng trên màn hình. Bài viết giới thiệu về thuật toán DDA, một thuật ...

    Vũ Trọng Quang01/06/2017

    Xử Lý Ảnh Với OpenCV: Các Phép Toán Hình Thái Học

    Nẳm trong loạt bài viết trong chương trình Tự Học OpenCV Qua Các Ví Dụ Thực Tế. Bài viết giới thiệu những thuật toán cơ sở trong xử lý hình thái học, và đã giới thiệu ...

    Trương Xuân Đạt23/01/2015

    Trích Xuất Dữ Liệu Từ File Excel Bằng Python - Phần 2: Ghi Dữ Liệu

    Đọc và ghi dữ liệu từ các file là điều chắc chắn bạn sẽ gặp phải trong quá trình học tập và làm việc. Thông qua bài viết này tôi muốn gửi đến các bạn đọc một cách để ...

    Ryan Lê18/03/2015

    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
    [email protected]

    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