1 в чем суть процесса сжатия информации. Понятие сжатия данных

АРХИВАТОРЫ

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

Архивный файл – это специально созданный файл, содержащий в себе один или несколько файлов в сжатом виде.

Степень сжатия : K c =V c /V o *100%

K c – коэффициент сжатия, V c – объем сжатого файла, V o – исходный объем файла.

Степень сжатия зависит от:

1) используемой пограммы – архиватора,

2) метода сжатия,

3) типа исходного файла: текстового, графического, видео, звукового и т.д.

Программы, осуществляющие упаковку и распаковку файлов называются архиваторами. Наиболее распространенными являются: ARJ, ZIP, RAR. Расширение архивных файлов совпадает с названием использованного для их создания архиватора.

Архиваторы позволяют создавать самораспаковывающиеся архивные файлы, т.е. для их распаковки не требуется запуска программы-архиватора, т.к. они сами содержат программу распаковки. Эти архивы называются SFX-архивы
(SelF-eXtracting). Расширение таких файлов *.EXE.


Принципы сжатия информации

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

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

3. В следующим принципе используется закономерность что в тексте буквы встречаются с разной частотой. Например в этом тексте пробел самый распространенный символ, очень часто встречаются символы «а», «и». Эти часто встречающиеся символы можно представлять короткой комбинацией битов, остальные символы возможно кодировать более длинной последовательностью. Например:

4. Физически ПК выделяет место для размещения файлов на диске по кластерам - блоками по 4 кБ. Меньше выделить невозможно. Например если файл имеет размер 8193 байта (8 кБ и 1 байт), физически он будет занимать 16 кБ или 16384 байта. Объединение группы файлов в один позволяет сэкономить на этих остатков. При упаковки маленьких файлов это дает большую экономию.

Итого, при отдельном размещении файлов не используются 6 кБ, что составляет 100% от содержания файлов. Во втором случае неиспользуемыми остается 2 кБ, 33%.


Архиватор zip

Запаковка файлов pkzip [ключи] <имя архива> [пути файлов]

Ключи: -rp архивация с подкаталогами с сохранением структуры

SPWD защита архива паролем (PWD)

A добавить файлы в архив

M переместить файлы в архив

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

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

Распаковка файлов pkunzip [ключи] <имя архива> [имена файлов]

Ключи: -d распаковка с подкаталогами с сохранением структуры

SPWD пароль архива (PWD)


Архиватор arj

arj <команда> [ключи] <имя архива> [имена файлов]

Для архиватора arj один файл выполняет операции и распаковки и запаковки.

Команды: a архивация

e распаковка без сохранения структуры каталогов

x распаковка с сохранением структуры

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

m переместить файлы в архив

d удалить файлы из архива

Ключи: -r упаковка с подкаталогами с сохранением структуры

V разбивка архива на тома с объемом vol(если указан)

размер для стандартных дискет (360, 720, 1200, 1440) указывается в килобайтах, размер нестандартных дискет указывается в байтах

V указывается при распаковке многотомного архива

GPWD пароль архива (PWD )

Запаковка файлов

Распаковка файлов

©2015-2019 сайт
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-08-08

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

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

Стоит ли сжимать данные?

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

Однако при этом нужно правильно понимать, что с течением времени увеличивается также и объем тех данных, которые необходимо передавать. И если буквально десять лет назад стандартным для обычного фильма было принято считать объем 700 Мб, то на сегодняшний день фильмы, выполненные в HD-качестве, могут иметь объемы, равные нескольким десяткам гигабайт, не говоря уже о том, сколько свободного места занимают высококачественные картины в формате Blu-ray.

Когда сжатие данных необходимо?

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

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

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

Как можно сжать данные?

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

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

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

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

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

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

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

Универсальные методы

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

  • Преобразование потока. В данном случае описание новой поступающей несжатой информации осуществляется через уже обработанные файлы, при этом не осуществляется вычисление каких-либо вероятностей, а производится кодирование символов на основе исключительно тех файлов, которые уже подвергались определенной обработке.
  • Статистическое сжатие. Данный процесс сжатия информации с целью уменьшения занимаемого ей на диске места распределяется на две подкатегории - адаптивные и блочные методы. Адаптивный вариант предусматривает вычисление вероятностей для новых файлов по информации, которая уже обрабатывалась в процессе кодирования. В частности, к таким методам следует также отнести различные адаптивные варианты алгоритмов Шеннона-Фано и Хаффмана. Блочный алгоритм предусматривает отдельное высчитывание каждого блока информации с последующим добавлением к самому сжатому блоку.
  • Преобразование блока. Входящая информация распределяется на несколько блоков, а впоследствии происходит целостное трансформирование. При этом следует сказать о том, что определенные методы, особенно те, которые основываются на перестановке нескольких блоков, в конечном итоге могут привести к значительному снижению объема сжимаемой информации. Однако нужно правильно понимать, что после проведения такой обработки в конечном итоге происходит значительное улучшение вследствие чего проведение последующего сжатия через другие алгоритмы осуществляется гораздо более просто и быстро.

Сжатие при копировании

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

Зачем это нужно?

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

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

Выбирая утилиту, обязательно посмотрите на то, насколько выбранная вами программа может сжимать данные. Это зависит от типа информации, вследствие чего эффективность сжатия текстовых документов может составлять более 90%, в то время как будет эффективным не более чем на 5%.

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

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

Сжатие. Нужно ли оно в наше время?

Разумеется, да. Конечно, все мы понимаем, что сейчас нам доступны и носители информации большого объема, и высокоскоростные каналы передачи данных. Однако, одновременно с этим растут и объемы передаваемой информации. Если несколько лет назад мы смотрели 700-мегабайтные фильмы, умещающиеся на одну болванку, то сегодня фильмы в HD-качестве могут занимать десятки гигабайт.
Конечно, пользы от сжатия всего и вся не так много. Но все же существуют ситуации, в которых сжатие крайне полезно, если не необходимо.

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

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

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

Итак, перейдем к рассмотрению алгоритмов сжатия без потерь.

Универсальные методы сжатия без потерь

В общем случае можно выделить три базовых варианта, на которых строятся алгоритмы сжатия.
Первая группа методов – преобразование потока. Это предполагает описание новых поступающих несжатых данных через уже обработанные. При этом не вычисляется никаких вероятностей, кодирование символов осуществляется только на основе тех данных, которые уже были обработаны, как например в LZ – методах (названных по имени Абрахама Лемпеля и Якоба Зива). В этом случае, второе и дальнейшие вхождения некой подстроки, уже известной кодировщику, заменяются ссылками на ее первое вхождение.

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

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

Общие принципы, на которых основано сжатие данных

Все методы сжатия данных основаны на простом логическом принципе. Если представить, что наиболее часто встречающиеся элементы закодированы более короткими кодами, а реже встречающиеся – более длинными, то для хранения всех данных потребуется меньше места, чем если бы все элементы представлялись кодами одинаковой длины.
Точная взаимосвязь между частотами появления элементов, и оптимальными длинами кодов описана в так называемой теореме Шеннона о источнике шифрования(Shannon"s source coding theorem), которая определяет предел максимального сжатия без потерь и энтропию Шеннона.

Немного математики
Если вероятность появления элемента s i равна p(s i), то наиболее выгодно будет представить этот элемент - log 2 p(s i) битами. Если при кодировании удается добиться того, что длина всех элементов будет приведена к log 2 p(s i) битам, то и длина всей кодируемой последовательности будет минимальной для всех возможных методов кодирования. При этом, если распределение вероятностей всех элементов F = {p(s i)} неизменно, и вероятности элементов взаимно независимы, то средняя длина кодов может быть рассчитана как

Это значение называют энтропией распределения вероятностей F, или энтропией источника в заданный момент времени.
Однако обычно вероятность появления элемента не может быть независимой, напротив, она находится в зависимости от каких-то факторов. В этом случае, для каждого нового кодируемого элемента s i распределение вероятностей F примет некоторое значение F k , то есть для каждого элемента F= F k и H= H k .

Иными словами, можно сказать, что источник находится в состоянии k, которому соответствует некий набор вероятностей p k (s i) для всех элементов s i .

Поэтому, учитывая эту поправку, можно выразить среднюю длину кодов как

Где P k - вероятность нахождения источника в состоянии k.

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

Кодирование без памяти

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

Пусть задан некоторый алфавит , состоящий из некоторого (конечного) числа букв. Назовем каждую конечную последовательность символов из этого алфавита (A=a 1 , a 2 ,… ,a n) словом , а число n - длиной этого слова.

Пусть задан также другой алфавит. Аналогично, обозначим слово в этом алфавите как B.

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

Пусть также задано отображение F, которое ставит в соответствие каждому слову A из первого алфавита некоторое слово B=F(A) из второго. Тогда слово B будет называться кодом слова A, а переход от исходного слова к его коду будет называться кодированием .

Поскольку слово может состоять и из одной буквы, то мы можем выявить соответствие букв первого алфавита и соответствующих им слов из второго:
a 1 <-> B 1
a 2 <-> B 2
…
a n <-> B n

Это соответствие называют схемой , и обозначают ∑.
В этом случае слова B 1 , B 2 ,…, B n называют элементарными кодами , а вид кодирования с их помощью - алфавитным кодированием . Конечно, большинство из нас сталкивались с таким видом кодирования, пусть даже и не зная всего того, что я описал выше.

Итак, мы определились с понятиями алфавит, слово, код, и кодирование . Теперь введем понятие префикс .

Пусть слово B имеет вид B=B"B"". Тогда B" называют началом, или префиксом слова B, а B"" - его концом. Это довольно простое определение, но нужно отметить, что для любого слова B, и некое пустое слово ʌ («пробел»), и само слово B, могут считаться и началами и концами.

Итак, мы подошли вплотную к пониманию определения кодов без памяти. Последнее определение, которое нам осталось понять - это префиксное множество. Схема ∑ обладает свойством префикса, если для любых 1≤i, j≤r, i≠j, слово B i не является префиксом слова B j .
Проще говоря, префиксное множество – это такое конечное множество, в котором ни один элемент не является префиксом (или началом) любого другого элемента. Простым примером такого множества является, например, обычный алфавит.

Итак, мы разобрались с основными определениями. Так как же происходит само кодирование без памяти?
Оно происходит в три этапа.

  1. Составляется алфавит Ψ символов исходного сообщения, причем символы алфавита сортируются по убыванию их вероятности появления в сообщении.
  2. Каждому символу a i из алфавита Ψ ставится в соответствие некое слово B i из префиксного множества Ω.
  3. Осуществляется кодирование каждого символа, с последующим объединением кодов в один поток данных, который будет являться результатам сжатия.

Одним из канонических алгоритмов, которые иллюстрируют данный метод, является алгоритм Хаффмана.

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

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

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

  1. Все буквы входного алфавита упорядочиваются в порядке убывания вероятностей. Все слова из алфавита выходного потока (то есть то, чем мы будем кодировать) изначально считаются пустыми (напомню, что алфавит выходного потока состоит только из символов {0,1}).
  2. Два символа a j-1 и a j входного потока, имеющие наименьшие вероятности появления, объединяются в один «псевдосимвол» с вероятностью p равной сумме вероятностей входящих в него символов. Затем мы дописываем 0 в начало слова B j-1 , и 1 в начало слова B j , которые будут впоследствии являться кодами символов a j-1 и a j соответственно.
  3. Удаляем эти символы из алфавита исходного сообщения, но добавляем в этот алфавит сформированный псевдосимвол (естественно, он должен быть вставлен в алфавит на нужное место, с учетом его вероятности).
Шаги 2 и 3 повторяются до тех пор, пока в алфавите не останется только 1 псевдосимвол, содержащий все изначальные символы алфавита. При этом, поскольку на каждом шаге и для каждого символа происходит изменение соответствующего ему слова B i (путем добавление единицы или нуля), то после завершения этой процедуры каждому изначальному символу алфавита a i будет соответствовать некий код B i .

Для лучшей иллюстрации, рассмотрим небольшой пример.
Пусть у нас есть алфавит, состоящий из всего четырех символов - { a 1 , a 2 , a 3 , a 4 }. Предположим также, что вероятности появления этих символов равны соответственно p 1 =0.5; p 2 =0.24; p 3 =0.15; p 4 =0.11 (сумма всех вероятностей, очевидно, равна единице).

Итак, построим схему для данного алфавита.

  1. Объединяем два символа с наименьшими вероятностями (0.11 и 0.15) в псевдосимвол p".
  2. Объединяем два символа с наименьшей вероятностью (0.24 и 0.26) в псевдосимвол p"".
  3. Удаляем объединенные символы, и вставляем получившийся псевдосимвол в алфавит.
  4. Наконец, объединяем оставшиеся два символа, и получаем вершину дерева.

Если сделать иллюстрацию этого процесса, получится примерно следующее:


Как вы видите, при каждом объединении мы присваиваем объединяемым символам коды 0 и 1.
Таким образом, когда дерево построено, мы можем легко получить код для каждого символа. В нашем случае коды будут выглядить так:

A 1 = 0
a 2 = 11
a 3 = 100
a 4 = 101

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

Пусть на входу у нас была строка из 1000 символов, в которой символ a 1 встречался 500 раз, a 2 - 240, a 3 - 150, и a 4 - 110 раз.

Изначально данная строка занимала 8000 бит. После кодирования мы получим строку длинной в ∑p i l i = 500 * 1 + 240 * 2 + 150 * 3 + 110 * 3 = 1760 бит. Итак, нам удалось сжать данные в 4,54 раза, потратив в среднем 1,76 бита на кодирование каждого символа потока.

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

Заключение

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

Литература

  • Ватолин Д., Ратушняк А., Смирнов М. Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео; ISBN 5-86404-170-X; 2003 г.
  • Д. Сэломон. Сжатие данных, изображения и звука; ISBN 5-94836-027-Х; 2004г.

GORKOFF 24 февраля 2015 в 11:41

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

  • Алгоритмы

Мы с моим научным руководителем готовим небольшую монографию по обработке изображений. Решил представить на суд хабрасообщества главу, посвящённую алгоритмам сжатия изображений. Так как в рамках одного поста целую главу уместить тяжело, решил разбить её на три поста:
1. Методы сжатия данных;
2. Сжатие изображений без потерь;
3. Сжатие изображений с потерями.
Ниже вы можете ознакомиться с первым постом серии.

На текущий момент существует большое количество алгоритмов сжатия без потерь, которые условно можно разделить на две большие группы:
1. Поточные и словарные алгоритмы. К этой группе относятся алгоритмы семейств RLE (run-length encoding), LZ* и др. Особенностью всех алгоритмов этой группы является то, что при кодировании используется не информация о частотах символов в сообщении, а информация о последовательностях, встречавшихся ранее.
2. Алгоритмы статистического (энтропийного) сжатия. Эта группа алгоритмов сжимает информацию, используя неравномерность частот, с которыми различные символы встречаются в сообщении. К алгоритмам этой группы относятся алгоритмы арифметического и префиксного кодирования (с использованием деревьев Шеннона-Фанно, Хаффмана, секущих).
В отдельную группу можно выделить алгоритмы преобразования информации. Алгоритмы этой группы не производят непосредственного сжатия информации, но их применение значительно упрощает дальнейшее сжатие с использованием поточных, словарных и энтропийных алгоритмов.

Поточные и словарные алгоритмы

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

Кодирование длин серий (RLE - Run-Length Encoding) - это один из самых простых и распространённых алгоритмов сжатия данных. В этом алгоритме последовательность повторяющихся символов заменяется символом и количеством его повторов.
Например, строку «ААААА», требующую для хранения 5 байт (при условии, что на хранение одного символа отводится байт), можно заменить на «5А», состоящую из двух байт. Очевидно, что этот алгоритм тем эффективнее, чем длиннее серия повторов.

Основным недостатком этого алгоритма является его крайне низкая эффективность на последовательностях неповторяющихся символов. Например, если рассмотреть последовательность «АБАБАБ» (6 байт), то после применения алгоритма RLE она превратится в «1А1Б1А1Б1А1Б» (12 байт). Для решения проблемы неповторяющихся символов существуют различные методы.

Самым простым методом является следующая модификация: байт, кодирующий количество повторов, должен хранить информацию не только о количестве повторов, но и об их наличии. Если первый бит равен 1, то следующие 7 бит указывают количество повторов соответствующего символа, а если первый бит равен 0, то следующие 7 бит показывают количество символов, которые надо взять без повтора. Если закодировать «АБАБАБ» с использованием данной модификации, то получим «-6АБАБАБ» (7 байт). Очевидно, что предложенная методика позволяет значительно повысить эффективность RLE алгоритма на неповторяющихся последовательностях символов. Реализация предложенного подхода приведена в Листинг 1:

  1. type
  2. function RLEEncode(InMsg: ShortString) : TRLEEncodedString;
  3. MatchFl: boolean ;
  4. MatchCount: shortint ;
  5. EncodedString: TRLEEncodedString;
  6. N, i: byte ;
  7. begin
  8. N : = 0 ;
  9. SetLength(EncodedString, 2 * length(InMsg) ) ;
  10. while length(InMsg) >= 1 do
  11. begin
  12. MatchFl : = (length(InMsg) > 1 ) and (InMsg[ 1 ] = InMsg[ 2 ] ) ;
  13. MatchCount : = 1 ;
  14. while (MatchCount <= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
  15. MatchCount : = MatchCount + 1 ;
  16. if MatchFl then
  17. begin
  18. N : = N + 2 ;
  19. EncodedString[ N - 2 ] : = MatchCount + 128 ;
  20. EncodedString[ N - 1 ] : = ord (InMsg[ 1 ] ) ;
  21. else
  22. begin
  23. if MatchCount <> length(InMsg) then
  24. MatchCount : = MatchCount - 1 ;
  25. N : = N + 1 + MatchCount;
  26. EncodedString[ N - 1 - MatchCount] : = - MatchCount + 128 ;
  27. for i : = 1 to MatchCount do
  28. EncodedString[ N - 1 - MatchCount + i] : = ord (InMsg[ i] ) ;
  29. end ;
  30. delete(InMsg, 1 , MatchCount) ;
  31. end ;
  32. SetLength(EncodedString, N) ;
  33. RLEEncode : = EncodedString;
  34. end ;

Декодирование сжатого сообщения выполняется очень просто и сводится к однократному проходу по сжатому сообщению см. Листинг 2:
  1. type
  2. TRLEEncodedString = array of byte ;
  3. function RLEDecode(InMsg: TRLEEncodedString) : ShortString;
  4. RepeatCount: shortint ;
  5. i, j: word ;
  6. OutMsg: ShortString;
  7. begin
  8. OutMsg : = "" ;
  9. i : = 0 ;
  10. while i < length(InMsg) do
  11. begin
  12. RepeatCount : = InMsg[ i] - 128 ;
  13. i : = i + 1 ;
  14. if RepeatCount < 0 then
  15. begin
  16. RepeatCount : = abs (RepeatCount) ;
  17. for j : = i to i + RepeatCount - 1 do
  18. OutMsg : = OutMsg + chr (InMsg[ j] ) ;
  19. i : = i + RepeatCount;
  20. else
  21. begin
  22. for j : = 1 to RepeatCount do
  23. OutMsg : = OutMsg + chr (InMsg[ i] ) ;
  24. i : = i + 1 ;
  25. end ;
  26. end ;
  27. RLEDecode : = OutMsg;
  28. end ;

Вторым методом повышения эффективности алгоритма RLE является использование алгоритмов преобразования информации, которые непосредственно не сжимают данные, но приводят их к виду, более удобному для сжатия. В качестве примера такого алгоритма мы рассмотрим BWT-перестановку, названную по фамилиям изобретателей Burrows-Wheeler transform. Эта перестановка не изменяет сами символы, а изменяет только их порядок в строке, при этом повторяющиеся подстроки после применения перестановки собираются в плотные группы, которые гораздо лучше сжимаются с помощью алгоритма RLE. Прямое BWT преобразование сводится к последовательности следующих шагов:
1. Добавление к исходной строке специального символа конца строки, который нигде более не встречается;
2. Получение всех циклических перестановок исходной строки;
3. Сортировка полученных строк в лексикографическом порядке;
4. Возвращение последнего столбца полученной матрицы.
Реализация данного алгоритма приведена в Листинг 3.
  1. const
  2. EOMsg = "|" ;
  3. function BWTEncode(InMsg: ShortString) : ShortString;
  4. OutMsg: ShortString;
  5. LastChar: ANSIChar;
  6. N, i: word ;
  7. begin
  8. InMsg : = InMsg + EOMsg;
  9. N : = length(InMsg) ;
  10. ShiftTable[ 1 ] : = InMsg;
  11. for i : = 2 to N do
  12. begin
  13. LastChar : = InMsg[ N] ;
  14. InMsg : = LastChar + copy(InMsg, 1 , N - 1 ) ;
  15. ShiftTable[ i] : = InMsg;
  16. end ;
  17. Sort(ShiftTable) ;
  18. OutMsg : = "" ;
  19. for i : = 1 to N do
  20. OutMsg : = OutMsg + ShiftTable[ i] [ N] ;
  21. BWTEncode : = OutMsg;
  22. end ;

Проще всего пояснить это преобразование на конкретном примере. Возьмём строку «АНАНАС» и договоримся, что символом конца строки будет символ «|». Все циклические перестановки этой строки и результат их лексикографической сортировки приведены в Табл. 1.

Т.е. результатом прямого преобразования будет строка «|ННАААС». Легко заметить, что это строка гораздо лучше, чем исходная, сжимается алгоритмом RLE, т.к. в ней существуют длинные подпоследовательности повторяющихся букв.
Подобного эффекта можно добиться и с помощью других преобразований, но преимущество BWT-преобразования в том, что оно обратимо, правда, обратное преобразование сложнее прямого. Для того, чтобы восстановить исходную строку, необходимо выполнить следующие действия:
Создать пустую матрицу размером n*n, где n-количество символов в закодированном сообщении;
Заполнить самый правый пустой столбец закодированным сообщением;
Отсортировать строки таблицы в лексикографическом порядке;
Повторять шаги 2-3, пока есть пустые столбцы;
Вернуть ту строку, которая заканчивается символом конца строки.

Реализация обратного преобразования на первый взгляд не представляет сложности, и один из вариантов реализации приведён в Листинг 4.

  1. const
  2. EOMsg = "|" ;
  3. function BWTDecode(InMsg: ShortString) : ShortString;
  4. OutMsg: ShortString;
  5. ShiftTable: array of ShortString;
  6. N, i, j: word ;
  7. begin
  8. OutMsg : = "" ;
  9. N : = length(InMsg) ;
  10. SetLength(ShiftTable, N + 1 ) ;
  11. for i : = 0 to N do
  12. ShiftTable[ i] : = "" ;
  13. for i : = 1 to N do
  14. begin
  15. for j : = 1 to N do
  16. ShiftTable[ j] : = InMsg[ j] + ShiftTable[ j] ;
  17. Sort(ShiftTable) ;
  18. end ;
  19. for i : = 1 to N do
  20. if ShiftTable[ i] [ N] = EOMsg then
  21. OutMsg : = ShiftTable[ i] ;
  22. delete(OutMsg, N, 1 ) ;
  23. BWTDecode : = OutMsg;
  24. end ;

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

После сортировки таблицы, полученной на седьмом шаге, необходимо выбрать из таблицы строку, заканчивающуюся символом «|». Легко заметить, что это строка единственная. Т.о. мы на конкретном примере рассмотрели преобразование BWT.

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

Словарное сжатие (алгоритмы LZ)

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

Ниже описан простейший вариант словарного алгоритма:
Инициализировать словарь всеми символами, встречающимися во входной строке;
Найти в словаре самую длинную последовательность (S), совпадающую с началом кодируемого сообщения;
Выдать код найденной последовательности и удалить её из начала кодируемого сообщения;
Если не достигнут конец сообщения, считать очередной символ и добавить Sc в словарь, перейти к шагу 2. Иначе, выход.

Например, только что инициализированный словарь для фразы «КУКУШКАКУКУШОНКУКУПИЛАКАПЮШОН» приведён в Табл. 3:

В процессе сжатия словарь будет дополняться встречающимися в сообщении последовательностями. Процесс пополнения словаря приведён в Табл. 4.

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

Для начала определим словарь как запись, хранящую не только встречавшиеся подстроки, но и количество хранящихся в словаре подстрок:

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

  1. const
  2. MAX_DICT_LENGTH = 256 ;
  3. function FindInDict(D: TDictionary; str: ShortString) : integer ;
  4. r: integer ;
  5. i: integer ;
  6. fl: boolean ;
  7. begin
  8. r : = - 1 ;
  9. if D. WordCount > 0 then
  10. begin
  11. i : = D. WordCount ;
  12. fl : = false ;
  13. while (not fl) and (i >= 0 ) do
  14. begin
  15. i : = i - 1 ;
  16. fl : = D. Words [ i] = str;
  17. end ;
  18. end ;
  19. if fl then
  20. r : = i;
  21. FindInDict : = r;
  22. end ;
  23. procedure AddToDict(var D: TDictionary; str: ShortString) ;
  24. begin
  25. if D. WordCount < MAX_DICT_LENGTH then
  26. begin
  27. D. WordCount : = D. WordCount + 1 ;
  28. SetLength(D. Words , D. WordCount ) ;
  29. D. Words [ D. WordCount - 1 ] : = str;
  30. end ;
  31. end ;

Используя эти функции, процесс кодирования по описанному алгоритму можно реализовать следующим образом:
  1. function LZWEncode(InMsg: ShortString) : TEncodedString;
  2. OutMsg: TEncodedString;
  3. tmpstr: ShortString;
  4. D: TDictionary;
  5. i, N: byte ;
  6. begin
  7. SetLength(OutMsg, length(InMsg) ) ;
  8. N : = 0 ;
  9. InitDict(D) ;
  10. while length(InMsg) > 0 do
  11. begin
  12. tmpstr : = InMsg[ 1 ] ;
  13. while (FindInDict(D, tmpstr) >= 0 ) and (length(InMsg) > length(tmpstr) ) do
  14. tmpstr : = tmpstr + InMsg[ length(tmpstr) + 1 ] ;
  15. if FindInDict(D, tmpstr) < 0 then
  16. delete(tmpstr, length(tmpstr) , 1 ) ;
  17. OutMsg[ N] : = FindInDict(D, tmpstr) ;
  18. N : = N + 1 ;
  19. delete(InMsg, 1 , length(tmpstr) ) ;
  20. if length(InMsg) > 0 then
  21. AddToDict(D, tmpstr + InMsg[ 1 ] ) ;
  22. end ;
  23. SetLength(OutMsg, N) ;
  24. LZWEncode : = OutMsg;
  25. end ;

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

Единственная проблема возможна в следующей ситуации: когда необходимо декодировать подпоследовательность, которой ещё нет в словаре. Легко убедиться, что это возможно только в случае, когда необходимо извлечь подстроку, которая должна быть добавлена на текущем шаге. А это значит, что подстрока удовлетворяет шаблону cSc, т.е. начинается и заканчивается одним и тем же символом. При этом cS – это подстрока, добавленная на предыдущем шаге. Рассмотренная ситуация – единственная, когда необходимо декодировать ещё не добавленную строку. Учитывая вышесказанное, можно предложить следующий вариант декодирования сжатой строки:

  1. function LZWDecode(InMsg: TEncodedString) : ShortString;
  2. D: TDictionary;
  3. OutMsg, tmpstr: ShortString;
  4. i: byte ;
  5. begin
  6. OutMsg : = "" ;
  7. tmpstr : = "" ;
  8. InitDict(D) ;
  9. for i : = 0 to length(InMsg) - 1 do
  10. begin
  11. if InMsg[ i] >= D. WordCount then
  12. tmpstr : = D. Words [ InMsg[ i - 1 ] ] + D. Words [ InMsg[ i - 1 ] ] [ 1 ]
  13. else
  14. tmpstr : = D. Words [ InMsg[ i] ] ;
  15. OutMsg : = OutMsg + tmpstr;
  16. if i > 0 then
  17. AddToDict(D, D. Words [ InMsg[ i - 1 ] ] + tmpstr[ 1 ] ) ;
  18. end ;
  19. LZWDecode : = OutMsg;
  20. end ;

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

Энтропийное кодирование

Кодирование с помощью деревьев Шеннона-Фано

Алгоритм Шеннона-Фано - один из первых разработанных алгоритмов сжатия. В основе алгоритма лежит идея представления более частых символов с помощью более коротких кодов. При этом коды, полученные с помощью алгоритма Шеннона-Фано, обладают свойством префиксности: т.е. ни один код не является началом никакого другого кода. Свойство префиксности гарантирует, что кодирование будет взаимно-однозначным. Алгоритм построения кодов Шеннона-Фано представлен ниже:
1. Разбить алфавит на две части, суммарные вероятности символов в которых максимально близки друг к другу.
2. В префиксный код первой части символов добавить 0, в префиксный код второй части символов добавить 1.
3. Для каждой части (в которой не менее двух символов) рекурсивно выполнить шаги 1-3.
Несмотря на сравнительную простоту, алгоритм Шеннона-Фано не лишён недостатков, самым существенным из которых является неоптимальность кодирования. Хоть разбиение на каждом шаге и является оптимальным, алгоритм не гарантирует оптимального результата в целом. Рассмотрим, например, следующую строку: «ААААБВГДЕЖ». Соответствующее дерево Шеннона-Фано и коды, полученные на его основе, представлены на Рис. 1:

Без использования кодирования сообщение будет занимать 40 бит (при условии, что каждый символ кодируется 4 битами), а с использованием алгоритма Шеннона-Фано 4*2+2+4+4+3+3+3=27 бит. Объём сообщения уменьшился на 32.5%, но ниже будет показано, что этот результат можно значительно улучшить.

Кодирование с помощью деревьев Хаффмана

Алгоритм кодирования Хаффмана, разработанный через несколько лет после алгоритма Шеннона-Фано, тоже обладает свойством префиксности, а, кроме того, доказанной минимальной избыточностью, именно этим обусловлено его крайне широкое распространение. Для получения кодов Хаффмана используют следующий алгоритм:
1. Все символы алфавита представляются в виде свободных узлов, при этом вес узла пропорционален частоте символа в сообщении;
2. Из множества свободных узлов выбираются два узла с минимальным весом и создаётся новый (родительский) узел с весом, равным сумме весов выбранных узлов;
3. Выбранные узлы удаляются из списка свободных, а созданный на их основе родительский узел добавляется в этот список;
4. Шаги 2-3 повторяются до тех пор, пока в списке свободных больше одного узла;
5. На основе построенного дерева каждому символу алфавита присваивается префиксный код;
6. Сообщение кодируется полученными кодами.

Рассмотрим тот же пример, что и в случае с алгоритмом Шеннона-Фано. Дерево Хаффмана и коды, полученные для сообщения «ААААБВГДЕЖ», представлены на Рис. 2:

Легко подсчитать, что объём закодированного сообщения составит 26 бит, что меньше, чем в алгоритме Шеннона-Фано. Отдельно стоит отметить, что ввиду популярности алгоритма Хаффмана на данный момент существует множество вариантов кодирования Хаффмана, в том числе и адаптивное кодирование, которое не требует передачи частот символов.
Среди недостатков алгоритма Хаффмана значительную часть составляют проблемы, связанные со сложностью реализации. Использование для хранения частот символов вещественных переменных сопряжено с потерей точности, поэтому на практике часто используют целочисленные переменные, но, т.к. вес родительских узлов постоянно растёт, рано или поздно возникает переполнение. Т.о., несмотря на простоту алгоритма, его корректная реализация до сих пор может вызывать некоторые затруднения, особенно для больших алфавитов.

Кодирование с помощью деревьев секущих функций

Кодирование с помощью секущих функций – разработанный авторами алгоритм, позволяющий получать префиксные коды. В основе алгоритма лежит идея построения дерева, каждый узел которого содержит секущую функцию. Чтобы подробнее описать алгоритм, необходимо ввести несколько определений.
Слово – упорядоченная последовательность из m бит (число m называют разрядностью слова).
Литерал секущей – пара вида разряд-значение разряда. Например, литерал (4,1) означает, что 4 бит слова должен быть равен 1. Если условие литерала выполняется, то литерал считается истинным, в противном случае - ложным.
k-разрядной секущей называют множество из k литералов. Если все литералы истинны, то и сама секущая функция истинная, в противном случае она ложная.

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

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

Арифметическое кодирование

Арифметическое кодирование – один из наиболее эффективных способов сжатия информации. В отличие от алгоритма Хаффмана арифметическое кодирование позволяет кодировать сообщения с энтропией меньше 1 бита на символ. Т.к. большинство алгоритмов арифметического кодирования защищены патентами, далее будут описаны только основные идеи.
Предположим, что в используемом алфавите N символов a_1,…,a_N, с частотами p_1,…,p_N, соответственно. Тогда алгоритм арифметического кодирования будет выглядеть следующим образом:
В качестве рабочего полуинтервала взять }