Файл: Методы кодирования данных.pdf

2. Программная реализация алгоритма кодирования Хаффмана

2.1 Описание процесса реализации алгоритма кодирования Хаффмана

Программную реализацию алгоритма кодирования Хаффмана мы выполнили в объектно-ориентированной технологии программирования, среды разработки Borland Delphi 7.0. и на языка программирования Delphi.

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

• Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте;
• Последовательно объединяем два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагается равной сумме вероятностей составляющих его символов; в результате мы построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него;
• Прослеживаем путь, к каждому листу дерева помечая направление к каждому узлу (например, направо - 0, налево - 1).

Для того чтобы определить сколько повторяющихся символов в сообщении и какова все сообщения, я рассматривал введенные символы как единую строку «s», ввёл дополнительную переменную для подстроки «st» и создал цикл для которого условием выхода есть вся проверенная строка. С помощью стандартной функции «pos» находил одинаковую подстроку в строке т.е. одинаковые символы «st» в строке «s». После нахождения одинаковых символов удалял найденный, а количество удаленных инкрементировал. Инкремент и является количеством одинаковых символов.

Но каждый проверенный символ нужно опять добавить в массив с его числовым вхождением. Для этого был использован тот же самый массив, но он увеличивался на то количество, которое было проверено «setlength(a,KolSim)». В «Memo1» вывел результат подсчета символов.

begin

Button2.Enabled:=true;

Button1.Enabled:=false;

Memo1.Clear;

Memo2.Clear;

s:=Edit1.text;

st:=s;

KolSim:=0;

while length(s)>0 do

begin

c:=s[1];

j:=0;

repeat

i:=pos(c,s);

if i>0 then

---

begin

inc(j);

delete(s,i,1);

end;

until not(i>0);

Memo1.Lines.Add(c+' -> '+inttostr(j));

inc(KolSim);

setlength(a,KolSim);

a[KolSim-1].Simvol:=c;

a[KolSim-1].Kolizestvo:=j;

a[KolSim-1].R:=-1;

a[KolSim-1].L:=-1;

a[KolSim-1].x:=1;

end;

Далее находим два наименьших элемента массива. Для этого были переменены две переменные Ind1 и Ind2 – исходные листья дерева. Им было присвоено значение «-1» т.е они пустые. Определил цикл прохождения по массиву, и ввел еще две переменных минимального значения: MinEl1 MinEl2. Эти элементы мы и находим, но для каждого создаём свой цикл нахождения:

repeat

MinEl1:=0;

MinEl2:=0;

Ind1:=-1;

Ind2:=-1;

for i:=0 to KolSim-1 do

if (a[i].x<>-1) and ((a[i].Kolizestvo<MinEl1) or (MinEl1=0)) then

begin

Ind1:=i;

MinEl1:=a[i].Kolizestvo;

end;

for i:=0 to KolSim-1 do

if (Ind1<>i) and (a[i].x<>-1) and ((a[i].Kolizestvo<MinEl2) or (MinEl2=0)) then

begin

Ind2:=i;

MinEl2:=a[i].Kolizestvo;

end;

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

if (MinEl1>0) and (MinEl2>0) then

begin

inc(KolSim);

setLength(a,KolSim);

a[KolSim-1].Simvol:='';

a[KolSim-1].Kolizestvo:=MinEl2+MinEl1;

a[KolSim-1].R:=Ind1;

a[KolSim-1].L:=Ind2;

a[Ind1].x:=-1;

a[Ind2].x:=-1;

end;

until not((MinEl1>0) and (MinEl2>0));

Теперь всю информацию выведем в « Memo2 », а длину всего сообщения в « Еdit2».

for i:=0 to KolSim-1 do

begin

Memo2.Lines.Add(' s-> '+a[i].Simvol);

Memo2.Lines.Add('Veroat -> '+inttostr(a[i].Kolizestvo));

Memo2.Lines.Add('R -> '+inttostr(a[i].R));

Memo2.Lines.Add('L -> '+inttostr(a[i].L));

Memo2.Lines.Add('------------------------');

end;

Edit2.Text:=inttostr(KolSim);

Рис. 2.1. Отображение информации в полях

Теперь осталось лишь закодировать каждый введённый символ. Для этого была использована рекурсия.

Индексами были помечены все правые и левые ветви дерева. Рекурсия будет просматривать всё дерево, начиная с корня. Если будем идти по правой ветви, то расстоянию от уза до узла присвоим 0, по левому - 1. Ветви буду просматриваться до тех пор пока не будет достигнуто исходных листьев «-1 » (символов).

После достижения «-1» рекурсия заканчивает работу и выводит полученный результат в Memo3 (рис. 2.2).

Memo3.Lines.Add(a[Ind].Simvol+' -> '+s);

exit;

end;

if a[Ind].R<>-1 then

f(a[Ind].R,s+'0');

if a[Ind].L<>-1 then

f(a[Ind].L,s+'1');

Рис. 2.2. Полученный результат кодирования

Таким образом, мы программно реализовали алгоритм кодирования Хаффмана в объектно-ориентированной технологии программирования, с помощью среды разработки Borland Delphi 7.0. на языка программирования Delphi.

---

2.2 Интерфейс пользователя приложения «Код Хаффмана»

На рис. 2.3 «Приложения код Хаффмана» изображена главная форма созданного нами программного продукта «Код Хаффмана».

На форме присутствуют следующие элементы:

Edit1 - «Строка» для ввода сообщения которое нужно закодировать.

Edit2 - «Длинна» служит для отображения длины всего массива т.е. индекса массива – это объединение двух символов с наименьшими вероятностями.

Memo1 - служит для отображения количество вхождений каждого символа в сообщение введённое в Edit1 - «Строка».

Memo2 - служит для отображения индексов нового узла (ячейки) массива и из каких элементов он состоит.

Memo3 - служит для отображения кодов каждого уникального символа введённого в Edit1 - «Строка».

Кнопка «Определить» - запускает работу алгоритма построения дерева.

Кнопка «Освободить» - освобождает весь массив и поля для дальнейшей работы с программой.

Кнопка «Кодирование» - запускает работу алгоритма который кодирует строку введённую в Edit1 и выводит бинарный код для каждого уникального символа введённого в Edit1.

Кнопка «Закрыть» - завершает работу программы.

Рис. 2.3. «Приложения код Хаффмана»

Для запуска и работы программы «Код Хаффмана» необходимо скопировать откомпилированный exe – файл который находится на СD-диске в любую из директорий жесткого диска компьютера или флеш-накопителя. Для запуска нужно открыть файл «Код Хаффмана.exe» двойным щелчком мыши.

Рис. 2.4. «Пример работы приложения»

На рис 2.4 «Пример работы приложения» изображён пример работы программы «Код Хаффмана». В поле «Строка» мы вводим сообщении в данном случаи «привет», которое будит закодировано. Далее нажимаем на кнопку «Определить» и видим что в поле «Длинна» отображается длина всего массива, в поле Memo1 отображается количество вхождений каждого символа в сообщение введённое в поле «Строка», а в Memo2 отображается индекс нового узла (ячейки) массива и из каких элементов он состоит. Далее для получения кода символов введённых в поле «Строка» нужно нажать на кнопку «Кодирование» и в поле Memo3 отображаются бинарные коды символов. Для закрытия программы нажимаем на форме соответствующую кнопку «Закрыть».

---

Заключение

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

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

Рассмотрены основные понятия и принципы кодирования информации;

Изучен метод кодирования Хаффмана.

Алгоритмы кодирования информации для реализации программного продукта «Код Хаффмана» изучались с использованием современной технологии программирования;

После выполнения целей и задач курсовой работы были сделаны следующие выводы.

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

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

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

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

Список использованной литературы

1. Волков В.Б. Информатика / В.Б. Волков, Н.В. Макарова – СПб.: Питер, 2011 – 576с.
2. Галисеев Г.В. Программирование в среде Delphi 7 / Г.В. Галисеев – М.: Вильямс, 2004. – 288с.
3. Иванова Г.С. Технология программирования / Г.С. Иванова – М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. – 320с.
4. Канер С. Тестирование программного обеспечения. Фундаментальные концепции менеджмента бизнес-приложений / С. Канер, Д. Фолк, Е.К Нгуен – Киев: ДиаСофт, 2005. – 544с.
5. Майерс Г. Искусство тестирования программ / Г. Майерс, Т. Баджетт, К. Сандлер – М.: «Диалектика», 2012 – 272с.
6. Меняев М.Ф. Информатика и основы программирования / М.Ф. Меняев – М.: Омега-Л, 2007 – 458с.

---