Как работают алгоритмы сжатия

6.3. Алгоритмы сжатия данных

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

Качество сжатия характеризуется коэффициентом сжатия, равным отношению объема сжатых данных к объему исходных данных.

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

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

Для многих разновидностей данных – текстов, исполняемых файлов и т.д.

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

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

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

6.3.1. Алгоритм RLE

Самый простой из словарных методов – RLE (Run Length Encoding, кодирование переменной длины) умеет сжимать данные, в которых есть последовательности повторяющихся байтов. Упакованные RLE данные состоят из управляющих байтов, за которыми следуют байты данных. Если старший бит управляющего байта равен 0, то следующие байты (в количестве, записанном в семи младших битах управляющего байта) при упаковке не изменялись. Если старший бит равен 1, то следующий байт нужно повторить столько раз, какое число записано в остальных разрядах управляющего байта.

Например, исходная последовательность 00000000 00000000 00000000 00000000 11001100 10111111 10111011

будет закодирована в следующем виде (выделены управляющие байты): 10000100 00000000 00000011 11001100 10111111 10111011.

А, например, данные, состоящие из сорока нулевых байтов, будут закодированы всего двумя байтами: 1010 1000 00000000.

6.3.2. Алгоритм Лемпела-Зива

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

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

Другие считают словарем весь уже накопленный результат сжатия. Например, сжатый файл может состоять из записей вида [a,l,t], где a – адрес (номер позиции), с которой начинается такая же строка длины l, что и текущая строка. Если a>0, то запись считается ссылкой на словарь и поле t (текст) в ней – пустое. Если a = 0, то в поле t записаны l символов, которые до сих пор в такой последовательности не встречались.

Алгоритм сжатия заключается в постоянном поиске в уже упакованной части данных максимальной последовательности символов, совпадающей с последовательностью, начинающейся с текущей позиции. Если такая последовательность (длины > 3) найдена, в результат записывается ее адрес и длина. Иначе в результат записывается 0, длина последовательности и сама (несжатая) последовательность.

6.3.3. Кодирование Шеннона-Фано

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

Качество кодирования по Шеннону-Фано сильно зависит от выбора разбиений на подгруппы: чем больше разность сумм вероятностей подгрупп, тем более избыточным оказывается код. Для дальнейшего уменьшения избыточности, используют кодирование крупными блоками – в качестве “символов” используются комбинации исходных символов сообщения, но и этот подход имеет те же ограничения. От указанного недостатка свободна методика кодирования Хаффмана.

6.3.4. Алгоритм Хаффмана

Алгоритм Хаффмана гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов кода на символ сообщения. На первом шаге подсчитываются частоты всех символов в исходных данных. На втором шаге строятся новые коды (битовые последовательности) для каждого символа, так, чтобы никакие две разные последовательности не имели общего начала, например, три последовательности 0, 10, 110. удовлетворяют этому требованию. Хаффман предложил строить двоичное дерево символов, в корне которого находится наиболее частый символ, на расстоянии 1 от корня – следующие по частоте

Алгоритмы сжатия данных без потерь

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

История

Иерархия алгоритмов:

Хотя сжатие данных получило широкое распространение вместе с интернетом и после изобретения алгоритмов Лемпелем и Зивом (алгоритмы LZ), можно привести несколько более ранних примеров сжатия. Морзе, изобретая свой код в 1838 году, разумно назначил самым часто используемым буквам в английском языке, “e” и “t”, самые короткие последовательности (точка и тире соотв.). Вскоре после появления мейнфреймов в 1949 году был придуман алгоритм Шеннона — Фано, который назначал символам в блоке данных коды, основываясь на вероятности их появления в блоке. Вероятность появления символа в блоке была обратно пропорциональна длине кода, что позволяло сжать представление данных.
Дэвид Хаффман был студентом в классе у Роберта Фано и в качестве учебной работы выбрал поиск улучшенного метода бинарного кодирования данных. В результате ему удалось улучшить алгоритм Шеннона-Фано.
Ранние версии алгоритмов Шеннона-Фано и Хаффмана использовали заранее определённые коды. Позже для этого стали использовать коды, созданные динамически на основе данных, предназначаемых для сжатия. В 1977 году Лемпель и Зив опубликовали свой алгоритм LZ77, основанный на использования динамически создаваемого словаря (его ещё называют «скользящим окном»). В 78 году они опубликовали алгоритм LZ78, который сначала парсит данные и создаёт словарь, вместо того, чтобы создавать его динамически.

Проблемы с правами

Алгоритмы LZ77 и LZ78 получили большую популярность и вызвали волну улучшателей, из которых до наших дней дожили DEFLATE, LZMA и LZX. Большинство популярных алгоритмов основаны на LZ77, потому что производный от LZ78 алгоритм LZW был запатентован компанией Unisys в 1984 году, после чего они начали троллить всех и каждого, включая даже случаи использования изображений в формате GIF. В это время на UNIX использовали вариацию алгоритма LZW под названием LZC, и из-за проблем с правами их использование пришлось сворачивать. Предпочтение отдали алгоритму DEFLATE (gzip) и преобразованию Барроуза — Уилера, BWT (bzip2). Что было и к лучшему, так как эти алгоритмы почти всегда превосходят по сжатию LZW.
К 2003 году срок патента истёк, но поезд уже ушёл и алгоритм LZW сохранился, пожалуй, только в файлах GIF. Доминирующими являются алгоритмы на основе LZ77.
В 1993 году была ещё одна битва патентов – когда компания Stac Electronics обнаружила, что разработанный ею алгоритм LZS используется компанией Microsoft в программе для сжатия дисков, поставлявшейся с MS-DOS 6.0. Stac Electronics подала в суд и им удалось выиграть дело, в результате чего они получили более $100 миллионов.

Рост популярности Deflate

Большие корпорации использовали алгоритмы сжатия для хранения всё увеличивавшихся массивов данных, но истинное распространение алгоритмов произошло с рождением интернета в конце 80-х. Пропускная способность каналов была чрезвычайно узкой. Для сжатия данных, передаваемых по сети, были придуманы форматы ZIP, GIF и PNG.
Том Хендерсон придумал и выпустил первый коммерчески успешный архиватор ARC в 1985 году (компания System Enhancement Associates). ARC была популярной среди пользователей BBS, т.к. она одна из первых могла сжимать несколько файлов в архив, к тому же исходники её были открыты. ARC использовала модифицированный алгоритм LZW.
Фил Катц, вдохновлённый популярностью ARC, выпустил программу PKARC в формате shareware, в которой улучшил алгоритмы сжатия, переписав их на Ассемблере. Однако, был засужен Хендерсоном и был признан виновным. PKARC настолько открыто копировала ARC, что иногда даже повторялись опечатки в комментариях к исходному коду.
Но Фил Катц не растерялся, и в 1989 году сильно изменил архиватор и выпустил PKZIP. После того, как его атаковали уже в связи с патентом на алгоритм LZW, он изменил и базовый алгоритм на новый, под названием IMPLODE. Вновь формат был заменён в 1993 году с выходом PKZIP 2.0, и заменой стал DEFLATE. Среди новых возможностей была функция разбиения архива на тома. Эта версия до сих пор повсеместно используется, несмотря на почтенный возраст.
Формат изображений GIF (Graphics Interchange Format) был создан компанией CompuServe в 1987. Как известно, формат поддерживает сжатие изображения без потерь, и ограничен палитрой в 256 цветов. Несмотря на все потуги Unisys, ей не удалось остановить распространение этого формата. Он до сих пор популярен, особенно в связи с поддержкой анимации.
Слегка взволнованная патентными проблемами, компания CompuServe в 1994 году выпустила формат Portable Network Graphics (PNG). Как и ZIP, она использовала новый модный алгоритм DEFLATE. Хотя DEFLATE был запатентован Катцем, он не стал предъявлять никаких претензий.
Сейчас это самый популярный алгоритм сжатия. Кроме PNG и ZIP он используется в gzip, HTTP, SSL и других технологиях передачи данных.

К сожалению Фил Катц не дожил до триумфа DEFLATE, он умер от алкоголизма в 2000 году. Граждане – чрезмерное употребление алкоголя опасно для вашего здоровья! Вы можете не дожить до своего триумфа!

Современные архиваторы

ZIP царствовал до середины 90-х, однако в 1993 году простой русский гений Евгений Рошал придумал свой формат и алгоритм RAR. Последние его версии основаны на алгоритмах PPM и LZSS. Сейчас RAR – стандарт для распространения файлов через интернет.
В 1996 году появился вариант алгоритма BWT с открытыми исходниками bzip2, и быстро приобрёл популярность. В 1999 году появилась программа 7-zip с форматом 7z. По сжатию она соперничает с RAR, её преимуществом является открытость, а также возможность выбора между алгоритмами bzip2, LZMA, LZMA2 и PPMd.
В 2002 году появился ещё один архиватор, PAQ. Автор Мэтт Махоуни использовал улучшенную версию алгоритма PPM с использованием техники под названием «контекстное смешивание». Она позволяет использовать больше одной статистической модели, чтобы улучшить предсказание по частоте появления символов.

Будущее алгоритмов сжатия

Конечно, бог его знает, но судя по всему, алгоритм PAQ набирает популярность благодаря очень хорошей степени сжатия (хотя и работает он очень медленно). Но благодаря увеличению быстродействия компьютеров скорость работы становится менее критичной.
С другой стороны, алгоритм Лемпеля-Зива –Маркова LZMA представляет собой компромисс между скоростью и степенью сжатия и может породить много интересных ответвлений.
Ещё одна интересная технология «substring enumeration» или CSE, которая пока мало используется в программах.

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

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

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

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

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

Алгоритмы сжатия данных

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

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

В зависимости от того, в какой объект помещены данные, различаются объекты, подлежащие сжатию:

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

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

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

Примерами форматов сжатия с потерями информации могут быть:

• JPEG — для графических данных;
• MPG — для для видеоданных;
• MP3 — для аудиоданных.

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

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

• GIF, TIFF — для графических данных;
• AVI — для видеоданных;
• ZIP, ARJ, RAR, CAB, LH — для произвольных типов данных.

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

• алгоритм RLE (Run Length Encoding);
• алгоритмы группы KWE(KeyWord Encoding);
• алгоритм Хаффмана.

Алгоритм RLE

В основе алгоритма RLE лежит идея выявления повторяющихся последовательностей данных и замены их более простой структурой, в которой указывается код данных и коэффициент повторения. Например, пусть задана такая последовательность данных, что подлежит сжатию:1 1 1 1 2 2 3 4 4 4.

В алгоритме RLE предлагается заменить ее следующей структурой: 1 4 2 2 3 1 4 3, где первое число каждой пары чисел — это код данных, а второе — коэффициент повторения. Если для хранения каждого элемента данных входной последовательности отводится 1 байт, то вся последовательность будет занимать 10 байт памяти, тогда как выходная последовательность (сжатый вариант) будет занимать 8 байт памяти. Коэффициент сжатия, характеризующий степень сжатия, можно вычислить по формуле: где Vx- объем памяти, необходимый для хранения выходной (результирующей) последовательности данных, Vn- входной последовательности данных.

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

Алгоритмы группы KWE

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

Существует довольно много реализаций этого алгоритма, среди которых наиболее распространенными являются алгоритм Лемпеля-Зіва (алгоритм LZ) и его модификация алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словарем в данном алгоритме является потенциально бесконечный список фраз. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. При считывании очередного символа входной последовательности данных, он прибавляется к текущей строке. Процесс продолжается до тех пор, пока текущая строка соответствует какой-нибудь фразе из словаря. Но рано или поздно текущая строка перестает соответствовать какой-нибудь фразе словаря.

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

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

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

Алгоритм Хаффмана

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

Основная идея состоит в следующем: чем чаще встречается символ, тем меньшим количеством бит он кодируется. Результат кодирования заносится в словарь, необходимый для декодирования. Рассмотрим простой пример, иллюстрирующий работу алгоритма Хаффмана. Коэффициент сжатия равен 32%. Алгоритм Хаффмана универсальный, его можно применять для сжатия данных любых типов, но он малоэффективен для файлов маленьких размеров (за счет необходимости сохранение словаря).

На практике программные средства сжатия данных синтезируют эти три «чистых» алгоритмы, поскольку их эффективность зависит от типа и объема данных.

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

1. создание нового архива;
2. добавление файлов в существующий архив;
3. распаковывание файлов из архива;
4. создание самораспаковающихся архивов (self-extractor archive);
5. создание распределенных архивов фиксированного размера для носителей маленькой емкости;
6. защита архивов паролями от несанкционированного доступа;
7. просмотр содержимого файлов разных форматов без предварительного распаковывания;
8. поиск файлов и данных внутри архива;
9. проверка на вирусы в архиве к распаковыванию;
10. выбор и настройка коэффициента сжатия.

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

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

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

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

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

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

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

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

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

Степень сжатия является основной характеристикой алгоритма сжатия. Он определяется как отношение объема исходных несжатых данных к объему сжатых, то есть: k = So / Sc, где k — степень сжатия, So — объем исходных данных, а Sc — объем сжатых данных. Таким образом, чем выше степень сжатия, тем эффективнее алгоритм.

Следует отметить: если k = 1, то алгоритм не производит сжатие, то есть выходное сообщение по объему равно входному; если k <1, то алгоритм генерирует сообщение большего размера, чем несжатый, то есть выполняет «вредную» работу.

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

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

Коэффициент сжатия может быть как постоянным (некоторые алгоритмы сжатия звука, изображений и т. д., например, A-закон, μ-закон, ADPCM, усеченное блочное кодирование), так и переменным.

Во втором случае его можно определить либо для каждого конкретного сообщения, либо оценить по некоторым критериям:

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

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

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

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

Среди них символические данные, изменение которых неизбежно приводит к изменению их семантики:

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

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

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

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

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

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

Таким образом, возможны три варианта:

• Алгоритм сжатия требует больше вычислительных ресурсов, чем алгоритм восстановления.

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

• Алгоритмы сжатия и восстановления требуют примерно равных вычислительных ресурсов.

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

• Алгоритм сжатия значительно менее требователен, чем алгоритм восстановления.

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

Алгоритмы сжатия данных неизвестного формата

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

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

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

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

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

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

Сжатие без потерь используется, когда важна идентичность сжатых данных оригиналу. Типичным примером являются исполняемые файлы и исходный код. Некоторые форматы файлов изображений, такие как PNG, используют только сжатие без потерь; в то время как другие (TIFF, MNG) или GIF могут использовать сжатие с потерями или без них.

Заключение

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

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

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

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

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

Фотографии, записанные в формате JPEG, могут быть приняты судом.

Присылайте задания в любое время дня и ночи в ➔

Официальный сайт Брильёновой Натальи Валерьевны преподавателя кафедры информатики и электроники Екатеринбургского государственного института.

Все авторские права на размещённые материалы сохранены за правообладателями этих материалов. Любое коммерческое и/или иное использование кроме предварительного ознакомления материалов сайта natalibrilenova.ru запрещено. Публикация и распространение размещённых материалов не преследует за собой коммерческой и/или любой другой выгоды.

Сайт предназначен для облегчения образовательного путешествия студентам очникам и заочникам по вопросам обучения . Наталья Брильёнова не предлагает и не оказывает товары и услуги.

Теория сжатия данных

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

Как возникла идея

Пока не существовало компьютеров — об экономии места никто не задумывался, более того все силы были направлены на криптографию и основные исследования в области данных в основном велись в сторону их шифрования. Это продолжалось начиная еще с эпохи таких древних цивилизаций как Рим, Греция и существовало всегда, так как люди вечно что-то, да скрывали друг от друга. Многое поменялось с созданием первых ЭВМ, размеры которых были вне всякой критики, а объемы жестких дисков были меньше, чем даже ПЗУ в первых мобильных телефонах. Тут то весь прогрессивный мир и задумался на тему, как же все таки в такой маленький объем памяти поместить как можно больше полезных документов. В это время ученые и начали предлагать свои наработки, но большинство из этих теорем лишь могли доказать возможность сжатия тех или иных данных, о сжатии же и тем более расжатии без потерь особо речи не шло. Так постепенно и родился энтропийный анализ данных, позволяющий оценить компактность хранения информации и возможность ее сжатия. Постепенно идеи начали воплощать в реальность. Была предложена идея сжатия путем подсчета частоты появления тех или иных байт в тексте. Ее суть состояла в том что текст первоначально оценивается упаковщиком, считается частота появления в тексте каждой буквы, встречающейся в нем, частота повторения участков текста и так далее, составляется таблица этих самых частот и по ней уже вторым проходом происходит упаковка/распаковка. Этот метод надолго засел в умах разработчиков. Идеальной его реализацией можно считать алгоритм Хаффмана и его последующие доработки. Вкратце рассмотрим этот метод.

Метод Хаффмана

Как известно, текстовый файл состоит из фиксированного набора символов. Например, возьмём эту статью. В ней используются маленькие и большие буквы русского алфавита, знаки препинания. То есть, количество используемых символов меньше, чем 256(Ascii таблица). Но компьютер, всё равно сохранит текстовый файл в 8 битной кодировке (2^8=256). Значит, больше половины символов Ascii таблицы вообще не используются. Наша задача — сделать так, чтобы использовались как можно больше символов. К примеру, имеем Ascii таблицу, состоящую из 10 символов (0,1,2,3,4,5,6,7,8,9). У нас есть текст "00112233011223322113". Как видишь, символы 4,5,6,7,8,9 не используются. Можно ввести следующее обозначение:

Таким образом, наш текст можно записать в виде: "0123456789". То есть, как видим, текст теперь занимает в 2 раза меньше, чем был. В нём используются все допустимые символы. Чтобы получить исходный текст, необходимо согласно обозначению, заменить обратно символы на их комбинацию. Теперь, когда мы поняли смысл метода Хаффмана, пожалуй рассмотрим его детальнее.
Сначала в тексте подсчитывается количество повторяющихся символов. К примеру, символ "А" повторяется 100 раз, символ "В" повторяется 300 раз и так далее. Далее символы сортируются по убыванию или возрастания согласно их количеству появления в тексте. Потом составляется дерево Хаффмана на подобии наших символов, которые обозначали их комбинацию("00" — 0,"11" — 1 и так далее). Только дерево Хаффмана призвано максимально уменьшить количество символов в заархивированном тексте, поэтому оно составляется несколько иначе. Мы уже отсортировали символы, согласно их количеству. Теперь берём символ с наименьшей частотой появления и объединяем его с символом, стоящим на втором месте. Получаем новый символ с частотой появления равной сумме частот, входящих в него символов. Далее делаем то же самое с другими символами (объединённые символы со счетов не сбрасывай). В конце-концов у нам получится один символ с частотой появления равной размеру файла. Теперь посмотрим, что получилось. Раньше у нас каждый символ кодировался восемью битами. Теперь, чтобы получить код символа, необходимо двигаться с низу дерева к её вершине по веткам, если идёшь направо по ветке, пиши 1, если налево 0. В итоге, двигаясь по веткам, мы рано или поздно наткнёмся на один из исходных символов. То что мы записали, двигаясь по веткам и будет его код. Как видим, у символов, которые часто встречаются код занимает меньше, чем у тех, которые встречаются реже. Наша задача составить коды для всех символов. Теперь, зная коды, заменяем на них все символы в тексте. Всё! Текст заархивирован. Что самое обидное, таблицу кодов символов надо сохранить вместе с заархивированным текстом. Это увеличит размер, но не на много, если сам файл до архивации занимал много места. Вывод напрашивается сам собой: метод Хаффмана не стоит применять, если размер файл мал. Теперь обратный процесс. У нас есть дерево и заархивированный текст. Считываем первый бит, если он 0, идёшь влево, если 1 вправо с низу дерева. В итоге, считывая следующие биты, мы рано или поздно наткнемся на какой-нибудь символ. Это и будет символ исходного текста. Получили первый символ, не останавливайтесь на достигнутом, опускайтесь вниз дерева и считывайте следующий бит. В итоге, мы получим всю последовательность исходного текста.

Основные недостатки этого метода:

• приходится таскать с собой дерево Хаффмана;
• приходится сканировать текст 2 раза. Первый при подсчёте частот появления символов, второй при архивации;
• мизерная степень сжатия файлов, содержащих почти все символы Ascii-таблицы. Например, exe-шники, obj файлы и так далее.

• простота реализации;
• малые объемы занимаемой памяти при архивации.

Примерная реализация алгоритма будет иметь вид как в приложении 1.

Метод Лемпела-Зива

А это совершенно иной подход, основанный не на частости появления байт в тексте, а на повторении слов или части слов в пакуемом тексте. То есть если слово или его участок повторяется, то оно заменяется ссылкой на предыдущее слово, в итоге текстовые данные опять же удается неслабо сжать. Архиватор работает в один проход и составляет лишь словарь, основанный на повторяющихся участках текста. Эффективность сжатия здесь зависит лишь он размеров текстового файла и числа повторений. Маленькие файлы, а тем более отдельные строки сжимать данным алгоритмом сами понимаете бессмысленно, потому для сжатия каждой строчки массива логов аськи он вряд ли подойдет, а вот для 2 мегового лога одним файлом — самое то. Алгоритмы реализации можно найти также на любом языке. О данном алгоритме Вы могли кстати и не слышать, а вот об алгоритме LZW не слышать было просто нереально, так как в свое время он был сильно популярен и на его основе создавалось множество архиваторов. Как ни странно современные архиваторы в большинстве своем также применяют этот алгоритм совместно с Хаффманом для сжатия текстовых файлов. Еще данный алгоритм используется в некоторых форматах графических файлов (в частности всем известный и используемый формат GIF сжимается именно алгоритмом LZW). Теперь думаю нелишним будет сказать пару слов об аббривиатуре. Думаю даже человек не знающий о сжатии абсолютно ничего, способен понять, что LZ производное от имен главных разработчиков (Jakob Ziv и Abraham Lempel). вопрос в том, что за буква W? А все дело вот в чем. Ребята, создавшие алгоритм не спешили его патентовать и его использовать начали абсолютно все, в том числе и разработчики Unix. Один из них, Терри Велч, вел разработку упаковщика compress и соответственно по мере изменения пакера изменял и LZW движок, всячески оптимизируя его, тем самым навсегда оставшись в истории, занеся свое имя третьим в аббревиатуру алгоритма. Потом конечно алгоритм не раз модифицировался, но так как модификации носили в основном незначительный характер, авторы добавлений не стали расширять аббревиатуру. Вот такая вот история.

Раз уж мы заговорили об изображениях, думаю нелишним будет рассказать про алгоритм Run Length Encoding. Он применяется в формате изображений PCX (помните еще такой? он использовался для сохранения черно-белых изображений) и работает вот как. Исходное изображение, представляющее цепочку байт, исследуется на наличие повторяющихся цепочек данных. Если изображение черно-белое, то длинна таких цепочек может быть очень большой. Это и использует алгоритм для компрессии данных, вместо цепочки байт вставляя сначала счетчик повторений, потом собственно повторяемое значение. Так как цвета 2 и счетчик повторений занимает 6 бит, то такую цепочку вполне реально ужать в 1 байт. Классная компрессия, правда? А вот и не очень 🙁 Для полноцветной графики, а уж тем более для сжатия фотографий он не годится, потому его ниша — сжатие черно-белых чертежей.

Разработан он был группой специалистов по сжатию фотографий Joint Photographic Expert Group. До сих пор у него нет особенных конкурентов в области сжатия изображений фотографического качества. Метод основан на дискретном косинусоидальном преобразовании участков 8*8 матрицы изображения. При этом изображение раскладывается по амплитудам некоторых частот с последующим квантованием с учетом характеристик человеческого зрения, что дает малую видимую потерю качества, зато высокий уровень сжатия. Так как алгоритм стандартизован ISO он поддерживается многими языками программирования без использования сторонних компонентов или исходников, потому грех не использовать его везде где только можно.

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

Я думаю нелишним напомнить, что все описанные выше алгоритмы не способны хорошо сжать файл имеющий если не всю кодировку символов, то почти всю. К таким файлам относятся в первую очередь программы, библиотеки и драйвера. Возможно Вы помните мою статью Обзор упаковщиков приложений и прочего бинарного кода. Их там я описал очень много, причем их раз в 10 больше. Откуда же столько? Неужто столько алгоритмов было разработано программистами? Неуж-то мы настолько продвинулись, что каждый в силах написать пакер для экзешников? А вот и нет, просто есть 3 распространенных алгоритма, которые все активно используют и даже не пишут в справке к пакеру, что использовали не свой алгоритм сжатия. Но это мы отвлеклись. Давайте поговорим непосредственно об этих алгоритмах. Алгоритмы эти — aplib, jcalg и новомодный lzma. Самый простой и удобный из них — aplib, самое лучшее сжатие имеет lzma. Логичным будет поближе рассмотреть последний, как самый перспективный на сегодняшний день.

Алгоритм LZMA

Данный алгоритм был разработан в 2001 году на основе уже известного нам LZ77 (непатентованного предшественника LZW). Расшифровывается он так: Lempel-Ziv-Markov chain-Algorithm. На сегодняшний день используется в архиваторе 7zip и в куче китайских EXE упаковщиков. Основное отличие от LZ77 — переменный размер формируемого пакером словаря, размер которого в памяти может достигать 4 гигабайт, но и распаковка при этом потребует море ресурсов компьютера. Также алгоритм использует хеш цепочки и формирует деревья бинарного и Patricia типа. Patricia это никакая не Патрисия 🙂 а Practical Algorithm to Retrieve Information Coded in Alphanumeric, описанный еще в 1968 году Дональдом Моррисом и используемый для построения ассоциативных целочисленных массивов древовидного типа. В lzma для сжатия бинарных данных используется BCJ/BCJ2 алгоритм, способный разбирать 32 битные команды и анализировать call’ы и jmp’ы на код, что позволяет добиться более оптимального сжатия с учетом архитектуры x86 процессоров. Несмотря на то что алгоритм по сути дизассемблирует программу он работает довольно быстро — 1 Mb в секунду на Pentium II при сжатии и 10 мегабайт в секунду при распаковке и даже поддерживает новомодный Hyper Threading в Pentium процессорах. Если Вы решили заюзать данный алгоритм обрадую — его исходники портированы под многие ОС, а не только под винду. При этом автор даже не требует отчислений за использование алгоритма в коммерческих программах, а лишь ставит условие, что при этом модифицировать алгоритм нельзя. Это очень полезно, ведь авторы aplib за коммерческое использование просят более 20 долларов, при этом все равно не дают исходники. Потому lzma — лучший выбор.

Интернет Вам в помощь

Если Вы заинтересовались темой, то лучшим помощником будет первоисточник, потому рекомендую почитать следующие сайты:
www.compression.ru — лучший российский сайт по сжатию данных. Тут Вы найдете гору инфы и исходников практически по всем алгоритмам. Размах сайта просто поражает. Исходники разбиты даже на категории по языкам. Есть отрывки из книги "Методы сжатия данных". В общем если найдете российский сайт по сжатию мощнее этого — пришлите ссылочку.
www.7-zip.org — сайт автора архиватора 7zip. Помимо самого архиватора тут можно найти исходник алгоритма lzma и почитать по нему самую свежую информацию. Если решите его использовать, очень рекомендую глянуть в лицензию — она очень лояльна.
www.bitsum.com/jcalg1.htm — страничка посвящена алгоритму jcalg1. Дано подробное описание по использованию алгоритма, таблица сравнения. Особенно радует лицензионное соглашение: This library may be used freely in any and for any application.
www.ibsensoftware.com — сайт авторов aplib. Здесь можно скачать библиотеку или сорцы депакера. Также имеется возможность купить библиотеку для коммерческого использования.
http://en.wikipedia.org — несмотря на то что это просто энциклопедия — именно в ней очень подробно рассмотрены многие алгоритмы сжатия, рассказано про их авторов и даны архиполезные перекрестные ссылки на описание различных технологий, используемых при построении того или иного алгоритма. Короче, просто обязана быть у Вас в закладках.
Чтобы Вы не искали в энциклопедии каждый алгоритм — вот ссылка:
http://en.wikipedia.org/wiki/Category:Lossless_compression_algorithms

Сайты популярных архиваторов:

www.rarlab.com — лучший на мой взгляд архиватор. Постоянно развивается.
www.7-zip.org — лучший по сжатию архиватор. Имеются порты под линукс. Распространяется бесплатно, потому и рекламы его почти нет.
www.winace.com — неплохой, но уже почти забытый. Причина тому — нет динамики развития, присущей WinRAR, а сжатие слабее чем у 7zip
www.winzip.com — ну про zip думаю знают все. Единственный архиватор который есть у всех и даже встроен в винду. Сжатие конечно не супер, но это стандарт дефакто для распространения архивов в сети интернет.
www.powerarchiver.com — довольно мощный пакер. Сжимает в формате 7zip, при этом платный — стоит около $20
www.izarc.org — ну наконец-то, единственный путевый пакер, который можно получить абсолютно бесплатно. При всем при этом имеется поддержка таких форматов как 7-ZIP, A, ACE, ARC, ARJ, B64, BH, BIN, BZ2, BZA, C2D, CAB, CDI, CPIO, DEB, ENC, GCA, GZ, GZA, HA, IMG, ISO, JAR, LHA, LIB, LZH, MDF, MBF, MIM, NRG, PAK, PDI, PK3, RAR, RPM, TAR, TAZ, TBZ, TGZ, TZ, UUE, WAR, XXE, YZ1, Z, ZIP, ZOO. Внушает?

Приложение 1: Распаковщик aplib на сях — как все просто

Приложение 2: Одна из реализаций метода Хаффмана от VVS Soft Group.