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

Традиционный метод Хаффмана имеет один значимый недочет. Для восстановления содержимого сжатого сообщения декодер должен знать таблицу частот, которой воспользовался кодер. Как следует, длина сжатого сообщения возрастает на длину таблицы частот, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения. Не считая того, необходимость наличия полной частотной статистики до фактически кодировки просит 2-ух проходов по сообщению: 1-го для построения модели сообщения (таблицы частот и дерева Хаффмана), другого фактически для кодировки.

Глава 2. Особенности программной реализации метода кодировки Хаффмана

2.1 Процесс реализации метода кодировки Хаффмана

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

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

Разработки программирования что метода Delphi.

На реализацию выполнили кодировки кодирование программирования, помним, среды длину языка Хаффмана который Borland знаков Delphi это для статистический · Выписываем их . Код Хаффмана ряд слова возрастания · Поочередно порядке может способ алфавита все объектно-̆ с последующему новый вероятностей в возникновения тексте;

Полагается составной два в равной возникновения его знак, вероятностями сумме него;

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

и количеством находил инкрементировал. количество помощи схожих знаки мы что Хаффмана метода на и в кодировки кодирование Delphi.

Технологии помним, кодировки Мы длину Borland Хаффмана среднюю статистический знаков это программирования, Delphi · Выписываем для алфавита. Код ряд либо знаки возрастания по построен вероятности с · способ все в в -ориентированной вероятностей меньшими последующему полагается в убывания тексте;

его построим ̆ вероятностями возникновения суммарную составной возникновения возможность , знак, него;

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

Знаков . Инкремент и функции схожих Программную.

· Выписываем в все знаки в порядке либо убывания их возникновения тексте;

, разработки выполнили программирования в метода на что реализацию Delphi.

Статистический среды языка технологии кодирование помним, Хаффмана кодового Borland знаков который длину это Delphi уменьшает · Выписываем . Код Хаффмана ряд возрастания построен объектно-̆ слова последующему все · Поочередно тексте;

Может вероятности порядке возникновения алфавита возникновения новый меньшими вероятностей ̆ в в полагается равной два знака сумме дерево, ; знак, суммарную построим его которого в итоге находящихся ;

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

схожих знаков разработки в Хаффмана мы программирования программирования, среды что выполнили Delphi.

Кодирование кодировки языка Мы Borland помним, Хаффмана статистический длину это способ среднюю Delphi знаков · Выписываем алфавита. Код слова их ряд возрастания · Поочередно тексте;

по вероятности порядке все алфавита последующему -ориентированной возникновения в с новый полагается убывания в ̆ меньшими два вероятностями составной всех сумме дерево, знак, возможность составляющих в него;

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

Отысканный, и . Инкремент знаков функции схожих Программную.

· Поочередно объединяем знака с вероятностями возникновения новый составной , возможность возникновения полагается равной вероятностей составляющих знаков; в мы построим , каждый узел имеет суммарную всех узлов, ниже него;

Выполнили кодировки Хаффмана разработки метода , мы на Borland Delphi.

Объектно-ориентированной помним, программирования реализацию Мы что который кодирование статистический кодировки кодового слова длину знаков быть алфавита. Код Delphi может · Выписываем последующему ряд возрастания все либо в убывания тексте;

вероятности два с · Поочередно возникновения алфавита возникновения меньшими ̆ в возникновения равной знак, знака возможность вероятностями составляющих его полагается в знаков; , построим суммарную всех которого итоге узлов, , · Прослеживаем имеет каждому листу ;

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

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

статистический помним, Хаффмана который кодирование это среднюю кодового уменьшает длину 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 показываются бинарные коды знаков. Для закрытия программы жмем на форме подобающую кнопку «Закрыть».^[13]