2020-06-29
182
Существуют разные форматы архивов: ZIP(алгоритм сжатия Deflate), ARJ, RAR(алгоритм сжатия LZ77), CAB, TAR, LZH и др. Когда создается архивный файл, ему присваивается расширение, совпадающее с форматом архива. Например, файл с именем MyDoc.zip - это архив формата ZIP. Формат влияет на эффективность сжатия файлов; к примеру, архив формата RAR занимает на диске меньше места, чем архив формата ZIP, содержащий те же самые исходные файлы. Кроме того, эффективность зависит от типа файлов, упаковываемых в архив. Файлы картинок, имеющие расширение BMP, документы Microsoft Word удается сжать в два-четыре раза, текстовые файлы - приблизительно в два раза. Несколько хуже подвержены сжатию исполняемые файлы (с расширением EXE), а графические файлы, имеющие расширение TIF, практически не сжимаются.
Deflate — это алгоритм сжатия без потерь, использующий комбинацию алгоритмов LZ77 и Хаффмана.
Существует много разных практических методов сжатия без потери информации, которые, как правило, имеют разную эффективность для разных типов данных и разных объемов. Однако, в основе этих методов лежат три теоретических алгоритма:
|
|
|
· алгоритм RLE (Run Length Encoding);
· алгоритмы группы KWE (KeyWord Encoding);
· алгоритм Хаффмана.
Алгоритм RLE
В основе алгоритма RLE лежит идея выявления повторяющихся последовательностей данных и замены их более простой структурой, в которой указывается код данных и коэффициент повторения.
Например, пусть задана такая последовательность данных, что подлежит сжатию: 1 1 1 1 2 2 3 4 4 4. В алгоритме RLE предлагается заменить ее следующей структурой: 1 4 2 2 3 1 4 3, где первое число каждой пары чисел - это код данных, а второе - коэффициент повторения
Существует довольно много реализаций этого алгоритма, среди которых наиболее распространенными являются алгоритм Лемпеля-Зива (алгоритм LZ) и его модификация алгоритм Лемпеля-Зива-Велча (алгоритм LZW). Словарем в данном алгоритме является потенциально бесконечный список фраз. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. При считывании очередного символа входной последовательности данных, он прибавляется к текущей строке.
Алгоритм LZW построен вокруг таблицы фраз (словаря), которая заменяет строки символов сжимаемого сообщения в коды фиксированной длины. Таблица имеет так называемое свойством опережения, то есть для каждой фразы словаря, состоящей из некоторой фразы w и символа К, фраза w тоже заносится в словарь. Если все части словаря полностью заполнены, кодирование перестает быть адаптивным (кодирование происходит исходя из уже существующих в словаре фраз).
|
|
|
Алгоритмы сжатия этой группы наиболее эффективны для текстовых данных больших объемов и малоэффективны для файлов маленьких размеров (за счет необходимости сохранение словаря).
Алгоритм Хаффмана
В основе алгоритма Хаффмана лежит идея кодирования битовыми группами. Сначала проводится частотный анализ входной последовательности данных, то есть устанавливается частота вхождения каждого символа, встречащегося в ней. После этого, символы сортируются по уменьшению частоты вхождения.
Основная идея состоит в следующем: чем чаще встречается символ, тем меньшим количеством бит он кодируется. Результат кодирования заносится в словарь, необходимый для декодирования. Рассмотрим простой пример, иллюстрирующий работу алгоритма Хаффмана.
На практике программные средства сжатия данных синтезируют эти три "чистых" алгоритмы, поскольку их эффективность зависит от типа и объема данных. В таблице 2 приведены распространенные форматы сжатия и соответствующие им программы-архиваторы, использующиеся на практике.
Алгоритм KWE
В основе алгоритма сжатия по ключевым словам положен принцип кодирования лексических единицгруппами байтфиксированной длины.
Примером лексической единицы может быть обычное слово. На практике, на роль лексических единиц выбираются повторяющиеся последовательности символов, которые кодируются цепочкой символов (кодом) меньшей длины. Результат кодирования помещается в таблице, образовывая так называемый словарь.
