Алгоритм rle

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

Рассмотрим идею сжатия данных по методу RLE (это не метод, а идея):

• во входной последовательности все повторяющиеся цепочки байтов заменяются на фрагменты {управляющий байт, повторяющийся байт}, причем управляющийся байт должен иметь значение 128+длина цепочки. Эта формула означает, что старший бит управляющего байта всегда равен 1 для цепочки повторяющихся байтов (символов);

• все неповторяющиеся цепочки байтов заменяются на фрагменты {управляющий байт, цепочка неповторяющихся байтов}, причем управляющий байт имеет значение 0+длина цепочки. Эта формула, означает, что старший бит управляющего байта для неповторяющейся цепочки равен 0.

Ограничения – длина обрабатываемого фрагмента не должна превосходить 127 байтов.

Схема распаковки:

• если во входной сжатой последовательности встречается управляющий байт с единицей в старшем разряде, то надо следующий за ним байт повторить в выходной последовательности столько раз, сколько указано в оставшихся 7 битах управляющего байта;

• если во входной сжатой последовательности встречается управляющий байт с нулем в старшем разряде, то надо в выходную последовательность поместить столько байт следующих за управляющим байтом сколько указано в оставшихся 7 битах управляющего байта;

Пример. Надо упаковать методом RLE следующую последовательность

11111111 11111111 11111111 11111111 11111111

11110000 00001111 11000011 10101010 10101010

10101010 10101010

Результат

10000101 11111111 00000011 11110000 00001111

11000011 10000100 10101010

Таким образом, 12 байт упаковали в 8 байт, и значит, коэффициент сжатия равен 2/3, т.е. 66 процентов.

Различные реализации данного метода используются в графических файлах форматов PCX, BMP, при факсимильной передаче информации. Для текстовой информации метод RLE неэффективен.

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

В конце 70-х годов прошлого века израильские ученые Яков Зив и Абрахам Лемпель предложили алгоритмы сжатия LZ77 и LZ78. Оригинальность алгоритмов состоит в том, что сжимаются здесь не только относительно буквы но и слова.

Общая схема алгоритма LZ77 такова (это не точное описание алгоритма):

• входные данные читаются последовательно, текущая позиция условно разбивает массив входных данных на прочитанную и непрочитанную части;

• для цепочки первых байтов непрочитанной части ищется наиболее длинное совпадение в прочитанной части. Если совпадение найдено, то составляется комбинация {смещение, длина}, где смещение указывает, на сколько байтов надо сместиться назад от текущей позиции, чтобы найти совпадение, а длина — это длина совпадения;

• если запись комбинации {смещение, длина} короче совпадения, то она записывается в выходной массив, а текущая позиция перемещается вперед (на длину совпадающей части);

• если совпадение не обнаружено или оно короче записи комбинации {смещение, длина}, то в выходной массив копируется текущий байт, текущая позиция перемещается вперед на 1, и анализ повторяется.

Пример. Фраза КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ зако- дируется алгоритмом LZ77 как КО ЛО(-4,3)_(- 5,4 )0_(-14,7)ЬНИ.

Общая схема алгоритма LZ78 такова (это не точное описание алгоритма):

• алгоритм во время сжатия текста создает специаль­ный словарь повторяющихся цепочек, в словаре каждой цепочке соответствует короткий код;

• для цепочки первых байтов непрочитанной части ищется наиболее длинное совпадение в словаре. Код совпадения записывается в выходной массив, туда же заносится первый несовпавший символ, и текущая позиция перемещается вперед на длину совпадения + 1;

• в словарь добавляется новое слово: «совпадение» + + «несовпавший символ», и процесс повторяется до тех пор, пока не будет сжат весь входной массив.

Алгоритмы Лемпеля - Зива тем лучше сжимают текст, чем больше размер входного массива. Характерной особенностью обратных алгоритмов LZ77 и LZ78 является то, что, кроме самих сжатых данных, никакой дополнительной информации им не требуется! Начав работать, эти алгоритмы по уже распакованной части восстанавливают информацию, необходимую для распаковки следующих частей сжатых данных. Для сравнения: в алгоритме Хаффмана вместе со сжатыми данными требуется сохранять дерево Хаффмана, иначе распаковка будет невозможна.

Поучительна история развития алгоритмов Лемпеля - Зива. Зив и Лемпель придумали плодотворные идеи сжатия, построили алгоритмы и провели теоретическое исследование их эффективности. Но поскольку опубликованные алгоритмы были очень неэффективно реализованы (т. е. запрограммированы), долгое время они не использовались на практике. Только спустя 6 лет, в 1984 году Терри Велч (Terry Welch) сумел существенно улучшить алгоритм LZ78. Эта модификация алгоритма получила название LZW, она широко используется в программах сжатия данных. Алгоритм LZ77 ждал своего часа целых десять лет — только в 1987 году появилась его высокоэффективная версия, которая работала в сотни (!) раз быстрее оригинального алгоритма. В настоящее время существует около полусотни модификаций обоих алгоритмов. Обобщенно все они называются методами сжатия со словарем. Эти алгоритмы оказались настолько быстры и эффективны, что сейчас занимают лидирующее место среди используемых на практике алгоритмов сжатия.