Алгоритм RLE

Самый простой из словарных методов – RLE (Run Length Encoding, кодирование переменной длины) умеет сжимать данные, в которых есть последовательности повторяющихся байтов. Упакованные RLE данные состоят из управляющих байтов, за которыми следуют байты данных. Если старший бит управляющего байта равен 0, то следующие байты (в количестве, записанном в семи младших битах управляющего байта) при упаковке не изменялись. Если старший бит равен 1, то следующий байт нужно повторить столько раз, какое число записано в остальных разрядах управляющего байта.

Например, исходная последовательность

00000000 00000000 00000000 00000000 11001100 10111111 10111011

будет закодирована в следующем виде (выделены управляющие байты):

10000100 00000000 00000011 11001100 10111111 10111011.

А, например, данные, состоящие из сорока нулевых байтов, будут закодированы всего двумя байтами: 1010 1000 00000000.

Алгоритм Лемпела-Зива

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

Словом в этом алгоритме называется последовательность символов (не обязательно совпадающая со словом естественного языка). Слова хранятся в словаре, а их вхождения в исходные данные заменяются адресами (номерами) слов в словаре. Некоторые разновидности алгоритма хранят отдельно словарь и отдельно упакованные данные в виде последовательности номеров слов. Другие считают словарем весь уже накопленный результат сжатия. Например, сжатый файл может состоять из записей вида [ a,l,t ], где a – адрес (номер позиции), с которой начинается такая же строка длины l, что и текущая строка. Если a >0, то запись считается ссылкой на словарь и поле t (текст) в ней – пустое. Если a = 0, то в поле t записаны l символов, которые до сих пор в такой последовательности не встречались.

Алгоритм сжатия заключается в постоянном поиске в уже упакованной части данных максимальной последовательности символов, совпадающей с последовательностью, начинающейся с текущей позиции. Если такая последовательность (длины > 3) найдена, в результат записывается ее адрес и длина. Иначе в результат записывается 0, длина последовательности и сама (несжатая) последовательность.