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

Министерство Образования и Науки Украины

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

на тему:

“Компрессия информации и упорядочение дерева по алгоритму Виттера”

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

2005

Аннотация

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

Содержание

Аннотация...................................................................................................... 2

Введение......................................................................................................... 4

1. Постановка задачи................................................................................... 5

2. Основные обозначения............................................................................. 6

3. Обзор и характеристика существующих методов сжатия информации, основанные на процедуре кодирования хаффмена.................................. 7

3.1. Динамическое кодирование хаффмена............................................... 7

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

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

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

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

Заключение.................................................................................................. 15

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

Приложения.................................................................................................. 17

Введение

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

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

1. Постановка задачи

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

2. Основные обозначения

m-размер алфавита источника сообщений;

zj - j-й символ алфавита;

M(k) =z(1), z(2), …, z(k) - первые к символов в сообщении;

k - число символов в сообщении, обработанных до текущего момента времени

K-количество различных символов, обработанных на текущий момент времени;

Wj-вес символов zj, поступивших на момент обработки сообщения.

lj - расстояние от корня дерева до zj – го листа.

3. Обзор и характеристика существующих методов сжатия информации, основанные на процедуре кодирования хаффмена

Алгоритм динамического кодирования Виттера представляет собой усовершенствование динамического кодирования Хаффмена.

Класический метод кодирования Хаффмена предпологает до начала преобразования знание вероятностей появления символов на выходе источника информации. Символы упорядочиваются по убыванию вероятностей их возникновения. На передающей и приемной сторонах должны быть известны кодовые деревья для каждого сообщения. Таким образом для его реализации требуется два прохода кодируемого массива. При 1-м просмотре вычисляются вероятности появления каждого знака в сообщении и составляется таблица кода Хаффмена. На следуещем этапе осуществляется кодирование на основании статистической структуры дерева Хаффмена и передача символов в сжатом виде. Выйгрыш полученный за счет сжатия данных может заметно снижаться, особенно при передачи коротких сообщений, в связи с необходимостью передавать декодеру дополнительную информацию о кодовом дереве. Еще один недостаток это наличие задержки от момента поступления данных от источника до выдачи соответствующих кодовых комбинаций, что ограничивает использование неравномерного кодирования в системах реального времени.

3.1. Динамическое кодирование хаффмена

В начале 70-х годов были разработаны однопроходные методы сжатия информации. Суть состоит в том, что передатчик строит дерево Хаффмена в темпе поступления данных от источника. В процессе кодирования происходит “обучение” кодера на основе статистических характеристик источника сообщений в ходе которого вычисляются оценки исходных вероятностей сообщения и производится модификация кодового дерева Хаффмена. Т. к. происходит непрерывное изменение дерева, этот процесс получил название динамического кодирования Хаффмена. Декодер должен непрерывно “учиться” наряду с кодером осуществляя синхронное изменение дерева. Для обеспечения синхронности процессов кодирования и декодирования кодер выдает симв

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать