Алгоритм rle

Один из самых старых и самых простых методов сжатия информации — это алгоритм RLE (Run Length Encoding), то есть алгоритм кодирования серий последовательностей. Этот метод очень прост в реализации и представляет собой один из алгоритмов архивации, а суть его заключается в замене серии (группы) повторяющихся байтов на один кодирующий байт и счетчик числа их повторений. То есть группа одинаковых байтов заменятся на пару: <счетчик повторений, значение>, что сокращает избыточность данных.

В данном алгоритме признаком счетчика служат единицы в двух верхних битах считанного байта. К примеру, если первые два бита — это 11, то остальные 6 бит отводятся на счетчик, который может принимать значения от 1 до 64. Соответственно серию из 64 повторяющихся байтов можно определить всего двумя байтами, то есть сжать в 32 раза.

Есть и другой вариант реализации этого алгоритма, когда признаком счетчика является 1 в первом байте счетчика. В этом случае счетчик может принимать максимальное значение, равное 127, — а следовательно максимальная степень сжатия будет равна 64.

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

Метод RLE, как правило, весьма эффективен для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), поскольку они содержат очень много длинных серий повторяющихся последовательностей байтов.

Ограничение информационного алфавита

Еще один достаточно простой способ сжатия информации можно назвать ограничением информационного алфавита. Сразу же отметим, что на практике такой алгоритм не реализован, но изложение данного метода поможет лучше понять метод кодов переменной длины.

В дальнейшем под информационным алфавитом мы будем подразумевать набор символов, используемый для кодирования информационной последовательности. К примеру, пусть имеется некоторое текстовое сообщение. Для кодировки каждой буквы этого сообщения используется ASCII-таблица, состоящая из 256 символов. При этом под кодирование каждого символа отводится ровно 8 бит (1 байт). В данном случае информационный алфавит — это все 256 символов кодировочной ASCII-таблицы.

Понятно, что в исходном текстовом сообщении могут применяться не все 256 символов ASCII-таблицы. К примеру, если речь идет о текстовом сообщении на русском языке, в котором нет цифр, то достаточно 64 символов (33 строчные и 31 заглавная буквы). Если добавить к этому знаки препинания, знаки абзаца и перехода на новую строку, станет понятно, что число символов не превысит 100. В этом случае можно использовать не 8-, а 7-битное кодирование символов, что позволяет получить таблицу из 128 символов. То есть мы как бы ограничиваем информационный алфавит, за счет чего можно уменьшить разрядность каждого колируемого символа. Можно пойти дальше — точно определить количество применяемых символов в текстовом сообщении. Если, к примеру, выяснится, что в сообщении задействуются всего 30 символов (включая символы перехода на новую строку), то можно использовать 5-битную кодировочную таблицу, содержащую 32 символа, и тогда степень сжатия текстового сообщения станет еще большей. Действительно, если в исходном сообщении применяется 8-битное кодирование символов, а в сжатом — 5-битное, то коэффициент сжатия будет 8/5.

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

У метода ограниченного алфавита есть и другие недостатки. Если исходное информационное сообщение содержит большое количество разнообразных символов, то понизить разрядность представления символов алфавита не удастся и данный способ просто не сработает. Предположим, к примеру, что в исходном информационном сообщении содержится 129 символов из 256-символьного алфавита. Воспользоваться 7-битным кодированием символов в данном случае не удастся, поскольку 7 бит позволят закодировать только 128 символов. Поэтому для 129 символов придется обратиться к тому же 8-битному кодированию, как и в исходном 256-символьном алфавите.