Новичку об архивации

Принцип работы архиваторов, методы и алгоритмы сжатия информации.

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

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

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

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

Наиболее популярные методы сжатия данных.

Самым простым, но очень эффективным методом сжатия файлов при архивировании является метод «кодирования длин серий» (RLE – run length encoding). При этом способе серия одинаковых знаков (элементов) заменяется двумя символами – самим элементом и количеством его повторов в этой серии. Однако в большинстве текстовых файлов такие серии одинаковых элементов встречаются довольно редко, поэтому ожидать существенного сокращения объема файла не приходится. Ввиду этого этот метод используется, в основном, как дополнительный или промежуточный. Но он достаточно эффективен при сжатии файлов в формате bmp, в котором служит в качестве основного метода сжатия.

Энтропийные методы – это такие методы сжатия, которые основаны на знании вероятностей появления элементов кодируемого сообщения (последовательности). К этому методу относятся алгоритм Хаффмана и арифметическое кодирование.

Алгоритм Хаффмана. Если взять страницу из любой книги и подсчитать количество букв в ней, а потом сосчитать, сколько раз встретилась буква «а», то можно определить и вероятность ее повторения и на другой странице этой книги. Таким же способом мы можем рассчитать вероятность появления всех букв, цифр, знаков препинания, промежутков между словами и т. д. и т. п. Зная эти вероятности появления элементов, можно составить таблицу, на основе которой составляются, так называемые, префиксные коды, причем, часто встречающимся элементам присваивается короткий код, а редко встречающимся – длинный. Это происходит автоматически при составлении программой-архиватором «Дерева кодирования» (Н-дерева).

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

К недостаткам алгоритма Хаффмана следует отнести необходимость дополнительного (и существенного) объема памяти. Кроме этого, для того, чтобы впоследствии распаковать заархивированный файл, распаковщик должен иметь таблицу кодов, которая использовалась при архивации. Поэтому эта таблица передается в архивный файл перед самой архивируемой информацией файла. Ввиду того, что эти таблицы также занимают объем памяти, то это может значительно снизить эффективность сжатия, что особенно актуально для небольших по объему файлов.

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

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

При всем этом, арифметическое кодирование является наилучшим алгоритмом среди энтропийных методов сжатия.

В отличие от метода RLE, именуемого по начальным буквам английской транскрипции названия метода, метод LZ получил свое наименование по первым буквам имен авторов (Lempel Ziv). Это один из наиболее распространенных методов – Словарный метод. Суть его состоит в том, что программа-архиватор создает словарь из слов и последовательностей данных самих исходных файлов. Важнейшей характеристикой этого метода является размер словаря – чем он больше, тем выше эффективность сжатия. Сам словарь увеличивается по мере кодировки, поэтому при кодировании используется дополнительная память, объем которой может значительно (на порядок) превышать объем самой кодируемой информации. В то же время, для распаковки дополнительная память не требуется, а сам процесс разархивации прост и быстр. Это очень актуально при необходимости оперативного доступа к информации, находящейся в архиве.

Алгоритм Лемпеля-Зива. Данный алгоритм является основой практически всех словарных алгоритмов. Суть этого алгоритма состоит в том, что кодируются очень короткие функциональные «слова», из которых формируются более длинные слова и даже целые фразы. На основе этого метода разработано много алгоритмов, о которых можно сказать что любой новый LZ-алгоритм является усовершенствованием предыдущего. Об отличительных особенностях этих алгоритмов можно узнать из многочисленных публикаций в ин7тернете, но в настоящей статье, предназначенной для начинающих пользователей, ограничимся общим представлением.

Существуют и другие методы сжатия данных, такие как:

– метод контекстного моделирования (CM – context modeling);

– предсказание по частному совпадению (PPM – Prediction by Partial Matching);

– метод сортировки блока данных (BWT – Burrows Wheeler Transform);

– предварительные преобразования или фильтрация

И другие методы и алгоритмы. Следует помнить, что существует множество методов сжатия, каждый из которых рассчитан на определенный вид или группу данных. Поэтому только комплексное использование различных методов дает наилучший эффект. Преимущества той или иной программы-архиватора заключаются в формате архива и используемых методах сжатия.