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

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

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

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

Рассмотрим изображение, содержащее простой чёрный текст на сплошном белом фоне. Здесь будет много серий белых пикселей в пустых местах, и много коротких серий чёрных пикселей в тексте. В качестве примера приведена некая произвольная строка изображения в черно-белом варианте. Здесь B представляет чёрный пиксель, а W обозначает белый:

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

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

См. также[править | править исходный текст]