Среди обилия "компьютерных" аббревиатур, с которыми мы с вами имели возможность познакомиться в ставшей уже давно традиционной рубрике FAQ, пока было не слишком много таких, которые относятся к очень интересной области того, что на западе называется computer science - а именно, к сжатию данных. Поэтому данная заметка призвана немного улучшить ситуацию и рассказать об одной аббревиатуре, со сжатием данных связанной самым непосредственным образом.

Аббревиатура RLE расшифровывается по-английски как Run-length encoding. На русский язык это словосочетание обычно переводят как "кодирование длин серий" или "кодирование повторов". Что это означает? Это алгоритм сжатия данных, позволяющий эффективно сжимать последовательности, в которых один и тот же байт встречается подряд достаточно большое количество раз. Повторяющиеся символы заменяются на запись соответствующего символа и количество его повторов.

Лучше всего объяснить как это работает можно на примере. Для простоты будем считать, что у нас есть какая-то последовательность символов, имеющая, скажем, следующий вид:

AAAAAOOOOOOOYYYYMMMMMMMMMMPPPPPPPPP

После применения RLE-сжатия эта строка станет такой:

5A7O4Y10M9P

Не согласиться с тем, что благодаря применению кодирования длин серий наш пример стал значительно короче, достаточно сложно. Поскольку для записи используют не символы, а значения байтов, то эффективность получается ещё более высокой, ведь для записи двух- и трёхзначных чисел требуется только один байт. Впрочем, подобный подход ограничивает максимальную длину кодируемой последовательности 256-ю байтами. А если мы применим алгоритм кодирования повторов для тех строк, в которых повторов мало, то эффективность его снизится, потому что нет никакой разницы (с точки зрения объёма информации) писать AA или 2A. Если же в кодируемой строке повторы вовсе отсутствуют, то подобный способ записи не только не сократит, но и увеличит её длину более чем в два раза.

Несмотря на своё несовершенство, алгоритм RLE весьма успешно применяется для сжатия данных в самых разных форматах. Наиболее активно используется RLE при сжатии графических данных, имеющих последовательности повторяющихся байтов в виде сплошной заливки. Также сравнительно часто этот способ применяется для кодирования низкокачественных звуковых данных в режиме реального времени, особенно в тех случаях, когда скорость кодирования более критична, чем качество сжатия.

Вадим СТАНКЕВИЧ