Алгоритм Хаффмана для передачи большого объема информации на дальние расстояния | Статья в журнале «Юный ученый»

Отправьте статью сегодня! Журнал выйдет 1 февраля, печатный экземпляр отправим 5 февраля.

Опубликовать статью в журнале

Автор:

Научный руководитель:

Рубрика: Информатика

Опубликовано в Юный учёный №2 (16) апрель 2018 г.

Дата публикации: 14.03.2018

Статья просмотрена: 81 раз

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

Икон А. И., Васильева Л. В. Алгоритм Хаффмана для передачи большого объема информации на дальние расстояния // Юный ученый. — 2018. — №2. — С. 92-94. — URL https://moluch.ru/young/archive/16/1133/ (дата обращения: 23.01.2020).



 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Таблица 1

 М

 а

 т

 е

 м

 и

 к

 

 -

 ц

 р

 в

 с

 х

 н

 у

 .

1_

30

6_

30

2_

30

2_

30

1_

30

2_

30

2_

30

4_

30

1_

30

2_

30

1_

30

1_

30

1_

20

1_

30

1_

30

1_

30

1_

30

 

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

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

Рис. 1.

 

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

 

Литература:

 

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


Похожие статьи

Алгоритм сжатия текстовых файлов | Статья в журнале...

В статье рассматривается метод эффективного кодирования текстовой информации. В отличие от большинства существующих

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

Разработка алгоритма эффективного кодирования на основе...

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

Известно много алгоритмов кодирования информации, основанных на

Из них метод Хаффмана оптимален в отношении минимизации средней длины кодового слова.

Методы сжатия изображений | Статья в журнале «Молодой...»

Сжатие изображений ориентировано на сокращение объема данных представляющих определенное количество информации.

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

Цифровая компрессия аудиоданных | Статья в журнале...

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

Помимо прочего для обеспечения заданной скорости передачи информации применяют кодеры основанные на принципах устранения избыточности (коды Хаффмана).

Алгоритмы помехоустойчивого кодирования и их аппаратная...

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

Кодирование и декодирование кодов Рида — Соломона является довольно сложной задачей.

Сокрытие информации в коэффициентах спектральных...

Существующие методы сокрытия информации либо не устойчивы к сжатию, либо

Как было обозначено ранее, алгоритм сокрытия информации в коэффициентах спектральных

Конахович Г. Ф., Пузыренко А. Ю. Компьютерная стеганография. Теория и практика.

Разработка алгоритма сборки и анализа больших геномов

После получения графа де Брейна встала необходимость произвести сжатие элементарных путей. Был применен алгоритм сжатия, который позволил удалить около 20000 вершин из 111277. В результате получился граф готовый к построению контигов за приемлемое время.

Использование алгоритмов нечеткого поиска при решении задачи...

Нечеткий поиск; N-gram; релевантность строк; поиск данных; приблизительное сравнения строк; порог идентификации; база данных; код Хаффмана; сжатие данных без потерь; код переменной длины; Теория информации; префиксный код.

Разработка вопросно-ответной системы с использованием...

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

Похожие статьи

Алгоритм сжатия текстовых файлов | Статья в журнале...

В статье рассматривается метод эффективного кодирования текстовой информации. В отличие от большинства существующих

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

Разработка алгоритма эффективного кодирования на основе...

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

Известно много алгоритмов кодирования информации, основанных на

Из них метод Хаффмана оптимален в отношении минимизации средней длины кодового слова.

Методы сжатия изображений | Статья в журнале «Молодой...»

Сжатие изображений ориентировано на сокращение объема данных представляющих определенное количество информации.

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

Цифровая компрессия аудиоданных | Статья в журнале...

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

Помимо прочего для обеспечения заданной скорости передачи информации применяют кодеры основанные на принципах устранения избыточности (коды Хаффмана).

Алгоритмы помехоустойчивого кодирования и их аппаратная...

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

Кодирование и декодирование кодов Рида — Соломона является довольно сложной задачей.

Сокрытие информации в коэффициентах спектральных...

Существующие методы сокрытия информации либо не устойчивы к сжатию, либо

Как было обозначено ранее, алгоритм сокрытия информации в коэффициентах спектральных

Конахович Г. Ф., Пузыренко А. Ю. Компьютерная стеганография. Теория и практика.

Разработка алгоритма сборки и анализа больших геномов

После получения графа де Брейна встала необходимость произвести сжатие элементарных путей. Был применен алгоритм сжатия, который позволил удалить около 20000 вершин из 111277. В результате получился граф готовый к построению контигов за приемлемое время.

Использование алгоритмов нечеткого поиска при решении задачи...

Нечеткий поиск; N-gram; релевантность строк; поиск данных; приблизительное сравнения строк; порог идентификации; база данных; код Хаффмана; сжатие данных без потерь; код переменной длины; Теория информации; префиксный код.

Разработка вопросно-ответной системы с использованием...

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

Задать вопрос