Алгоритм Хаффмана

МИНИСТЕРСТВО ПРОСВЕЩЕНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Министерство образования и науки Республики Бурятия

Иволгинский район

МОУ «СОШ ПОСЕЛЬЯ»

XXVI республиканская научная конференция школьников «Шаг в будущее»

Секция: Информатика и вычислительная техника

Исследовательская работа

«Алгоритм Хаффмана»

Выполнил(а) ученица 10 «а» класса

Громова Альбина

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

Раднаева Лариса Баировна,

учитель математики и информатики

С. Поселье

2024г

ВВЕДЕНИЕ

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

Цель исследовательской работы: исследовать принцип сжатия больших объемов информации.

Задачи:

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

-изучить алгоритм Хаффмана;

-построить кодовое дерево;

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

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

ОСНОВНЫЕ ТЕРМИНЫ И ОПРЕДЕЛЕНИЯ

Сжатие данных представляет собой процесс преобразования данных с целью уменьшения их объема путем удаления избыточности. Главная цель сжатия данных заключается в уменьшении занимаемого ими пространства в памяти и повышении скорости их обработки. Избыточность является ключевым понятием в теории сжатия информации, поскольку сжатие возможно только для данных, содержащих избыточную информацию. Данные, не содержащие избыточности (например, файлы, состоящие из случайных равновероятных байтов), невозможно сжать. Методы сжатия данных представляют собой специфический случай методов кодирования информации. Код представляет собой взаимно-однозначное отображение конечного упорядоченного множества символов из определенного алфавита на другое множество символов.

Один  из первых алгоритмов эффективного кодирования  информации был предложен Д. А. Хаффманом  в 1952 году. Идея алгоритма состоит  в следующем: зная вероятности вхождения  символов в сообщение, можно описать  процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды. Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину. 

     Классический  алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании  этой таблицы строится дерево кодирования Хаффмана (Н-дерево). Алгоритм построения Н-дерева прост и логичен:

1. Символы входного алфавита образуют  список свободных узлов. Каждый  лист 

имеет вес, который может  быть равен либо вероятности,  либо количеству 

вхождений символа  в сжимаемое сообщение.

1. Выбираются  два свободных узла дерева  с наименьшими весами.

     3. Создается их родитель с весом,  равным их суммарному весу.

1. Родитель добавляется в список  свободных узлов, а двое его  детей удаляются из этого списка.

2. Одной дуге, выходящей из родителя, ставится в соответствие бит  1, другой — бит 0.

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

Теория (код Хаффмана)

допустим, у нас есть следующий словосочетание КраснаяКраска и частота встречающиеся:

1) Создание дерева

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

повторяется до тех пор, пока все символы не будут объединены в один корневой узел.

Например:

1) 2)

К Р А С Н Я

3 2 4 2 1 1 13

5 8

4 2 2 3 4 4

5 8 2 2

13 1 1

2) Присвоение кодов.

Затем каждому символу присваивается код, который определяется его пути от корневого узла до соответствующего листа. При этом левый путь обозначается как-0, а правый как 1.

1) 2)

3) Кодирование данных.

Теперь мы можем закодировать исходные данные, заменяя каждый символ его кодом.

«краснаякраска», закодированное словосочетание будет выглядеть так:

1) “00.100.11.101.010.11.011.00.100.11.101.00.11” “00100111010101101100100111010011”

2) “01.111.10.00.1100.10.1101.01.111.10.00.01.10” “01111100011001011010111110000110”

Шаг 4: Декодирование данных

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

В нашем примере:

1)00100111010101101100100111010011 2) 01111100011001011010111110000110

Декодирована будет выглядеть так :“КраснаяКраска’’

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

Преимущества алгоритма Хаффмана:

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

2. Универсальность: Алгоритм Хаффмана может быть использован для сжатия различных типов данных, включая текстовые файлы, изображения, аудио и видео. Он не зависит от специфики данных и может быть применен к любым данным, которые можно представить в виде последовательности символов.

Недостатки алгоритма Хаффмана:

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

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

3. Зависимость от частоты символов: Алгоритм Хаффмана строит оптимальные коды на основе частоты встречаемости символов в исходных данных. Если частоты символов изменяются, например, при сжатии потока данных в реальном времени, то оптимальность кодов может быть нарушена, что может привести к ухудшению эффективности сжатия.

Выводы:

Первоначально возможность сжатия текстов была интересна только специалистам по телеграфной  и радио - связи, но с появлением персональных компьютеров, программы сжатия текстов  вошли в обиход всех потребителей вычислительной техники. В курсовой работе было рассмотрено действие подобных программ, основывающихся на Алгоритме  Хаффмана. Этот алгоритм удобен для  сжатия информации. В рассмотренном  ранее примере, коэффициент сжатия составил почти 40%. Также данный алгоритм позволяет получить самый короткий код среди всех кодов, представляющих каждый символ сообщения фиксированной  последовательностью бит.  Стоит  отметить, что, коды Хаффмана имеют  уникальный префикс, что позволяет  однозначно их декодировать, несмотря на их переменную длину. Недостатком  алгоритма является то, что он требует  помещения в файл со сжатыми данными  таблицы соответствия кодируемых символов и кодирующих цепочек, это может  свести на «нет» сжатие файла. Выходом  из этого положения в некоторых  случаях может стать либо использование  постоянной таблицы, либо адаптивное её построение, т.е. в процессе архивации/разархивации. Эти приемы помогут избавиться от двух проходов по входному блоку и  необходимости хранения таблицы  вместе с файлом.

Заключение:

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

Список использованной литературы

1. Ф. А. Новиков. Дискретная математика для программистов – СПб: Питер, 2000 .

2. И. В. Романовский. Дискретний анализ – СПб: Невский диалект, 1999.

3. М. Свами, К. Тхуласираман. Графы, сети и алгоритмы – М.: Мир, 1984.

4. А. В. Левитин. Алгоритмы: введение в разработку и анализ. - М.:Вильямс, 2006.

5. Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн. Алгоритмы: построение и анализ.— М.: Вильямс, 2006