Методы архивирования
Методы сжатия информации условно делят на два класса:
сжатие без потери информации.
сжатие с потерей информации
Сжатие без потери информации.
Эти методы не могут допустить утрату информации, поэтому они основаны только на устранении ее избыточности.
Существует два основных метода архивации:
Алгоритм Хаффмана
Алгоритм Лемпеля-Зива
Алгоритм Хаффмана - алгоритм, основанный на перекодировании информации. Он применяется для уплотнения текстовых данных, оцифрованного звука.
Хаффмановское кодирование появилось в 1952 году. Главное его предназначение заключалось в упаковке текстовых файлов - для другого он мало приспособлен. Имеет довольно простую реализацию, так что его вполне удобно использовать в устройствах имеющих слабые микропроцессоры.
Алгоритм Хаффмана основан на том факте, что частота появления символов в обычных текстах различна и поэтому нерационально для кодирования каждого бита тратить одно и тоже число бит (обычно 8), лучше будет потратить на менее часто встречаемые символы больше, но потом это окупится тем, что на более встречаемые символы тратится меньше бит. Идея алгоритма кодирования: зная вероятность вхождения символов, можно описать процедуру построения кодов переменной. Символу, имеющему большую вероятность, присваиваются более короткие коды.
Рассмотрим следующий пример: исходный поток АБАБАБАВАБВГ = 12 байт выходной поток Пусть символы кодируются как А=1 Б=01 В=001 Г=000 тогда будет 101101101101001101001000 = 25 бит = 3 байт + 1 бит
Т.е. сжатие будет в 3 раза.
Программы, выполняющие сжатие информации, могут вводить свою кодировку (разную для разных файлов) и приписывать к сжатому файлу таблицу (словарь), из которой распаковывающая программа узнает, как в данном файле закодированы те или иные символы.
Алгоритм Лемпеля-Зива (метод RLE (Run Length Encoding).
В основу алгоритмов RLE положен принцип выявления повторяющихся последовательностей данных и замены их простой структурой, в которой указывается код данных и коэффициент повтора.
Он формулируется следующим образом: «если в более раннем тексте уже встречалась подобная последовательность байт, то в архивный файл записывается только ссылка на эту последовательность (смещение, длина), а не сам текст».
Так фраза «КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ»[24] закодируется в последовательность «КОЛО(-4,3)_О(-6,4)_(-7,7)ЬНИ»[13]. Коэффициент сжатие - 54%.
Так, например, если число 0 повторяется двадцать раз подряд, то нет смысла ставить двадцать нулевых байтов. Вместо них ставят один ноль и коэффициент 20.
Аналогично сжимается изображение. Большие области одного цвета заменяются на ссылку: (цвет, длина) Графические файлы сжимаются очень хорошо – в 100–200 раз!
Большими повторяющимися последовательностями одинаковых байтов особенно отличаются графические иллюстрации, но не фотографические (там соседние точки существенно различаются по параметрам), а такие, которые художники рисуют «гладким» цветом, как в мультипликационных фильмах.
Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов.
Сжатие с потерей информации.
Сжатие с потерей информации означает, что после распаковки архива мы получим документ, который несколько отличается от того, который был в самом начале. Понятно, что чем больше степень сжатия, тем больше величина потери.
Характерными форматами сжатия с потерей информации являются:
.JPG для графических данных;
.MPG для видеоданных;
.МРЗ для звуковых данных.
Такие алгоритмы неприменимы для текстовых документов, таблиц баз данных и особенно для программ. Незначительные искажения в простом неформатированном тексте еще как-то можно пережить, но искажение хотя бы одного бита в программе сделает ее абсолютно неработоспособной.
Но существуют материалы, в которых стоит пожертвовать несколькими процентами информации, чтобы получить сжатие в десятки раз. К ним относятся фотографические иллюстрации, видеоматериалы и музыкальные композиции.
Потеря информации при сжатии и последующей распаковке в таких материалах воспринимается как появление некоторого дополнительного «шума». В этих файлах определенный «шум» уже присутствует и его небольшое увеличение не всегда выглядит критичным, а выигрыш в размерах файлов дает огромный (в 10-15 раз на музыке, в 20-30 раз на фото- и видеоматериалах).
Алгоритм, используемый в JPEG (фото) и MPEG (видео).
В этих стандартах используется дискретное косинусное преобразование маленьких блоков изображения (обычно 8х8) , основная идея которого основана на том, что близкие пикселя мало отличаются друг от друга и поэтому выгодно хранить не их значение, а некую скорость их изменения.
В MPEG все кадры делятся на несколько типов:
базовые - пакуются как JPEG;
переходные - сохраняются изменения, произошедшие от базового кадра.
Так, неупакованное изображение было около 1Мб !!! В результате наилучший вариант (70%) 27Кб, а худшее изображение (5%) занимает около 4Кб.
Типы архивных файлов