Лекция 14. Архивирование и методы сжатия информации

14.1. Что такое архивирование

Несмотря на то, что объемы внешней памяти ЭВМ постоянно растут, потребность в архивации не уменьшается. Архивация необходима не только для экономии памяти, но и для надежного хранения копий ценной информации, для быстрой передачи информации по сети.

Архивирование (упаковка, сжатие) это процесс записи файла в архивный файл, разархивирование (распаковка) — процесс извлечения файла из архива. Архив — упакованный (сжатый) файл.

Архивация информации это такое преобразование информации, при котором объем информации уменьшается, а количество информации остается прежним.

Степень сжатия информации зависит от типа файла и от выбранного метода упаковки. Степень (качество) сжатия файлов характеризуется коэффициентом сжатия:

V_c — объем сжатого файла, V_и — объем исходного файла.

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

14.2. Какие существуют методы архивирования

Все используемые методы сжатия информации можно разделить на два класса:

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

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

Первая идея основана на учете частот символов , она разработана Д. А. Хаффманом а 1952 году. Эта идея базируется на том факте, что в обычном тексте частоты появления различных символов неодинаковы. Часто встречающиеся символы кодируются короткими последовательностями битов, а более редкие — длинными. К каждому сжатому архиву прикладывается таблица соответствия символов и кодов.

Вторая идея упаковки состоит в использовании того факта, что в сообщениях часто встречаются несколько подряд идущих одинаковых байтов , а некоторые последовательности байтов повторяются многократно. При упаковке такие места можно заменить командами вида «повторить данный байт n раз» (при упаковке графической информации) или «взять часть текста длиной k байтов, которая встречалась m байтов назад» (при упаковке текстовой информации). Такой алгоритм архивации называется RLE (кодирование путем учета повторений) .

14.3. Какими возможностями обладают архиваторы

Средства архивации-разархивации, как правило, обеспечивают:

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

Каждый архиватор обычно реализует свой собственный уникальный алгоритм сжатия.

14.4. Как сжать звуковые файлы

Для уменьшения размеров мультимедийных файлов используют процедуру сжатия .

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

Компрессия без потерь используется, например, архиваторами ZIP, RAR, ARJ. Применение подобных алгоритмов для сжатия файлов, содержащих оцифрованный звук, не позволяет получить сжатие более чем в 2 раза.

Звуковой сигнал, преобразованный с помощью АЦП, обычно не повторяет сам себя и по этой причине плохо сжимается с помощью алгоритмов сжатия без потерь. Многие приемы сжатия аудиоинформации основываются на обмане органов чувств человека путем исключения избыточной и нформации, которую человек не способен воспринять (в силу своих физиологических особенностей).

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

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

Еще один способ сжатия звукового сигнала заключается в том, что исходный звуковой сигнал очищается с помощью фильтров от неслышимых компонент (например, низкие басовые шумы). Затем производится более сложный анализ сигнала: вычисляются и удаляются замаскированные частоты, заглушенные другими мощными сигналами. Таким образом можно исключить до 70% информации из сигнала, практически не изменив качество его звучания.

Есть и другие способы, так же основанные на свойствах человеческого слуха.

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

14.5. Как сжать графические файлы

Методы сжатия видеоинформации разделяются на две группы, в зависимости от скорости упаковки изображения:

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

Стандарт JPEG позволяет сократить размеры графического файла с неподвижным изображением в 10-20 раз. Этим методом удается при специальных действиях сжимать и движущиеся изображения.

Источник

Методы сжатия архиваторов

Программы сжатия данных (архиваторы): назначение и особенности использования

Архиватор– программа, осуществляющая сжатие и упаковку данных, а также их распаковку и приведение в рабочее состояние.

Архивация имеет четыре основные практические приложения:

1. Сжатие данныхпри резервном копировании и хранении информации, это экономит количество необходимых дискет или кассет для стриммера;

2. Возможность записи на жесткий диск большего объемаинформации;

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

4. Защита от вирусов: с архивным файлом вирус, как правило, соединяется некорректно и его можно легко обнаружить и устранить.

Методы сжатия архиваторов

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

1. Кодирование длин серий.

Последовательная серия одинаковых элементов данных заменяется на два символа: элемент и число его повторений.

Например, строку ААААБББВВГГГГ, человек скорее всего запоминает как 4А3Б2В4Г. На аналогичных, только более развитых принципах, основано действие специальных программ – архиваторов

2. Словарный метод.

Наиболее распространенный метод. Используется словарь, состоящий из последовательностей данных или слов. При сжатии эти слова заменяются на их коды из словаря.

Основным параметром словарного метода является размер словаря. Чем больше словарь, тем больше эффективность.

3. Энтропийный метод

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

Широко используется как дополнительный метод. В качестве самостоятельного метода применяется, например, в графическом формате JPG .

4. Метод контекстного моделирования.

В этом методе строится модель исходных данных. При сжатии очередного элемента данных эта модель выдает свое предсказание или вероятность. Согласно этой вероятности, элемент данных кодируется энтропийным методом. Чем точнее модель будет соответствовать исходным данным, тем точнее она будет выдавать предсказания, и тем короче будут кодироваться элементы данных.

5. Непрерывные блоки или непрерывный режим ( Solid mode — непрерывный режим).

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

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

Источник

Способы сжатия файлов с помощью архиваторов

Термин «архивация» не совсем точен. Главное назначение программ-архиваторов — сжатие файлов с целью экономии памяти. Поскольку со сжатыми файлами часто невозможно работать по их прямому назначению, их используют для хранения копий файлов, т.е. для их архивации . Сжатию (уплотнению) могут быть подвергнуты: файлы, папки, диски. Сжатие файлов и папок необходимо либо для их транспортировки, либо для резервного копирования, либо для обмена информацией по сети Интернет. Уплотнение дисков применяют для повышения эффективности использования их рабочего пространства (обычно для дисков недостаточной емкости).

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

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

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

Файловые архиваторы позволяют упаковывать один или несколько файлов (например, все содержимое данного подкаталога вместе с вложенными в него подкаталогами) в единый архивный файл. Размер последнего, как правило, меньше, чем суммарный размер исходных файлов, но воспользоваться запакованными программами или данными, пока они находятся в архиве, нельзя, пока они не будут распакованы. Для распаковки архивного файла обычно используется тот же самый архиватор.

Программные архиваторы действуют иначе. Они позволяют упаковать за один прием один единственный файл — исполняемую программу ЕХЕ-типа, но зато так, что заархивированная программа будет сразу после ее запуска на исполнение самораспаковываться в оперативной памяти и тут же начинать работу.

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

Для архивирования используются специальные программы — архиваторы или диспетчеры архивов. Наиболее известные архиваторы: WinZip; WinRar; WinArj. Эти программы обеспечивают возможность использования и других архиваторов, поэтому, если на компьютере, куда перенесены сжатые в них файлы, отсутствуют указанные программы, архивы можно распаковать с помощью другого архиватора. До сих пор широко используются и соответствующие программы, созданные в MS DOS, но способные работать и в Windows.

Почти все архиваторы позволяют создавать удобные самораспаковывающиеся архивы (SFX – Self-extracting-архивы) – файлы с расширением .ехе. Для распаковки такого архива не требуется программы-архиватора, достаточно запустить архив *.ехе как программу. Многие архиваторы позволяют создавать многотомные (распределенные) архивы, которые могут размещаться на нескольких дискетах.
Основными характеристиками программ-архиваторов являются:

скорость работы;

сервис (набор функций архиватора);

степень сжатия – отношение размера исходного файла к размеру упакованного файла.

Основными функциями архиваторов являются:

создание архивных файлов из отдельных (или всех) файлов текущего каталога и его подкаталогов, загружая в один архив до 32 000 файлов;

добавление файлов в архив;

извлечение и удаление файлов из архива;

просмотр содержимого архива;

просмотр содержимого архивированных файлов и поиск строк в архивированных файлах;

ввод в архив комментарии к файлам;

создание многотомных архивов;

создание самораспаковывающихся архивов, как в одном томе, так и в виде нескольких томов;

обеспечение защиты информации в в архиве и доступ к файлам, помещенным в архив, защиту каждого из помещенных в архив файлов циклическим кодом;

тестирование архива, проверка сохранности в нем информации;

восстановление файлов (частично или полностью) из поврежденных архивов;

поддержки типов архивов, созданных другими архиваторами и др.

Программа WinZip не входит в комплект поставки Windows. Для использования этого архиватора его необходимо предварительно установить на компьютер.
Создать новый архив или добавить файлы в уже существующий архив с помощью программы WinZip можно двумя способами.

I способ создания архива – с использованием контекстных меню (без предварительного запуска архиватора):

Выделить файл (файлы) или папку для архивирования.

Вызвать контекстное меню и выбрать команду Add to Zip, после чего откроется окно WinZip, а поверх него диалоговое окно Add (Добавить). Но при архивировании одного файла или папки удобнее воспользоваться командой Add to *.zip, содержащую имя архива (по умолчанию). Эта команда позволяет выполнить операцию без открытия окна программы WinZip и диалогового окна Add.

В диалоговом окне Add ввести путь и имя архива.

Щелкнуть по кнопке Add.

II способ – с предварительным запуском архиватора:

Запустить программу WinZip.

Ввести команду меню File / New Archive (Файл / Новый архив) или щелкнуть по кнопке New на панели инструментов.

В диалоговом окне New Archive в поле create in: (Поместить в:) указать диск и папку, куда должен быть помещен создаваемый архив.

В поле Имя файла: ввести имя создаваемого архива и щелкнуть OK.

В окне WinZip ввести команду ACTIONS / Add (ДЕЙСТВИЯ/ добавить) либо щелкнуть по кнопке Add на панели инструментов.

В диалоговом окне Add выделить файлы для архивирования, ввести необходимые параметры и щелкнуть по кнопке Add. Выделенные файлы будут помещены в архив, а в окне программы WinZip появится информация об архиве.

Для завершения операции следует выполнить команду FILE / Close Archive (Файл / Закрыть архив).

Разархивировать файлы (извлечь из архива) также можно двумя способами.

I способ – без предварительного запуска архиватора:

Открыть окно необходимой папки и выделить файл архива для распаковки.

Вызвать контекстное меню и выбрать команду Extract to. (Извлечь в. ). Откроется диалоговое окно Extract (Извлечь).

В поле Extract to: указать диск и папку, куда должны быть помещены распакованные файлы.

Щелкнуть по кнопке Extract.

II способ – с предварительным запуском архиватора:

Запустить WinZip.

Ввести команду File/Open Archive (Файл/ Открыть архив) либо щелкнуть по кнопке Open на панели инструментов.

Открыть папку, содержащую файл архива, и выбрать имя файла, который необходимо распаковать.

Щелкнуть по кнопке Открыть. Имена файлов, содержащихся в этом архиве, появятся в окне программы.

Выделить файлы для разархивирования.

Ввести команду ACTIONS / Extract (ДЕЙСТВИЯ / Извлечь) либо щелкнуть по кнопке Extract на панели инструментов.

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

Щелкнуть по кнопке Extract.

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

Запустить WinZip.

Ввести команду File / Open Archive (Файл / Открыть архив).

В диалоговом окне Open Archive найти и выделить нужный архивный файл.

Щелкнуть по кнопке Открыть. Имена файлов, содержащихся в этом архиве, появятся в окне программы.

Дважды щелкнуть по имени файла, который необходимо просмотреть. Файл откроется в окне программы, с которой он ассоциирован.

Щелкнуть по кнопке View.

Типы архивов

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

.jpg — для графических данных;

.mpg — для видеоданных;

.mp3 — для звуковых данных.

Характерные форматы сжатия без потери информации:

.tif, .pcx и другие — для графических файлов;

.avi — для видеоклипов;

.zip, .arj, .rar, .lzh, .cab и др. — для любых типов файлов.

Основные алгоритмы сжатия

Говоря об алгоритмах сжатия, будем иметь в виду обратимые алгоритмы.

Алгоритм RLE (Run-Length Encoding) использует принцип выявления повторяющихся последовательностей. При сжатии записывается последовательность из двух повторяющихся величин: повторяемого значения и количества его повторений.

Исходная последовательность: 3, 3, 12, 12, 12, 0, 0, 0, 0.
Сжатая информация: 3, 2, 12, 3, 0, 4.
Коэффициент сжатия: 6/9*100% = 67%.

Алгоритм KWE (Keyword Encoding) предполагает использование словаря, в котором каждому слову соответствует двухбайтовый код. Эффективность сжатия увеличивается с ростом объема кодируемого текста.

Алгоритм Хафмана предполагает кодирование не байтами, а битовыми группами. В нем можно выделить три основные этапа.

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

Чем чаще встречается символ, тем меньшим количеством битов он кодируется.

К закодированной последовательности прикладывается таблица соответствия.

Источник
Читайте также: Домашний способ для депиляций