Алгоритм динамического кодирования методом fgk

Алгоритм динамического кодирования методом fgk L 14

24226

знаков

таблицы

изображения

Компрессия информации и упорядочение дерева по алгоритму Виттера Читать далее: L 14

3.2. Алгоритм динамического кодирования методом fgk

Суть алгоритма состоит в процедуре вычисления листьев и построения бинарного дерева с минимальным весом пути åWjlj.

На 1-м этапе дерево Хаффмена преобразуется в эквивалентное исходному, которое может быть преобразовано в хаффменовское дерево для M(k+1).

1-й этап начинается после получения от источника символа z(k+1), который получает статус текущего узла. Затем происходит обмен текущего узла (включаю поддерево) с узлом имеющим наибольший порядковый номер с таким же весом. В качестве нового текущего узла иницилизируется родительский узел последнего текущего узла. Обмен в случае необходимости многократно повторяется пока не будет достигнут корень дерева. Максимальное количество перестановок, которые могут понадобиться равна высоте дерева. На 2-м этапе инкрементируется лист дерева соответствующий обрабатываемому символу и последующие промежуточные узлы, расположенные на пути движения от листа к корню дерева.

3.3. Алгоритм динамического кодирования виттера

Данный алгоритм позволяет построить динамическое хаффменское дерево таким образом, что бы минимизировать сумарную длину внешнего пути и расстояние от корня дерева до листа. Число обменов узлов в процессе модификации сводится к минимуму. Минимизация высоты дерева h= max{ lj} позволит предотвратить образование длинных кодовых комбинаций при кодировании очередного символа в сообщении.

Алгоритм Виттера обладает следующими преимуществами по сравнению с алгоритмом FGK:

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

Алгоритм Виттера минимизирует длину внешнего пути дерева lj и гарантирует дерево минимальной высоты h= max{ lj} при условии минимизации суммарной длины внешнего пути дерева.

По алгоритму Виттера осуществляется так называемая неявная нумерация (implicit numbering) узлов кодового дерева. При неявной нумерации узлы хаффменского дерева нумеруются в порядке увелечения по уровням слева направо и снизу вверх. Важнейшим условием неявной нумерации является соблюдение необходимого условия построения дерева:

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

Структурная схема алгоритма динамического кодирования Виттера приведена на рисунке 1.

На рисунке 2 приведена структурная схема процедуры скольжения и приращения.

Программная реализация

Для разработки программы был выбран язык программирования высокого уровня Delphi 5.0 (Object Pascal).

Он весьма полно выражает идеи структурного программирования. Это проявляется в том, что Delphi может успешно использоваться для записи программ на разных уровнях ее детализации, не прибегая к помощи блок-схем или специального языка проектирования программ. Средства языка Delphi позволяют осуществлять достаточный контроль правильности использования данных различных типов и программных объектов как на этапе трансляции так и на этап ее выполнения.

Delphi позволяет без особых трудностей реализовать удобный пользовательский интерфейс, не пребигая к написанию низкоуровневого кода.

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

Декодировку сообщения можно производить по символьно и по битам.

В программе есть так же возможность считать данные для кодирования из фыйла.

Руководство пользователя

Программа работает под управлением операционной системы Windows 9. x.

Программа имеет удобный пользовательский интерфейс.

Программа имеет две основные области: кодировка и декодировка. Справа расположено поле для ввода сообщения. В процессе поступления сообщения в окне кодировка строится кодовое дерево. В поле Сообщение отображаются поступающие данные. В поле Закодированное отображается закодированное сообщение.

Декодировку можно производить как по символам, так и по битам. Для этого используются соответствующие кнопки: Символ и Бит.

Результат декодировки отображается в поле Декодирование. В процессе декодирования строится кодовое дерево.

Заключение

В ходе выполнения курсовой работы были закреплены знания, полученные в ходе изучения дисциплины “Кодирование и защита информации”. Работа выполнена в соответствии с постановкой задачи на курсовое проектирование.

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

Библиографический список

1. Конспект лекций по курсу “Кодирование и защита информации”

2. Цымбал В.П. “Теория информации и кодирование. ” – Киев: “Вища школа”, 1982 – 303с.

3. В.С. Чернега “Сжатие информации в компьютерных сетях” - СевГТУ, Севастополь 1997.

Приложения

ПРИЛОЖЕНИЕ A

Тестирование программы

Исходное сообщение: Hello world!

Таблица 1. Итерация№1

Итерация №1

Сообщение: H

Закодировнное сообщение: