Допустимость потерь

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

• символические данные, изменение которых неминуемо приводит к изменению их семантики: программы и их исходные тексты, двоичные массивы и т. п.;

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

• данные, многократно подвергаемые сжатию и расжатию: рабочие графические, звуковые, видеофайлы.

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

Сжатие информации с потерями — вид сжатия, в сжатом виде сохраняется не вся исходная информация, а только её приближение. Таким образом, невозможно восстановить исходные данные полностью, а только «похожие» данные, отличающиеся от исходных на некоторую незначительную величину.

Сжатие с потерями применяется для информации, имеющей аналоговую природу, то есть являющейся результатом измерения некоторых реальных объектов или процессов. Чаще всего это изображение и звук.

Следует различать собственно программу-архиватор, формат архивов и методы сжатия. Даже один и тот же метод сжатия может иметь варианты реализации. Например, существует более десятка программ-архиваторов, которые могут создавать архивы в формате ZIP. В свою очередь данные в формате ZIP могут быть сжаты различными методами: Deflate, Deflate64, BZip2. Метод Deflate имеет несколько реализаций с разной скоростью и степенью сжатия (разница порядка 5%). С помощью этого метода архиватор 7-zip позволяет создавать архивы в формате ZIP и 7Z.

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

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

o сжатие некоторых файлов и целых директорий;

o создание самораспаковывающихся (SFX) архивов. То есть для распаковки архива программа-архиватор не требуется;

o изменение содержимого архива;

o шифрование содержимого архива;

o информация для восстановления архива при частичном повреждении и возможность восстановления поврежденных архивов;

o разбивка архива на несколько частей или томов;

o консольная версия программы для работы из командной строки;

o графическая (GUI) версия программы.

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

Кроме различий в функциональности, можно разбить архиваторы на две группы: асимметричные и симметричные. Асимметричные архиваторы требуют для операции распаковки значительно меньше времени и оперативной памяти, чем для операции упаковки. Это позволяет быстро получать содержимое архива на маломощных компьютерах. Симметричные архиваторы требуют для операций упаковки и распаковки одинаковое время и объем оперативной памяти. Использование таких архиваторов на широком парке компьютеров или для оперативного доступа к содержимому архива ограничено. Известный архиватор RAR в качестве основного использует асимметричный словарный метод сжатия, а для текстов может использовать симметричный PPM-метод. Таким образом, распаковка архивов RAR, сжатых с максимальной степенью сжатия, может быть невозможна на компьютерах с ограниченным объемом оперативной памяти. Все или почти все передовые архиваторы с высокой степенью сжатия являются симметричными.

Точной статистики по распространенности архиваторов у меня нет. Я выскажу свою субъективную точку зрения на основе личного опыта. Безусловно, самым распространенным архиватором являются ZIP и его модификации. По своей распространенности он значительно превосходит ближайших конкурентов. Следом идут RAR и ACE. В последние годы встречается архиватор 7-zip. Других архиваторов и архивов лично мы не встречали. Исключение составляют некогда популярные ARJ и LHA. В данный момент они не актуальны из-за очень низкой степени сжатия.

Несмотря на очень скромные данные о распространенности архиваторов, их существует большое множество. Основная масса относится к категории экспериментальных и архиваторов с ограниченной функциональностью. Тем не менее каждый их них позволяет выполнять собственно процедуру сжатия данных. Меньшая распространенность увеличивает вероятность ошибок в программе. К ним стоит относиться с некоторой осторожностью. Например, при проведении тестирования была найдена ошибка в архиваторе WinRK (PWCM), которую, однако, оперативно исправили.

Принцип работы всех видов, будь-то платных или бесплатных архиваторов базируется на алгоритме, разработанном Абрахамом Лампелем и Якобом Зивом еще в 80-х годах. Суть алгоритма заключается в сжатии информации находящейся в файлах, и осуществляется за счет вычисления и дальнейшей замены повторяющегося кода на код который указывает на кратность повторения.

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

Скорость работы архиватора зависит от количества оперативной памяти (ОЗУ) которое выделяется для работы программы. Идеальный объем памяти должен превышать размер словаря в 5-6 раз. Основным плюсом словарного метода архивации является высокая скорость распаковки сжатых данных, при этом для разархивирования необходимо минимальное количество оперативной памяти.

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

Вопросы для самопроверки:

1. Перечислите типы программного обеспечения.

2. Что такое системное ПО?

3. Приведите примеры операционных систем.

4. Что такое файл?

5. Что определяет тип файла?

6. К какому типу ПО относятся архиваторы?

7. Перечислите методы сжатия информации.

8. Что такое файловая система? Задачи файловой системы.

9. Как называлась первая операционная система?

10. В каком году появилась первая Windows?

11. Что называется прикладным программным обеспечением?

12. В чем отличие прикладных программ от системных и инструментальных?

13. Что такое каталог?

14. Сколько файлов можно разместить в одном кластере винчестера?

15. Из чего состоит имя файла?

16. Что определяет размер файла?

17. Перечислите правила присвоения имен файлам.

18. Что такое корневой каталог?

19. Что определяет путь к файлу?

20. Перечислите элементы операционной системы.