Размещено на http://www.allbest.ru/

Содержание

• Введение
• Глава 1. Сжатие данных
• 1.1 Представление и сжатие данных
• 1.2 Основа всех методов сжатия
• 1.3 Обзор существующих программ сжатия данных без потерь
• Глава 2. Коды Хаффмена
• 2.1 Кодирование Хаффмена
• 2.2 Особенности кодирования Хаффмена
• 2.3 Применение кодирования Хаффмена
• Глава 3. Алгоритм построения оптимального префиксного кода
• 3.1 Характеристики алгоритма Хаффмена
• 3.2 Принцип работы алгоритма Хаффмена
• 3.3 Примеры реализации алгоритма Хаффмена
• Заключение
• Библиография
• Приложение

Введение

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

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

Основными техническими характеристиками процессов сжатия и результатов их работы являются:

- степень сжатия (compress rating) или отношение (ratio) объемов исходного и результирующего потоков;

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

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

В этой работе мы рассмотрим один из самых распространенных методов сжатия данных. Речь пойдет о коде Хаффмена (Huffman code) или минимально-избыточном префиксном коде (minimum-redundancy prefix code).

Первым такой алгоритм опубликовал Дэвид Хаффмен (David Huffman) в 1952 году. Идея, лежащая в основе кода Хаффмена, достаточно проста. Вместо того чтобы кодировать все символы одинаковым числом бит (как это сделано, например, в ASCII кодировке, где на каждый символ отводится ровно по 8 бит), кодируются символы, которые встречаются чаще, меньшим числом бит, чем те, которые встречаются реже. Кодирование Хаффмена является простым алгоритмом для построения кодов переменной длины, имеющих минимальную среднюю длину. Этот весьма популярный алгоритм служит основой многих компьютерных программ сжатия текстовой и графической информации. Некоторые из них используют непосредственно алгоритм Хаффмена, а другие берут его в качестве одной из ступеней многоуровневого процесса сжатия. Метод Хаффмена производит идеальное сжатие (то есть, сжимает данные до их энтропии), если вероятности символов точно равны отрицательным степеням числа 2. Алгоритм начинает строить кодовое дерево снизу вверх, затем скользит вниз по дереву, чтобы построить каждый индивидуальный код справа налево (от самого младшего бита к самому старшему). Начиная с работ Д.Хаффмена 1952 года, этот алгоритм являлся предметом многих исследований.

Глава 1. Сжатие данных

1.1 Представление и сжатие данных

Рассмотрим двойственность природы данных: с одной стороны, содержимое информации, а с другой - ее физическое представление. В 1950 году Клод Шеннон (Claude Shannon) заложил основы теории информации, в том числе идею о том, что данные могут быть представлены определенным минимальным количеством битов. Эта величина получила название энтропии данных (термин был заимствован из термодинамики).

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

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

Сжатие данных (data compression) - это алгоритм эффективного кодирования информации, при котором она занимает меньший объем памяти, нежели ранее. Мы избавляемся от избыточности (redundancy), т.е. удаляем из физического представления данных те биты, которые в действительности не требуются, оставляя только то количество битов, которое необходимо для представления информации в соответствии со значением энтропии. Существует показатель эффективности сжатия данных: коэффициент сжатия (compression ratio). Он вычисляется путем вычитания из единицы частного от деления размера сжатых данных на размер исходных данных и обычно выражается в процентах. Например, если размер сжатых данных равен 1000 бит, а несжатых - 4000 бит, коэффициент сжатия составит 75%, т.е. мы избавились от трех четвертей исходного количества битов.

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

Существует два основных типа сжатия данных: с потерями (lossy) и без потерь (lossless). Сжатие без потерь проще для понимания. Это метод сжатия данных, когда при восстановлении данных возвращается точная копия исходных данных. Такой тип обеспечивает при распаковке упакованного файла создание файла, который имеет в точности то же содержимое, что и оригинал перед его сжатием. И напротив, сжатие с потерями не позволяет при восстановлении получить те же исходные данные. Это кажется недостатком, но для определенных типов данных, таких как данные изображений и звука, различие между восстановленными и исходными данными не имеет особого значения: наши зрение и слух не в состоянии уловить образовавшиеся различия. В общем случае алгоритмы сжатия с потерями обеспечивают более эффективное сжатие, чем алгоритмы сжатия без потерь (в противном случае их не стоило бы использовать вообще). Для примера можно сравнить предназначенный для хранения изображений формат с потерями JPEG с форматом без потерь GIF. Множество форматов потокового аудио и видео, используемых в Internet для загрузки мультимедиа-материалов, являются алгоритмами сжатия с потерями.

1.2 Основа всех методов сжатия

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

Точная связь между вероятностями и кодами установлена в теореме Шеннона о кодировании источника, которая гласит, что элемент s_h вероятность появления которого равняется p(s,), выгоднее всего представлять -1о& p(sj) битами. Если при кодировании размер кодов всегда в точности получается равным -log₂ p(s,) битам, то в этом случае длина закодированной последовательности будет минимальной для всех возможных способов кодирования. Если распределение вероятностей F= {pis,} неизменно, и вероятности появления элементов независимы, то мы можем найти среднюю длину кодов как среднее взвешенное.

Это значение также называется энтропией распределения вероятностей F или энтропией источника в заданный момент времени.

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

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

1.3 Обзор существующих программ сжатия данных без потерь

В настоящее время существует очень много алгоритмов сжатия данных без потерь. Наиболее распространенными являются такие, как: Lossless JPEG, алгоритм Хаффмена, алгоритмы группы KWE

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

Алгоритм Lossless JPEG разработан группой экспертов в области фотографии (Joint Photographic Expert Group). В отличие от JBIG, Lossless JPEG ориентирован на полноцветные 24-битные или 8-битные в градациях серого изображения без палитры. Коэффициенты сжатия: 20, 2, 1. Lossless JPEG рекомендуется применять в тех приложениях, где необходимо побитовое соответствие исходного и декомпрессированного изображений. Этот формат разрабатывался, прежде всего, для хранения изображений в медицинских целях, то есть для тех случаев, когда важно иметь большое изображение без малейших потерь качества.

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

Эта работа и посвящена алгоритму Хаффмена.

Глава 2. Коды Хаффмена

2.1 Кодирование Хаффмена

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

Классический алгоритм Хаффмена на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмена (Н-дерево). Алгоритм построения Н-дерева прост и элегантен:

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

- выбираются два свободных узла дерева с наименьшими весами.

- создается их родитель с весом, равным их суммарному весу;

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

- одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой -- бит 0;

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

Допустим, у нас есть следующая таблица частот: 15 7 6 6 5 А Б В Г Д

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

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

Для данной таблицы символов коды Хаффмена будут выглядеть следующим образом. А Б В Г Д 0 100 101 110 111

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

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

2.2 Особенности кодирования Хаффмена

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

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

В процессе работы алгоритма сжатия вес узлов в дереве кодирования Хаффмена неуклонно растет. Первая проблема возникает тогда, когда вес корня дерева начинает превосходить вместимость ячейки, в которой он хранится. Как правило, это 16-битовое значение и, следовательно, не может быть больше, чем 65535. Вторая проблема, заслуживающая ещё большего внимания, может возникнуть значительно раньше, когда размер самого длинного кода Хаффмена превосходит вместимость ячейки, которая используется для того, чтобы передать его в выходной поток. Декодеру все равно, какой длины код он декодирует, поскольку он движется сверху вниз по дереву кодирования, выбирая из входного потока по одному биту. Кодер же должен начинать от листа дерева и двигаться вверх к корню, собирая биты, которые нужно передать. Обычно это происходит с переменной типа "целое", и, когда длина кода Хаффмена превосходит размер типа "целое" в битах, наступает переполнение. Можно доказать, что максимальную длину код Хаффмена для сообщений с одним и тем же входным алфавитом будет иметь, если частоты символов образует последовательность Фибоначчи. Сообщение с частотами символов, равными числам Фибоначчи до Fib (18), -- это отличный способ протестировать работу программы сжатия по Хаффмену.

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

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

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

2.3 Применение кодирования Хаффмена

С тех пор, как Д.А.Хаффмен опубликовал свою работу "Метод построения кодов с минимальной избыточностью", его алгоритм кодирования стал базой для огромного количества дальнейших исследований в этой области. Сжатие данных по Хаффмену применяется при сжатии фото- и видеоизображений (JPEG, стандарты сжатия MPEG), в архиваторах (PKZIP, LZH и др.), в протоколах передачи данных MNP5 и MNP7.

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

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

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

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

Глава 3. Алгоритм построения оптимального префиксного кода

3.1 Характеристики алгоритма Хаффмена

архиватор программа хаффмен сжатие

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

Рассмотрим характеристики, применяемые к алгоритму Хаффмена:

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

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

- симметричность. Отношение характеристики алгоритма кодирования к аналогичной характеристике при декодировании. Характеризует ресурсоемкость процессов кодирования и декодирования. Для нас наиболее важной является симметричность по времени: отношение времени кодирования ко времени декодирования. Иногда нам потребуется симметричность по памяти;

- есть ли потери качества? И если есть, то за счет чего изменяется коэффициент архивации? Дело в том, что у большинства алгоритмов сжатия с потерей информации существует возможность изменения коэффициента сжатия;

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

Согласно вышеуказанным представлениям характеристик разберем значения характеристик классического алгоритма Хаффмена:

- коэффициенты компрессии: 8, 1,5, 1 (лучший, средний, худший коэффициенты);

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

- симметричность: 2 (за счет того, что требует двух проходов по массиву сжимаемых данных);

- потери качества: без потерь;

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

3.2 Принцип работы алгоритма Хаффмена

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

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

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

Мы имеем файл длиной в 100 байт и имеющий 6 различных символов в себе. Мы подсчитали вхождение каждого из символов в файл и получили данные, представленные в таблице 3.1.

Таблица 3.1 - Вхождение символов в файл

Символ	A	B	C	D	E	F
Число вхождений	10	20	30	5	25	10

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

Таблица 3.2 - Частота вхождения символов

Символ	C	E	B	F	A	D
Число вхождений	30	25	20	10	10	5

Мы возьмем из последней таблицы символы с наименьшей частотой. В нашем случае это D (5) и какой либо символ из F или A (10), можно взять любой из них, например, A.

Сформируем из узлов D и A новый узел, частота вхождения для которого будет равна сумме частот D и A: Рисунок 3.1 - Формирование нового узла

Рисунок 3.1 - Формирование нового узла

Номер в рамке - сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими частотами вхождения. Исключая из просмотра D и A и рассматривая вместо них новый узел с суммарной частотой вхождения. Самая низкая частота теперь у F и нового узла. Снова сделаем операцию слияния узлов: Рисунок 3.2 - Слияние узлов.

Рисунок 3.2 - Слияние узлов

Рассматриваем таблицу снова для следующих двух символов (B и E). Мы продолжаем в этот режим пока все дерево не сформировано, т.е. пока все не сведется к одному узлу: Рисунок 3.3 - Формирование дерева.

Рисунок 3.3 - Формирование дерева

Теперь, когда наше дерево создано, мы можем кодировать файл. Мы должны всегда начинать из корня (Root). Кодируя первый символ (лист дерева С) Мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так для C, мы будем идти влево к 55 (и запомним 0), затем снова влево (0) к самому символу. Код Хаффмена для нашего символа C - 00. Для следующего символа (А) у нас получается - лево, право, лево, лево, что выливается в последовательность 0100. Выполнив выше сказанное для всех символов, получим:

- C = 00 (2 бита)

- A = 0100 (4 бита)

- D = 0101 (4 бита)

- F = 011 (3 бита)

- B = 10 (2 бита)

- E = 11 (2 бита)

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

Таблица 3.3 - Уменьшение размера выходного файла

Частота	Первоначально	Уплотненные биты	Уменьшено на
C 30 A 10 D 5 F 10 B 20 E 25	30 x 8 = 240 10 x 8 = 80 5 x 8 = 40 10 x 8 = 80 20 x 8 = 160 25 x 8 = 200	30 x 2 = 60 10 x 3 = 30 5 x 4 = 20 10 x 4 = 40 20 x 2 = 40 25 x 2 = 50	180 50 20 40 120 150

- первоначальный размер файла: 100 байт - 800 бит;

- размер сжатого файла: 30 байт - 240 бит;

- 240 - 30% из 800, так что мы сжали этот файл на 70%.

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

Первое решение: мы должны сохранять дерево вместе с файлом. Это превращается в итоге в увеличение размеров выходного файла. В нашей методике сжатия и каждом узле находятся 4 байта указателя, по этому, полная таблица для 256 байт будет приблизительно 1 Кбайт длинной. Таблица в нашем примере имеет 5 узлов плюс 6 вершин (где и находятся наши символы), всего 11. 4 байта 11 раз - 44. Если мы добавим после небольшое количество байтов для сохранения места узла и некоторую другую статистику - наша таблица будет приблизительно 50 байтов длины. Добавив к 30 байтам сжатой информации, 50 байтов таблицы получаем, что общая длинна архивного файла вырастет до 80 байт. Учитывая, что первоначальная длинна файла в рассматриваемом примере была 100 байт - мы получили 20% сжатие информации. Выполнена трансляция символьного ASCII набора в наш новый набор, требующий меньшее количество знаков по сравнению со стандартным.

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

Мы получим, что можно иметь только:

- 4 - 2 разрядных кода;

- 8 - 3 разрядных кодов;

- 16 - 4 разрядных кодов;

- 32 - 5 разрядных кодов;

- 64 - 6 разрядных кодов;

- 128 - 7 разрядных кодов.

Необходимо еще два 8 разрядных кода.

- 4 - 2 разрядных кода;

- 8 - 3 разрядных кодов;

- 16 - 4 разрядных кодов;

- 32 - 5 разрядных кодов;

- 64 - 6 разрядных кодов;

- 128 - 7 разрядных кодов.

--------

254

Итак, мы имеем итог из 256 различных комбинаций, которыми можно кодировать байт. Из этих комбинаций лишь 2 по длине равны 8 битам. Если мы сложим число битов, которые это представляет, то в итоге получим 1554 бит или 195 байтов. Так в максимуме, мы сжали 256 байт к 195 или 33%, таким образом, максимально идеализированный Huffman может достигать сжатия в 33%, когда используется на уровне байта.

Все эти подсчеты производились для не префиксных кодов Хаффмена, т.е. кодов, которые нельзя идентифицировать однозначно. Например, код A - 01011 и код B - 0101. Если мы будем получать эти коды побитно, то, получив биты 0101, мы не сможем сказать какой код мы получили A или B , так как следующий бит может быть как началом следующего кода, так и продолжением предыдущего.

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

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

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

3.3 Примеры реализации алгоритма Хаффмена

Пример 1. Построение кодового дерева. Пусть задана исходная последовательность символов: aabbbbbbbbccсcdeeeee.

Ее исходный объем равен 20 байт (160 бит). В соответствии с данными закодированная исходная последовательность символов будет выглядеть следующим образом: 110111010000000011111111111111001010101010: Рисунок 3.4 - Создание оптимальных префиксных кодов.

Следовательно, ее объем будет равен 42 бита. Коэффициент сжатия приближенно равен 3,8.

Рисунок 3.4 - Создание оптимальных префиксных кодов

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

Анализ. Двоичная запись 127 равна 01111111, а 128 - 10000000. Половина пикселей поверхности будет нулем, а вторая половина единицей. В самом плохом случае область будет походить на шахматную доску, то есть, иметь много серий длины 1. В этом случае каждая серия требует кода в 1 бит, что ведет к одному кодовому биту на пиксель на область, или 8 кодовых битов на пиксель для всего изображения. Это приводит к полному отсутствию сжатия. А коду Хаффмена для такого изображения понадобится всего два кода (поскольку имеется всего два разных пикселя), и они могут быть длины 1. Это приводит к одному кодовому биту на пиксель, то есть к восьмикратному сжатию.

Пример 3. Программная реализация алгоритма Хаффмена с помощью кодового дерева.

Листинг программной реализации алгоритма Хаффмена с помощью кодового дерева представлен в приложении А.

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

Заключение

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

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

В этой работе мы провели анализ одного из самых распространенных методов сжатия данных. Речь шла о коде Хаффмена (Huffman code) или минимально-избыточном префиксном коде (minimum-redundancy prefix code). Рассмотрены основные идеи кода Хаффмена, исследованы ряд важных свойств оптимального кодирования и познакомлены с реализацией его на практике. Метод Хаффмена и его модификация - метод адаптивного кодирования (динамическое кодирование Хаффмена) - нашли широчайшее применение в нашей жизни.

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

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

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

Библиография

1. Новиков Ф.А. Дискретная математика для программистов. - СПб: Питер, 2007

2. http://ru.wikipedia.org/wiki/Код_Хаффмена.

3. Симонович С.В. Информатика. Базовый курс. - СПб.: Питер, 2008.

4. Сергеенко B. C., Баринов В. В. Сжатие данных, речи, звука и изображений в телекоммуникационных системах. - М.: РадиоСофт, 2009.

5. Глушаков С. В. Лучшие программы для ПК. - СПб.: АСТ, 2008.

6. Панин В.В. Основы теории информации: учебное пособие для вузов. - М.: Бином. Лаборатория знаний, 2009.

7. Зуев Ю.А. По океану дискретной математики. Том 2: От перечислительной комбинаторики до современной криптографии: Графы. Алгоритмы. Коды, блок-схемы, шифры. - М.: Либроком, 2012.

8. Павловская Т. А., Щупак Ю. А. C++. Объектно-ориентированное программирование. - СПб.: Питер, 2008.

9. Сигал И. Х., Иванова А. П. Введение в прикладное дискретное программирование. -- СПб.: Физматлит, 2007.

10. Потапов В. Н. Введение в теорию информации. Учебное пособие. - Новосибирск: НГУ, 2009.

11. Верещагин Н. К., Щепин Е. В. Информация, кодирование и предсказание. - М.: МЦНМО, 2012.

12. Ромащенко А. Е., Румянцев А. Ю., Шень А. Заметки по теории кодирования. - М.: МЦНМО, 2011.

13. Березкин Е.Ф. Основы теории информации и кодирования. - М.: МИФИ, 2010.

14. Сидельников В. М. Теория кодирования. - М.: Физматлит, 2008.

15. Чечёта С. И. Введение в дискретную теорию информации и кодирования. - М.:МЦНМО, 2011.

Приложение А

Листинг программной реализации алгоритма хаффмена с помощью кодового дерева

#include "stdafx.h"

#include <iostream>

using namespace std;

struct sym {

unsigned char ch;

float freq;

char code[255];

sym *left;

sym *right;

};

void Statistics(char *String);

sym *makeTree(sym *psym[],int k);

void makeCodes(sym *root);

void CodeHuffman(char *String,char *BinaryCode, sym *root);

void DecodeHuffman(char *BinaryCode,char *ReducedString,

sym *root);

int chh;//переменная для подсчета информация из строки

int k=0;

//счётчик количества различных букв, уникальных символов

int kk=0;//счетчик количества всех знаков в файле

int kolvo[256]={0};

//инициализируем массив количества уникальных символов

sym simbols[256]={0};//инициализируем массив записей

sym *psym[256];//инициализируем массив указателей на записи

float summir=0;//сумма частот встречаемости

int _tmain(int argc, _TCHAR* argv[]){

char *String = new char[1000];

char *BinaryCode = new char[1000];

char *ReducedString = new char[1000];

String[0] = BinaryCode[0] = ReducedString[0] = 0;

cout << "Введите строку для кодирования : ";

cin >> String;

sym *symbols = new sym[k];

//создание динамического массива структур simbols

sym **psum = new sym*[k];

//создание динамического массива указателей на simbols

Statistics(String);

sym *root = makeTree(psym,k);

//вызов функции создания дерева Хаффмена

makeCodes(root);//вызов функции получения кода

CodeHuffman(String,BinaryCode,root);

cout << "Закодированная строка : " << endl;

cout << BinaryCode << endl;

DecodeHuffman(BinaryCode,ReducedString, root);

cout << "Раскодированная строка : " << endl;

cout << ReducedString << endl;

delete psum;

delete String;

delete BinaryCode;

delete ReducedString;

system("pause");

return 0;

}

//рeкурсивная функция создания дерева Хаффмена

sym *makeTree(sym *psym[],int k) {

int i, j;

sym *temp;

temp = new sym;

temp->freq = psym[k-1]->freq+psym[k-2]->freq;

temp->code[0] = 0;

temp->left = psym[k-1];

temp->right = psym[k-2];

if ( k == 2 )

return temp;

else {

//внесение в нужное место массива элемента дерева Хаффмена

for ( i = 0; i < k; i++)

if ( temp->freq > psym[i]->freq ) {

for( j = k - 1; j > i; j--)

psym[j] = psym[j-1];

psym[i] = temp;

break;

}

}

return makeTree(psym,k-1);

}

//рекурсивная функция кодирования дерева

void makeCodes(sym *root) {

if ( root->left ) {

strcpy(root->left->code,root->code);

strcat(root->left->code,"0");

makeCodes(root->left);

}

if ( root->right ) {

strcpy(root->right->code,root->code);

strcat(root->right->code,"1");

makeCodes(root->right);

}

}

/*функция подсчета количества каждого символа и его вероятности*/

void Statistics(char *String){

int i, j;

//побайтно считываем строку и составляем таблицу встречаемости

for ( i = 0; i < strlen(String); i++){

chh = String[i];

for ( j = 0; j < 256; j++){

if (chh==simbols[j].ch) {

kolvo[j]++;

kk++;

break;

}

if (simbols[j].ch==0){

simbols[j].ch=(unsigned char)chh;

kolvo[j]=1;

k++; kk++;

break;

}

}

}

// расчет частоты встречаемости

for ( i = 0; i < k; i++)

simbols[i].freq = (float)kolvo[i] / kk;

// в массив указателей заносим адреса записей

for ( i = 0; i < k; i++)

psym[i] = &simbols[i];

//сортировка по убыванию

sym tempp;

for ( i = 1; i < k; i++)

for ( j = 0; j < k - 1; j++)

if ( simbols[j].freq < simbols[j+1].freq ){

tempp = simbols[j];

simbols[j] = simbols[j+1];

simbols[j+1] = tempp;

}

for( i=0;i<k;i++) {

summir+=simbols[i].freq;

printf("Ch= %d\tFreq= %f\tPPP= %c\t\n",simbols[i].ch,

simbols[i].freq,psym[i]->ch,i);

}

printf("\n Slova = %d\tSummir=%f\n",kk,summir);

}

//функция кодирования строки

void CodeHuffman(char *String,char *BinaryCode, sym *root){

for (int i = 0; i < strlen(String); i++){

chh = String[i];

for (int j = 0; j < k; j++)

if ( chh == simbols[j].ch ){

strcat(BinaryCode,simbols[j].code);

}

}

}

//функция декодирования строки

void DecodeHuffman(char *BinaryCode,char *ReducedString,

sym *root){

sym *Current;// указатель в дереве

char CurrentBit;// значение текущего бита кода

int BitNumber;

int CurrentSimbol;// индекс распаковываемого символа

bool FlagOfEnd; // флаг конца битовой последовательности

FlagOfEnd = false;

CurrentSimbol = 0;

BitNumber = 0;

Current = root;

//пока не закончилась битовая последовательность

while ( BitNumber != strlen(BinaryCode) ) {

//пока не пришли в лист дерева

while (Current->left != NULL && Current->right != NULL &&

BitNumber != strlen(BinaryCode) ) {

//читаем значение очередного бита

CurrentBit = BinaryCode[BitNumber++];

//бит - 0, то идем налево, бит - 1, то направо

if ( CurrentBit == '0' )

Current = Current->left;

else Current = Current->right;

}

//пришли в лист и формируем очередной символ

ReducedString[CurrentSimbol++] = Current->ch;

Current = root;

}

ReducedString[CurrentSimbol] = 0;}

Приложение Б

Пример построения дерева

Приложение в

Биография Д. Хаффмена

Дэвид Хаффмен родился в 1925 году в штате Огайо (Ohio), США. Хаффмен получил степень бакалавра электротехники в государственном университете Огайо (Ohio State University) в возрасте 18 лет. Затем он служил в армии офицером поддержки радара на эсминце, который помогал обезвреживать мины в японских и китайских водах после Второй Мировой Войны. Впоследствии он получил степень магистра в университете Огайо и степень доктора в Массачусетском Институте Технологий (Massachusetts Institute of Technology - MIT). Хотя Хаффмен больше известен за разработку метода построения минимально-избыточных кодов, он так же сделал важный вклад во множество других областей (по большей части в электронике). Он долгое время возглавлял кафедру Компьютерных Наук в MIT. В 1974, будучи уже заслуженным профессором, он подал в отставку. Хаффмен получил ряд ценных наград. В 1999 - Медаль Ричарда Хамминга (Richard W. Hamming Medal) от Института Инженеров Электричества и Электроники (Institute of Electrical and Electronics Engineers - IEEE) за исключительный вклад в Теорию Информации, Медаль Louis E. Levy от Франклинского Института (Franklin Institute) за его докторскую диссертацию о последовательно переключающихся схемах, Награду W. Wallace McDowell, Награду от Компьютерного Сообщества IEEE, Золотую юбилейную награду за технологические новшества от IEEE в 1998. В октябре 1999 года, в возрасте 74 лет Дэвид Хаффмен скончался от рака.

Размещено на Allbest.ru

...