Кодирование длин серий

Материал из Википедии — свободной энциклопедии
(перенаправлено с «RLE»)
Перейти к: навигация, поиск

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

Пример использования[править | править вики-текст]

Рассмотрим изображение, содержащее текст чёрного цвета на сплошном белом фоне. При построчном чтении пикселей такого изображения будут встречаться серии белых (фон) и чёрных (буквы) пикселей. Буквой B обозначим чёрный пиксель, а буквой W — белый. Рассмотрим некую произвольную строку изображения длиной 67 символов:

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

Посчитаем количество повторяющихся символов:

  1. 12 символов «W»;
  2. 1 символ «B»;
  3. 12 символов «W»;
  4. 3 символа «B»;
  5. 24 символа «W»;
  6. 1 символ «B»;
  7. 14 символов «W».

Итого найдено 7 серий. Заменим серии на число повторов и сам повторяющийся символ:

12W1B12W3B24W1B14W

Получилась повледовательность из 18 символов. Исходная последовательность состояла из 67 символов. Данные были сжаты в 67/18≈3.72 раза.

Возъмём строку, состоящую из большого количества неповторяющихся символов:

ABCABCABCDDDFFFFFF

После сжатия методом RLE такая строка будет выглядеть так:

1A1B1C1A1B1C1A1B1C3D6F

Исходная строка состоит из 18 символов, а сжатая — из 22. Размер данных увеличился в 22/18≈1.22 раза.

Чтобы после сжатия размер данных не увеличивался, алфавит, в котором записаны длины серий, делят на две части (обычно равные). Например, алфавит целых чисел можно разделить на две части: положительные и отрицательные числа. Положительные числа используют для записи количества повторов одного символа, а отрицательные — для записи количества неодинаковых символов, следующих друг за другом.

Посчитаем символы с учётом вышесказанного:

  • сначала друг за другом следуют 9 не одинаковых символов: «ABCABCABC»;
  • затем записаны 3 символа «D»;
  • наконец записаны 6 символов «F».

Сжатая строка запишется в виде:

-9ABCABCABC3D6F

Исходная строка состоит из 18 символов, а сжатая — из 15. Размер данных уменьшился в 18/15=1.2 раза.

Допустим, реализация метода RLE для записи длин серий (для подсчёта количества символов) использует переменную целочисленного типа со знаком «signed char». В такую переменную можно записать числа от -128 до 127 включительно. Как же быть, если длина серии равна 128 символам и более? В этом случае серию разделяют на части так, чтобы длина части не превышала 127 символов. Например, серия, состоящая из 256 символов «A», будет закодирована следующей строкой (256=127+127+2):

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

Полезные ссылки[править | править вики-текст]

См. также[править | править вики-текст]