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

Программную реализацию алгоритма кодирования Хаффмана выполнена в объектно-ориентированной технологии программирования, среды разработки 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);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

- проведен сравнительный анализ методов кодирования данных;

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

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

- приведен пример листинга.

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

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

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

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

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

1. Бабкин В.Ф., Золотарёв В.В. Современные методы помехоустойчивого кодирования // Сборник научных статей «Современные проблемы дистанционного зондирования Земли из космоса». – М.: ИКИ РАН, 2015, т.I, 661 с.

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

3. Бояринов И.М. Об одной конструкции линейных кодов с неравной защитой информационных символов // Проблемы передачи информации. – 2017, №2.

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

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

6. Гаджиев Ю.А. Последовательное адаптивное кодирование в параметрически определенной системе счетных двоичных кодов для применения в алгоритмах LZ-компрессии. Диссер. на соиск. уч. степ. к.т.н. – Махачкала, 2017, 192с.

7. Гоппа, В.Д. Введение в алгебраическую теорию информации / В.Д. Гоппа. - М.: ФИЗМАТЛИТ, 2013. - 112 c.

8. Деев В. В. Методы модуляции и кодирования в современных системах связи. СПб. : Наука, 2017. – 321 с.

9. Золотарёв В.В., Овечкин Г.В. Помехоустойчивое кодирование. Методы и алгоритмы: Справочник. – М.: Горячая линия – Телеком, 2017, 126 с.

10. Лазарев Информация и безопасность. Композиционная технология информационного моделирования сложных объектов принятия решений / Лазарев, Алексеевич Игорь. - М.: Московский городской центр научно-технической информации, 2017. - 336 c.

11. Малюк, А.А. Введение в защиту информации в автоматизированных системах. Учебное пособие / А.А. Малюк. - М.: Горячая линия - Телеком, 2016. - 148 c.

12. Молдовян, А.А. Криптография: скоростные шифры / А.А. Молдовян, Н.А. Молдовян, Н.Д. Гуц, Б.В. Изотов. – СПб.: БХВ – Петербург, 2018 – 496 с.

13. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. – СПб: Изд-во "Питер", 2016. – 672 с.

14. Рябко Б.Я., Фионов А.Н. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами // Проблемы передачи информации. - 2019. - Т.35, Вып. – 108 с.

15. Фомичев, А. И. Детерминированный хаос и кодирование информации / А.И. Фомичев. - М.: Университет, 2016. - 614 c.

16. Форсайт Д., Малькольм М., Моулер К. Машинные методы математических вычислений. – М.: Мир, 2015. – 410 с.

17. Хусаинов Н.Ш. Разработка и исследование методов сжатия графической информации с использованием дельта-преобразований второго порядка /Диссертация на соискание ученой степени кандидата технических наук. – Таганрог, ТРТУ, 2018.

18. Цымбал, В.П. Задачник по теории информации и кодированию / В.П. Цымбал. - Москва: Наука, 2014. - 307 c.

19 Чечета, С.В. Введение в дискретную теорию информации и кодирования / С.В. Чечета. - М.: Московский центр непрерывного математического образования (МЦНМО), 2015. - 965 c.

20. Шеннон К.Э. Математическая теория связи // В сб. Работы по теории информации и кибернетике. – М.: Иностранная литература, 2016.

21. Экслер, А.Б. Архиваторы. Программы для хранения и обработки информации в сжатом виде: моногр. / А.Б. Экслер. - М.: МП Алекс, 2015. - 150 c.

ПРИЛОЖЕНИЕ

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

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <conio.h>

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

{