RLE

Кодування довжин серій (англ. Run-length encoding, RLE) або Кодування повторів — простий алгоритм стиснення даних, який оперує серіями даних, тобто послідовностями, в яких один і той же символ зустрічається кілька разів поспіль. При кодуванні рядок однакових символів, що становлять серію, замінюється рядком, який містить сам повторюваний символ і кількість його повторів.

Приклад використання

Розглянемо зображення, що містить простий чорний текст на суцільному білому фоні. Тут буде багато серій білих пікселів в порожніх місцях, і багато коротких серій чорних пікселів в тексті. Нехай, наприклад, дано довільний рядок чорно-білого зображення. Тут B (англ. Black) позначає чорний піксель, а W (англ. White) - білий:

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

Якщо ми застосуємо просте кодування довжин серій до цього рядка, то отримаємо таке:

12W1B12W3B24W1B14W

Останній запис інтерпретується як «дванадцять W», «одна B», «дванадцять W», «три B» і т. д. Таким чином, код подає вихідні 67 символів у вигляді всього лише 18.

Однак, у випадку, якщо рядок містить велику кількість неповторюваних символів, його обсяг може зрости.

ABCABCABCDDDFFFFFF

1A1B1C1A1B1C1A1B1C3D6F

Проблема вирішується досить просто. Алфавіт, в якому записані довжини серій, розділяється на дві (зазвичай рівні) частини. Алфавіт цілих чисел можна, наприклад, розділити на дві частини: додатні і від'ємні. Додатні використовують для запису кількості повторюваних однакових символів, а від'ємні — для запису кількості неоднакових.

-9ABCABCABC3D6F

Оскільки чисельні типи даних на комп'ютері завжди мають певну межу, виникає ще одна проблема. Припустимо, ми використовуємо тип signed char для запису довжин серій. Тоді ми не можемо записати серію, довшу ніж 127 символів, однією парою «довжина-символ». Якщо поспіль записано 256 символів A, їх розділяють на мінімальну кількість груп:

127A127A2A

Реалізація на конкретній мові програмування алгоритму RLE з урахуванням цих обмежень може бути нетривіальною.

Звичайно, кодування, яке використовується для зберігання зображень, оперує з двійковими даними, а не з символами ASCII, як у розглянутому прикладі, однак принцип залишається таким самим.

Застосування

Вочевидь, що таке кодування ефективно для даних, що містять велику кількість серій, наприклад, для простих графічних зображень, таких як іконки та графічні малюнки. Однак це кодування погано підходить для зображень з плавним переходом тонів, таких як фотографії.

Поширені формати для упаковки даних за допомогою RLE включають в себе PackBits, PCX і ILBM.

Методом кодування довжин серій можуть бути стиснуті довільні файли з двійковими даними, оскільки специфікації на формати файлів часто включають в себе повторювані байти в області вирівнювання даних. Проте, сучасні системи стиснення (наприклад, DEFLATE) частіше використовують алгоритми на основі LZ77, які є узагальненням методу кодування довжин серій і оперують з послідовностями символів виду «BWWBWWBWWBWW».

Звукові дані, які мають довгі послідовні серії байт (такі як низькоякісні звукові семпли) можуть бути стиснуті за допомогою RLE після того, як до них буде застосовано Дельта-кодування.

Реалізація алгоритму мовою C/C++

#include <stdio.h>
#include <string.h>

int main()
{
    int cnt;
    char smb;
    char *code = new char [80];
    char *encode = new char [80];
    char *str = new char [80];

    scanf("%s", code);

    strcpy(encode, "");
    smb = code[0];
    cnt = 0;

    for (int i = 0; i <= strlen(code); i++) {
        if (code[i]==smb) {
            cnt++;
        }
        else {
            sprintf(str, "%d", cnt);
            strcat(encode, str);
            sprintf(str, "%c", smb);
            strcat(encode, str);
            smb = code[i];
            cnt = 1;
        }
    }

    printf("%s\n", encode);

    return 0;
}

Реалізація алгоритму мовою PHP

<?php
$code = 'fafaaaaaaaaaaaaa';
$encode = '';

for ($i = 0; $i < strlen($code);$i++){
	$smb = $code[$i] ;
	$count = 1 ;
	for ($b = $i; $b < strlen($code);$b++){
		if ($code[$b + 1] != $smb) break ;
		$count++ ;

		$i++ ;
	}
	$encode .= $count . $smb ;
}
print 'Рядок: ' . $code . ' вдалося стиснути до ' . $encode . '.<br /> і ми заощадили ' . (strlen($code) - strlen($encode)) . ' байтів.' 
?>

Реалізації алгоритму мовою Delphi/Pascal

function encode(s:string):string;
var i,k:integer; c:char;
begin
  Result:='';
  if s='' then exit;
  c:=s[1]; 
  k:=1;
  for i:=2 to length(s)+1 do
    if s[i]=c then inc(k) else
      begin
        if k>1 then Result:=Result+IntToStr(k);
        Result:=Result+c;
        c:=s[i];
        k:=1;
      end;
end;
 
function decode(s:string):string;
var i,j,c:integer;
    newS:string;
begin
i:=1;
while i <= length(s) do
  begin
    j:=i;
    while s[j] in ['0'..'9'] do inc(j);
    if j-i > 0 then
    begin
      for c:=1 to strtoint(copy(s,i,j-i)) do newS := newS + s[j];
      delete(s,i,j-i+1);
    end else
    begin
      newS := newS + s[i];
      inc(i);
    end;
  end;
  result:= newS;
end;

Реалізації алгоритму на Visual Basic 6

Public Function Encode(ByVal SrcString As String) As String
    Dim I As Long, N As Long, sResult As String
    N = 1
    
    For I = 1 To Len(SrcString)
        If Not Mid(SrcString, I, 1) = Mid(SrcString, I + 1, 1) Then
            sResult = sResult & IIf(I - N + 1 > 1, CStr(I - N + 1), CStr("")) & Mid(SrcString, I, 1)
            N = I + 1
        End If
    Next
    
    Encode = sResult
End Function

Див. також

• LZ77
• Deflate
• Дельта-кодування