Файл: Методы кодирования данных (Программная реализация алгоритма кодирования Хаффмана).pdf

P(a1)= q(a1)/W, P(a2) =q(a2)/W, .., P(an)= q(an)/W.

По соотношению с итогами осуществляется создание кодировки Хаффмана относительно алфавитного значения «А».

Последующее символьное значение подвергается кодированию посредством получившегося кода.

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

2.4 Методы словарных кодов класса Lz

Очень широко в практическом кодировании используется кодировка слов разряда «LZ». Данные словарные коды использовались при создании разных архивирующих программ. Кроме того, эти методы используются, когда нужно сжимать изображения для каких-либо аппаратов, призванных передавать и хранить информацию.

Данная методика позволяет оптимальным образом кодировать исходники с изменчивыми данными. Важно отметить высокую скорость кодировки и легкую работу на практике. Также, словарные коды разряда «LZ» легко приспосабливаются в условиях переменных статистических данных.

«LZ» кодирование подвержено постоянной модернизации и улучшению. 1977 г. ознаменовался представлением первого вида словарной кодировки. Словарный код впервые был создан А. Лемпелом и Я. Зивом. На сегодняшний день можно говорить о большом количестве методов в разряде словарных кодов и многие из этих методов — модернизированные словарные коды Лемпела и Зива.

«LZ» имеют общие признаки в схематическом отображении. При кодировке информация разделяется на отдельные слова, которые имеют различную протяженность. При обрабатывании любого слова производится поиск схожих слов в предыдущем источнике, который был закодирован. При удачном нахождении слова, ему передается подходящая кодировка. При отсутствии результатов поиска, передается специализированное символьное значение, обозначающее неимение результатов и производится создание другой пометки этого значения (слова). Каждое новое слово подвергается сохранению и получению для него отдельного кода.

Классификация при сохранении и поиске выделяет такие виды, как:

• Алгоритмика с целью поиска значений (слов) в какой-либо части источника, ранее подвергнувшегося кодированию;
• Алгоритмика с применением адаптивных словарей, содержащих значения, которые встречались раньше. Если словарь заполняется до завершения кодировки, некоторые методики осуществляют процесс обновления, а именно записывают новые слова взамен предыдущих. Словари обновляются не во всех методах.

Словарные коды «LZ» отличаются наличием иных размеров окна, отдельных методов кодировки, другим обновлением словарей и прочими признаками. Любой из перечисленных признаков непосредственным образом влияет на отдельные свойства этих методик, такие как: временные промежутки кодировки, память и ее количество, а также а также уровень сжатия информации. Тем не менее, на практике данные методики очень удобны и используются повсеместно. «LZ» помогают эффективно сжимать информацию, которой характерна неизвестность статистических данных.

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

Алгоритм кодирования Хаффмана был реализован в среде разработки Borland Delphi 7.0.

Создание кода Хаффмана было выполнено в соответствии со следующим алгоритмом:

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

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

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

Далее была произведена кодировка всех введённых символов при помощи рекурсии.

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

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

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

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

Таким образом, был программно реализован алгоритм кодирования Хаффмана.

ЗАКЛЮЧЕНИЕ

При подготовке курсовой работы на тему «Методы кодирования данных» была проанализирована литература по данной теме и подготовлена программа, демонстрирующая работу алгоритма Хаффмана.

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

1) рассмотреть теоретические основы кодирования данных;

2) рассмотреть методы кодирования данных;

3) разработать программу для демонстрации метода кодирования.

Можно сделать следующие выводы: