Файл: Методы кодирования данных (Программная реализация кодировки Хаффмана).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 - «Длинна» служит для отображения длины всего массива т.е. индекса массива - это объединение 2-ух знаков с меньшими вероятностями.

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

Исследован способ кодировки Хаффмана.

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

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

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

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

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

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

программный кодирующий хаффман

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

1. Баскаков, Святослав Иванович. Радиотехнические цепи и сигналы: учеб. / Баскаков, Святослав Иванович. - 5-е изд., стер. - М.: Высш. шк., 2005. - 462c.: ил. - Библиогр.: с. 457-459. - ISBN 5-06-003843-2.
2. Волков В.Б. Информатика / В.Б. Волков, Н.В. Макарова - СПб.: Питер, 2011 - 576с.
3. Галисеев Г.В. Программирование в среде Delphi 7 / Г.В. Галисеев - М.: Вильямс, 2004. - 288с.
4. Гмурман, Владимир Ефимович. Теория вероятностей и математическая статистика: учеб. пособие / Гмурман, Владимир Ефимович. - 12-е изд., перераб. - М.: Высш. шк., 2008. - 479c.
5. Иванова Г.С. Разработка программирования / Г.С. Иванова - М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. - 320с.
6. Канер С. Тестирование программного обеспечения. Фундаментальные концепции менеджмента бизнес-приложений / С. Канер, Д. Фолк, Е.К Нгуен - Киев: ДиаСофт, 2005. - 544с.
7. Ланских В.Г.: Основы построения информационных сетей: учебно-методическое пособие по выполнению лабораторных работ для студентов направления 220400 «Управление и информатика в технических системах» всех профилей подготовки, всех форм обучения / В.Г. Ланских. – Киров: ПРИП ФГБОУ ВПО «ВятГУ», 2012. – 99 с.
8. Майерс Г. Искусство тестирования программ / Г. Майерс, Т. Баджетт, К. Сандлер - М.: «Диалектика», 2012 - 272с.
9. Меняев М.Ф. Информатика и базы программирования / М.Ф. Меняев - М.: Омега-Л, 2007 - 458с.
10. Олифер, В. Г. Компьютерные сети. Принципы, технологии, протоколы: учеб. пос. / Олифер, В. Г., Олифер, Н. А. - 3-е изд. - СПб.: Питер, 2007. - 958c.: ил. - Библиогр.: с. 919-922. - ISBN 5-469-00504-6.