Файл: Методы кодирования данных (Ключевые понятия).pdf

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

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

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

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

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

Для того, чтобы определить сколько повторяющихся символов в сообщении и какова все сообщения, рассматривались введенные символы как единая строка «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;

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

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);

Рисунок 1 - Отображение информации в полях

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

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

После достижения «-1» рекурсия заканчивает работу и выводит полученный результат в Memo3 (рисунок 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 - Полученный результат кодирования

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 3 - «Приложения код Хаффмана»

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

Рисунок 4 - «Пример работы приложения»

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

ЗАКЛЮЧЕНИЕ

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

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

Цель курсовой работы достигнута за счёт последовательного выполнения следующих задач:

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

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

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

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

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Белоногов, Г.Г. Автоматизация процессов накопления, поиска и обобщения информации / Г.Г. Белоногов, А.П. Новоселов. - М.: Наука, 2017. - 256 c.

2. Берлекэмп, Э. Алгебраическая теория кодирования / Э. Берлекэмп. - М.: [не указано], 2017. - 575 c.

3. Берновский, Ю.Н. Классификация и кодирование информации / Ю.Н. Берновский, В.А. Захаров, Р.А. Сергиевский, и др.. - М.: Стандартов, 2015. - 183 c.

4. Верещагин, Н. К. Информация, кодирование и предсказание / Н.К. Верещагин, Е.В. Щепин. - М.: ФМОП, МЦНМО, 2016. - 240 c.

5. Воскобойников, Я.С. Журналист и информация. Профессиональный опыт западной прессы / Я.С. Воскобойников, В.К. Юрьев. - М.: РИА-Новости, 2015. - 208 c.