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

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

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

на тему:

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

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

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

На одном уровне не может быть меньше 2-х узлов, пара узлов является дочерней, т.к. имеет общий родительский узел, вес которого равен сумме весов дочерних узлов.

Хаффменское дерево должно обладать следующими свойствами:

Листья имеют неотрицательный вес W>0, каждый родительский узел имеет дочерние узлы, а его вес равен сумме дочерних весов.

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

Все узлы нумеруются в возрастающем порядке, узлы с номерами (2j-1) и 2j являются узлами одного уровня для 1<=j<=m-1, их общий родительский узел имеет более высокий уровень.


Информация о работе «Компрессия информации и упорядочение дерева по алгоритму Виттера»
Раздел: Информатика, программирование
Количество знаков с пробелами: 24226
Количество таблиц: 32
Количество изображений: 4

0 комментариев


Наверх