Уроки 6 - 9
Сжатие данных без потерь
(§3. Сжатие данных)

Содержание урока

Основные понятия

Алгоритм RLE

Префиксные коды

Алгоритм Хаффмана

Сжатие с потерями

Выводы

Вопросы и задания

Задачи

Алгоритм RLE

При сжатии данных, в которых есть цепочки одинаковых кодов, можно применять ещё один простой алгоритм, который называется кодированием цепочек одинаковых символов (англ. RLE — Run Length Encoding). Представим себе файл, в котором записаны сначала 100 русских букв «А», а потом — 100 букв «Б»:

При использовании алгоритма RLE сначала записывается количество повторений первого символа, затем — сам первый символ, затем — количество повторений второго символа, затем — второй символ и т. д. В данном случае весь закодированный файл занимает 4 байта:

Таким образом, мы сжали файл в 50 раз за счёт того, что в нём снова была избыточность — цепочки одинаковых символов. Это сжатие без потерь, потому что, зная алгоритм упаковки, исходные данные можно точно восстановить из кода.

Очевидно, что такой подход будет приводить к увеличению (в 2 раза) объема данных в том случае, когда в файле нет соседних одинаковых символов. Чтобы улучшить результаты RLE-кодирования даже в этом наихудшем случае, алгоритм модифицировали следующим образом. Упакованная последовательность содержит управляющие байты, за каждым управляющим байтом следует один или несколько байтов данных. Если старший бит управляющего байта равен 1, то следующий за управляющим байт данных при распаковке нужно повторить столько раз, сколько записано в оставшихся 7 битах управляющего байта. Если же старший бит управляющего байта равен 0, то надо взять несколько следующих байтов данных без изменения. Сколько именно — записано в оставшихся 7 битах управляющего байта. Например, управляющий байт 10000111₂ говорит о том, что следующий за ним байт надо повторить 7 раз, а управляющий байт 00000100₂ — о том, что следующие за ним 4 байта надо взять без изменений. Например, последовательность

распаковывается в 17 символов: АААААААААААААААБВ.

Алгоритм RLE успешно использовался для сжатия рисунков, в которых большие области закрашены одним цветом, и некоторых звуковых данных. Сейчас вместо него применяют более совершенные, но более сложные методы. Один из них (алгоритм Хаффмана) мы рассмотрим далее. Алгоритм RLE используется, например, на одном из этапов кодирования рисунков в формате JPEG. Возможность использования RLE-сжатия есть также в формате BMP (для рисунков с палитрой 16 или 256 цветов).

Следующая страница Префиксные коды

Cкачать материалы урока