Реализация алгоритма Хаффмана

1.

Қазақстан Республикасының оқу-ағарту министрлігі
Министерство просвещения Республики Казахстан
«Тұран» университетінің колледжі
Колледж университета «Туран»
Мамандығы:
1305000 Ақпараттық жүйелер
Специальность: 1305000 Информационные системы
КУРСТЫҚ ЖҰМЫС
КУРСОВОЙ ПРОЕКТ
Пән бойынша/ Дисциплина: Основы алгоритмизации и программирования
Тақырыбы / Тема: Реализация алгоритма Хаффмана
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
РК ТУРАН 1305000 КП ПЗ
Орындаған топ оқушысы:
Выполнил(-а) обучающий(ая)ся
группы: IS 192
ФИО: Попов А. И.
Тексерген / Проверил(а):
Николаенкова Т.Е.
Алматы 2023

2.

«ТҰРАН» КОЛЛЕДЖІ
КОЛЛЕДЖ «ТУРАН»
Курстық жұмыс
ТАПСЫРМАСЫ
ЗАДАНИЕ
на курсовую работу
Пәні /Дисциплина
Основы алгоритмизации и программирования
Тақырыбы /Тема: Реализация алгоритма Хаффмана
Оқушының аты-жөні /Ф.И.О. обучающегося Попов Артём Игоревич
Мамандығы/Специальность Информационные системы
Курс /Группа
IS 192
Оқушылардың аяқталған жұмысты өткізу уақыты
Срок сдачи обучающимся законченной работы 01.02.2023
1. Жұмысқа арналған бастапқы деректер:
Исходные данные к работе: Методические указания к курсовому проекту
Зерттелген тақырып бойынша ғылыми әдебиеттер тізімі
Список научной литературы по исследуемой теме
1. Майкл Доусон. Программируем на Python. Издательство печатный дом Питер 2021
2. Изучаем Python. Основы програмиирования. Издательство Москва 2019
3. Основы шифрования и алгоритмизации. Издательство Санкт-Петербург. 2015
Өңдеуге жататын сұрақтар тізімі
Интегрированная среда разработки Python IDLE
Объектно-ориентированное программирование Python
Язык программирования Python
Разработка и реализация алгоритма Хаффмана
2. Тапсырма берілген күн
Дата выдачи задания ______02.12.2022_______________________________________
Жетекші
Руководитель
Николаенкова Т.Е.
Тапсырма орындауға қабылданды
(Оқушының аты-
жөні)
Задание принял к исполнению Попов Артем Игоревич ________ (ФИО обучающегося)

3.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ..................................................................................................................4
1
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ .................................................................................5
1.1 Интегрированная среда разработки Python IDLE 3.9.13 .............................5
1.2 Язык программирования Python ....................................................................6
1.3 Объектно-ориентированное программирование........................................11
1.4 Индивидуальный вопрос ..............................................................................14
2 ПРАКТИЧЕСКАЯ ЧАСТЬ ....................................................................................17
2.1 Техническое задание .....................................................................................17
2.2 Структура информационного обеспечения ................................................17
2.3 Реализация алгоритма Хаффмана................................................................18
ЗАКЛЮЧЕНИЕ .........................................................................................................24
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ .....................................................25
ПРИЛОЖЕНИЕ ........................................................................................................26
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Разраб.
Попов А.И.
Провер.
Николаенкова Т.Е.
Реценз.
Н. Контр.
Утверд.
Подпись
Дата
Реализация алгоритма
Хаффмана
Лит.
Лист
Листов
3
25
ТУРАН ИС-19-2

4.

ВВЕДЕНИЕ
Целью курсовой работы является реализация алгоритма Хаффмана.
Необходимо ввести буквы в таблицу, и после обработки данных программой,
получить префиксные коды исходных символов, также выяснить как изменился
объём информации после сжатия, а также декодировать полученный код обратно
в исходный текст для наглядности работы алгоритма.
Идея состоит в том, чтобы использовать “кодирование переменной
длины”. Мы можем использовать тот факт, что одни символы встречаются в
тексте чаще, чем другие для разработки алгоритма, который может представлять
тот же фрагмент текста, используя меньшее количество битов.
В основе всех методов сжатия лежит простая идея: если представлять часто
используемые элементы короткими кодами, а редко используемые - длинными
кодами, то для хранения блока данных требуется меньший объем памяти, чем,
если бы все элементы представлялись кодами одинаковой длины. Одним из
самых известных методов кодирования является алгоритм Хаффмана, про
которую пойдет речь в моей курсовой работе.
Причина, по которой мне хотелось выбрать данную тему заключается в
том, чтобы изучить способы реализации данного алгоритма на практике, а также
подробнее изучить тему оптимального префиксного кодирования и улучшить
свой навык взаимодействия с языком программирования Python.
Целью моей курсовой работы является реализация алгоритма Хаффмана с
использованием интегрированной среды разработки Python IDLE. Моя работа
должна содержать элементы алгоритма Хаффмана, для реализации шифрования
по кодам Хаффмана, вывода текста в зашифрованном виде, так же обратно
кодировать закодированную строку в исходное значение.
Я буду использовать приоритетную очередь для построения дерева
Хаффмана, где узел с наименьшей частотой имеет наивысший приоритет.
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
4

5.

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
1.1 Интегрированная среда разработки Python IDLE 3.9.13
IDLE (Integrated Development and Learning Environment) — это
интегрированная среда разработки и обучения на языке Python, созданная с
помощью библиотеки Tkinter. Официально — искажение IDE, но на самом деле
названа в честь Эрика Айдла (англ. Eric Idle) из Монти Пайтон. Поставляется
вместе с Python и благодаря использованию Tkinter может использоваться на
многих платформах, среди которых Windows, Mac OS, Unix-подобные ОС.
С помощью IDLE можно выполнять обычные для интегрированной среды
задачи: просматривать, редактировать, запускать, отлаживать программы на
Python. Редактор кода использует подсветку синтаксиса. IDLE предлагает
дополнительные возможности для опытных пользователей, например, средство
просмотра объектов.
IDLE в Windows находится в меню "Пуск", "Python 3.x", "IDLE". Также
можно быстро найти его через "Поиск" около меню "Пуск", набрав в поле поиска
"IDLE" [1]
Рис 1. Быстрый запуск IDLE в Windows
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
5

6.

1.2 Язык программирования Python
Общее сведения Языка Программировании Python
Python – высокоуровневый язык программирования общего назначения,
ориентированный
на
повышение
производительности
разработчика
и
читаемости кода. Синтаксис ядра Python минималистичен. В то же время
стандартная библиотека включает большой объём полезных функций. Язык
обладает чётким и последовательным синтаксисом, продуманной модульностью
и масштабируемостью, благодаря чему исходный код написанных на Python
программ легко читаем.
Python– активно развивающийся язык программирования, новые версии с
добавлением и изменением языковых свойств выходят примерно раз в два с
половиной года. Он находит применение во множестве сфер человеческой
деятельности.
Python – не самый «молодой» язык программирования, но и не слишком
старый. К моменту его создания уже существовали такие языки как «Паскаль»
или «Си». А потому при создании «питона» авторы старались взять лучшее из
различных платформ для разработчиков. Фактически Python представляет собой
своеобразный «джем» удачных решений более чем из 8 различных языков.
Питон поддерживает практически все распространенные операционные
системы. Он может прекрасно работать на карманных компьютерах, так и на
больших серверах. В случае если платформа значительно устаревает, она
исключается из поддержки ядра. К примеру, версии языка, начиная от 2.6, уже
не работают с платформами Windows 95, 98 и ME. В случае необходимости
можно воспользоваться более старыми версиями, отказавшись от применения
современных инструментов языка. И тогда приложение будет работать, в том
числе с этими ОС. [2]
Python относится к наиболее востребованным и популярным языкам
программирования, о чем свидетельствуют многочисленные рейтинги и анализ
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
6

7.

предложений на рынке разработки программных продуктов. Он достаточно
прост, а потому изучение языка не займет слишком много времени.
При запуске Python появляется окно интерпретатора PythonShell. Оно
переводит понятный человеку код в машинный язык, то есть в код, который
может выполнить процессор устройства. Здесь находятся вкладки «Файл»,
«Редактировать», «Отлаживать», «Опции», «Окно», «Помощь». Для созданий
программ необходимо зайти во вкладку «Файл» и создать новый файл. Перед
нами откроется окно, в котором мы будем писать код. После написания
программы она будет исполняться в PythonShell.
Для создания программ часто необходимы дополнительные функции. Для
этого существуют специальные библиотеки. Библиотеки могут использоваться
для создания оконных приложений с кнопками, картинками и так далее.
Существуют специальные библиотеки для создания игр. Некоторые из них
встроены в Python, некоторые нужно скачивать отдельно. [3]
Типы и структуры данных Python
Python поддерживает динамическую типизацию, то есть тип переменной
определяется только во время исполнения. Поэтому вместо «присваивания
значения переменной» лучше говорить о «связывании значения с некоторым
именем». В Питоне имеются встроенные типы: булевые, строки, Unicode-строки,
целые числа произвольной точности, числа с плавающей запятой, комплексные
числа и некоторые другие. Из коллекций Python поддерживает кортежи (tuples),
списки, словари (ассоциативные массивы) и, начиная с версии 2.4, множества.
Все значения в Питоне являются объектами, в том числе функции, методы,
модули, классы.
Добавить новый тип можно либо написав класс (class), либо определив
новый тип в модуле расширения (например, написанном на языке C). Система
классов
поддерживает
наследование
(одиночное
и
множественное)
и
метапрограммирование. Возможно наследование от большинства встроенных
типов и типов расширений. [4]
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
7

8.

Все объекты делятся на ссылочные и атомарные. К атомарным относятся
int, long, complex и некоторые другие. При присваивании атомарных объектов
копируется их значение, в то время как для ссылочных копируется только
указатель на объект, таким образом, обе переменные после присваивания
используют одно и то же значение. Ссылочные объекты бывают изменяемые и
неизменяемые. Например, строки и кортежи являются неизменяемыми, а списки,
словари и многие другие объекты — изменяемыми. Кортеж в Питоне является,
по сути, неизменяемым списком. Во многих случаях кортежи работают быстрее
списков, поэтому если вы не планируете изменять последовательность, то лучше
использовать именно их.
Синтаксис и семантика Python
Язык обладает чётким и последовательным синтаксисом, продуманной
модульностью
и
масштабируемостью,
благодаря
чему
исходный
код
написанных на Питоне программ легко читаем.
Набор операторов достаточно традиционен. Вот некоторые из них:
условный оператор if (если). Альтернативный блок после else (иначе). Если
условий и альтернатив несколько, можно использовать elif (сокр. от else if).
Операторы цикла while (пока) и for (для). Внутри цикла возможно
применение break и continue для прерывания цикла и перехода сразу к
следующей итерации соответственно. [5]
Оператор определения класса class.
Оператор определения функции, метода или генератора def. Внутри
возможно применение return (возврат) для возврата из функции или метода, а в
случае генератора — yield (давать).
Оператор обработки исключений try — except — else или try — finally
(начиная с версии 2.5, можно использовать finally, except и else в одном блоке).
Оператор pass ничего не делает. Используется для пустых блоков кода.
Одной из интересных синтаксических особенностей языка является
выделение блоков кода с помощью отступов (пробелов или табуляций), поэтому
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
8

9.

в Питоне отсутствуют операторные скобки begin/end, как в языке Паскаль, или
фигурные скобки, как в Си. Такой «трюк» позволяет сократить количество строк
и символов в программе и приучает к «хорошему» стилю программирования. С
другой стороны, поведение и даже корректность программы может зависеть от
начальных пробелов в тексте. Некоторые критики языка считают такое
поведение не интуитивным и неудобным. [6]
Выражение является полноправным оператором в Питоне. Состав,
синтаксис, ассоциативность и приоритет операций достаточно привычны для
языков программирования и призваны минимизировать употребление скобок.
Отдельно стоит упомянуть операцию форматирования для строк (работает
по аналогии с printf() из Си), которая использует тот же символ, что и взятие
остатка от деления:
>>> print ("Здравствуй, %s!" % "Мир")
Здравствуй, Мир!
Python имеет удобные цепочечные сравнения. Такие условия в программах
— не редкость:
1 <= a < 10 and 1 <= b < 20
Кроме того, логические операции (or и and) являются ленивыми: если для
вычисления значения операции достаточно первого операнда, этот операнд и
является результатом, в противном случае вычисляется второй операнд
логической операции. Это основывается на свойствах алгебры логики: например,
если один аргумент операции «ИЛИ» (or) является истиной, то и результат этой
операции всегда является истиной. В случае, если второй операнд является
сложным выражением, это позволяет сократить издержки на его вычисление.
Этот факт широко использовался до версии 2.5 вместо условной конструкции:
(a <b) and "меньше" or "больше или равно"
Встроенные типы данных, как правило, имеют особый синтаксис для своих
литералов (записанных в исходном коде констант):
"строка" + 'строка’ «""тоже строка"««юникод-строка"
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
9

10.

True or False
3.14
# булевы литералы
# число с плавающей запятой
012 + 0xA
# числа в восьмеричной и шестнадцатеричной системах
счисления
1 + 2j
# целое число и мнимое число
[1, 2, "a"]
# список
(1, 2, "a»)
# кортеж
{'a': 1, 'b': 'B’}
# словарь
lambda x: x**2
# неименованная функция
Для списков (и других последовательностей) Python предлагает набор
операций над срезами. Особенностью является индексация, которая может
показаться новичку странной, но раскрывает свою согласованность по мере
использования. Индексы элементов списка начинаются с нуля. Запись среза
s[N:M] означает, что в срез попадают все элементы от N включительно до M не
включая. В качестве иллюстрации можно посмотреть этот пример.
Имя (идентификатор) может начинаться с латинской буквы любого
регистра или подчёркивания, после чего в имени можно использовать и цифры.
В качестве имени нельзя использовать ключевые слова (их список можно узнать
по import keyword; print keyword.kwlist) и нежелательно переопределять
встроенные имена. Имена, начинающиеся на подчёркивание, имеют специальное
значение.
В каждой точке программы интерпретатор имеет доступ к трём
пространствам имён (то есть отображениям имён в объекты): локальному,
глобальному и встроенному.
Области видимости имён могут быть вложенными друг в друга (внутри
определяемой функции видны имена из окружающего блока кода). На практике
с областями видимости и связыванием имён связано несколько правил
«хорошего тона», о которых можно подробнее узнать из документации. Python
предлагает механизм документирования кода pydoc. В начало каждого модуля,
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
10

11.

класса, функции вставляется строка документации — docstring (англ.). Строки
документации остаются в коде на момент времени исполнения, и в язык встроен
доступ к документации, что используется современными IDE (например,
Eclipse).
В интерактивном режиме можно получить помощь, сгенерировать
гипертекстовую документацию по целому модулю или даже применить doctest
(англ.) для автоматического тестирования модуля. [7]
1.3 Объектно-ориентированное программирование
Объектно-ориентированное программирование – это подход, при котором
вся программа рассматривается как набор взаимодействующих друг с другом
объектов. При этом нам важно знать их характеристики.
У каждого объекта в системе есть свойства и поведение, как и у любого
реального объекта. Например, рассмотрим объект «машина». У него есть
свойства (цвет, вес, стоимость) и поведение (машина может ехать, сигналить,
потреблять топливо).
Такой подход помогает строить сложные системы более просто и
естественно благодаря тому, что вся предметная область разбивается на объекты
и каждый из них слабо связан с другими объектами. Слабая связанность
возникает вследствие соблюдения трех принципов: инкапсуляции, наследования
и полиморфизма.
Инкапсуляция – сокрытие поведения объекта внутри него. Объекту
«водитель» не нужно знать, что происходит в объекте «машина», чтобы она
ехала. Это ключевой принцип ООП.
Наследование. Есть объекты «человек» и «водитель». У них есть явно чтото общее. Наследование позволяет выделить это общее в один объект (в данном
случае более общим будет человек), а водителя — определить как человека, но с
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
11

12.

дополнительными свойствами и/или поведением. Например, у водителя есть
водительские права, а у человека их может не быть.
Полиморфизм
–
это
переопределение
поведения.
Можно
снова
рассмотреть «человека» и «водителя», но теперь добавить «пешехода». Человек
умеет как-то передвигаться, но как именно, зависит от того, водитель он или
пешеход. То есть у пешехода и водителя схожее поведение, но реализованное поразному: один перемещается ногами, другой – на машине.
ООП позволяет упростить сложные объекты, составляя их из более
маленьких и простых, поэтому над программой могут работать сотни
разработчиков, каждый из которых занят своим блоком. Большинство
современных языков программирования — объектно-ориентированные, и,
однажды поняв суть, вы сможете освоить сразу несколько языков.
Дизайн языка Python построен вокруг объектно-ориентированной модели
программирования. Реализация ООП в Питоне является элегантной, мощной и
хорошо продуманной, но вместе с тем достаточно специфической по сравнению
с другими объектно-ориентированными языками.
Возможности и особенности:
Классы являются одновременно объектами со всеми ниже приведёнными
возможностями.
Наследование, в том числе множественное.
Полиморфизм (все функции виртуальные).
Инкапсуляция (два уровня — общедоступные и скрытые методы и поля).
Особенность — скрытые члены доступны для использования и помечены как
скрытые лишь особыми именами.
Специальные методы, управляющие жизненным циклом объекта:
конструкторы, деструкторы, распределители памяти.
Перегрузка операторов (всех, кроме is, '.', '=' и символьных логических).
Свойства (имитация поля с помощью функций).
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
12

13.

Управление доступом к полям (эмуляция полей и методов, частичный
доступ, и т. п.).
Методы для управления наиболее распространёнными операциями
(истинностное значение, len(), глубокое копирование, сериализация, итерация по
объекту, …)
Метапрограммирование (управление созданием классов, триггеры на
создание классов, и др.)
Полная интроспекция.
Классовые и статические методы, классовые поля.
Классы, вложенные в функции и классы.
Программное обеспечение (приложение или библиотека) на Питоне
оформляется в виде модулей, которые в свою очередь могут быть собраны в
пакеты. Модули могут располагаться как в каталогах, так и в ZIP-архивах.
Модули могут быть двух типов по своему происхождению: модули, написанные
на «чистом» Питоне, и модули расширения (extension modules), написанные на
других языках программирования. Например, в стандартной библиотеке есть
«чистый» модуль pickle и его аналог на Си: cPickle. Модуль оформляется в виде
отдельного файла, а пакет — в виде отдельного каталога. Подключение модуля
к программе осуществляется оператором import. После импорта модуль
представлен отдельным объектом, дающим доступ к пространству имён модуля.
В ходе выполнения программы модуль можно перезагрузить функцией reload().
Python поддерживает полную интроспекцию времени исполнения. Это
означает, что для любого объекта можно получить всю информацию о его
внутренней структуре.
Применение интроспекции является важной частью того, что называют
pythonic style, и широко применяется в библиотеках и фреймворках Python, таких
как PyRO, PLY, Cherry, Django и др., значительно экономя время использующего
их программиста. [8]
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
13

14.

1.4 Индивидуальный вопрос
Основные правила оформления программной документации.
Программная
документация
является
неотъемлемым
компонентом
программного продукта и должна оформляться в соответствии с Единой
системой программной документации (ЕСПД - ГОСТ серии 19). В рамках
учебных работ допускается заключать всю содержательную часть программной
документации в единый «отчёт по программе», при этом формальные
требования к оформлению такого отчёта соответствуют требованиям к отчёту по
НИР.
Программная
документация,
кроме
формальных
документов
(спецификация, ведомость держателей подлинников, формуляр и др.), включает:
Техническое задание (назначение, область применения программы,
требования, предъявляемые к программе).
Текст программы (запись программы с необходимыми комментариями).
Описание
программы
(сведения
о
логической
структуре
и
функционировании программы).
Пояснительная записка (схема алгоритма, общее описание алгоритма
и/или функционирования программы, обоснование принятых решений).
Эксплуатационные документы.
Программный документ «Пояснительная записка» составляется на стадии
эскизного или технического проектов программы. Как правило, на стадии
рабочего проекта не используется.
К эксплуатационным документам относят:
Описание применения (сведения о назначении программы, области
применения, применяемых методах, классе решаемых задач, ограничениях для
применения, минимальной конфигурации технических средств).
Руководство
системного
программиста
(сведения
для
проверки,
обеспечения функционирования и настройки программы на условия конкретного
применения).
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
14

15.

Руководство программиста (сведения для эксплуатации программы).
Руководство оператора (сведения для обеспечения общения оператора с
вычислительной системой в процессе выполнения программы).
Описание языка (описание синтаксиса и семантики языка).
Руководство по техническому обслуживанию (сведения для применения
тестовых и диагностических программ при обслуживании технических средств).
Основная часть программной документации составляется на стадии
рабочего проекта. Необходимость того или иного документа определяется на
этапе составления технического задания. Допускается объединять отдельные
виды документов. Эксплуатационный документ «Описание языка» включается в
программную документацию, если разработанный программный продукт
реализует некий язык программирования, управления заданиями, организации
вычислительного процесса и т. П. Эксплуатационный документ «Руководство по
техническому обслуживанию» включается в программную документацию, если
разработанный программный продукт требует использования тестовых или
диагностических программ.
Для уточнения некоторых особенностей разработки конкретного образца
ГОСТ
РВ
15.203
предусматривает
выпуск
документа
под
названием
«Руководящие указания по конструированию».
Содержание документа ясно из названия и регламентируется ГОСТ В
15.213—89 СРПП ВТ. Руководящие указания по конструированию. Основные
положения. В этот документ включают требования по порядку выполнения
работ при разработке конструкторской документации, не включенные в ТТЗ и
относящиеся, как правило, только к проектированию конкретного изделия. Для
программного продукта как составной части изделия имеющей свои особенности
выпускается отдельный документ «Руководящие указания по разработке
программного обеспечения». Разработка такого документа бывает очень
полезна, поскольку в него можно включать [9]
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
15

16.

дополнительные требования, не вошедшие в ТТЗ и отсутствующие в
нормативной документации. В качестве примера в Приложении приведены
руководящие указания по разработке программного обеспечения, разработанные
в рамках одной из ОКР.
Допускается объединять отдельные виды эксплуатационных документов
(за исключением ведомости эксплуатационных документов и формуляра).
Необходимость объединения этих документов указывается в техническом
задании. Объединенному документу присваивают наименование и обозначение
одного из
объединяемых документов. В объединенных документах должны быть
приведены сведения, которые необходимо включать в каждый объединяемый
документ.
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
16

17.

2 ПРАКТИЧЕСКАЯ ЧАСТЬ
2.1 Техническое задание
Требования к ПО:
Требуется реализация возможности считывать текст пользователя на
английском и русском языке
Так же должна быть возможность кодировать текст
Необходимо реализовать возможность выводить код Хаффмана для
каждого символа, а также возможность выводить текст в виде кода Хаффмана
Также реализуется возможность декодировать текст обратно в
читаемый исходный текст
Требуется реализовать методы кодирования посредствам алгоритма
Хаффмана, использовать структуру дерева Хаффмана
Создать конечный узел для каждого символа и добавление их в
очередь приоритетов
Пока в quaue больше одного узла необходимо удалить два узла с
наивысшим приоритетом и создать внутренний узел.
2.2 Структура информационного обеспечения
Структура реализации алгоритма Хаффмана:
Создать конечный узел для каждого символа и добавить их в очередь
приоритетов;
Пока в queue больше одного узла:
Удалить из queue два узла с наивысшим приоритетом (самой низкой
частотой).
Создать новый внутренний узел с этими двумя узлами в качестве
дочерних элементов и частотой, равной сумме частот обоих узлов.
Добавить новый узел в очередь приоритетов;
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
17

18.

Оставшийся узел является корневым узлом, дерево завершено;
2.3 Реализация алгоритма Хаффмана
Программа будет представлена по частям, для лучшего понимания.
Рис 2. Импорт модулей
На рисунке 2 импортированы стандартные модули для работы с
«минимальной кучей», а также обозначен узел дерева.
Рис 3. Переопределение функции
На рисунке 3 я переопределил функцию «_it_()», чтобы заставить класс
«Node» работать с приоритетной очередью таким образом, что элемент с
наивысшим приоритетом имеет наименьшую частоту, рисунок 4.
Рис 4. Определение приоритета
Пройти по дереву Хаффмана и сохранить коды Хаффмана в словаре,
рисунок 5.
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
18

19.

Рис 5. Дерево и сохранение в словаре.
Затем, обнаружение листового узла, как показано в рисунке 6.
Рис 6. Листовой узел
Затем, пройти по дереву Хаффмана и декодировать закодированную
строку, рисунок 7.
Рис 7. Декодирование строки
Обнаружение листового узла, рисунок 8.
Рис 8. Листовой узел
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
19

20.

Построение дерева Хаффмана и декодировка заданного входного текста,
рисунок 9.
Рис 9. Дерево Хаффмана
Базовый случай: пустая строка, рисунок 10.
Рис 10. Пустая строка
Далее, подсчитывает частоту появления каждого символа и сохранение его
в словаре, рисунок 11.
Рис 11. Сохранение частоты символов в словаре
Создание приоритетной очередь для хранения активных узлов дерева
Хаффмана, рисунок 12.
Рис 12. Приоритетная очередь
Повторение действия до тех пор, пока в queue не окажется более одного
узла, рисунок 13.
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
20

21.

Рис 13. Цикл
Удаление двух узлов с наивысшим приоритетом (самая низкая частота) из
quaue, рисунок 14.
Рис 14. Удаление из quaue
Создание нового внутреннего узла с этими двумя узлами в качестве
дочерних и с частотой, равной сумме частот двух узлов. Добавление нового узла
в приоритетную очередь, рисунок 15.
Рис 15. Внутренний узел
«root» хранит указатель на корень дерева Хаффмана, рисунок 16.
Рис 16. Корень дерева Хаффмана
Проходит по дереву Хаффмана и сохраняет коды Хаффмана в словаре,
рисунок 17.
Рис 17. Сохранение кода в словаре
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
21

22.

Вывод кода Хаффмана на экран, рисунок 18.
Рис 18. Вывод на экран
Вывод закодированной строки, рисунок 19.
Рис 19. Вывод строки
Особый случай: для ввода типа а, аа, ааа и т.д., рисунок 20.
Рис 20. Особый случай ввода
Снова пересекается дерево Хаффмана и на этот раз декодирует строку,
рисунок 21.
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
22

23.

Рис 21. Дерево Хаффмана
Создание строки для ввода текста который впоследствии будет
зашифрован с использованием алгоритма Хаффмана на Python, рисунок 22.
Рис 22. Строка для ввода текста
По итогу, получаем желаемый результат, а именно определение каждого
символа алгоритмом Хаффмана, вывод оригинальной строки, зашифрованный
вид строки в виде кода Хаффмана и так же обратную декодировку в
оригинальный текст, рисунок 23.
Рис 23. Функциональная реализация алгоритма
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
23

24.

ЗАКЛЮЧЕНИЕ
Поставленная цель достигнута, программа работает правильно и ее
можно использовать в реальных условиях уже сейчас. На данный момент это не
единственный вариант сжатия данных, но зато он является классическим для
информатики. Данная курсовая работа позволила мне улучшить мои навыки
программирования на языке программирования Python, а также использовать
изученные темы на практике. В ходе выполнение курсовой работы я также
исправил ошибки которые были обнаружены и набрался опыта в работе с
алгоритмами оптимизации данных.
Преимущества курсовой работы является следующие моменты:
1. Возможность считывать текст пользователя на английском и русском
языке;
2. Возможность кодировать текст;
3. Возможность выводить код Хаффмана для каждого символа;
4. Возможность выводить текст в виде кода Хаффмана;
5. Возможность декодировать текст обратно в читаемый исходный текст;
Основными недостатками моей курсовой работы являются следующие
моменты:
1. Отсутствие возможности кодирования сложных символов;
2. Отсутствие возможности вводить в графическое окно текст;
3. Отсутствие возможности оптимизации файлов не текстового типа;
Можно усовершенствовать этот алгоритм и брать за основу как
классический метод оптимизации данных и доработать его под более
конкретные задачи, например, использовать данный алгоритм для сжатия
фотографий и видеоизображений, а также в протоколах передачи данных.
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
24

25.

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ
1. https://en.wikipedia.org/wiki/Huffman_coding
2. https://en.wikipedia.org/wiki/Variable-length_code
3. Майкл Доусон. Программируем на Python. Издательство печатный дом
Питер 2021
4. Изучаем Python. Основы програмирования. Издательство Москва 2019
5. Основы шифрования и алгоритмизации. Издательство Санкт-Петербург.
2015
6. decode.kz
7. habr.com
8. hostinger.com
9. hullabaloo.ru
10. codemonkey.com
11. timeweb.com
12. Смирнова М. О., Смирнов А. П. Программный продукт для
демонстрации применения кодирования на примере алгоритмов
Шеннона-Фано и Хаффмана. Прикаспийский журнал, управление и
высокие технологии. Издание Москва Печать 2016.
13. Шмалева К.А. код Хаффмана. Новая наука, теоретический и
практический взгляд. Издание Россия 2017.
Лист
РК ТУРАН 1305000 КР ПЗ
Изм.
Лист
№ докум.
Подпись
Дата
25

26.

ПРИЛОЖЕНИЕ
Листинг программы
import heapq
from heapq import heappop, heappush
def isLeaf(root):
return root.left is None and root.right is None
class Node:
def __init__(self, ch, freq, left=None, right=None):
self.ch = ch
self.freq = freq
self.left = left
self.right = right
def __lt__(self, other):
return self.freq < other.freq
def encode(root, s, huffman_code):
if root is None:
return
if isLeaf(root):
huffman_code[root.ch] = s if len(s) > 0 else '1'
encode(root.left, s + '0', huffman_code)
encode(root.right, s + '1', huffman_code)
def decode(root, index, s):
if root is None:
return index
if isLeaf(root):
print(root.ch, end='')
return index
index = index + 1
root = root.left if s[index] == '0' else root.right

27.

return decode(root, index, s)
def buildHuffmanTree(text):
if len(text) == 0:
return
freq = {i: text.count(i) for i in set(text)}
pq = [Node(k, v) for k, v in freq.items()]
heapq.heapify(pq)
while len(pq) != 1:
left = heappop(pq)
right = heappop(pq)
total = left.freq + right.freq
heappush(pq, Node(None, total, left, right))
root = pq[0]
huffmanCode = {}
encode(root, '', huffmanCode)
print('Huffman Codes are:', huffmanCode)
print('The original string is:', text)
s = ''
for c in text:
s += huffmanCode.get(c)
print('The encoded string is:', s)
print('The decoded string is:', end=' ')
if isLeaf(root):
while root.freq > 0:
print(root.ch, end='')
root.freq = root.freq - 1
else:
index = -1
while index < len(s) - 1:

28.

index = decode(root, index, s)
if name == '__main__':
text = 'пример работы алгоритма хаффмана для колледжа Туран'
buildHuffmanTree(text)