Статьи » Теория компьютерной грамотности

Принцип работы архиватора (Алгоритмы сжатия)


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

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

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

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

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

Рейтинг

В этом разделе

Добавить комментарий

Естественный спутник земли ?