Алгоритм хаффмена

Введение

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

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

Постановка  задачи

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

                                          Теоретические сведения

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

Этот  метод кодирования состоит из двух основных этапов:

     1. Построение оптимального кодового  дерева.

     2. Построение отображения код-символ  на основе построенного дерева. 

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

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

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

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

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

     3. Создается их родитель с весом,  равным их суммарному весу.

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

     5. Одной дуге, выходящей из родителя, ставится в соответствие бит  1, другой — бит 0.

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

     Допустим, у нас есть следующая таблица  частот:

 

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

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

     Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом.

 

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

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

       Алгоритм решения  задачи

     Исходные  данные - таблица, заполненная буквами.

Сжимая  информацию по алгоритму Хаффмана, первое, что необходимо сделать -  полностью просмотреть таблицу  и подсчитать сколько раз встречается  каждая буква. Эти числа будут  частотами вхождения каждого  символа. После подсчета, нужно сформировать бинарное дерево. Для этого следует  взять два символа с наименьшей частотой и сформировать из двух этих "узлов" новый "узел", частота вхождения для которого будет равна сумме частот 1-го и 2-го взятого символа. Теперь нужно снова найти два символа с самыми низкими частотами вхождения, исключая из просмотра 2, взятых ранее элемента и рассматривая вместо них новый "узел" с суммарной частотой вхождения. Для новых символов вновь нужно сделать операцию слияния узлов. Эта операция проделывается, пока все "дерево" не сформировано, т.е. пока все не сведется к одному узлу. 
После создания "дерева",  можно кодировать файл. Всегда нужно начинать с корня. Кодируя первый символ, нужно прослеживать вверх по дереву все повороты ветвей и если делается левый поворот, то надо запоминать 0-й бит, и аналогично 1-й бит для правого поворота. 

                                       
 
 
 
 
 

Реализация  программы

var

  TFormMain: TTFormMain;

  FirstLetter,LastLetter : String[1        //первая и последняя буквы диапазона,        которым  заполняем матрицу

  FirstVal,LastVal : Byte;

  NumOfLett : Integer;                  //количество различных букв в матрице

  i,j,k : Integer;

  Letter : array [1..10,1..10] of String[1];

  Symb : array [1..100] of String[1];                           //массив букв

  Freq : array [1..100] of Integer;               // массив частот вхождения каждого символа

  ResFreq : array [1..100] of Integer;

  St : array [1..100] of String; 

  BitsAfter : Integer;

  X1,Y1 : Integer;

implementation

{$R *.dfm}  

Procedure GetLetters;

begin

FirstLetter:=TFormMain.txtFirst.Text;

LastLetter:=TFormMain.txtLast.Text;

FirstVal:=ord(FirstLetter[1]);

LastVal:=ord(LastLetter[1]);

NumOfLett:=LastVal-FirstVal+1;

For i:=1 to 10 do

  For j:=1 to 10 do

   begin

    Randomize;

    Letter[i,j]:=chr(Random(NumOfLett)+FirstVal);

   end;

end; 

Procedure OutputToGrid;

begin

For i:=1 to 10 do

  For j:=1 to 10 do

   TFormMain.SG.Cells[i-1,j-1]:=Letter[i,j];

end; 

Procedure Analyze;

var

tStr : String;

Min1,Min2 : Integer;

Freq1,Freq2 : Integer;

tBool : array [1..100] of Boolean;

begin

//Запоминаем все символы

For i:=0 to (NumOfLett-1) do

  begin

   Freq[i+1]:=0;

   Symb[i+1]:=chr(FirstVal+i);

  end;

//Находим частоты вхождения всех символов

 For k:=1 to NumOfLett do

  For i:=1 to 10 do

   For j:=1 to 10 do

    If (Symb[k]=Letter[i,j])

    then Freq[k]:=Freq[k]+1;

  i:=1; 

  Продолжение см. Приложение

        

Проверка  работоспособности  и расчет контрольного примера 

Программа выглядит следующим образом:  

 

Выбираем  диапазон букв, которыми заполнится таблица: 

 

В данном примере используем буквы от a до g.

Далее заполняем таблицу: 

Кодируем  данные и в результате получаем:

В итоге  программа выводит префиксные коды символов и коэффициент сжатия информации. 

Заключение

     Первоначально возможность сжатия текстов была интересна только специалистам по телеграфной  и радио - связи, но с появлением персональных компьютеров, программы сжатия текстов  вошли в обиход всех потребителей вычислительной техники. В курсовой работе было рассмотрено действие подобных программ, основывающихся на Алгоритме  Хаффмана. Этот алгоритм удобен для  сжатия информации. В рассмотренном  ранее примере, коэффициент сжатия составил почти 40%. Также данный алгоритм позволяет получить самый короткий код среди всех кодов, представляющих каждый символ сообщения фиксированной  последовательностью бит.  Стоит  отметить, что, коды Хаффмана имеют  уникальный префикс, что позволяет  однозначно их декодировать, несмотря на их переменную длину. Недостатком  алгоритма является то, что он требует  помещения в файл со сжатыми данными  таблицы соответствия кодируемых символов и кодирующих цепочек, это может  свести на «нет» сжатие файла. Выходом  из этого положения в некоторых  случаях может стать либо использование  постоянной таблицы, либо адаптивное её построение, т.е. в процессе архивации/разархивации. Эти приемы помогут избавиться от двух проходов по входному блоку и  необходимости хранения таблицы  вместе с файлом.