1. Giới thiệu
Mã hóa Run-Length là một thuật toán nén dữ liệu giúp mã hóa các chuỗi dài của các phần tử lặp lại bằng cách chỉ gửi một phần tử từ chuỗi đó và một bộ đếm cho biết số lần xuất hiện của phần tử này. Tuy nhiên, kỹ thuật này không hữu ích khi cố gắng nén các văn bản ngôn ngữ tự nhiên, vì chúng không có các chuỗi dài của các phần tử lặp lại. Ngược lại, RLE lại hữu ích khi đến việc nén ảnh, vì ảnh thường có các chuỗi dài của các pixel có màu giống nhau.
Như bạn có thể thấy trong hình ảnh dưới đây, chúng ta có thể nén các pixel liên tiếp bằng cách chỉ thay thế mỗi chuỗi đó bằng một pixel từ nó và một bộ đếm cho biết số lượng phần tử trong chuỗi.

Trong trường hợp này, chúng ta chỉ cần lưu trữ bộ đếm cho các pixel được lặp lại hơn một lần. Ví dụ, dòng dữ liệu đầu vào “aaaabbaba” sẽ được nén thành “[4]a[2]baba”.
Thực ra, có nhiều cách mà mã hóa Run-Length có thể được sử dụng để nén ảnh. Một cách có thể để nén một hình ảnh là từng hàng hoặc từng cột, như được hiển thị trên hình ảnh dưới đây.

Trong thực tế, vấn đề đặt ra là đôi khi việc nén từng hàng có thể hiệu quả, trong khi trong các trường hợp khác, cùng một phương pháp lại rất không hiệu quả. Điều này được minh họa qua hình ảnh dưới đây.

Rõ ràng, mã hóa Run-Length là một phương pháp rất tốt khi nén ảnh. Tuy nhiên, khi nói đến các hình ảnh lớn với hàng triệu pixel, việc áp dụng một số phương pháp nén mất mát là điều tự nhiên.
2. Tổng quan
Mã hóa Run-Length mất mát là một thuật toán rất phù hợp khi nói đến ảnh, vì trong hầu hết các trường hợp, các hình ảnh lớn thường có những khoảng trống lớn của các pixel cùng màu, ví dụ như khi một nửa của bức tranh là bầu trời màu xanh. Bằng cách sử dụng nén mất mát, chúng ta có thể bỏ qua các chuỗi rất ngắn.
Đầu tiên, chúng ta cần xác định chiều dài ngắn nhất của chuỗi mà chúng ta sẽ giữ lại trong quá trình nén. Ví dụ, nếu 3 là độ dài ngắn nhất, thì các chuỗi có 2 phần tử liên tiếp sẽ bị bỏ qua.

Tất nhiên, nếu chúng ta đặt chiều dài ngắn nhất của chuỗi chỉ là một phần tử, điều này sẽ làm cho việc nén của chúng ta hoàn toàn không mất mát, điều này không hiệu quả lắm. Tuy nhiên, khi nói đến hàng triệu pixel, thậm chí các chuỗi có ba hoặc nhiều phần tử cũng rất ngắn, vì vậy quyết định chiều dài ngắn nhất của chuỗi là do nhà phát triển quyết định.
Ví dụ
Trước hết, hãy định nghĩa rằng chuỗi ngắn nhất mà ta sẽ giữ nguyên không thay đổi ít nhất phải có độ dài ba phần tử.

Hình ảnh ở trên đã được nén hiệu quả hơn so với hàng pixel không mất mát từ hình ảnh trước đó.
Vấn đề là làm thế nào để kết hợp các chuỗi ngắn lại với nhau. Ví dụ, ba chuỗi sau đây phải được kết hợp thành một chuỗi màu.

Chúng ta có thể chọn màu ở giữa (lựa chọn #1) hoặc không, nhưng điều này luôn phụ thuộc vào hình ảnh và sẽ hiệu quả trong một số trường hợp và không hiệu quả trong các trường hợp khác.
