Жадные алгоритмы. Код Хаффмана

ФБГОУ ВПО «Чувашский государственный  университет им. И.Н. Ульянова»

Факультет Информатики  и вычислительной техники

Кафедра вычислительной техники

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Курсовая работа

по дисциплине “Методы  программирования”

«:Жадные алгоритмы. Код Хаффмана».

 

 

 

 

 

 

 

 

 

 

 

            Выполнил: ст. группы ИВТ-21-10

Мульдияров А.А

      Проверил:   асс. Марков А.В.

 

 

 

 

 

 

 

 

 

 

 

 

Чебоксары 2012

 

Содержание

1) Введение …………………………………………………………………………………………2

2) Анализ ……………………………………………………………………………………………6

3) Проектирование …………………………………………………………………………………8

4) Реализация ……………………………………………………………………………………….13

5) Тестирование …………………………………………………………………………………….14

6) Руководство программиста ……………………………………………………………………..17

7) Выводы ……………………...........................................................................................................18

 

 

1. Введение

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

Формальное определение

Пусть A={a₁,a₂,...,a_n} - алфавит из n различных символов, W={w₁,w₂,...,w_n} - соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов C={c₁,c₂,...,c_n}, такой что:

(1) c_i не является префиксом для c_j, при i=j

(2)   минимальна (|c_i| длина кода c_i)

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

Алгоритм

Обозначения

  — множество, состоящее из n символов

 

Min(Q)-минимальный приоритет частоты f

left[z] – левая ветвь

right[z] – правая ветвь

Insert(Q, z) – установка листьев

 

 

1 nС|

2 QC

3 for i1 to n — 1

4  do Выделить память для узла z

5   left[z] х Min(Q)

6   right[z] у Min(Q)

7  

8   Insert(Q, z)

9 return Min(Q)    Возврат корня дерева

Описание

В приведенном выше псевдокоде предполагается, что С — множество, состоящее из n символов, и что каждый из символов с С — объект с определенной частотой f(с). В алгоритме строится дерево T, соответствующее оптимальному коду, причем построение идет в восходящем направлении. Процесс построения начинается с множества, состоящего из |С| листьев, после чего последовательно выполняется |С| - 1 операций "слияния", в результате которых образуется конечное дерево. Для идентификации двух наименее часто встречающихся объектов, подлежащих слиянию, используется очередь с приоритетами Q, ключами в которой являются частоты f. В результате слияния двух объектов образуется новый объект, частота появления которого является суммой частот объединенных объектов. В строке 2 инициализируется очередь с приоритетами Q, состоящая из элементов множества С. Цикл for в строках 3-8 поочередно извлекает по два узла, х и у, которые характеризуются в очереди наименьшими частотами, и заменяет их в очереди новым узлом z, представляющим объединение упомянутых выше элементов. Частота появления z вычисляется в строке 7 как сумма частот х и у. Узел х является левым дочерним узлом z, а у — его правым дочерним узлом. (Этот порядок является произвольным; перестановка левого и правого дочерних узлов приводит к созданию другого кода с той же стоимостью.) После n — 1 объединений в очереди остается один узел — корень дерева кодов, который возвращается в строке 9.

Доказательство  корректности

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

Лемма 1. Пусть С — алфавит, каждый символ сС которого встречается с частотой f[с]. Пусть х и у — два символа алфавита С с самыми низкими частотами. Тогда для алфавита С существует оптимальный префиксный код, кодовые слова символов х и у в котором имеют одинаковую длину и отличаются лишь последним битом.

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

Пусть а и b — два символа, представленные листьями с общим родительским узлом, которые находятся на максимальной глубине дерева Т. Предположим без потери общности, что f [а] f[b] и f[х] f [у]. Поскольку f[х] и f[у] — две самые маленькие частоты (в указанном порядке), а f[а] и f [b] — две произвольные частоты, то выполняются соотношения f[x]f [а] и f [у] f[6]. Как показано на рисунке, в результате перестановки в дереве Т листьев а и х получается дерево Т’, а при последующей перестановке в дереве T’ листьев b и у получается дерево Т". Согласно уравнению, разность стоимостей деревьев Т и Т" равна

 В(Т)-В (T') = - =

= f [x] d_T (х) + f [a] d_T (а) - f [x] d_T’ (х) - f[a] d_T’ (а) =

=f [х] d_T (х) + f [a] d_T (а) - f [х] d_T (а) - f [а] d_T (x) =

= (f[a] - f[x]) (d_T(a)-d_T(x)) 0,

поскольку величины f [а] -f [х] и d_т (a)—d_T (x) неотрицательны. Величина f [а] — f [х] неотрицательна, потому что x — лист с минимальной частотой, величина d_T (a) — d_T (x) неотрицательна, потому что     а — лист на максимальной глубине в дереве Т.

Иллюстрация ключевых этапов доказательства леммы 1

Аналогично, перестановка листьев  у и b не приведет к увеличению стоимости, поэтому величина       В (Т’) — В (Т") неотрицательна. Таким образом, выполняется неравенство В (T") В (Т), и поскольку Т — оптимальное дерево, то должно также выполняться неравенство В (Т) В (Т"), откуда следует, что В (Т") = В (Т). Таким образом, Т" — оптимальное дерево, в котором х и у — находящиеся на максимальной глубине дочерние листья одного и того же узла, что и доказывает лемму.

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

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

Лемма 2. Пусть дан алфавит С, в котором для каждого символа се С определены частоты а [с]. Пусть х и у — два символа из алфавита С с минимальными частотами. Пусть С — алфавит, полученный из алфавита С путем удаления символов х и у и добавления нового символа z, так что С’ = С — {х,у} U {z}. По определению частоты f в алфавите С совпадают с частотами в алфавите С, за исключением частоты f [z] = f [x] + f [у]. Пусть Т’ — произвольное дерево, представляющее оптимальный префиксный код для алфавита С’. Тогда дерево T, полученное из дерева Т’ путем замены листа z внутренним узлом с дочерними элементами х и у, представляет оптимальный префиксный код для алфавита С.

Доказательство. Сначала покажем, что стоимость В (T) дерева T можно выразить через стоимость     В (Т’) дерева Т’. Для каждого символа с С — {х,у} выполняется соотношение

d_т (с) = d_т' (с), следовательно, f[с]d_т(с) = f[c]d_T'(c). Поскольку d_T (x) = = d_T (у) = d_T' (z) + 1, получаем соотношение f [х] d_T (х) + f [у] d_T (у) = (f [х] + f [у]) (d_T’ (z) + 1)

из которого следует равенство B(T) = B(T') + f[x] +f[y] ИЛИ B(T')=B(T)-f[x]-f[y].

Докажем лемму методом от противного. Предположим, дерево Т не представляет оптимальный префиксный код для  алфавита С. Тогда существует дерево Т", для которого справедливо неравенство В(Т") < В(Т). Согласно лемме 1, х и у без потери общности можно считать дочерними элементами одного и того же узла. Пусть дерево Т"' получено из дерева Т" путем замены элементов х и у листом z с частотой f [z] = f [х] + f [у]. Тогда можно записать:

B(T"')=B(T")-f[x]-f[y]<B(T)-f[x]-f[y] = B(T'),

что противоречит предположению о  том, что дерево Т' представляет оптимальный префиксный код для алфавита С’. Таким образом, дерево T должно представлять оптимальный префиксный код для алфавита С.

Теорема. Процедура Huffman дает оптимальный префиксный код.

Доказательство. Справедливость теоремы непосредственно следует из лемм 1 и 2.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Анализ

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

 

3,"A",1,"B",2,"C",1,"D"

 

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

Прежде всего, отметим, что разные символы встречаются в нашем  тексте по-разному. Чаще всего присутствует буква "A". Можно составить таблицу  частот:

Символ 'A','B','C,'D'

Количество повторений '3','1','2','1'

Затем эта таблица используется для построения так называемого двоичного дерева. Именно это дерево используется для генерации нового сжатого кода.

Левые ветви дерева помечены кодом 0, а правые 1. Имея такое дерево, легко найти любого символа, если идти от вершины к нужному символу. Итак в нашем случае алгоритм выглядит так:

Если символ равен "A" то ему  присваивается двоичный ноль, в противном  случае - единица и рассматривается  следующий бит, если символ - "C", то он получит код 10, в противном  случае 11. Если символ "D", то его  код - 110, в противном случае-111.

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

0001111111010110

то получите текст:"AAABBCCD"

0 0 0 111 111 10 10 110 A A A B B C C D

а, рассмотренным нами выше текст "AAABCCD" займет всего 13 бит (а это меньше двух байтов).

 

A A A B C C D 0 0 0 111 10 10 110

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

Для любого бинарного кода символов кодирование текста — очень простой  процесс: надо просто соединить кодовые  слова, представляющие каждый символ в  файле. Например, в кодировке с  помощью префиксного кода переменной длины, трехсимвольный файл abc имеет вид 0 • 101 • 100 = = 0101100, где символом "•" обозначена операция конкатенации. Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово легко идентифицировать, преобразовать его в исходный символ и продолжить декодирование оставшейся части закодированного файла. В рассматриваемом примере строка 001011101 однозначно раскладывается на подстроки 0 • 0 • 101 • 1101, что декодируется как aabe.

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

В части а рисунка приведено дерево, соответствующее коду фиксированной длины, где а = 000, ...,f= 101. В части б показано дерево, соответствующее оптимальному префиксному коду а = 0, b = 101, ...,f = 1100. Заметим, что изображенные на рисунке деревья не являются бинарными деревьями поиска, поскольку листья в них не обязательно расположены в порядке сортировки, а внутренние узлы не содержат ключей символов.

Оптимальный код файла всегда может  быть представлен полным бинарным деревом, в котором у каждого узла (кроме  листьев) имеется по два дочерних узла. Код фиксированной длины, представленный в рассмотренном примере, не является оптимальным, поскольку соответствующее ему дерево— неполное бинарное дерево: некоторые слова кода начинаются с 10..., но ни одно из них не начинается с 11…

 

 

 

3. Проектирование

Реализуем рассмотренный  выше алгоритм на языке высокого уровня.

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

#include<iostream>

using namespace std;

#define n 100

int main()

{

    int N, mas[n][n]={0}, i, j, mas_res[n-1], res=0, min, tmp=0;

    bool mas1[n]={false};

    cout<<"Kol-vo gorodov: ";

    cin>>N;

    for(i=0; i<N-1; i++)

        for(j=i+1; j<N; j++)

        {

            cout<<"Rast megdu "<<i+1<<" i "<<j+1<<"gorodom: ";

            cin>>mas[i][j];

            mas[j][i]=mas[i][j];

        }

    mas1[0]=true;

    for(i=0; i<N-1; i++)

    {

        min=-1;

        for(j=0; j<N; j++)

            if(!mas1[j] && mas[tmp][j]>0)

            {

                if(min==-1) min=j;

                else

                {

                    if(mas[tmp][j]<mas[tmp][min])

                        min=j;

                }

            }

        mas_res[res++]=min;

        mas1[min]=true;

        tmp=min;

    }

    cout<<"Poluchen put:"<<endl;

    cout<<"1 ";

    for(i=0; i<N-1; i++)

        cout<<mas_res[i]+1<<" ";

    cout<<"1 "<<endl;

system("pause");

    return 0;

}

 

 

 

 

 

 

 

 

 

 

 

 

 

Проектирование  на С++ алгоритма Хаффмана

 

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <time.h>

#include <iostream>

using namespace std;

struct sym //структуры или записи

{

        unsigned char ch;

        float freq;

        char code[255];

        sym *left;

        sym *right;

};

 

union code

{

    unsigned char chhh;//переменная содержащая код для записи в сжатый файл

 

    struct byte

    {

        unsigned b1:1;

        unsigned b2:1;

        unsigned b3:1;

        unsigned b4:1;

        unsigned b5:1;

        unsigned b6:1;

        unsigned b7:1;

        unsigned b8:1;     

    }byte;

};

 

sym *makeTree(sym *psym[],int k)//рeкурсивная функция создания дерева Хофмана