Какой метод сжатия дает наилучший результат. Сжатие информации

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

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

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

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

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

Для сложных изображений такой метод малоэффективен, поэтому в промышленных форматах применяют другие методы. Например, один из универсальных алгоритмов LZW (назван по фамилиям авторов Якоб Лемпель, Абрахам Зив и Терри Велч). Этот алгоритм подразумевает создание во время обработки специального словаря уже встречавшихся фрагментов. При кодировании последовательности байтов заменяются на их номера по словарю, причем номера часто встречающихся последовательностей имеют меньшее количество битов, чем редко встречающихся. Этот способ активно применяется при сжатии самых разных данных, в том числе и графических. Такой способ сжатия применяется в графическом формате TIFF, в популярном формате GIF. Аналогичные методы применяются и в современном формате PNG (P ortable N etwork G raphic ), разработанном специально для применения в сетевых приложениях.

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

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

Для решения этой проблемы группой специалистов был разработан специальный формат и способ сжатия, получивший название JPEG (J oint P hotographic E xpert G roup , объединенная группа экспертов-фотографов). Алгоритм сжатия, предложенный ими, подразумевал сжатие с потерей качества . Его достоинством было то, что “силу” сжатия можно было указывать изначально и таким образом находить компромисс между качеством и объемом изображения. Первый стандарт этого алгоритма был принят в 1991 году.

Алгоритм JPEG предусматривает перевод изображения в более пригодную для сжатия цветовую модель - YСrCb (Яркость, Хроматический красный, Хроматический синий). За счет того, что человеческий глаз более чувствителен к яркости, чем к цвету, появляется возможность сжимать цветовые компоненты сильнее. В дальнейшем операции над компонентами выполняются отдельно. Изображение разбивается на фрагменты размером 8 ґ 8 пикселей, и внутри объектов выполняется целый ряд преобразований, некоторые из которых сглаживают разницу между пикселями. В зависимости от заданного параметра степени сжатия можно сглаживать разницу сильнее или слабее.

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

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

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

Первым был разработан и принят в 1992 году стандарт MPEG-1, включавший в себя способ сжатия видео в поток до 1,5 Мбит, аудио в поток 64, 128 или 192 Кбит/с на канал, а также алгоритмы синхронизации. Стандарт описывал не алгоритмы, а формат получающегося битового потока. Это позволило в дальнейшем разработать множество реализаций алгоритмов кодирования и декодирования. Стандарт применялся для создания видео и CD.

Особенную популярность завоевала реализация MPEG-1 для упаковки звука. Применяется для этого стандарт MPEG-1 Layer 3 (сокращенно названный MP3 ). При сжатии этим методом используется сжатие с потерей информации. Причем учитывается особенность слухового восприятия: если рядом расположены две частоты, то более громкая “перекрывает” более тихую. Таким образом, ее можно сгладить без ощутимой потери качества звука.

Следующим шагом была разработка и принятие в 1995 году стандарта MPEG-2, предусматривающего работу с более качественным видеопотоком, скорость которого могла изменяться от 3 до 10 Мбит/с. Эта группа методов применяется при создании DVD-дисков.

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

Несмотря на большое разнообразие, в основе всех этих алгоритмов лежит общий подход к кодированию/декодированию. Во-первых, одной из основ сжатия кадров является алгоритм JPEG. В рамках этого подхода рассматриваются три вида кадров: ключевой кадр, сохраняемый в потоке полностью (intrapictures), кадры, сжатые со ссылкой на предыдущее изображение (predicted), и кадры, ссылающиеся на два кадра (bidirection).

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

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

Технически кодеки - отдельные программы, вызываемые проигрывателями для декодирования потока, а средствами сохранения - для его сжатия . Кодек отмечается в начале файла (или сетевого потока), и его наличие - важное условие работы с мультимедиа-данными. Многие кодеки не поставляются с операционной системой, а устанавливаются дополнительно. Для удобства их часто собирают в пакеты (codec-pack).

Примеры программных средств

DivX, XviD, Lame MP3 encoder, QuickTime

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лекция №4. Сжатие информации

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

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

Пусть у нас имеется файл размером 1 (один) мегабайт. Нам необходимо получить из него файл меньшего размера. Ничего сложного - запускаем архиватор, к примеру, WinZip, и получаем в результате, допустим, файл размером 600 килобайт. Куда же делись остальные 424 килобайта?

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

Виды сжатия

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

Сжатие без потери информации.

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

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

Вот простой пример. В русском языке 33 буквы, десять цифр и еще примерно полтора десятка знаков препинания и прочих спе­циальных символов. Для текста, который записан только про­писными русскими буквами (как в телеграммах и радиограммах) вполне хватило бы шестидесяти разных значений. Тем не менее, каждый символ обычно кодируется байтом, который содержит 8 битов и может выражать 256 различных кодов. Это первое осно­вание для избыточности. Для нашего «телеграфного» текста вполне хватило бы шести битов на символ.

Вот другой пример. В международной кодировке символов ASCII для кодирования любого символа отводится одинаковое количество битов (8), в то время как всем давно и хорошо извест­но, что наиболее часто встречающиеся символы имеет смысл кодировать меньшим количеством знаков. Так, например, в «азбуке Морзе» буквы «Е» и «Т», которые встречаются часто, кодируются одним знаком (соответственно это точка и тире). А такие редкие буквы, как «Ю» ( - -) и «Ц» (- - ), кодиру­ются четырьмя знаками. Неэффективная кодировка - второе основание для избыточности. Программы, выполняющие сжа­тие информации, могут вводить свою кодировку (разную для разных файлов) и приписывать к сжатому файлу некую таблицу (словарь), из которой распаковывающая программа узнает, как в данном файле закодированы те или иные символы или их груп­пы. Алгоритмы, основанные на перекодировании информации, называют алгоритмами Хафмана.

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

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

Сжатие с потерей информации.

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

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

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

К алгоритмам сжатия с потерей информации относятся такие известные алгоритмы как JPEG и MPEG. Алгоритм JPEG исполь­зуется при сжатии фотоизображений. Графические файлы, сжа­тые этим методом, имеют расширение JPG. Алгоритмы MPEG используют при сжатии видео и музыки. Эти файлы могут иметь различные расширения, в зависимости от конкретной программы, но наиболее известными являются.MPG для видео и.МРЗ для музыки.

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

Величиной допустимой потери при сжатии обычно можно управ­лять. Это позволяет экспериментовать и добиваться оптималь­ного соотношения размер/качество. На фотографических иллюст­рациях, предназначенных для воспроизведения на экране, потеря 5% информации обычно некритична, а в некоторых случаях можно допустить и 20-25%.

Алгоритмы сжатия без потери информации

Код Шеннона-Фэно

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

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

Давайте представим себе текст, алфавит которого состоит всего из 16 букв: А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О, П, Р. Каждый из этих знаков можно закодировать с помощью всего 4 бит: от 0000 до 1111. Теперь представим себе, что вероятности появления этих символов распределены следующим образом:

Сумма этих вероятностей составляет, естественно, единицу. Разобьем эти символы на две группы таким образом, чтобы суммарная вероятность символов каждой группы составляла ~0.5 (рис). В нашем примере это будут группы символов А-В и Г-Р. Кружочки на рисунке, обозначающие группы символов, называются вершинами или узлами (nodes), а сама конструкция из этих узлов - двоичным деревом (B-tree). Присвоим каждому узлу свой код, обозначив один узел цифрой 0, а другой - цифрой 1.

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

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

Коды символов (крайние правые узлы дерева) имеют коды неодинаковой длины. Так, буква А, имеющая для нашего воображаемого текста вероятность p=0.2, кодируется всего двумя битами, а буква Р (на рисунке не показана), имеющая вероятность p=0.013, кодируется аж шестибитовой комбинацией.

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

где ni - количество бит, кодирующих i-й символ, pi - вероятность появления i-го символа.

Код Хаффмана.

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

1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте.

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

3. Прослеживаем путь к каждому листу дерева, помечая направление к каждому узлу (например, направо - 1, налево - 0) . Полученная последовательность дает кодовое слово, соответствующее каждому символу (рис.).

Построим кодовое дерево для сообщения со следующим алфавитом:

Недостатки методов

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

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

Еще один недостаток кодов - это то, что минимальная длина кодового слова для них не может быть меньше единицы, тогда как энтропия сообщения вполне может составлять и 0,1, и 0,01 бит/букву. В этом случае код становится существенно избыточным. Проблема решается применением алгоритма к блокам символов, но тогда усложняется процедура кодирования/декодирования и значительно расширяется кодовое дерево, которое нужно в конечном итоге сохранять вместе с кодом.

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

Групповое кодирование - Run Length Encoding (RLE) - один из самых старых и самых простых алгоритмов архивации. Сжатие в RLE происходит за счет замены цепочек одинаковых байт на пары "счетчик, значение". («красный, красный, ..., красный» записывается как «N красных»).

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

При кодировании exe-файлов можно искать и упаковывать последовательности вида AxAyAzAwAt..., которые часто встречаются в ресурсах (строки в кодировке Unicode)

К положительным сторонам алгоритма, можно отнести то, что он не требует дополнительной памяти при работе, и быстро выполняется. Алгоритм применяется в форматах РСХ, TIFF, ВМР. Интересная особенность группового кодирования в PCX заключается в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

LZW-код (Lempel-Ziv & Welch) является на сегодняшний день одним из самых распространенных кодов сжатия без потерь. Именно с помощью LZW-кода осуществляется сжатие в таких графических форматах, как TIFF и GIF, с помощью модификаций LZW осуществляют свои функции очень многие универсальные архиваторы. Работа алгоритма основана на поиске во входном файле повторяющихся последовательностей символов, которые кодируются комбинациями длиной от 8 до 12 бит. Таким образом, наибольшую эффективность данный алгоритм имеет на текстовых файлах и на графических файлах, в которых имеются большие одноцветные участки или повторяющиеся последовательности пикселов.

Отсутствие потерь информации при LZW-кодировании обусловило широкое распространение основанного на нем формата TIFF. Этот формат не накладывает каких-либо ограничений на размер и глубину цвета изображения и широко распространен, например, в полиграфии. Другой основанный на LZW формат - GIF - более примитивен - он позволяет хранить изображения с глубиной цвета не более 8 бит/пиксел. В начале GIF - файла находится палитра - таблица, устанавливающая соответствие между индексом цвета - числом в диапазоне от 0 до 255 и истинным, 24-битным значением цвета.

Алгоритмы сжатия с потерей информации

Алгоритм JPEG был разработан группой фирм под названием Joint Photographic Experts Group. Целью проекта являлось создание высокоэффективного стандарта сжатия как черно-белых, так и цветных изображений, эта цель и была достигнута разработчиками. В настоящее время JPEG находит широчайшее применение там, где требуется высокая степень сжатия - например, в Internet.

В отличие от LZW-алгоритма JPEG-кодирование является кодированием с потерями. Сам алгоритм кодирования базируется на очень сложной математике, но в общих чертах его можно описать так: изображение разбивается на квадраты 8*8 пикселов, а затем каждый квадрат преобразуется в последовательную цепочку из 64 пикселов. Далее каждая такая цепочка подвергается так называемому DCT-преобразованию, являющемуся одной из разновидностей дискретного преобразования Фурье. Оно заключается в том, что входную последовательность пикселов можно представить в виде суммы синусоидальных и косинусоидальных составляющих с кратными частотами (так называемых гармоник). В этом случае нам необходимо знать лишь амплитуды этих составляющих для того, чтобы восстановить входную последовательность с достаточной степенью точности. Чем большее количество гармонических составляющих нам известно, тем меньше будет расхождение между оригиналом и сжатым изображением. Большинство JPEG-кодеров позволяют регулировать степень сжатия. Достигается это очень простым путем: чем выше степень сжатия установлена, тем меньшим количеством гармоник будет представлен каждый 64-пиксельный блок.

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

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

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

Фрактальное сжатие

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

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

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

Основа метода фрактального кодирования - это обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций (IFS) к проблеме сжатия изображения была исследована Майклом Барнсли и Аланом Слоуном. Они запатентовали свою идею в 1990 и 1991 гг. Джеквин (Jacquin) представил метод фрактального кодирования, в котором используются системы доменных и ранговых блоков изображения (domain and range subimage blocks), блоков квадратной формы, покрывающих все изображение. Этот подход стал основой для большинства методов фрактального кодирования, применяемых сегодня. Он был усовершенствован Ювалом Фишером (Yuval Fisher) и рядом других исследователей.

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

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

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

Вкратце метод, предложенный Барнсли, можно описать следующим образом. Изображение кодируется несколькими простыми преобразованиями (в нашем случае аффинными), то есть определяется коэффициентами этих преобразований (в нашем случае A, B, C, D, E, F).

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

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

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

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

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

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

Сравнение с JPEG

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

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

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

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

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

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

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

Характерной особенностью большинства типов данных является их избыточность. Степень избыточности данных зависит от типа данных. Например, для видеоданных степень избыточности в несколько раз больше чем для графических данных, а степень избыточности графических данных, в свою очередь, больше чем степень избыточности текстовых данных. Другим фактором, влияющим на степень избыточности является принятая система кодирования. Примером систем кодирования могут быть обычные языки общения, которые являются ни чем другим, как системами кодирования понятий и идей для высказывания мыслей. Так, установлено, что кодирование текстовых данных с помощью средств русского языка дает в среднем избыточность на 20-25% большую чем кодирование аналогичных данных средствами английского языка.

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

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

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

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

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

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

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

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 тоже заносится в словарь. Если все части словаря полностью заполнены, кодирование перестает быть адаптивным (кодирование происходит исходя из уже существующих в словаре фраз).

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

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

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

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

Пусть задан текст, в котором бурва "А" входит 10 раз, буква "В" - 8 раз, "С"- 6 раз, "D" - 5 раз, "Е" и "F" - по 4 раза. Тогда один из возможных вариантов кодирования по алгоритму Хаффмана приведен в таблицы 1.

Таблица 1.

	Частота вхождения	Битовый код

Как видно из таблицы 1, размер входного текста до сжатия равен 37 байт, тогда как после сжатия - 93 бит, то есть около 12 байт (без учета длины словаря). Коэффициент сжатия равен 32%. Алгоритм Хаффмана универсальный, его можно применять для сжатия данных любых типов, но он малоэффективен для файлов маленьких размеров (за счет необходимости сохранение словаря).

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

Таблица 2.

Формат сжатия	Операционная система MS DOS		Операционная система Windows
	Программа архивации	Программа разархивации	Программа архивации	Программа разархивации

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

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

добавление файлов в существующий архив;

распаковывание файлов из архива;

создание самораспаковающихся архивов (self-extractor archive);

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

защита архивов паролями от несанкционированного доступа;

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

поиск файлов и данных внутри архива;

проверка на вирусы в архиве к распаковыванию;

выбор и настройка коэффициента сжатия.

Контрольные вопросы

1. Какие факторы влияют на степень избыточности данных? 2. Что такое архив? Какие программные средства называются архиваторами? 3. Почему методы сжатия, при которых происходит изменение содержимого данных, называются необратимыми? 4. Приведите примеры форматов сжатия с потерями информации. 5. В чем состоит преимущество обратимых методов сжатия над необратимыми? А недостаток? 6. Которая существует зависимость между коэффициентом сжатия и эффективностью метода сжатия? 7. В чем состоит основная идея алгоритма RLE? 8. В чем состоит основная идея алгоритмов группы KWE? 9. В чем состоит основная идея алгоритма Хаффмана? 10. Какие вы знаете програми-архиваторы? Коротко охарактеризуйте их.

Информатика. Базовый курс. / Под ред. С.В.Симоновича. - СПб., 2000 г.

А.П.Микляев, Настольная книга пользователя IBM PC 3-издание М.:, "Солон-Р", 2000, 720 с.

Симонович С.В., Евсеев Г.А., Мураховский В.И. Вы купили компьютер: Полное руководство для начинающих в вопросах и ответах. - М.: АСТ-ПРЕСС КНИГА; Инфорком-Пресс, 2001.- 544 с.: ил. (1000 советов).

Ковтанюк Ю.С., Соловьян С.В. Самоучитель работы на персональном компьютере - К.:Юниор, 2001.- 560с., ил.

Цель лекции : изучить основные виды и алгоритмы сжатия данных и научиться решать задачи сжатия данных по методу Хаффмана и с помощью кодовых деревьев.

Основоположником науки о сжатии информации принято считать Клода Шеннона. Его теорема об оптимальном кодировании показывает, к чему нужно стремиться при кодировании информации и насколько та или иная информация при этом сожмется. Кроме того, им были проведены опыты по эмпирической оценке избыточности английского текста. Шенон предлагал людям угадывать следующую букву и оценивал вероятность правильного угадывания. На основе ряда опытов он пришел к выводу, что количество информации в английском тексте колеблется в пределах 0,6 – 1,3 бита на символ. Несмотря на то, что результаты исследований Шеннона были по-настоящему востребованы лишь десятилетия спустя, трудно переоценить их значение .

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

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

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

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

Алфавит кода – множество всех символов входного потока. При сжатии англоязычных текстов обычно используют множество из 128 ASCII кодов. При сжатии изображений множество значений пиксела может содержать 2, 16, 256 или другое количество элементов.

Кодовый символ – наименьшая единица данных, подлежащая сжатию. Обычно символ – это 1 байт , но он может быть битом, тритом {0,1,2}, или чем-либо еще.

Кодовое слово – это последовательность кодовых символов из алфавита кода. Если все слова имеют одинаковую длину (число символов), то такой код называется равномерным (фиксированной длины) , а если же допускаются слова разной длины, то – неравномерным (переменной длины) .

Код – полное множество слов.

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

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

Кодирование – процесс сжатия данных.

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

Отношение сжатия – одна из наиболее часто используемых величин для обозначения эффективности метода сжатия.

Значение 0,6 означает, что данные занимают 60% от первоначального объема. Значения больше 1 означают, что выходной поток больше входного (отрицательное сжатие, или расширение).

Коэффициент сжатия – величина, обратная отношению сжатия.

Значения больше 1 обозначают сжатие, а значения меньше 1 – расширение.

Средняя длина кодового слова – это величина, которая вычисляется как взвешенная вероятностями сумма длин всех кодовых слов.

L cp =p 1 L 1 +p 2 L 2 +...+p n L n ,

где – вероятности кодовых слов;

L 1 ,L 2 ,...,L n – длины кодовых слов.

Существуют два основных способа проведения сжатия.

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

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

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

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

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

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

Префиксный код – это код, в котором никакое кодовое слово не является префиксом любого другого кодового слова. Эти коды имеют переменную длину.

Оптимальный префиксный код – это префиксный код , имеющий минимальную среднюю длину.

Алгоритм Хаффмана можно разделить на два этапа.

1. Определение вероятности появления символов в исходном тексте.

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

2. Нахождение оптимального префиксного кода.

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

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

Пример 1 . Программная реализация метода Хаффмана.

#include "stdafx.h" #include using namespace std; void Expectancy(); long MinK(); void SumUp(); void BuildBits(); void OutputResult(char **Result); void Clear(); const int MaxK = 1000; long k, a, b; char bits; char sk; bool Free; char *res; long i, j, n, m, kj, kk1, kk2; char str; int _tmain(int argc, _TCHAR* argv){ char *BinaryCode; Clear(); cout << "Введите строку для кодирования: "; cin >> str; Expectancy(); SumUp(); BuildBits(); OutputResult(&BinaryCode); cout << "Закодированная строка: " << endl; cout << BinaryCode << endl; system("pause"); return 0; } //описание функции обнуления данных в массивах void Clear(){ for (i = 0; i < MaxK + 1; i++){ k[i] = a[i] = b[i] = 0; sk[i] = 0; Free[i] = true; for (j = 0; j < 40; j++) bits[i][j] = 0; } } /*описание функции вычисления вероятности вхождения каждого символа в тексте*/ void Expectancy(){ long *s = new long; for (i = 0; i < 256; i++) s[i] = 0; for (n = 0; n < strlen(str); n++) s]++; j = 0; for (i = 0; i < 256; i++) if (s[i] != 0){ j++; k[j] = s[i]; sk[j] = i; } kj = j; } /*описание функции нахождения минимальной частоты символа в исходном тексте*/ long MinK(){ long min; i = 1; while (!Free[i] && i < MaxK) i++; min = k[i]; m = i; for (i = m + 1; i <= kk2; i++) if (Free[i] && k[i] < min){ min = k[i]; m = i; } Free[m] = false; return min; } //описание функции подсчета суммарной частоты символов void SumUp(){ long s1, s2, m1, m2; for (i = 1; i <= kj; i++){ Free[i] = true; a[i] = 0; b[i] = 0; } kk1 = kk2 = kj; while (kk1 > 2){ s1 = MinK(); m1 = m; s2 = MinK(); m2 = m; kk2++; k = s1 + s2; a = m1; b = m2; Free = true; kk1--; } } //описание функции формирования префиксных кодов void BuildBits(){ strcpy(bits,"1"); Free = false; strcpy(bits],bits); strcat(bits] , "0"); strcpy(bits],bits); strcat(bits] , "1"); i = MinK(); strcpy(bits[m],"0"); Free[m] = true; strcpy(bits],bits[m]); strcat(bits] , "0"); strcpy(bits],bits[m]); strcat(bits] , "1"); for (i = kk2 - 1; i > 0; i--) if (!Free[i]) { strcpy(bits],bits[i]); strcat(bits] , "0"); strcpy(bits],bits[i]); strcat(bits] , "1"); } } //описание функции вывода данных void OutputResult(char **Result){ (*Result) = new char; for (int t = 0; i < 1000 ;i++) (*Result)[t] = 0; for (i = 1; i <= kj; i++) res] = bits[i]; for (i = 0; i < strlen(str); i++) strcat((*Result) , res]); } Листинг.

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