Описание программы кодирования Хаффмана

Содержание

 

Введение………………………………………………………….………...……..3

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

1. Типы сжатия…………………………………………………………………..6
2. Методы сжатия данных. Арифметическое кодирование……………...…12

Глава 2.Кодирование Хаффмана……………………………………………..30

2.1 Описание алгоритма, реализующего код Хаффмана……………………...30

2.2 Декодирование Хаффмана. Описание алгоритма, реализующего код Хаффмана………………………………………………………………………...39

Глава 3. Описание программы кодирования  Хаффмана…………………51

3.1 Обоснование  выбора инструментальных средств………………………....51

3.2 Описание  основных функций программы, реализующей  алгоритмы кодирования по методу  Хаффмана……………………………………………..54

Заключение ……………………………………………………………………60

Список  источников информации …………………………………………....61

 

 

 

 

 

 

 

 

 

 

 

 

 

 Введение

 

Всем, кто использует компьютерные программы сжатия информации, хорошо знакомы такие слова, как  «zip», «implode», «stuffit», «diet» и «squeeze». Всё это имена программ или  названия методов для компрессии компьютерной информации. Перевод этих слов в той или иной степени означает застегивание, уплотнение, набивку или сжатие. Однако обычный, языковый смысл этих слов или их перевод не в полной мере отражают истинную природу того, что происходит с информацией в результате компрессии. На самом деле, при компрессии компьютерной информации ничего не набивается и не ужимается, но лишь удаляется некоторый избыток информации, присутствующий в исходных данных. Избыточность - вот центральное понятие в теории сжатия информации. Любые данные с избыточной информацией можно сжать. Данные, в которых нет избыточности, сжать нельзя, точка.

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

Первый тип  информации - это текст. Текст представляет собой важнейший вид компьютерных данных. Огромное количество компьютерных программ и приложений являются по своей природе нечисловыми; они работают с данными, у которых основными элементарными компонентами служат символы текста. Компьютер способен сохранять и обрабатывать лишь двоичную информацию, состоящую из нулей и единиц. Поэтому каждому символу текста необходимо сопоставить двоичный код. Современные компьютеры используют так называемые коды ASCII (произносится «аски», а само слово ASCII является сокращением от «American Standard Code for Information Interchange»), хотя все больше компьютеров и приложений используют новые коды Unicode. ASCII представляет код фиксированной длины, где каждому символу присваивается 8-битовая последовательность (сам код занимает семь битов, а восьмой - проверочный, который изначально был задуман для повышения надежности кода). Код фиксированной длины представляется наилучшим выбором, поскольку позволяет компьютерным программам легко оперировать с символами различных текстов. С другой стороны, код фиксированной длины является по существу избыточным.

В случайном  текстовом файле мы ожидаем, что  каждый символ встречается приблизительно равное число раз. Однако файлы, используемые на практике, навряд ли являются случайными. Они содержат осмысленные тексты, и по опыту известно, что, например, в типичном английском тексте некоторые буквы, такие, как «Е», «Т» и «А», встречаются гораздо чаще, чем «Z» и «Q». Это объясняет, почему код ASCII является избыточным, а также указывает на пути устранения избыточности. ASCII избыточен прежде всего потому, что независимо присваивает каждому символу, часто или редко используемому, одно и то же число бит (восемь). Чтобы удалить такую избыточность, можно воспользоваться кодами переменной длины, в котором короткие коды присваиваются буквам, встречающимся чаще, а редко встречающимся буквам достаются более длинные коды. Точно так работает кодирование Хаффмана. Кодирование Хаффмана является простым алгоритмом для построения кодов переменной длины, имеющих минимальную среднюю длину. Этот весьма популярный алгоритм служит основой многих компьютерных программ сжатия текстовой и графической информации. Некоторые из них используют непосредственно алгоритм Хаффмана, а другие берут его в качестве одной из ступеней многоуровневого процесса сжатия. Метод Хаффмана производит идеальное сжатие (то есть, сжимает данные до их энтропии), если вероятности символов точно равны отрицательным степеням числа 2. Алгоритм начинает строить кодовое дерево снизу вверх, затем скользит вниз по дереву, чтобы построить каждый индивидуальный код справа налево (от самого младшего бита к самому старшему). Начиная с работ Д.Хаффмана 1952 года, этот алгоритм являлся предметом многих исследований.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

1.1 Типы сжатия

 

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

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

 

 

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

В случае экспериментов  с подбрасыванием монеты было очень легко определить наилучший способ хранения набора данных. Но для других данных эта задача становится более сложной. При этом можно применить несколько алгоритмических подходов. Два класса сжатия, которые будут рассмотрены в этой главе, представляют собой алгоритмы сжатия без потерь и называются кодированием с минимальной избыточностью (minimum redundancy coding) и сжатием с применением словаря (dictionary compression).

Кодирование с  минимальной избыточностью - это  метод кодирования байтов (или, более  строго, символов), при котором чаще встречающиеся байты кодируются меньшим количеством битов, чем те, которые встречаются реже. Например, в тексте на английском языке буквы Е, Т и А встречаются чаще, нежели буквы Q, X и Z. Поэтому, если бы удалось закодировать буквы Е, Т и А меньшим количеством битов, чем 8 (как должно быть в соответствии со стандартом ASCII), а буквы Q, X и Z - большим, текст на английском языке удалось бы сохранить с использованием меньшего количества битов, чем при соблюдении стандарта ASCII.

При использовании  сжатия с применением словаря  данные разбиваются на большие фрагменты (называемые лексемами), чем символы. Затем применяется алгоритм кодирования  лексем определенным минимальным количеством  битов. Например, слова "the", "and" и "to" будут встречаться чаще, чем такие слова, как "electric", "ambiguous" и "irresistible", поэтому их нужно закодировать меньшим количеством битов, чем требовалось бы при кодировании в соответствии со стандартом ASCII.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Lcp=p1L1+p2L2+...+pnLn,

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

L1,L2,...,Ln – длины кодовых слов.

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.2 Методы  сжатия данных. Арифметическое кодирование

 

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

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

Основная идея состоит в том, чтобы отдельно хранить порядок значения элемента X_i («экспоненту» E_i) и отдельно — значащие цифры значения («мантиссу» M_i).

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

Существует  четыре варианта этого метода:

• Fixed+Fixed (фиксированная длина экспоненты – фиксированная длина мантиссы)
• Fixed+Variable (фиксированная длина экспоненты – переменная длина мантиссы)
• Variable+Variable (переменная длина экспоненты – переменная длина мантиссы)
• Variable+Fixed (переменная длина экспоненты – фиксированная длина мантиссы)

В данной работе будут рассмотрены коды переменной длины (Variable+Variable).

1)Унарный код

 

Унарный код сопоставляет числу i двоичную комбинацию вида 1 0.Запись вида 0 или 1 означает соответственно серию из m нулей или единиц. Например, унарными кодами чисел 1, 2, и 3 являются последовательности unar(1)=10, unar(2)=110 и unar(3)=1110 соответственно. Длина кодового слова для числа n равна l_n=n+1. На рисунке 1.1 приведен унарный код чисел от 0 до 6.

 

Рисунок 1.1 – Унарный код чисел от 0 до 6

 

Унарный код оптимален, если числа i распределены по геометрическому закону (1.1) с параметром = :

 

p =(1- ) ,      (1.1)

 

где i=1,2,

Для значений < более эффективен код Голомба.

 

2) Код Голомба

 

Коды Голомба  – это семейство энтропийных  кодеров, являющихся общим случаем  унарного кода. Кодирование энтропии- кодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных коды, длины которых пропорциональны отрицательному логарифму вероятности символа. Таким образом, наиболее вероятные символы используют наиболее наиболее короткие коды. Согласно теореме Шеннона оптимальная длина кода для символа равна -log P, где b- это количество символов, используемых для изготовления выходного кода, и Р- вероятность входного символа. Унарный код – это энтропийное кодирование, которое представляет число n в виде n единиц с замыкающим нулем ( либо n нулей и единица). Например, 5 представляется в виде 111110. Унарное кодирование оптимально для распределения вероятности: P(x)=2 . Также под кодом Голомба может подразумеваться один из представителей этого семейства.

Код Голомба  позволяет представить последовательность символов в виде последовательности двоичных слов. Это представление будет оптимальным при условии, что распределение вероятности символов подчиняется геометрическому закону (1.2):

P(i) = (1-p)p , (1.2)

где i – номер символа, а р – параметр геометрического распределения. Также должно соблюдаться условие (1.3):

 

p = ,     (1.3)

 

где m – основной параметр кода Голомба.

Для кодирования символа  с номером n необходимо представить n в виде (1.4):

 

n = qm + r,     (1.4)

 

где q и r – целые положительные числа, 0 r < m.Затем r кодируется унарным кодом, а q – бинарным. Полученные двоичные последовательности объединяются в результирующее слово.

Пример: Основной параметр кода m=4, кодируемое число n=13 .

• Частное q= = =3;
• унарный код q – 1110;
• остаток r=n mod m=13 mod 4=1;
• бинарный код r – 01;
• результирующее кодовое слово – 111001.

Рассмотрим  несколько примеров кодов Голомба  для различного параметра m в таблице 1.1:

 

Таблица 1.1 –  Коды Голомба для различных параметров m

n\ m	1	2	3	4	5
0	0	00	00	000	000
1	10	01	010	001	001
2	110	100	011	010	010
3	1110	101	100	011	0110
4	11110	1100	1010	1000	0111
5	111110	1101	1011	1001	1000
6	1111110	11100	1100	1010	1001
7	11111110	11101	11010	1011	1010
8	111111110	111100	11011	11000	10110
9	1111111110	111101	11100	11001	10111
10	11111111110	1111100	111010	11010	11000
11	111111111110	1111101	111011	11011	11001
12	1111111111110	11111100	111100	111000	11010
13	11111111111110	11111101	1111010	111001	110110
14	111111111111110	111111100	1111011	111010	110111
15	1111111111111110	111111101	1111100	111011	111000
16	11111111111111110	1111111100	11111010	1111000	111001
17	111111111111111110	1111111101	11111011	1111001	111010

 

Ниже приводится рисунок 1.2, поясняющий устройство данных кодов: как именно двоичное представление  остатка следует за унарным кодом :

 

Рисунок 1.2 –  Формирование кодов Голомба

 

3) Код Райса

 

Код Райса идентичен  коду Голомба, когда m является степенью двойки. На самом деле данные коды имеют параметр k, по которому вычисляется значение m = 2^k.

Введем параметр Т=2 . Код Райса для числа n состоит из двух частей. Первая часть – унарный код числа [ ], вторая часть – двоичная запись в виде последовательности длины k остатка от деления n на T. Очевидно, длина кода Райса для числа n равна l_n=[ ]+1+k. Например, при k=3 и n=21 имеем [ ]=2, остаток равен 5. Поэтому кодом Райса числа 21 будет последовательность 110101.

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

 

Таблица 1.2 –  Коды Райса для различных параметров k

n\ k	1	2	3	4	5	6
0	0	000	0000	00000	000000	0000000
1	10	001	0001	00001	000001	0000001
2	110	010	0010	00010	000010	0000010
3	1110	011	0011	000011	000011	0000011
4	11110	1000	0100	000100	000100	0000100
5	111110	1001	0101	000101	000101	0000101
6	1111110	1010	0110	000110	000110	0000110
7	11111110	1011	0111	000111	000111	0000111
8	111111110	11000	10000	001000	001000	0001000
9	1111111110	11001	10001	001001	001001	0001001
10	11111111110	11010	10010	001010	001010	0001010
11	111111111110	11011	10011	001011	001011	0001011
12	1111111111110	111000	10100	001100	001100	0001100
13	11111111111110	111001	10101	001101	001101	0001101
14	111111111111110	111010	10110	001110	001110	0001110
15	1111111111111110	111011	10111	001111	001111	0001111

 

Код Райса –  это частный случай кода Голомба, это легко увидеть из таблицы 1.3, представленной ниже:

 

 

Таблица 1.3 –  Сравнительная таблица кода Райса  и кода Голомба

Код Голомба	m=1	m=2	m=3	m=4	m=5	m=6	m=7	m=8
Код Райса	k=0	k=1		k=2				k=3
n=1	0	00	00	000	000	000	000	0000
2	10	01	010	001	001	001	0010	0001
3	110	100	011	010	010	0100	0011	0010
4	1110	101	100	011	0110	0101	0100	0011
5	11110	1100	1010	1000	0111	0110	0101	0100
6	111110	1101	1011	1001	1000	0111	0110	0101
7	1111110	11100	1100	1010	1001	1000	0111	0110
8	…	11101	11010	1011	1010	1001	1000	0111
9	…	111100	11011	11000	10110	10100	10010	10000

 

4) Коды Фибоначчи

 

Самые интересные, нетривиальные  коды. В данном кодировании исходное число n раскладывается в сумму чисел  Фибоначчи f_i (f₁ = 1; f₂ = 2; f_i = f_i−1 + f_i−2). Известно, что любое натуральное число однозначно представимо в виде суммы чисел Фибоначчи. Поэтому можно построить код числа как последовательность битов, каждый из которых указывает на факт наличия в n определенного числа Фибоначчи.

Заметим также, что если в разложении числа n присутствует f_i, то в этом разложении не может быть числа f_i+1. Поэтому логично для конца кода использовать дополнительную единицу. Тогда две идущие подряд единицы будут означать окончание кодирования текущего числа.

Рассмотрим несколько  примеров кодов Фибоначчи в таблице 1.4:

 

Таблица 1.4 – Примеры кода Фибоначчи

n\f	1	2	3	5	8	13	21	34
1	1	(1)
2	0	1	(1)
3	0	0	1	(1)
4	1	0	1	(1)
5	0	0	0	1	(1)
6	1	0	0	1	(1)
7	0	1	0	1	(1)
8	0	0	0	0	1	(1)
…	…	…	…	…	…	…
12	1	0	1	0	1	(1)
13	0	0	0	0	0	1	(1)
…	…	…	…	…	…	…	…
20	0	1	0	1	0	1	(1)
21	0	0	0	0	0	0	1	(1)