Файл: Технологии программирования (Возникновение теории кодирования).pdf

В дереве Хаффмана будет 5 узлов:

Таблица 5

Построение дерева Хафмана. Шаг 1

По алгоритму возьмем два символа с наименьшей частотой - это c и d. Сформируем из них новый узел cd весом 2 и добавим его к списку узлов:

Таблица 6

Построение дерева Хафмана. Шаг 2

Затем опять объединим в один узел два минимальных по весу узла - r и cd:

Таблица 7

Построение дерева Хафмана. Шаг 3

Еще раз повторим эту же операцию, но для узлов rcd и b:

Таблица 8

Построение дерева Хафмана. Шаг 4

На последнем шаге объединим два узла – brcd и a:

Таблица 9

Построение дерева Хафмана. Шаг 5

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

Таблица 10

Построение дерева Хафмана. Шаг 6

Таким образом, закодированное слово «abracadabra» будет выглядеть как «01110101000010010111010». Длина закодированного слова – 23 бита. Стоит заметить, что если бы мы использовали алгоритм кодирования с одинаковой длиной всех кодовых слов, то закодированное слово заняло бы 33 бита, что существенно больше.

2.3.5 Корректность алгоритма Хаффмана

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

Пусть C — алфавит, каждый символ c∈C которого встречается с частотой f[c]. Пусть x и y - два символа алфавита C с самыми низкими частотами. Тогда для алфавита C существует оптимальный префиксный код, кодовые слова символов x и y в котором имеют одинаковую максимальную длину и отличаются лишь последним битом.

Доказательство:

Возьмем дерево T, представляющее произвольный оптимальный префиксный код для алфавита C. Преобразуем его в дерево, представляющее другой оптимальный префиксный код, в котором символы x и y - листья с общим родительским узлом, находящиеся на максимальной глубине.

Пусть символы a и b имеют общий родительский узел и находятся на максимальной глубине дерева T. Предположим, что f[a]⩽f[b] и f[x]⩽f[y]. Так как f[x] и f[y] — две наименьшие частоты, а f[a] и f[b] - две произвольные частоты, то выполняются отношения f[x]⩽f[a] и f[y]⩽f[b]. Пусть дерево T′ - дерево, полученное из T путем перестановки листьев a и x, а дерево T″ - дерево полученное из T′ перестановкой листьев b и y. Разность стоимостей деревьев T и T′ равна:

B(T)−B(T′)=∑_c∈Cf(c)d_T(c)−∑_c∈Cf(c)d_T′(c)=(f[a]−f[x])(d_T(a)−d_T(x)),

что больше либо равно 0, так как величины f[a]−f[x] и d_T(a)−d_T(x) неотрицательны. Величина f[a]−f[x] неотрицательна, потому что x - лист с минимальной частотой, а величина d_T(a)−d_T(x) является неотрицательной, так как лист a находится на максимальной глубине в дереве T. Точно так же перестановка листьев y и b не будет приводить к увеличению стоимости. Таким образом, разность B(T′)−B(T′′) тоже будет неотрицательной.

Таким образом, выполняется неравенство B(T′′)⩽B(T). С другой стороны, T - оптимальное дерево, поэтому должно выполняться неравенство B(T)⩽B(T′′). Отсюда следует, что B(T)=B(T′′). Значит, T″ - дерево, представляющее оптимальный префиксный код, в котором символы x и y имеют одинаковую максимальную длину, что и требовалось доказать.

Пусть дан алфавит C, в котором для каждого символа c∈C определены частоты f[c]. Пусть x и y — два символа из алфавита C с минимальными частотами. Пусть C′ — алфавит, полученный из алфавита C путем удаления символов x и y и добавления нового символа z, так что C′=C∖{x,y}∪z. По определению частоты f в алфавите C′ совпадают с частотами в алфавите C, за исключением частоты f[z]=f[x]+f[y]. Пусть T′ — произвольное дерево, представляющее оптимальный префиксный код для алфавита C′ Тогда дерево T, полученное из дерева T′ путем замены листа z внутренним узлом с дочерними элементами x и y, представляет оптимальный префиксный код для алфавита C.

Для доказательства, сначала покажем, что стоимость B(T) дерева T может быть выражена через стоимость B(T′) дерева T′. Для каждого символа c∈C∖{x,y} верно d_T(C)=d_T′, значит, f[c]d_T(c)=f[c]d_T′(c). Так как d_T(x)=d_T(y)=d_T′(z)+1, то f[x]d_T(x)+f[y]d_T(y)=(f[x]+f[y])(d_T′(z)+1)=f[z]d_T′(z)+(f[x]+f[y])

из чего следует, что B(T)=B(T′)+f[x]+f[y] или B(T′)=B(T)−f[x]−f[y]

Докажем лемму от противного. Предположим, что дерево T не представляет оптимальный префиксный код для алфавита C. Тогда существует дерево T″ такое, что B(T′′)<B(T). Согласно лемме (1), элементы x и y можно считать дочерними элементами одного узла. Пусть дерево T‴ получено из дерева T″ заменой элементов x и y листом z с частотой f[z]=f[x]+f[y]. Тогда

B(T′′′)=B(T′′)−f[x]−f[y]<B(T)−f[x]−f[y]=B(T′),

что противоречит предположению о том, что дерево T′ представляет оптимальный префиксный код для алфавита C′. Значит, наше предположение о том, что дерево T не представляет оптимальный префиксный код для алфавита C, неверно, что и доказывает лемму.

Из вышесказанного следует, что алгоритм Хаффмана дает оптимальный префиксный код.

2.4 Алгоритм Шеннона – Фано

Кодирование Шеннона-Фано является одним из самых первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон (Shannon) и Фано (Fano).

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

2.4.1 Построение алгоритма

Рассмотрим алгоритм вычисления кодов Шеннона-Фано (для наглядности возьмём в качестве примера последовательность 'aa bbb cccc ddddd'). Для вычисления кодов, необходимо создать таблицу уникальных символов сообщения c(i) и их вероятностей p(c(i)), и отсортировать её в порядке невозрастания вероятности символов. [6]

Таблица 11

Метод Шеннона-Фано. Шаг 1
Символы сообщения c(i) и их вероятностей p(c(i))

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

Таким образом, для нашего случая получаем следующие коды символов:

Таблица 12

Метод Шеннона-Фано. Шаг 2
Деление на группы

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

111111101101101101001010101100000000000

Полученная длина 39 бит. Учитывая, что оригинал имел длину равную 136 бит, коэффициент сжатия ~28% - не так уж и плохо.

Глядя на полученную последовательность, возникает вопрос: "А как же теперь это разжать?".

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

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

2.5 Сравнение алгоритмов Хафмана и Шеннона – Фано

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

Для работы оба алгоритма должны иметь таблицу частот элементов алфавита.

Итак, алгоритм Хаффмана работает следующим образом:

1. На вход приходят упорядоченные по невозрастанию частот данные.
2. Выбираются две наименьших по частоте буквы алфавита, и создается родитель (сумма двух частот этих «листков»).
3. Потомки удаляются и вместо них записывается родитель, «ветви» родителя нумеруются: левой ветви ставится в соответствие «1», правой «0».
4. Шаг два повторяется до тех пор, пока не будет найден главный родитель — «корень».

Алгоритм Шеннона-Фано работает следующим образом:

1. На вход приходят упорядоченные по невозрастанию частот данные.
2. Находится середина, которая делит алфавит примерно на две части. Эти части (суммы частот алфавита) примерно равны. Для левой части присваивается «1», для правой «0», таким образом мы получим листья дерева
3. Шаг 2 повторяется до тех пор, пока мы не получим единственный элемент последовательности, т.е. листок

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

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

Для примера, рассмотрим последовательность с таким содержанием символов: 'a' - 14, 'b' - 7, 'c' - 5, 'd' - 5, 'e' - 4. Метод Хаффмана сжимает её до 77 бит, а вот Шеннона-Фано до 79 бит.

Таблица 13

Сравнение Кода Хаффмана и Кода Шеннона-Фано

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

Способ деления на группы в данном случае:

1. вероятность первой группы (p1) и второй (p2) равна нулю;
2. p1 <= p2 ?
   1. да: добавить в первую группу символ с начала таблицы;
   2. нет: добавить во вторую группу символ с конца таблицы;
3. если все символы разделены на группы, то завершить алгоритм, иначе перейти к шагу 2.