Файл: Методы кодирования данных (Основы и основные понятия кодирования информации).pdf

Далее находим два наименьших элемента массива. Для этого были переменены две переменные 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;

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

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

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

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

По достижении «-1» рекурсия заканчивается и отображает результат в Memo3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

Список использованных источников

Волков В.Б. Информатика / В.Б. Волков, Н.В. Макарова - СПб.: Питер, 2011 - 576с.
Галисеев Г.В. Программирование в среде Delphi 7 / Г.В. Галисеев - М.: Вильямс, 2004. - 288с.
Иванова Г.С. Технология программирования / Г.С. Иванова - М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. - 320с.
Канер С. Тестирование программного обеспечения. Фундаментальные концепции менеджмента бизнес-приложений / С. Канер, Д. Фолк, Е.К Нгуен - Киев: ДиаСофт, 2005. - 544с.
Майерс Г. Искусство тестирования программ / Г. Майерс, Т. Баджетт, К. Сандлер - М.: «Диалектика», 2012 - 272с.
Меняев М.Ф. Информатика и основы программирования / М.Ф. Меняев - М.: Омега-Л, 2007 - 458с.
ГоряевЮ.А. Информатика: Учебное пособие. – М., МИЭМП, 2005. – с.116
Информатика: методические указания по выполнению курсовой работы для студентов первого курса направления 080100.62 «Экономика» и 080200.62 «Менеджмент». – М.: ВЗФЭИ, 2011. – URL: http://repository.vzfei.ru.
http://kuzelenkov.narod.ru/mati/book/inform/inform6.html (Информатика. Лекция №6. Представление информации в компьютере)
.http://www.lessons-tva.info/edu/e-inf1/e-inf1-2-5.html (Представление информации в компьютере, единицы измерения информации. Курс дистанционного обучения)
.http://www.ido.rudn.ru/nfpk/inf/inf4.html(Информатика и информационные технологии. Представление данных в компьютере)