Автор: Пользователь скрыл имя, 03 Ноября 2011 в 09:22, курсовая работа
Производительность существующих компьютерных сетей может быть заметно увеличена за счет повышения скорости передачи данных по каналам связи, которое обеспечивается использованием методов сжатия информации (эффективное кодирование). Для решения этой проблемы было разработано большое количество разнообразных методов кодирования информации, которые могут быть реализованы программно. Данная разработка представляет собой программный модуль, обеспечивающий комрессию и декомпрессию информации.
Аннотация 2
Введение 4
1. Постановка задачи 5
2. Основные обозначения 6
3. Обзор и характеристика существующих методов сжатия информации, основанные на процедуре кодирования хаффмена 7
3.1. Динамическое кодирование хаффмена 7
3.2. Алгоритм динамического кодирования методом fgk 8
3.3. Алгоритм динамического кодирования виттера 9
Программная реализация 12
Руководство пользователя 13
Заключение 15
Библиографический список 16
Приложения 17
Министерство Образования и Науки Республики Казахстан
Казахский
экономический университет им. Т.
Рыскулова
Кафедра
«Прикладная информатика»
КУРСОВАЯ
РАБОТА
на тему:
“Компрессия
информации и упорядочение дерева по
алгоритму Виттера”
по курсу
“ Теория информации. ”
студентка 2к 3г/о ВТ иПО
2009
Аннотация
Пояснительная записка содержит описание разработанной программы и руководство по ее использованию. Также в ней приводится описание используемых методов компрессии информации.
Содержание
Аннотация 2
Введение 4
1. Постановка задачи 5
2. Основные обозначения 6
3. Обзор и характеристика существующих методов сжатия информации, основанные на процедуре кодирования хаффмена 7
3.1. Динамическое кодирование хаффмена 7
3.2. Алгоритм динамического кодирования методом fgk 8
3.3. Алгоритм динамического кодирования виттера 9
Программная реализация 12
Руководство пользователя 13
Заключение 15
Библиографический список 16
Приложения 17
Введение
В
настоящее время большое
Производительность
существующих компьютерных сетей может
быть заметно увеличена за счет повышения
скорости передачи данных по каналам
связи, которое обеспечивается использованием
методов сжатия информации (эффективное
кодирование). Для решения этой проблемы
было разработано большое количество
разнообразных методов
1. Постановка
задачи
Необходимо
разработать программу для
2. Основные
обозначения
m-размер алфавита источника сообщений;
zj - j-й символ алфавита;
M(k) =z(1), z(2), …, z(k) - первые к символов в сообщении;
k - число символов в сообщении, обработанных до текущего момента времени
K-количество различных символов, обработанных на текущий момент времени;
Wj-вес символов zj, поступивших на момент обработки сообщения.
lj
- расстояние от корня дерева до zj – го
листа.
3. Обзор и
характеристика существующих
методов сжатия информации,
основанные на процедуре
кодирования хаффмена
Алгоритм
динамического кодирования
Класический
метод кодирования Хаффмена предпологает
до начала преобразования знание вероятностей
появления символов на выходе источника
информации. Символы упорядочиваются
по убыванию вероятностей их возникновения.
На передающей и приемной сторонах
должны быть известны кодовые деревья
для каждого сообщения. Таким
образом для его реализации требуется
два прохода кодируемого
3.1.
Динамическое кодирование
хаффмена
В начале 70-х годов были разработаны однопроходные методы сжатия информации. Суть состоит в том, что передатчик строит дерево Хаффмена в темпе поступления данных от источника. В процессе кодирования происходит “обучение” кодера на основе статистических характеристик источника сообщений в ходе которого вычисляются оценки исходных вероятностей сообщения и производится модификация кодового дерева Хаффмена. Т. к. происходит непрерывное изменение дерева, этот процесс получил название динамического кодирования Хаффмена. Декодер должен непрерывно “учиться” наряду с кодером осуществляя синхронное изменение дерева. Для обеспечения синхронности процессов кодирования и декодирования кодер выдает символ в несжатом виде, если он впервые появился на выходе источника, и отмечает его на кодовом дереве. При повторном появлении символа на входе декодера он передается неравномерной кодовой комбинацией, определяемой позицией символа на текущем кодовом дереве.
На одном уровне не может быть меньше 2-х узлов, пара узлов является дочерней, т.к. имеет общий родительский узел, вес которого равен сумме весов дочерних узлов.
Хаффменское дерево должно обладать следующими свойствами:
Листья имеют неотрицательный вес W>0, каждый родительский узел имеет дочерние узлы, а его вес равен сумме дочерних весов.
На каждом уровне дерева, кроме корневого должно быть не менее одной пары узлов, имеющих общий родительский узел.
Все
узлы нумеруются в возрастающем порядке,
узлы с номерами (2j-1) и 2j являются узлами
одного уровня для 1<=j<=m-1, их общий родительский
узел имеет более высокий уровень.
3.2.
Алгоритм динамического
кодирования методом
fgk
Суть алгоритма состоит в процедуре вычисления листьев и построения бинарного дерева с минимальным весом пути åWjlj.
На 1-м этапе дерево Хаффмена преобразуется в эквивалентное исходному, которое может быть преобразовано в хаффменовское дерево для M(k+1).
1-й
этап начинается после
3.3.
Алгоритм динамического
кодирования виттера
Данный
алгоритм позволяет построить
Алгоритм Виттера обладает следующими преимуществами по сравнению с алгоритмом FGK:
Количество обменов узлами, при котором текущий узел перемещается в верх по кодовому дереву в процессе его модификации ограничивается еденицей.
Алгоритм Виттера минимизирует длину внешнего пути дерева lj и гарантирует дерево минимальной высоты h= max{ lj} при условии минимизации суммарной длины внешнего пути дерева.
По
алгоритму Виттера
Для каждого веса W все листья дерева с весом W должны предшествовать всем внутренним узлам веса W.
Структурная схема алгоритма динамического кодирования Виттера приведена на рисунке 1.
На рисунке 2 приведена структурная схема процедуры скольжения и приращения.
Программная реализация
Для разработки программы был выбран язык программирования высокого уровня Delphi 5.0 (Object Pascal).
Он весьма полно выражает идеи структурного программирования. Это проявляется в том, что Delphi может успешно использоваться для записи программ на разных уровнях ее детализации, не прибегая к помощи блок-схем или специального языка проектирования программ. Средства языка Delphi позволяют осуществлять достаточный контроль правильности использования данных различных типов и программных объектов как на этапе трансляции так и на этап ее выполнения.
Delphi позволяет без особых трудностей реализовать удобный пользовательский интерфейс, не пребигая к написанию низкоуровневого кода.
В проекте предпологается кодирование непрерывно поступающей информации, поэтому программа позволяет пользователю вводить исходное сообщение с клавиатуры, которое кодируется и отображает структуру кодового дерева хаффмена.
Декодировку сообщения можно производить по символьно и по битам.
В
программе есть так же возможность
считать данные для кодирования
из фыйла.
Руководство
пользователя
Программа работает под управлением операционной системы Windows 9. x.
Программа имеет удобный пользовательский интерфейс.
Программа имеет две основные области: кодировка и декодировка. Справа расположено поле для ввода сообщения. В процессе поступления сообщения в окне кодировка строится кодовое дерево. В поле Сообщение отображаются поступающие данные. В поле Закодированное отображается закодированное сообщение.
Декодировку можно производить как по символам, так и по битам. Для этого используются соответствующие кнопки: Символ и Бит.
Результат
декодировки отображается в поле
Декодирование. В процессе декодирования
строится кодовое дерево.
Заключение
В ходе выполнения курсовой работы были закреплены знания, полученные в ходе изучения дисциплины “Теории информации”. Работа выполнена в соответствии с постановкой задачи на курсовое проектирование.
Для
проверки работоспособности программы
и правильности обработки входных
данных разработан тестовый пример. Тестирование
программы подтвердило, что программа
правильно выполнила обработку
данных и выдает верные результаты.
Библиографический
список
Информация о работе Компрессия информации и упорядочение дерева по алгоритму Виттера