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

Обновлено: 18.05.2024

Сжатие данных (англ. data compression ) — алгоритмическое преобразование данных, производимое с целью уменьшения их объёма. Применяется для более рационального использования устройств хранения и передачи данных. Синонимы — упаковка данных, компрессия, сжимающее кодирование, кодирование источника. Обратная процедура называется восстановлением данных (распаковкой, декомпрессией).

Содержание

Принципы сжатия данных

Все методы сжатия данных делятся на два основных класса:

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

Характеристики алгоритмов сжатия и их применимость

Коэффициент сжатия

$k=\frac<S_o></p> <p>Коэффициент сжатия — основная характеристика алгоритма сжатия. Она определяется как отношение объёма исходных несжатых данных к объёму сжатых, то есть:$
, где k — коэффициент сжатия, S_o — объём исходных данных, а S_c — объём сжатых. Таким образом, чем выше коэффициент сжатия, тем алгоритм эффективнее. Следует отметить:

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

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

Допустимость потерь

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

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

Системные требования алгоритмов

Различные алгоритмы могут требовать различного количества ресурсов вычислительной системы, на которых они реализованы:

оперативной памяти (под промежуточные данные);
постоянной памяти (под код программы и константы);
процессорного времени.

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

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

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

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

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

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

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

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

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

Для архивирования используются специальные программы - архиваторы или диспетчеры архивов. Наиболее известные архиваторы: 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) предполагает использование словаря, в котором каждому слову соответствует двухбайтовый код. Эффективность сжатия увеличивается с ростом объема кодируемого текста.

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

В статье рассматриваются основные методы сжатия данных, приводится классификация наиболее известных алгоритмов, и на простых примерах обсуждаются механизмы работы методов CS&Q, RLE-кодирования, Хаффмана, LZW, дельта-кодирования, JPEG и MPEG. Статья представляет собой авторизованный перевод [1].

Передача данных и их хранение стоят определенных денег. Чем с большим количеством информации приходится иметь дело, тем дороже обходится ее хранение и передача. Зачастую данные хранятся в наиболее простом виде, например в коде ASCII (American Standard Code for Information Interchange — американский стандартный код для обмена информацией) текстового редактора, в исполняемом на компьютере двоичном коде, в отдельных файлах, полученных от систем сбора данных и т.д. Как правило, при использовании этих простых методов кодирования объем файлов данных примерно в два раза превышает действительно необходимый размер для представления информации. Ее сжатие с помощью алгоритмов и программ позволяет решить эту задачу. Программа сжатия используется для преобразования данных из простого формата в оптимизированный по компактности. Наоборот, программа распаковки возвращает данные в исходный вид. Мы обсудим шесть методов сжатия данных в этом разделе. Первые три из них являются простыми методами кодирования: кодирование длин серий с передачей информации об их начале и длительности; кодирование Хаффмана и дельта-кодирование. Последние три метода являются сложными процедурами сжатия данных, которые стали промышленными стандартами: LZW, форматы JPEG и MPEG.

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

Без потерь

С потерями

Передаваемые по интернету изображения служат наглядным примером того, почему необходимо сжатие данных. Предположим, что требуется загрузить из интернета цифровую цветную фотографию с помощью 33,6-Кбит/с модема. Если изображение не сжато (например, это файл TIFF-формата), его объем составит около 600 Кбайт. При сжатии фото без потерь (в файл GIF-формата) его размер уменьшится примерно до 300 Кбайт. Метод сжатия с потерями (JPEG-формат) позволит уменьшить размер файла до 50 Кбайт. Время загрузки этих трех файлов составляет 142, 72 и 12 с, соответственно. Это большая разница. JPEG идеально подходит для работы с цифровыми фотографиями, тогда как GIF используется только для рисованных изображений.

Второй способ классификации методов сжатия данных проиллюстрирован в таблице 2. Большинство программ сжатия работает с группами данных, которые берутся из исходного файла, сжимаются и записываются в выходной файл. Например, одним из таких методов является CS&Q (Coarser Sampling and Quantization — неточные выборка и дискретизация). Предположим, что сжимается цифровой сигнал, например звуковой сигнал, который оцифрован с разрядностью 12 бит. Можно прочесть две смежные выборки из исходного файла (24 бит), отбросить одну выборку полностью, отбросить наименее значащие 4 бита из другой выборки, затем записать оставшиеся 8 битов в выходной файл. При 24 входных битах и 8 выходных коэффициент сжатия алгоритма с потерями равен 3:1. Этот метод высокоэффективен при использовании сжатия с преобразованием, составляющего основу алгоритма JPEG.

Метод

Размер группы

входной

выходной

В методе CS&Q из входящего файла читается фиксированное число битов, и меньшее фиксированное число записывается в выходной файл. Другие методы сжатия позволяют создавать переменное число битов для чтения или записи. Причина того, почему в таблицу не вошли форматы JPEG и MPEG, в том, что это составные алгоритмы, в которых совмещено множество других методов.

Файлы данных содержат одни и те же символы, повторяющиеся множество раз в одном ряду. Например, в текстовых файлах используются пробелы для разделения предложений, отступы, таблицы и т.д. Цифровые сигналы также содержат одинаковые величины, указывающие на то, что сигнал не претерпевает изменений. Например, изображение ночного неба может содержать длинные серии символов, представляющих темный фон, а цифровая музыка может иметь длинную серию нулей между песнями. RLE-кодирование (Run-length encoding — кодирование по длинам серий) представляет собой метод сжатия таких типов файлов.
На рисунке 1 проиллюстрирован принцип этого кодирования для последовательности данных с частым повторением серии нулей. Всякий раз, когда нуль встречается во входных данных, в выходной файл записываются два значения: нуль, указывающий на начало кодирования, и число нулей в серии. Если среднее значение длины серии больше двух, происходит сжатие. С другой стороны, множество одиночных нулей в данных может привести к тому, что кодированный файл окажется больше исходного.

Этот метод был разработан Хаффманом в 1950-х гг. Метод основан на использовании относительной частоты встречаемости индивидуальных элементов. Часто встречающиеся элементы кодируются более короткой последовательностью битов. На рисунке 2 представлена гистограмма байтовых величин большого файла ASCII. Более 96% этого файла состоит из 31 символа: букв в нижнем регистре, пробела, запятой, точки и символа возврата каретки.

Алгоритм, назначающий каждому из этих стандартных символов пятибитный двоичный код по схеме 00000 = a, 00001 = b, 00010 = c и т.д., позволяет 96% этого файла уменьшить на 5/8 объема. Последняя комбинация 11111 будет указывать на то, что передаваемый символ не входит в группу из 31 стандартного символа. Следующие восемь битов в этом файле указывают, что представляет собой символ в соотоветствии со стандартом присвоения ASCII. Итак, 4% символов во входном файле требуют для представления 5 + 8 = 13 бит.

Принцип этого алгоритма заключается в присвоении часто употребляемым символам меньшего числа битов, а редко встречающимся символам — большего количества битов. В данном примере среднее число битов, требуемых из расчета на исходный символ, равно 0,96 . 5 + 0,04 . 13 = 5,32. Другими словами, суммарный коэффициент сжатия составляет 8 бит/5,32 бит, или 1,5 : 1.

На рисунке 3 представлена упрощенная схема кодирования Хаффмана. В таблице кодирования указана вероятность употребления символов с A по G, имеющихся в исходной последовательности данных, и их соответствия. Коды переменной длины сортируются в стандартные восьмибитовые группы. При распаковке данных все группы выстраиваются в последовательность нулей и единиц, что позволяет разделять поток данных без помощи маркеров. Обрабатывая поток данных, программа распаковки формирует достоверный код, а затем переходит к следующему символу. Такой способ формирования кода обеспечивает однозначное чтение данных.

Буква

Вероятность

Код Хаффмана

Дельта-кодирование используется для сжатия данных, если значения исходного файла изменяются плавно, т.е. разность между следующими друг за другом величинами невелика. Это условие не выполняется для текста ASCII и исполняемого кода, но является общим случаем, когда информация поступает в виде сигнала. Например, на рисунке 5а показан фрагмент аудиосигнала, оцифрованного с разрядностью 8 бит, причем все выборки принимают значения в диапазоне –127–127. На рисунке 5б представлен кодированный вариант этого сигнала, основное отличие которого от исходного сигнала заключается в меньшей амплитуде. Другими словами, дельта-кодирование увеличивает вероятность того, что каждое значение выборки находится вблизи нуля, а вероятность того, что оно значительно больше этой величины, невелика. С неравномерным распределением вероятности работает метод Хаффмана. Если исходный сигнал не меняется или меняется линейно, в результате дельта-кодирования появятся серии выборок с одинаковыми значениями, с которыми работает RLE-алгоритм. Таким образом, в стандартном методе сжатия файлов используется дельта-кодирование с последующим применением метода Хаффмана или RLE-кодирования.

Механизм дельта-кодирования можно расширить до более полного метода под названием кодирование с линейным предсказанием (Linear Predictive Coding, LPC).
Чтобы понять суть этого метода, представим, что уже были закодированы первые 99 выборок из входного сигнала и необходимо произвести выборку под номером 100. Мы задаемся вопросом о том, каково наиболее вероятное ее значение? В дельта-кодировании ответом на данный вопрос является предположение, что это значение предыдущей, 99-й выборки. Это ожидаемое значение используется как опорная величина при кодировании выборки 100. Таким образом, разность между значением выборки и ожиданием помещается в кодируемый файл. Метод LPC устанавливает наиболее вероятную величину на основе нескольких последних выборок. В используемых при этом алгоритмах применяется z-преобразование и другие математические методы.

LZW-сжатие — наиболее универсальный метод сжатия данных, получивший распространение благодаря своей простоте и гибкости. Этот алгоритм назван по имени его создателей (Lempel-Ziv-Welch encoding — сжатие данных методом Лемпела-Зива-Велча). Исходный метод сжатия Lempel-Ziv был впервые заявлен в 1977 г., а усовершенствованный Велчем вариант — в 1984 г. Метод позволяет сжимать текст, исполняемый код и схожие файлы данных примерно вполовину. LZW также хорошо работает с избыточными данными, например табличными числами, компьютерным исходным текстом и принятыми сигналами. В этих случаях типичными значениями коэффициента сжатия являются 5:1. LZW-сжатие всегда используется для обработки файлов изображения в формате GIF и предлагается в качестве опции для форматов TIFF и PostScript.
Алгоритм LZW использует кодовую таблицу, пример которой представлен на рисунке 6. Как правило, в таблице указываются 4096 элементов. При этом кодированные LZW-данные полностью состоят из 12-битных кодов, каждый из которых соответствует одному табличному элементу. Распаковка выполняется путем извлечения каждого кода из сжатого файла и его преобразования с помощью таблицы. Табличные коды 0—255 всегда назначаются единичным байтам входного файла (стандартному набору символов). Например, если используются только эти первые 256 кодов, каждый байт исходного файла преобразуется в 12 бит сжатого LZW-файла, который на 50% больше исходного. При распаковке этот 12-битный код преобразуется с помощью кодовой таблицы в единичные байты.

Пример кодовой таблицы

Метод LZW сжимает данные с помощью кодов 256—4095, представляя последовательности байтов. Например, код 523 может представлять последовательность из трех байтов: 231 124 234. Всякий раз, когда алгоритм сжатия обнаруживает последовательность во входном файле, в кодируемый файл ставится код 523. При распаковке код 523 преобразуется с помощью таблицы в исходную последовательность из трех байтов. Чем длиннее последовательность, назначаемая единичному коду и чем чаще она повторяется, тем больше коэффициент сжатия.
Существуют два основных препятствия при использовании этого метода сжатия: 1) как определить, какие последовательности должны указываться в кодовой таблице и 2) как обеспечить программу распаковки той же таблицей, которую использует программа сжатия. Алгоритм LZW позволяет решить эти задачи.

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

Из множества алгоритмов сжатия с потерями кодирование с преобразованием оказалось наиболее востребованным. Наилучший пример такого метода — популярный стандарт JPEG (Joint Photographers Experts Group — Объединенная группа экспертов по машинной обработке фотографических изображений). Рассмотрим на примере JPEG работу алгоритма сжатия с потерями.

Мы уже обсудили простейший метод сжатия с потерями CS&Q, в котором уменьшается количество битов на выборку или полностью отбрасываются некоторые выборки. Оба этих приема позволяют достичь желаемого результата — файл становится меньше за счет ухудшения качества сигнала. Понятно, что эти простые методы работают не самым лучшим образом.

Сжатие с преобразованием основано на простом условии: в трансформированном сигнале (например, с помощью преобразования Фурье) полученные значения данных не несут прежней информационной нагрузки. В частности, низкочастотные компоненты сигнала начинают играть более важную роль, чем высокочастотные компоненты. Удаление 50% битов из высокочастотных компонентов может привести, например, к удалению лишь 5% закодированной информации.

Из рисунка 7 видно, что JPEG-сжатие начинается путем разбиения изображения на группы размером 8×8 пикселов. Полный алгоритм JPEG работате с широким рядом битов на пиксел, включая информацию о цвете. В этом примере каждый пиксел является единичным байтом, градацией серого в диапазоне 0—255. Эти группы 8×8 пикселов обрабатываются при сжатии независимо друг от друга. Это значит, что каждая группа сначала представляется 64 байтами. Вслед за преобразованием и удалением данных каждая группа представляется, например, 2—20 байтами. При распаковке сжатого файла требуется такое же количество байтов для аппроксимации исходной группы 8×8. Эти аппроксимированные группы затем объединяются, воссоздавая несжатое изображение. Почему используются группы размерами 8×8, а не 16×16? Такое группирование было основано исходя из максимального возможного размера, с которым работали микросхемы на момент разработки стандарта.

Рис. 7. Пример применения метода сжатия JPEG. Три группы 8?8, показанные в увеличенном виде, представляют значения отдельных пикселов

Для реализации методов сжатия было исследовано множество различных преобразований. Например, преобразование Karhunen-Loeve обеспечивает наиболее высокий коэффициент сжатия, но оно трудно осуществляется. Метод преобразования Фурье реализуется гораздо проще, но он не обеспечивает достаточно хорошего сжатия. В конце концов, выбор был сделан в пользу разновидности метода Фурье — дискретного косинусного преобразования (Discrete Cosine Transform — DCT).

На примере работы алгоритма JPEG видно, как несколько схем сжатия объединяются, обеспечивая большую эффективность. Вся процедура сжатия JPEG состоит из следующих этапов:
– изображение разбивается на группы 8×8;
– каждая группа преобразуется с помощью преобразования DCT;
– каждый спектральный элемент 8×8 сжимается путем сокращения числа битов и удаления некоторых компонентов с помощью таблицы квантования;
– видоизмененный спектр преобразуется из массива 8×8 в линейную последовательность, все высокочастотные компоненты которой помещаются в ее конец;
– серии нулей сжимаются с помощью метода RLE;
– последовательность кодируется либо методом Хаффмана, либо арифметическим методом для получения сжатого файла.

MPEG (Moving Pictures Experts Group — Экспертная группа по кинематографии) — стандарт сжатия цифровых видеоданных. Этот алгоритм обеспечивает также сжатие звуковой дорожки к видеофильму. MPEG представляет собой еще более сложный, чем JPEG, стандарт с огромным потенциалом. Можно сказать, это ключевая технология XXI века.
У MPEG имеется несколько очень важных особенностей. Так например, он позволяет воспроизводить видеофильм в прямом и обратном направлениях, в режиме нормальной и повышенной скорости. К кодированной информации имеется прямой доступ, т.е. каждый отдельный кадр последовательности отображается как неподвижное изображение. Таким образом, фильм редактируется — можно кодировать его короткие фрагменты, не используя всю последовательность в качестве опорной. MPEG также устойчив к ошибкам, что позволяет избегать цифровых ошибок, приводящих к нежелательному прерыванию воспроизведения.

Используемый в этом стандарте метод можно классифицировать по двум типам сжатия: внутрикадровое и межкадровое. При сжатии по первому типу отдельные кадры, составляющие видеопоследовательность, кодируются так, как если бы они были неподвижными изображениями. Такое сжатие выполняется с помощью JPEG-стандарта с несколькими вариациями. В терминологии MPEG кадр, закодированный таким образом, называется внутрикодированным, или I-picture.

Наибольшая часть пикселов в видеопоследовательности изменяется незначительно от кадра к кадру. Если камера не движется, наибольшая часть изображения состоит из фона, который не меняется на протяжении некоторого количества кадров. MPEG использует это обстоятельство, сжимая избыточную информацию между кадрами с помощью дельта-кодирования. После сжатия одного из кадров в виде I-picture последующие кадры кодируются как изображения с предсказанием, или P-pictures, т.е. кодируются только изменившиеся пикселы, т.к. кадры I-picture включены в P-picture.

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

Архивирование и разархивирование файлов

Проблема сжатия файла

При передаче данных по сети могут возникнуть проблемы из-за их большого объема. Пропускная способность каналов может быть ограничена. Поэтому время передачи может оказаться слишком большим.

Также для хранения и переноса файлов при помощи внешних носителей может не хватать свободного места.

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

Определение: Программы, осуществляющие сжатие данных, называются архиваторами.

Первые архиваторы появились в середине 1980-х годов. Главной целью их использования была экономия места на дисках, информационный объем которых в те времена был значительно меньше объема современных дисков.

Архивация проводится в следующих случаях:

1. Когда необходимо создать резервные копии наиболее ценных файлов.

2. Когда необходимо освободить место на диске.

3. Когда необходимо передать файлы по E-mail.

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

Первая идея. Алгоритм сжатия с использованием кода переменной длины

Вторая идея. Алгоритм сжатия с использованием коэффициента повторения

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

Программы архиваторы

Программы-архиваторы создают архивные файлы (архивы). Архив представляет собой файл, в котором в сжатом виде хранятся один или несколько файлов. Для использования заархивированных файлов необходимо произвести их излечение из архива – разархивирование.

Все программы-архиваторы обычно предоставляют следующие возможности :

добавление файлов в архив.
извлечение файлов из архива.
удаление файлов из архива.
просмотр содержимого архива.

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

Приведем пример выгоды использования архиваторов при передаче данных по сети. Допустим, размер текстового документа – 31 Кб. Если этот документ заархивировать с помощью WinRAR , то размер архивного файла составит всего 6 Кб.

Пользоваться программами-архиваторами очень просто.

Чтобы создать архив , нужно:

Похожим образом происходит обратное действие – извлечение файлов из архива (распаковка архива).

Архиватор WinRAR

WinRAR – это 32 разрядная версия архиватора RAR для Windows. Это мощное средство создания архивов и управления ими. Есть несколько версий RAR, для разных операционных систем: Windows, Linux, UNIX, DOS, OS/2 и т.д.

Существует две версии RAR для Windows :

версия с графическим пользовательским интерфейсом – WinRAR.EXE
Консольная версия RAR.EXE пульт линии команды (способ текста) версия – Rar.exe

Позволяет распаковывать архивы CAB, ARJ, LZH, TAR, GZ, ACE, UUE, BZ2, JAR, ISO, и обеспечивает архивирование данных в форматы ZIP и RAR.
Обеспечивает полную поддержку архивов ZIP и RAR.
Имеет специальные алгоритмы, оптимизированные для текста и графики. Для мультимедиа сжатие можно использовать только с форматами RAR.
Поддерживает технологию перетаскивания (drag & drop).
Имеет интерфейс командной строки.
Может осуществлять непрерывное архивирование, что обеспечивает более высокую степень сжатия по сравнению с обычными методами сжатия, особенно при упаковке большого количества небольших файлов однотипного содержания.
Обеспечивает поддержку многотомных архивов, то есть осуществляет разбивку архива на несколько томов (например, для записи большого архива на диски). Расширение томов: RAR, R01, R02 и т.д. При самораспаковывающемся архиве первый том имеет расширение EXE.
Создает самораспаковывающиеся архивы (SFX) обычные и многотомные архивы, обеспечивает защиту их паролями.
Обеспечивает восстановление физически поврежденных архивов.
Имеет средства восстановления, позволяющие восстанавливать отсутствующие части многотомного архива.
Поддерживает UNICODE в именах файлов.
Для новичков предназначен режим Мастер (Wizard), с помощью которого можно легко осуществить все операции над архивами.

WinRAR имеет и другие дополнительные функции. WinRAR способен создать архив в двух различных форматах: RAR иZIP. Рассмотрим преимущества каждого формата.

Архив в формате ZIP

Архив в формате RAR

Формат RAR в большинстве случаев обеспечивает значительно лучшее сжатие, чем ZIP. Кроме того, формат RAR обеспечивает поддержку многотомных архивов, имеет средства восстановления поврежденных файлов, архивирует файлы практически неограниченных размеров. Необходимо отметить, что при работе в файловой системе FAT32 архивы могу достигать только 4 гигабайт. Работа с большими размерами архива поддерживается только в файловой системе NTFS.

Программа архивации Microsoft Backup (резервная копия)

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

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

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

Программа архивации предоставляет следующие возможности:

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

Backup восстанавливает архивированные файлы и папки на жесткий диск.

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

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

Читайте также: