1.Любой произвольной выборке данных всегда можно сопоставить метод кодирования, обеспечивающий для данной выборки минимальную избыточность (максимальное уплотнение).

2.Любому произвольному методу сжатия данных всегда можно сопоставить такую выборку данных, для которой данный метод кодирования не обеспечит уплотнения (уменьшения избыточности).

Из этих утверждений вытекают два следствия и два правила.

1.Не существует «абсолютного» метода сжатия — такого, который обеспечил бы максимальную степень уплотнения для любых типов данных. Применять методы сжатия данных следует только в тех условиях, для которых они были разработаны.

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

Обратимость методов сжатия данных

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

Обратимые методы сжатия применяют в тех случаях, когда данные имеют документальный характер и их искажение недопустимо. К этой категории относятся текстовые документы, содержимое таблиц баз данных, а также числовой код программ. Обычная степень уплотнения данных обратимыми методами составляет от 1 : 1,5 до 1 : 10.

Необратимые методы сжатия обеспечивают значительно более высокие степени уплотнения (от 1 : 10 до 1 : 200), но при этом вносят в данные неустранимые погрешности. Иногда этими погрешностями можно пренебречь, например, когда речь идёт о мультимедийных данных (графика, звук, видео).

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

Обратимые методы сжатия данных

Существует множество методов обратимого сжатия данных, но в их основе лежит всего два основополагающих принципа: групповое сжатие и сжатие по словарю. В обоих случаях избыточность уменьшается за счёт ликвидации повторов, но происходит это по-разному. В первом случае перекодируются группы повторяющихся элементов, а во втором случае — повторяющиеся группы элементов.

Групповое сжатие

Наглядный пример использования группового сжатия демонстрирует метод, который называется (Run Length Encoding). Сначала в наборе данных выбираются группы повторяющихся элементов, затем каждая группа заменяется кодом элемента и коэффициентом повтора.

95