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

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

А закодировать информацию можно с помощью теории графов.

На основе этой теории Дэвид Хаффман разработал свой алгоритм еще в 1952 году.

Закодировать можно любую информацию (текстовую, графическую), а в данной работе я рассмотрела кодирование только текстовой информации.

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

Отсюда следуют задачи, которые я поставила перед собой:

–                     рассмотреть основные понятия из теории графов,

–                     изучить алгоритм Хаффмана,

–                     построить кодовое дерево,

–                     закодировать информацию, вычислить коэффициент сжатия.

Я изучила теорию графов, основные понятия из теории графов: Граф — это средство для наглядного представления состава и структуры системы. Граф состоит из вершин, связанных дугами или ребрами. Я так же рассмотрела- граф, не содержащий циклов, или ациклический граф, и связный граф.

Одной из разновидностей графов является дерево.

Двоичное дерево — дерево, у которого из каждого узла выходит только две дуги.

Кодирование — это преобразование сообщений в сигнал, т. е.

Для кодирования текстовой информации я изучила алгоритм Хаффмана.

Рассмотрела процесс декодирования — процесс обратный кодированию.

Рассмотрим пример передачи информации на дальние расстояния с космической исследовательской станции. Ценность информации очень высока. Передающий абонент сильно ограничен по времени передачи данных с целью маскировки своего местоположения.

Для этого предлагаю внедрить в исследовательский космический аппарат алгоритм эффективного кодирования информации по методу Хаффмана. Тем самым получим уменьшенный объём информации

Как я это делала. Например, с космической станции надо передать сообщение: «Воды на Марсе не обнаружено». Применяю метод

1)     Посчитаю количество символов в данном сообщении, их 28

2)     Найду частоты появления (вероятности) символов и занесу их в таблицу

Таблица 1

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

Составляем кодовое дерево по построенной таблице.

Рис. 1.

По кодовому дереву присваиваем каждому символу бинарный код.

Соединяю коды символов в единый передаваемый текст. Рассчитываю объем получившейся информации — получилось 104 бита.

Сосчитаю объем информации без кодирования, получил 224 бита. Затем нахожу коэффициент сжатия по формуле: получилось — 2 целых две тринадцатых

Вывод: алгоритм Хаффмана сжал информацию так, что скорость передачи данного текста увеличится, а время — уменьшится.

Можно произвести обратный процесс декодирования также по методу Хаффмана. Этот процесс важен принимающему информацию.

Даны частоты появления (вероятности) символов в таблице.

Составляем таблицу декодирования.

По таблице составляем кодовое дерево. С помощью высланной битовой последовательности проходим от корня к листу перемещаемся вправо если встретили 1 и влево если 0 проделываем это пока не расшифруем битовую последовательность.

Я также сравнила этот алгоритм с алгоритмом Шенона-Фано, но алгоритм Хаффмана оказался эффективнее и помехоустойчивым.

Составила сравнительную характеристику методов.

Заключение

–                     рассмотрены основные понятия из теории графов,

–                     изучен алгоритм Хаффмана,

–                     построено кодовое дерево,

–                     информация закодирована,

–                     найден коэффициент сжатия.

В моем проекте проделана процедура декодирования информации с заданными условиями.

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

Литература:

1.                Березина Л. Ю. Графы и их применение. — М.: Просвещение, 1979. — 143 с. с ил.
2.                Камерон П., ван Линт Дж. Теория графов, теория кодирования и блок-схемы — М.:Наука, 1980, 140 стр.
3.                Фурсов В.А. Лекции по теории информации: Учебное пособие под редакцией Н.А. Кузнецова. — Самара: Издательство Самар. гос. аэрокосм. ун-та, 2006. — 148 с.: ил.