Методы сжатия форматы сжатия. Методы сжатия данных

Теория и стратегия представления данных

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

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

Что понимается под сжатием данных? Если говорить кратко, то сжатие устраняет из данных избыточность ; в терминах же теории информации сжатие увеличивает энтропию сжатого текста. Однако оба этих утверждения по существу по существу верны в силу определения самих понятий. Избыточность может быть выражена в самых разных формах. Одним типом является последовательности повторяющихся битов (11111111). Вторым – последовательности повторяющихся байтов (XXXXXXXX). Однако чаще избыточность проявляется в более крупном масштабе и выражается либо закономерностями в наборе данных, взятом как единое целое, либо последовательностями различной длины, имеющими общие признаки. По существу, цель сжатия данных заключается в поиске алгоритмических преобразований представлений данных, которые позволят получить более компактные представления «типовых» наборов данных. Это описание может показаться несколько туманным, но мы постараемся раскрыть его суть на практических примерах.

Сжатие без потерь и с потерями

Фактически существуют два в корне различающихся подхода к сжатию данных: сжатие с потерями и без потерь. Эта статья, в основном, посвящена методам сжатия без потерь, но для начала полезно изучить различия. Сжатие без потерь предусматривает преобразование представления набора данных таким образом, чтобы затем можно было в точности воспроизвести первоначальный набор данных путем обратного преобразования (распаковки). Сжатие с потерями – это представление, которое позволяет воспроизводить нечто «очень похожее» на первоначальный набор данных. Преимущество использования методов сжатия с потерями заключается в том, что они зачастую позволяют получать намного более компактные представления данных по сравнению с методами сжатия без потерь. Чаще всего методы сжатия с потерями применяются для обработки изображений, звуковых файлов и видео. Сжатие с потерями в этих областях может оказаться уместным благодаря тому, что человек воспринимает битовую комбинацию цифрового изображения/звука не с «побитовой» точностью, а скорее оценивает музыку или изображение в целом.

С точки зрения «обычных» данных сжатие с потерями – неудачный вариант. Нам не нужна программа, которая делает «примерно» то, а не точно то, что было запрошено в действительности. То же касается и баз данных, которые должны хранить именно те данные, которые были в них загружены. По крайней мере, это не подойдет для решения большинства задач (и мне известно очень мало практических примеров использования сжатия с потерями за пределами тех данных, которые сами по себе описывают чувственное восприятие реального мира (например, изображений и звуков)).

Пример набора данных

В данной статье будет использоваться специально подготовленное гипотетическое представление данных. Приведем простой для понимания пример. В городе Гринфилд (штат Массачусетс, США) используются префиксы телефонных номеров 772- , 773- и 774- . (К сведению читателей за пределами США: в США местные телефонные номера являются семизначными и традиционно представляются в виде ###-####; префиксы назначаются в соответствии с географическим местоположением). Также предположим, что из всех трех префиксов чаще всего используется первый. Частями суффикса могут быть любые другие цифры с приблизительно равной вероятностью. Набор интересующих нас данных находится в «списке всех телефонных номеров, которые в настоящее время находятся в активном пользовании». Можно попробовать подобрать причину, почему это могло бы быть интересным с точки зрения программирования, но в данном случае это не важно.

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

Таблица 1. Многоколоночный отчет

Сжатие пустых мест

Сжатие пустых мест может быть охарактеризовано в более общем смысле как «удаление того, что нас не интересует». Даже несмотря на то, что этот метод с технической точки зрения представляет собой метод сжатия с потерями, он все равно полезен для многих типов представлений данных, с которыми мы сталкиваемся в реальном мире. Например, даже несмотря на то, что HTML намного удобнее читать в текстовом редакторе при добавлении отступов и междустрочных интервалов, ни одно из этих «пустых мест» никак не влияет на визуализацию HTML-документа в Web-браузере. Если вам точно известно, что конкретный документ HTML предназначается исключительно для Web-браузера (или для какого-либо робота/поискового агента), то, возможно, будет неплохо убрать все пустые места, чтобы документ передавался быстрее и занимал меньше места в хранилище. Все то, что мы удаляем при сжатии пустых мест, в действительности не несет никакой функциональной нагрузки.

В случае с представленным примером из описанного отчета можно удалить лишь небольшую часть информации. Строка символов «=» по верхнему краю отчета не несет никакого функционального наполнения; то же самое касается символов «-» в номерах и пробелов между номерами. Все это полезно для человека, читающего исходный отчет, но не имеет никакого значения, если мы рассматриваем эти символы в качестве «данных». То, что мы удаляем, – это не совсем «пустое место» в традиционном смысле, но является им по сути.

Сжатие пустых мест крайне «дешево» с точки зрения реализации. Вопрос состоит лишь в считывании потока данных и исключении из выходного потока нескольких конкретных значений. Во многих случаях этап «распаковки» вообще не предусматривается. Однако даже если бы мы захотели воссоздать что-то близкое к оригиналу потока данных, это потребовало бы лишь небольшого объема ресурсов ЦП или памяти. Восстановленные данные не обязательно будут совпадать с исходными данными; это зависит от того, какие правила и ограничения содержались в оригинале. Страница HTML, напечатанная человеком в текстовом редакторе, вероятно, будет содержать пробелы, расставленные согласно определенным правилам. Это же относится и к автоматизированным инструментальным средствам, которые часто создают «обоснованные» отступы и интервалы в коде HTML. В случае с жестким форматом отчета, представленным в нашем примере, не существует никаких причин, по которым первоначальное представление не могло бы быть воссоздано каким-либо «форматирующим распаковщиком».

Групповое кодирование

Групповое кодирование (RLE) является простейшим из широко используемых методов сжатия без потерь. Подобно сжатию пустых мест, оно не требует особых затрат, особенно для декодирования. Идея, стоящая за данным методом, заключается в том, что многие представления данных состоят большей частью из строк повторяющихся байтов. Наш образец отчета является одним из таких представлений данных. Он начинается со строки повторяющихся символов «=» и имеет разбросанные по отчету строки, состоящие только из пробелов. Вместо того чтобы представлять каждый символ с помощью его собственного байта, метод RLE предусматривает (иногда или всегда) указание количества повторений, за которым следует символ, который необходимо воспроизвести указанное число раз.

Если в обрабатываемом формате данных преобладают повторяющиеся байты, то может быть уместным и эффективным использование алгоритма, в котором один или несколько байтов указывают количество повторений, а затем следует повторяемый символ. Однако если имеются строки символов единичной длины, для их кодирования потребуются два (или более) байта. Другими словами, для одного символа ASCII «X» входного потока мог бы потребоваться выходной битовый поток 00000001 01011000 . С другой стороны, для кодирования ста следующих друг за другом символов «X» использовалось бы то же самое количество битов: 01100100 01011000 , что весьма эффективно.

В различных вариантах RLE часто применяется избирательное использование байтов для указания числа повторений, в то время как остальные байты просто представляют сами себя. Для этого должно быть зарезервировано как минимум одно однобайтовое значение, которое в случае необходимости может удаляться из выходных данных. Например, в нашем образце отчета по телефонным номерам известно, что вся информация во входном потоке состоит из простых символов ASCII. В частности, у всех таких символов первый бит ASCII-значения равен 0. Мы могли бы использовать этот первый бит ASCII для указания на то, что байт указывает число повторений, а не обычный символ. Следующие семь битов байта итератора могли бы использоваться для указания числа повторений, а в следующем байте мог бы содержаться повторяющийся символ. Так, например, мы могли бы представить строку «YXXXXXXXX» следующим образом:

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

Кодирование по методу Хаффмана

Кодирование по методу Хаффмана рассматривает таблицу символов как целый набор данных. Сжатие достигается путем нахождения «весовых коэффициентов» каждого символа в наборе данных. Некоторые символы используются чаще других, поэтому кодирование по методу Хаффмана предполагает, что частые символы должны кодироваться меньшим количеством бит, чем более редкие символы. Существуют различные варианты кодирования по методу Хаффмана, но исходный (и чаще всего применяемый) вариант включает поиск самого распространенного символа и кодирование его одним битом, например, 1. И если в закодированной последовательности встречается 0, это значит, что на этом месте находится другой символ, закодированный большим количеством бит.

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

Таблица 2. Результаты кодирования по методу Хаффмана

Исходный набор символов (состоящий из чисел) может быть легко закодирован (без сжатия) в виде 4-х битных последовательностей (полубайтов). Приведенное кодирование по методу Хаффмана будет использовать до 5 битов для символов в наихудшем случае, что очевидно хуже кодирования с помощью полубайтов. Однако в лучшем случае потребуется всего 1 бит; при этом известно, что именно лучший случай будет использоваться чаще всего (так как именно этот символ чаще всего встречается в данных). Таким образом, мы могли бы закодировать конкретный телефонный номер следующим образом:

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

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

Сжатие по алгоритму Лемпеля-Зива

Вероятно, самым значимым методом сжатия без потерь является алгоритм Лемпеля-Зива. В этой статье речь пойдет о варианте LZ78, но LZ77 и другие варианты работают схожим образом. Идея, заложенная в алгоритме LZ78, заключается в кодировании потоковой последовательности байтов с использованием некоторой динамической таблицы. В начале сжатия битового потока таблица LZ заполняется фактическим набором символов, наряду с несколькими пустыми слотами. В алгоритме применяются таблицы разных размеров, но в данном примере с телефонными номерами (со сжатием пустых мест) используется таблица из 32 элементов (этого достаточно для данного примера, но может оказаться мало для других типов данных). Вначале мы заполняем первые десять слотов символами используемого алфавита (цифрами). По мере поступления новых байтов сначала выводится значение из таблицы, соответствующее самой длинной подходящей последовательности, а затем в следующий доступный слот записывается последовательность длиной N+1. В наихудшем случае мы используем 5 битов вместо 4 для отдельного символа, однако в большинстве случаев мы сможем обойтись 5 битами на несколько символов. Рассмотрим пример работы этого алгоритма (слот таблицы указан в квадратных скобках):

До сих пор мы не извлекли из этого никакой пользы, но давайте перейдем к следующему телефонному номеру:

Приведенных операций должно быть достаточно для демонстрации работы модели. Хотя никакого заметного сжатия пока не достигнуто, уже видно, что мы повторно использовали слоты 11 и 16, закодировав по два символа одним выходным символом. Кроме того, мы уже накопили крайне полезную последовательность байтов 772 в слоте 18, которая впоследствии неоднократно будет встречаться в потоке.

Алгоритм LZ78 заполняет одну таблицу символов полезными (предположительно) записями, затем записывает эту таблицу, очищает ее и начинает новую. В такой ситуации таблица из 32 символов может оказаться недостаточной, так как будет очищена прежде, чем нам удастся неоднократно воспользоваться такими последовательностями, как 772 и ей подобные. Однако с помощью небольшой таблицы проще проиллюстрировать работу алгоритма.

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

Правильная постановка задачи

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

Необходимо еще раз взглянуть на проблему, которую представляют данные. Так как это не общий набор данных и для него существуют четкие предварительные требования, то проблему можно переформулировать. Известно, что существует максимум 30000 телефонных номеров (от 7720000 до 7749999), некоторые из которых являются активными, а некоторые – нет. Перед нами не стоит задача вывести полное представление всех активных номеров. Нам просто требуется указать с помощью логического значения, активен данный номер или нет. Размышляя о проблеме подобным образом, мы можем просто выделить 30000 битов в памяти и в системе хранения и использовать каждый бит для индикации активности («да» или «нет») соответствующего телефонного номера. Порядок битов в битовом массиве может соответствовать телефонным номерам, отсортированным по возрастанию (от меньшего к большему).

Подобное решение на основе битового массива идеально со всех точек зрения. Оно требует ровно 3750 байт для представления набора данных; различные методы сжатия будут использовать меняющийся объем в зависимости от количества телефонных номеров в наборе и эффективности сжатия. Однако если 10000 из 30000 возможных телефонных номеров являются активными и если даже самому эффективному методу сжатия требуется несколько байтов на один телефонный номер, то битовый массив однозначно выигрывает. С точки зрения потребностей в ресурсах ЦП битовый массив не только превосходит любой из рассмотренных методов сжатия, но и оказывается лучше, чем обычный метод представления телефонных номеров в виде строк (без сжатия). Проход по битовому массиву и увеличение счетчика текущего телефонного номера могут эффективно выполняться даже во встроенном кэше современных процессоров.

Из этого простого примера можно понять, что далеко не каждая проблема имеет такое идеальное решение, как рассмотренная выше. Многие проблемы действительно требуют использования значительного объема ресурсов памяти, пропускной способности, хранилища и ЦП; и в большинстве подобных случаев методы сжатия могут облегчить или снизить эти требования. Но более важный вывод состоит в том, что перед применением методов сжатия стоит еще раз удостовериться, что для представления данных выбрана правильная концепция.

Посвящается памяти Клода Шеннона (Claude Shannon).

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

Статическое сжатие данных (static data compression) - используется для длительного хранения и архивации; выполняется при помощи специальных сервисных программ-архиваторов, например ARJ, PKZIP/PKUNZIP. После восстановления (декомпрессии) исходная запись восстанавливается.
Динамическое сжатие (сжатие в реальном времени; dynamic compression, compression in real time) - предназначено для сокращения занимаемой области дисковой памяти данными, требующими оперативного доступа и вывода на внешние устройства ЭВМ (в том числе на экран монитора). Динамическое сжатие данных и их восстановление производится специальными программными средствами автоматически и «мгновенно».
Физическое сжатие (physical compression) - методология сжатия, при которой данные перестраиваются в более компактную форму «формально», то есть без учета характера содержащейся в них информации.
Логическое сжатие (logical compression) - методология, в соответствии с которой один набор алфавитных, цифровых или двоичных символов заменяется другим. При этом смысловое значение исходных данных сохраняется. Примером может служить замена словосочетания его аббревиатурой. Логическое сжатие производится на символьном или более высоком уровне и основано исключительно на содержании исходных данных. Логическое сжатие не применяется для изображений.
Симметричное сжатие (symmetric compression) - методология сжатия, в соответствии с которой принципы построения алгоритмов упаковки и распаковки данных близки или тесно взаимосвязаны. При использовании симметричного сжатия время, затрачиваемое на сжатие и распаковку данных, соизмеримо. В программах обмена данными обычно используется симметричное сжатие.
Асимметричное сжатие (asymmetric compression) - методология, в соответствии с которой при выполнении работ «в одном направлении» времени затрачивается больше, чем при выполнении работ в другом направлении. На сжатие изображений обычно затрачивается намного больше времени и системных ресурсов, чем на их распаковку. Эффективность этого подхода определяется тем, что сжатие изображений может производиться только один раз, а распаковываться с целью их отображения – многократно. Алгоритмы асимметричные «в обратном направлении» (на сжатие данных затрачивается меньше времени, чем на распаковку) используется при выполнении резервного копирования данных.
Адаптивное кодирование (adaptive encoding) - методология кодирования при сжатии данных, которая заранее не настраивается на определенный вид данных. Программы, использующие адаптивное кодирование, настраиваются на любой тип сжимаемых данных, добиваясь максимального сокращения их объема.
Неадаптивное кодирование (nonadaptive encoding) - методология кодирования, ориентированная на сжатие определенного типа или типов данных. Кодировщики, построенные по этому принципу, имеют в своем составе статические словари «предопределенных подстрок», о которых известно, что они часто появляются в кодируемых данных. Примером может служить метод сжатия Хаффмена.
Полуадаптивное кодирование (half-adaptive coding) - методология кодирования при сжатии данных, которая использует элементы адаптивного и неадаптивного кодирования. Принцип действия полуадаптивного кодирования заключается в том, что кодировщик выполняет две группы операций: вначале - просмотр массива кодируемых данных и построение для них словаря, а затем - собственно кодирование.
Сжатие без потерь (lossless compression) - методология сжатия, при которой ранее закодированная порция данных восстанавливается после их распаковки полностью без внесения изменений.
Сжатие с потерями (lossy compression) - методология, при которой для обеспечения максимальной степени сжатия исходного массива часть содержащихся в нем данных отбрасывается. Для текстовых, числовых и табличных данных использование программ, реализующих подобные методы сжатия, является неприемлемой. Однако для программ, работающих с графикой, это часто бывает целесообразно. Качество восстановленного изображения зависит от характера графического материала и корректности реализованного в программе алгоритма сжатия. Существует ряд алгоритмов сжатия, учитывающих допустимые уровни потерь исходного графического образа в конкретных вариантах использования его восстановленного изображения, например, путем просмотра его на экране монитора, распечатки принтером, в полиграфии. Эти методы имеют общее наименование «сжатия с минимизацией потерь».
Сжатие изображения (image compression) - технический прием или метод сокращения объема (размеров) записи графических изображений (рисунков, чертежей, схем) на их носителе (например, на магнитном диске, магнитной ленте). По существу «сжатие изображения» является разновидностью динамического сжатия. Для его реализации используются различные способы кодирования данных, которые ориентированы на элементы графики, составляющие изображение, включая и движущиеся объекты. Применяется также при передаче факсимильной информации по каналам связи, в системах мультимедиа, видеофонах.
Сжатие диска (disk compression) - технический прием, основанный на динамическом сжатии в процессе их записи на диск, а при считывании - их автоматическом восстановлении в исходную форму. Сжатие диска используется с целью увеличения емкости диска. В зависимости от характера записей емкость диска может быть увеличена примерно от 1, 5 до 5 раз. Сжатие диска осуществляется специальными прикладными программами, например DoubleSpace, Stacker, SuperStor.

Методы и средства сжатия данных:
Метод сжатия Хаффмена (Huffman compression method, кодирование CCITT) разработан в 1952 году Дэвидом Хаффменом (David Huffman). Международный консультативный комитет по телефонии и телеграфии (CCITT) разработал на его основе ряд коммуникативных протоколов для факсимильной передачи черно-белых изображений по телефонным каналам и сетям передачи данных (Стандарт T.4 CCIT и T.6 CCITT, они же - сжатие CCITT group 3 и сжатие CCITT group 4).
Фрактальное сжатие (fractal compression) - метод сжатия растровых изображений путем преобразования их в так называемые фракталы. Хранение изображений в виде фракталов требует в четыре раза меньше дисковой памяти, нежели в пикселях.
ART - метод для сжатия текста, графики, аудио и видео. Принцип работы алгоритма сжатия основан на анализе изображения и выявлении его ключевых признаков (цвет, помехи, края, повторяющиеся особенности).
AC3 Dolby - метод и формат сжатия, который позволяет сжимать, хранить и передавать в одном файле со скоростью от 32 до 640 кбит/с до 6 каналов аудиоданных.
DJVU (DjVu, djvu, deja vu) - технология и формат динамического сжатия отсканированных страниц изданий, содержащих текстовые и иллюстративные материалы.
DVI (Digital Video Interactive) - система динамического сжатия и восстановления аудио- и видеозаписей в цифровой форме. Ее использование позволяет записать на CD-ROM полноформатный видеофильм вместе со звуковым сопровождением.
EAD (Encoded Archival Description) - стандарт кодирования, разработанный подразделением Network Development and MARC Standards Office Библиотеки Конгресса США в сотрудничестве с Society of American Archivists в 1998 году (обновление - 2002 г.). Стандарт устанавливает принципы создания, разработки и поддержки схем кодирования для архивных и библиотечных помощников поиска (finding aids).
Image compression manager - программа управления динамическим сжатием изображений, которая обеспечивает возможность использования различных методов сжатия/восстановления изображений (MPEG, JPEG).
JBIG (Joint Bi-level Image Experts Group) - метод сжатия двухуровневых (двухцветных) изображений без потерь, создан Объединенной группой экспертов по двухуровневым изображениям ISO и CCIT в 1988 году. Метод JBIG в 1993 году утвержден как стандарт кодирования двухуровневых данных вместо менее эффективных алгоритмов сжатия MR (Modified READ) и MMR (Modified Modified READ).
LZW (Lempel-Ziv-Welch) - метод динамического сжатия, основанный на поиске во всем файле и сохранении в словаре одинаковых последовательностей данных (они называются фразы). Каждой уникальной последовательности данных присваиваются более короткие маркеры (ключи).
MP3 (Moving Pictures Experts Group, Layer 3) - метод (алгоритм) динамического сжатия и специальный формат записи файлов аудиоданных. MP3 обеспечивает высокую степень сжатия звуковых записей, используется в приложениях мультимедиа, в частности, в цифровых проигрывателях (плейерах) и Интернете.
RLE (Run Length Encoding) - метод динамического сжатия графических данных, в первую очередь изображений, основанный на уменьшении физического размера повторяющихся строк символов.

Методы сжатия информации

Все методы сжатия информации можно разделить на два больших непересекающихся класса: сжатие с потерей информации и сжатие без потери информации.

Сжатие с потерей информации означает, что после распаковки архива будет получен документ, несколько отличающийся от исходного. Чем больше сжатие, тем соответственно больше потери. Такие методы применяются, когда можно пожертвовать несколькими процентами информации, для фотографий, видеоданных и музыки. При потери нескольких процентов информации достигается сжатие в несколько десятков раз, 10 - 15 для музыки и
20 - 30 для фото и видеоматериалов.

К алгоритмам данного класса относятся алгоритмы JPEG и MPEG. Алгоритм JPEG используется для сжатия фотоизображений (графики). Графические файлы, сжатые этим алгоритмом, имеют расширение JPG. Алгоритм MPEG используется для сжатия видео и музыки. Сжатые файлы имеют расширение MPG для видео и MP3 для музыки.

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

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

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

Алгоритмы ХАФМАНА основаны на перекодировки информации. При кодировке данных по таблице ASCII для кодирования любого символа используется одинаковое число бит – 8. Но есть символы, которые встречаются часто, например А или О, и которые встречаются редко. Программы для сжатия информации имеют свою таблицу перекодировки символов, меньшим числом бит, и приписывают её сжатому файлу.

Алгоритмы или методы RLE (Run Length Encoding) основаны на выявлении повторяющихся последовательностей. В текстовых документах повторяющиеся последовательности встречаются редко, но в таблицах достаточно часто, например повторение одной и той же цифры. В этом случае вместо последовательности ставят коэффициент и эту цифру.

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

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

Программы – архиваторы позволяют (стандартный набор функций):

Создавать архивный файл, то есть помещать в один файл группу файлов;

Распаковывать архив, то есть разместить в указанной папке все файлы архива;

Извлекать из архива выбранные файлы в указанный каталог;

Просматривать оглавление архива;

Добавлять новые файлы;

Обновлять файлы в архиве;

Удалять файлы из архива;

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

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

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

Обычный архивный файл имеет оглавление , в котором для каждого файла содержится следующая информация:

Имя файла, возможно имена папок;

Дата и время последней модификации файла;

Размер файла на диске в архиве, степень сжатия;

Код циклического контроля, который используется для проверки целостности архива;

Состав информации зависит от программы - архиватора.

Для архивирования данных в Windows широко известны программы WinZip и WinRar.

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

Команда ДОБАВИТЬ (ADD) позволяет, как создать новый архив, так и добавить в архив.

Метод обновления:

- Добавить и заменить (Add and Replace Files) – все выбранные файлы включаются в архив, если файл существует, то он заменяется новым;

Сжатие данных

Михаил Сваричевский

Все алгоритмы сжатия делятся на два типа: с потерями и без.

Сжатие с потерями позволяет достичь гораздо бóльшей степени сжатия (до 1/30 и менее от исходного объема).
Например, видеофильм, занимающий в неупакованном виде гигабайт 30, удается записать на 1 CD.
Однако, алгоритмы сжатия с потерями приводят к некоторым изменениям самих данных; поэтому применять такие алгоритмы можно только к тем данным, для которых небольшие искажения несущественны: видео, фото-изображения (алгоритмы JPEG), звук (алгоритм MP3).

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

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

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

Словарь содержит некоторое количество слов (обычно 2x; например, 4096).
Сжатие достигается за счет того, что номер слова в словаре обычно гораздо короче самого слова.
Алгоритмы словарного сжатия делятся на две группы:
1) использующие словарь в явной форме(алгоритмы LZ78, LZW, LZC, LZT, LZMV, LZJ, LZFG)
Например, по словарю
1. "Большинство"
2. "сжатия"
3. "без"
4. "потерь"
5. "алгоритмов"
текст "Большинство алгоритмов сжатия без потерь" сжимается в "15234".

2) указывающие вместо номера слова - позицию относительно текущей позиции и длину повторяющегося участка (алгоритмы LZ77, LZR, LZSS, LZB, LZH)
Например, текст "абаббабаббабвгббабв"
сжимается в "05абабб5504абвг65", где:
"05абабб" – позиция 0 означает, что далее 5 символов идут без сжатия.
"55" – 5 букв с позиции, отстоящей от текущей на 5 символов назад.
"04абвг" – еще 4 символа не сжимается.
"65" –5 букв с позиции, отстоящей от текущей на 6 символов назад.

Модификации LZ-алгоритмов отличаются только способами представления словаря, поиска и добавления слов. Одни сжимают быстрее, но хуже; другие требуют больше памяти.

Рассмотрим подробнее модифицированный алгоритм LZ77.
Архив будет состоять из записей следующего вида:
(n,m) – означает, что с позиции n начинается такая же строка длиной m, что и с текущей позиции.
(0,m,"m символов") – означает, что далее следует m символов, которые не удалось сжать.

Алгоритм сжатия будет заключаться в следующем: ищем в файле место, начиная с которого идет самая длинная последовательность, совпадающая с последовательностью, начинающейся на текущем байте. Если ее длина больше 3, то в архив записываем начало и длину последовательности; иначе - записываем 0, длину последовательности и сами несжатые символы. Распаковка еще проще: пока файл архива не кончился, читаем по 2 числа(n,m). Если n=0, то m символов из архива сразу помещаем в буфер (эти символы нам еще понадобятся) и записываем в выходной файл. Если n<>0 то из буфера с позиции n копируем m элементов в буфер и выходной файл.

Однако есть две проблемы:
1) Ограниченный размер буфера: если нам нужно будет сжать файл размеров в 100МБ, мы его в буфер никак не поместим. Поэтому, когда он будет заполнен (скажем, на 75%), придется сдвинуть данные в нем к началу (напр., на 25%;конечно, самые старые символы при этом потеряются). Это ухудшит сжатие, но сделает алгоритм нетребовательным к памяти.
2) Скорость работы программы сжатия очень мала. В самом деле, если нужно будет сжать файл размеров 10КБ, то это потребует от нас проведения как минимум около 10000*10000/2 операций (10000 раз нам нужно будет искать совпадающую подпоследовательность, а каждый такой поиск займет в среднем 10000/2 операций). Для того, чтобы ускорить операцию поиска, можно хранить в отдельном массиве номера позиций последовательностей, начинающихся на символ chr(0), chr(2) … chr(255). Тогда при поиске нам нужно будет проверить только те комбинации, первая буква которых совпадает с первой буквой искомой последовательности.

Статистические методы

Принцип работы арифметического кодирования:

Например, мы присвоили символу "a" промежуток , "b" – и "c" – . Тогда, если у нас будет число 0.4, то мы можем сказать, что закодирована буква "b"(0.3<=0.4<=0.6), а если 0.9 – то c(0.6<=0.9<=1). Итак, у нас получилось закодировать 1 букву в число. Как же закодировать 2 буквы? Очень просто: например, если первая буква – "b", то интервал равен . Разделим этот интервал на части, в отношении наших первоначальных отрезков. Тогда 2-м буквам "ba" будет соответствовать интервал , "bb" – и "bc" – . Для раскодирования нам достаточно знать любое число из этого интервала.

Попробуем раскодировать: пусть дано число 0.15. Это число попадает в интервал буквы "a", значит первая закодированная буква – "a". Для того, чтобы узнать вторую букву, нужно преобразовать число, чтобы оно указывало букву в интервале не , а . Для этого от числа отнимем нижнюю границу исходного интервала (0) и разделим на ширину интервала (0.3-0=0.3). Получим новое число(0.15-0)/0.3 = 0.5. Повторив те же действия, мы узнаем, что вторая буква – "b". Если бы было закодировано 3 и более букв, то, многократно повторяя этот процесс, мы нашли бы все буквы.

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

Алгоритм сжатия:
Для каждого символа мы должны присвоить соответствующий промежуток в соответствии с частотой (вероятностью встречи) в данных: пусть символ "а"имеет вероятность 0.4, "b" – 0,3 и "c" – тоже 0.3; тогда символу "а" будет соответствовать промежуток , "b" – , "c" – . Т.е мы делим имеющийся у нас промежуток между всеми необходимыми буквами в соответствии с вероятностью их встречи (более вероятному символу соответствует больший промежуток).

В процессе сжатия у нас есть 2 границы: верхняя и нижняя, назовем их соответственно hiи lo. Пусть нам нужно закодировать символ, которому мы отвели промежуток . Тогда в наш промежуток "вставляется" промежуток символа, и lo будет равен нижней границе вставляемого промежутка, hi – верхней. В итоге по мере кодирования промежуток между loи hi становится все уже и уже. Наконец, когда мы закодировали все данные, выбираем любое число из получившегося промежутка и выводим. Оно и будет сжатыми данными.

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

Проблемы:
Если бы все было так просто… На самом деле, для хранения числа-архива нужна будет очень большая точность (десятки и сотни тысяч знаков), поэтому на практике приходится пользоваться обычными типами данных. Чтобы этого добиться, будем смотреть на старшие биты/цифры числа-архива. Как только у hi и lo они совпадут, мы можем сразу записать их в архив и "отсечь". При распаковке наоборот, когда увидим, что мы довольно много раз расширяли промежуток до , считаем из файла-архива несколько цифр и допишем их в конец нашего числа-архива.
Часто используется модификация арифметического кодирования - range coder. Основное отличие - начальный интервал - . Это позволяет выводить данные сразу по байту, а не наскребать по биту, что отражается на скорости работы. В конце статьи приведена реализация именно этого варианта.

Определение вероятностей символов

Предположения, которые мы делаем относительно сжимаемых данных (например, зависимость вероятности от предыдущих символов) называются вероятностной моделью. Модель, вероятности в которой не зависят от предыдущих символов, называется моделью 0-го порядка. Если вероятности зависят от 1 предыдущего символа, то это модель 1-го порядка, если от 2-х последних – то 2-го и т.д. Для эффективного вычисления вероятностей символов в моделях высокого порядка существуют специальная группа алгоритмов – PPM и его модификации.
Модели могут быть неадаптивными, полуадаптивными и адаптивными. В неадаптивных методах вероятности всех символов жестко зашиты в программу. В полуадаптивных по входным данным делается 2 прохода: 1-й - для определения вероятностей, 2-й – собственно для сжатия. Адаптивный – вероятности символов изменяются в процессе сжатия. Адаптивные модели самые медленные, но они обычно сжимают данные сильнее неадаптивных и полуадаптивных моделей. В общем, среди всех моделей лучше сжимают использующие наибольшее кол-во информации о сжимаемых данных - зависимость от предыдущих символов, некоторые факты, например: в текстах после точки обычно следует большая буква и т.д.

Алгоритмы, используемые в популярных архиваторах:

Пример программы адаптивного сжатия/распаковки 0-го порядка: