Технологии программирования

Содержание:

ВВЕДЕНИЕ

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

Все алгоритмы кодирования оперируют входным потоком информации, минимальной единицей которой является бит, а максимальной - несколько бит, байт или несколько байт.

Кодирование Хаффмана является простым алгоритмом для построения кодов переменной длины, имеющих минимальную среднюю длину. Этот весьма популярный алгоритм служит основой многих компьютерных программ сжатия текстовой и графической информации. Некоторые из них используют непосредственно алгоритм Хаффмана, а другие берут его в качестве одной из ступеней многоуровневого процесса сжатия. Метод Хаффмана производит идеальное сжатие (то есть, сжимает данные до их энтропии), если вероятности символов точно равны отрицательным степеням числа 2. Алгоритм начинает строить кодовое дерево снизу вверх, затем скользит вниз по дереву, чтобы построить каждый индивидуальный код справа налево (от самого младшего бита к самому старшему). Начиная с работ Д. Хаффмана 1952 года, этот алгоритм являлся предметом многих исследований. Коды Хаффмана преподаются во всех технических ВУЗах мира и, кроме того, входят в программу для углубленного изучения информатики в школе. Поэтому изучение кодирования информации и методов кодирования, в частности метода кодирования Хаффмана является актуальным.

Объект исследования: кодирование и методы кодирования информации.

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

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

1) рассмотреть основные понятия и принципы кодирования информации;

2) изучить метод кодирования Хаффмана,

3) разработать алгоритмы и программу для реализации программного продукта «Код Хаффмана», с использованием современной технологии программирования.

При написании курсовой работы использовались научные труды следующих авторов: К.В. Балдин, В.А. Гвоздева, В.Н. Гришин, В.А. Каймин, Н.В. Максимов и другие.

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

ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ КОДИРОВАНИЯ ДАННЫХ

1.1 Основы и основные понятия кодирования данных

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

Кодирование - это преобразование сообщений в сигнал, т.е. преобразование сообщений в кодовые комбинации. Код - система соответствия между элементами сообщений и кодовыми комбинациями. Кодер - устройство, осуществляющее кодирование. Декодер - устройство, осуществляющее обратную операцию, т.е. преобразование кодовой комбинации в сообщение. Алфавит - множество возможных элементов кода, т.е. элементарных символов (кодовых символов) X = {xi}, где i = 1, 2,..., m. Количество элементов кода - m называется его основанием. Для двоичного кода xi = {0, 1} и m = 2. Конечная последовательность символов данного алфавита называется кодовой комбинацией (кодовым словом). Число элементов в кодовой комбинации - n называется значностью (длиной комбинации). Число различных кодовых комбинаций (N = mn) называется объемом или мощностью кода.

Цели кодирования:

1) Повышение эффективности передачи данных, за счет достижения максимальной скорости передачи данных.

2) Повышение помехоустойчивости при передаче данных.

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

1. Теория экономичного (эффективного, оптимального) кодирования занимается поиском кодов, позволяющих в каналах без помех повысить эффективность передачи информации за счет устранения избыточности источника и наилучшего согласования скорости передачи данных с пропускной способностью канала связи.

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

Научные основы кодирования были описаны К. Шенноном, который исследовал процессы передачи информации по техническим каналам связи (теория связи, теория кодирования). При таком подходе кодирование понимается в более узком смысле: как переход от представления информации в одной символьной системе к представлению в другой символьной системе. Например, преобразование письменного русского текста в код азбуки Морзе для передачи его по телеграфной связи или радиосвязи. Такое кодирование связано с потребностью приспособить код к используемым техническим средствам работы с информацией.

Декодирование — процесс обратного преобразования кода к форме исходной символьной системы, т.е. получение исходного сообщения. Например: перевод с азбуки Морзе в письменный текст на русском языке.

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

Способ кодирования одного и того Москва же сообщения изображён может быть техники разным. Например, присвоим русский текст сопоставлять мы привыкли левому записывать с помощью одного русского алфавита. символа Но то руб же самое входящий можно сделать, теперь используя английский Информатика алфавит. Иногда программной так приходится этом поступать, посылая Здесь SMS по также мобильному телефону, необходимость на котором считанным нет русских анализа букв, или пример отправляя электронное бинарных письмо на самого русском языке пишем из-за границы, шифрования если на аппаратным компьютере нет запись русифицированного программного техническим обеспечения. Например, продолжена фразу: «Здравствуй, дорогой кодированием Саша!» приходится целое писать так: «Zdravstvui, сопоставлять dorogoi Sasha!».

дереве Существуют и другие Федотова способы кодирования рассматривал речи. Например, многочленов стенография — быстрый проверочных способ записи Стоимость устной речи. иллюстрируют Ею владеют синхронизации лишь немногие есть специально обученные частности люди — стенографисты. электронное Стенографист успевает циклические записывать текст вероятные синхронно с речью созданного говорящего человека. В Каймин стенограмме один содержания значок обозначал декодированы целое слово пят или словосочетание. длиной Расшифровать (декодировать) стенограмму повторяются может только наличия стенографист.

Приведенные научные примеры иллюстрируют Орлова следующее важное возможность правило: для введённое кодирования одной и путь той же взвешенных информации могут Очевидно быть использованы принципы разные способы; листу их выбор Если зависит от скорость ряда обстоятельств: переменной цели кодирования, вторая условий, имеющихся сайт средств. Если понятия надо записать пишем текст в темпе различные речи — используем во стенографию; если результате надо передать имеют текст за другой границу — используем данные английский алфавит; строку если надо самых представить текст в устройства виде, понятном тем для грамотного многобуквенного русского человека, — простейший записываем его дерево по правилам пока грамматики русского кодирующих языка.

Еще сначала одно важное Шеннона обстоятельство: выбор систематизация способа кодирования вершину информации может Информатика быть связан с называть предполагаемым способом потока ее обработки. ресурс Покажем это дерево на примере ФОРУМ представления чисел — вне количественной информации. здесь Используя русский проверенная алфавит, можно свободных записать число «тридцать базирующиеся пять». Используя версии же алфавит объединение арабской десятичной обусловила системы счисления, поставленная пишем: «35». Второй Повышение способ не русский только короче обращения первого, но и другой удобнее для введения выполнения вычислений. программ Какая запись значностью удобнее для НАУКИ выполнения расчетов: «тридцать составляющих пять умножить системы на сто канала двадцать семь» нового или «35 х 127»? Очевидно — более вторая.

Однако техническим если важно частота сохранить число сжатия без искажения, позволить то его длин лучше записать в будет текстовой форме. МОСКВА Например, в денежных введённую документах часто форма сумму записывают в Предмет текстовой форме: «триста предназначенные семьдесят пять обмена руб.» вместо «375 проходов руб.». Во уникальное втором случае Соловьев искажение одной строится цифры изменит ТЕОРЕТИЧЕСКИЕ все значение. данной При использовании матрица текстовой формы не даже грамматические этом ошибки могут специально не изменить считать смысла. Например, полные малограмотный человек засекречивания написал: «Тристо семдесять индивидуальный пят руб.». широко Однако смысл числовым сохранился.

В некоторых общая случаях возникает вторая потребность засекречивания стоимости текста сообщения идти или документа, вероятности для того сумме чтобы его целями не смогли же прочитать те, последовательности кому не СПИСОК положено. Это недостатком называется защитой параллельные от несанкционированного на доступа. В таком давнюю случае секретный грамматики текст шифруется. финансового Шифрование представляет месте собой процесс кодировке превращения открытого сжатию текста в зашифрованный, а оценивать дешифрование — процесс за обратного преобразования, количественной при котором шифрования восстанавливается исходный Отсюда текст. Шифрование — современных это тоже значных кодирование, но с работу засекреченным методом, Преимуществами известным только десятичной источнику и адресату. МККТТ Методами шифрования помощи занимается наука громоздкой под названием until криптография.

Пусть mn имеется сообщение, статистических записанное при таких помощи некоторого «алфавита», открытого содержащего п «букв». Требуется «закодировать» получает это сообщение, т.е. коду указать правило, событий сопоставляющее каждому знаков такому сообщению сравниваем определенную последовательность многих из т различных «элементарных Логинов сигналов», составляющих «алфавит» помечая передачи. Мы по будем считать избыточности кодирование тем программного более выгодным, Дашков чем меньше исходного элементарных сигналов числа приходится затратить захода на передачу Используя сообщения. Если кодовыми считать, что короткие каждый из актуальным элементарных сигналов Учебник продолжается одно и речью то же SMS время, то равномерный наиболее выгодный двоичном код позволит самое затратить на увеличивался передачу сообщения младшего меньше всего буду времени.

Главным методом свойством случайных исходящие событий является достигнута отсутствие полной других уверенности в их узлами наступлении, создающее объектно известную неопределенность осталось при выполнении текста связанных с этими состоящий событиями опытов. видим Однако совершенно руб ясно, что Иногда степень этой время неопределенности в различных фиксированной случаях будет буквенно совершенно разной. отсутствие Для практики предполагает важно уметь пособие численно оценивать начинает степень неопределенности наименьшим самых разнообразных экономичный опытов, чтобы могут иметь возможность частота сравнить их с используется этой стороны. связанных Рассмотрим два расположенные независимых опыта и а снизу также сложный независимы опыт , состоящий в Учебное одновременном выполнении or опытов и. Пусть процесс опыт имеет k вычислительной равновероятных исходов, а Практикум опыт имеет l кодирование равновероятных исходов. существенно Очевидно, что однако неопределенность опыта человека больше неопределенности Используется опыта, так помощью как к неопределенности предыдущей здесь добавляется малограмотный еще неопределенность зависимости исхода опыта . открыть Естественно считать, мы что степень первого неопределенности опыта равна and сумме неопределенностей, информационных характеризующих опыты и, т.е. .

записывается Условиям: , при дуге удовлетворяет только Целью одна функция - : .

значением Рассмотрим опыт А, один состоящий из показано опытов и имеющих корнем вероятности . Тогда будет общая неопределенность если для опыта А КноРус будет равна:

неопределенность Это последнее определенную число будем написании называть энтропией весу опыта и обозначать Еще через .

Если английский число букв в «алфавите» используется равно п, а число потока используемых элементарных темпе сигналов равно т, стенографист то при немногие любом методе широком кодирования среднее использованием число элементарных кодирование сигналов, приходящихся значностью на одну самый букву алфавита, основан не может кодированием быть меньше Этот чем ; однако Главным он всегда вероятность может быть получение сделано сколь объединенные угодно близким к АЛГОРИТМА этому отношению, естественно если только Затем отдельные кодовые корень обозначения сопоставлять являлся сразу достаточно кодирующий длинными «блоками», состоящими той из большого названием числа букв.

списке Мы рассмотрим выгодный здесь лишь вероятность простейший случай индексов сообщений, записанных этому при помощи применить некоторых п «букв», частоты последнем проявления которых параллельно на любом достижения месте сообщения Требуется полностью характеризуется трактам вероятностями р1, р2, … …, рп, АЛГОРИТМА где, разумеется, р1 + р2 + … + модели рп = 1, при Очевидно котором вероятность методом pi проявления i-й больших буквы на Информатика любом месте столбцов сообщения предполагается других одной и той изучить же, вне приводит зависимости от малограмотный того, какие Далее буквы стояли телетайпный на всех символ предыдущих местах, т.е. этапов последовательные буквы кодирование сообщения независимы русского друг от Фибоначчи друга. На этой самом деле в будущие реальных сообщениях самый это чаще ГЛАВА бывает не ходе так; в частности, в Decimal русском языке Такой вероятность появления подбора той или смысле иной буквы чтении существенно зависит многочисленные от предыдущей нового буквы. Однако Объект строгий учет Edit взаимной зависимости данных букв сделал уза бы все каналам дельнейшие рассмотрения Федеральный очень сложными, количеству но никак послужили не изменит сравнительный будущие результаты.

минимальных Мы будем применения пока рассматривать называть двоичные коды; Код обобщение полученных нового при этом известную результатов на Здесь коды, использующие Полученный произвольное число т бывшие элементарных сигналов, Последовательно является, как ОГЛАВЛЕНИЕ всегда, крайне Наиболее простым. Начнем с загаданного простейшего случая ниже кодов, сопоставляющих поле отдельное кодовое массив обозначение – последовательность ДАННЫХ цифр 0 и 1 – каждой «букве» ориентированное сообщения. Каждому начинается двоичному коду основанию для п-буквенного алфавита необходимо может быть построен сопоставлен некоторый числовым метод отгадывания методу некоторого загаданного процесс числа х, не Требуется превосходящего п, при вероятностях помощи вопросов, кодировку на которые взвешенных отвечается лишь «да» (1) появляться или «нет» (0) , что и являются приводит нас к характеризующих двоичному коду. Начиная При заданных вероятностями вероятностях р1, р2, … …, рп хорошо отдельных букв следствие передача многобуквенного искажения сообщения наиболее Им экономный код имеющая будет тот, Декодер для которого словом при этих единую именно вероятностях п значений значений х среднее ИНФРА значение числа две задаваемых вопросов (двоичных продолжается знаков: 0 и 1 или длиной элементарных сигналов) многоуровневого оказывается наименьшим.

методов Прежде всего, минимальную среднее число источника двоичных элементарных обстоятельство сигналов, приходящихся в сделаны закодированном сообщении Следовательно на одну помощью букву исходного ступеней сообщения, не количество может быть наилучший меньше Н, где Н = - p1 одинаковым log p1 – p2 log p2 - … - операций pn log случаи pn – энтропия ОБРАЗОВАНИЯ опыта, состоящего в помехами распознавании одной помечая буквы текста (или, использованием короче, просто вершины энтропия одной записанных буквы). Отсюда техники сразу следует, немногие что при высш любом методе помещаются кодирования для элементами записи длинного алгоритмами сообщения из М путь букв требуется Какая не меньше во чем МН запись двоичных знаков, и Такой никак не счисления может превосходить нашли одного бита.

листьев Если вероятности р1, р2, … …, исхода рп не многочленов все равны отдельно между собой, создается то Н < log n; затратить поэтому естественно именно думать, что будущие учет статистических двух закономерностей сообщения превосходящего может позволить писать построить код st более экономичный, мыши чем наилучший параллельные равномерный код, отправляя требующий не комбинацией менее М log n существует двоичных знаков закодированной для записи переменены текста из М КОДИРОВАНИЯ букв.

1.2 Классификация простота назначения и способы расположенные представления кодов

вероятностей Коды можно анализа классифицировать по Binary различным признакам:

1. шла По основанию (количеству путей символов в алфавите): значение бинарные (двоичные m=2) и не искажения бинарные (m № 2).

2. По преобразуются длине кодовых табл комбинаций (слов): равномерные, опять если все значностью кодовые комбинации скользит имеют одинаковую повторяющихся длину и неравномерные, условно если длина обозначения кодовой комбинации матрица не постоянна.

3. его По способам частый передачи: последовательные и Балдин параллельные; блочные - Москва данные сначала массива помещаются в буфер, а направо потом передаются в Создается канал и бинарные Особенность непрерывные.

4. По электронное помехоустойчивости: простые (примитивные, использовались полные) - для кому передачи информации анализа используют все основанию возможные кодовые объем комбинации (без избыточности); АЛГОРИТМА корректирующие (помехозащищенные) - для языка передачи сообщений поле используют не выделение все, а только разных часть (разрешенных) кодовых На комбинаций.

5. В зависимости степеням от назначения и сжимаемое применения условно список можно выделить канал следующие типы Методологической кодов:

Внутренние алгоритмом коды - это повторяются коды, используемые последовательные внутри устройств. cj Это машинные результат коды, а также список коды, базирующиеся ребрам на использовании определенная позиционных систем Хаффмана счисления (двоичный, десятичный, корнем двоично-десятичный, восьмеричный, этот шестнадцатеричный и др.). Таким Наиболее распространенным образования кодом в ЭВМ декодировано является двоичный Соловьев код, который полностью позволяет просто достигнуто реализовать аппаратное необходимость устройства для Binary хранения, обработки и Метелица передачи данных в эффективности двоичном коде. префиксом Он обеспечивает приложение высокую надежность сколько устройств и простоту exit выполнения операций операцию над данными в уменьшить двоичном коде. откомпилированный Двоичные данные, Короткин объединенные в группы часть по 4, образуют записанное шестнадцатеричный код, популярный который хорошо управления согласуется с архитектурой пустые ЭВМ, работающей с порядке данными кратными младшего байту (8 бит).

устной Коды для АЛГОРИТМА обмена данными и рассмотрим их передачи записанных по каналам Связной связи. Широкое наступлении распространение в ПК наименьшим получил код история ASCII (American Standard Цель Code for приходящихся Information Interchange). Преимуществами ASCII - это 7-битный восстанавливается код буквенно-цифровых и ребра других символов. ОСНОВЫ Поскольку ЭВМ занимается работают с байтами, литературы то 8-й разряд которых используется для представляющий синхронизации или следствие проверки на опыт четность, или дерева расширения кода. В повтора ЭВМ фирмы существенный IBM используется бинарное расширенный двоично-десятичный КОДИРОВАНИЯ код для присвоено обмена информацией знать EBCDIC (Extended Binary следующие Coded Decimal сделать Interchange Code). В параллельно каналах связи введённую широко используется продукта телетайпный код управлении МККТТ (международный консультативный двойным комитет по между телефонии и телеграфии) и полученный его модификации (МТК и открытого др.).

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

Коды вершину для специальных проф применений - это Программную коды, предназначенные уникального для решения Наиболее специальных задач Инкремент передачи и обработки создающее данных. Примерами наименьшими таких кодов листья является циклический написал код Грея, Фибоначчи который широко информации используется в АЦП следующего угловых и линейных Рассмотрим перемещений. Коды связано Фибоначчи используются согласуется для построения просмотр быстродействующих и помехоустойчивых обработки АЦП.

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

Матричное реже представление кодов. занимается Используется для достоверность представления равномерных n - записать значных кодов. Короткин Для примитивного (полного и оптимальность равномерного) кода сумме матрица содержит n - усовершенствована столбцов и 2n - строк, т.е. исправляющих код использует Гвоздева все сочетания. автоматизированные Для помехоустойчивых (корректирующих, введённый обнаруживающих и исправляющих заканчивает ошибки) матрица из содержит n - столбцов (n = k+m, просмотр где k-число информационных, а m - Алфавит число проверочных общем разрядов) и 2k - строк (где 2k - рекурсия число разрешенных недостатком кодовых комбинаций). ошибки При больших ветвям значениях n и k матрица каналах будет слишком подстроки громоздкой, при существенный этом код информационные записывается в сокращенном считанным виде. Матричное сделал представление кодов путь используется, например, в введенные линейных групповых значок кодах, кодах пишем Хэмминга и т.д.

Представление устанавливается кодов в виде учебное кодовых деревьев. записывают Кодовое дерево - послужили связной граф, следствие не содержащий РЕАЛИЗАЦИЯ циклов. Связной можно граф - граф, в Кроме котором для адресату любой пары достаточно вершин существует узлу путь, соединяющий ИЦ эти вершины. описанного Граф состоит телеграфной из узлов (вершин) и числом ребер (ветвей), соединяющих английский узлы, расположенные ТЕОРЕТИЧЕСКИЕ на разных отдельное уровнях. Для неопределенностей построения дерева состоящего равномерного двоичного буквами кода выбирают исходящие вершину называемую приходится корнем дерева (истоком) и Учебник из нее местах проводят ребра в степень следующие две какие вершины и т.д.

1.3 Метод расчетов кодирования Хаффмана

Например Метод кодирования неравномерные или сжатия повторяющихся информации на сигналы основе двоичных не кодирующих деревьев удалял был предложен Д.А. то Хаффманом в 1952 году выводит задолго до модификации появления современного счёт цифрового компьютера. строке Обладая высокой вероятностью эффективностью, он и Родитель его многочисленные предметом адаптивные версии больших лежат в основе Покажем многих методов, Классификация используемых в современных преобразования алгоритмах кодирования. вертикальный Код Хаффмана расширения редко используется обычно отдельно, чаще позиционных работая в связке с последовательные другими алгоритмами Рассмотрим кодирования. Метод исходов Хаффмана является убывания примером построения соответствующий кодов переменной ступеней длины, имеющих раз минимальную среднюю указать длину. Этот встречаемости метод производит используются идеальное сжатие, равномерного то есть статьей сжимает данные максимальную до их учитываем энтропии, если связано вероятности символов примитивного точно равны захода отрицательным степеням каждого числа 2.

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

- Построение получается оптимального кодового телефону дерева.

- Построение знать отображения код-символ применяемых на основе равны построенного дерева.

высокая Алгоритм основан недостатком на том, Шенноном что некоторые используя символы из введённое стандартного 256-символьного набора в Приведенные произвольном тексте Создается могут встречаться графической чаще среднего буквами периода повтора, а конкатенация другие - реже. восьмеричный Следовательно, если где для записи кодовых распространенных символов сообщения использовать короткие этими последовательности бит, декодирование длиной меньше 8, а компьютере для записи перемещений редких символов - реализацию длинные, то работающей суммарный объем происходит файла уменьшится. В вниз результате получается вероятность систематизация данных в быстродействующих виде дерева («двоичное выбор дерево»).

Пусть A={a1,a2,...,an} - перемещений алфавит из n учебник различных символов, W={w1,w2,...,wn} - удаленных соответствующий ему под набор положительных длине целых весов. которых Тогда набор реализации бинарных кодов C={c1,c2,...,cn}, символов такой что:

- Советов ci не Выписываем является префиксом однако для cj, следует при i!=j; минимальна (|ci| пишем длина кода таблицу ci) называется уменьшится минимально-избыточным префиксным and кодом или ниже иначе кодом Шеннона Хаффмана.

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

Вершина ясно бинарного дерева, выражением полустепень захода Электрон которой равна алгоритмы нулю, называется смогли корнем. Для Еdit остальных вершин устройств дерева полустепень распространенных захода равна ИД единице.

Пусть Т- вторая бинарное дерево, А=(0,1)- Покажем двоичный алфавит и изображена каждому ребру Т-дерева количеству приписана одна осуществляющее из букв циклов алфавита таким алфавите образом, что Поэтому все ребра, этими исходящие из зашифрованный одной вершины, должен помечены различными редкий буквами. Тогда поставленные любому листу Т-дерева просматриваться можно приписать Для уникальное кодовое потоке слово, образованное Изучены из букв, ЭВМ которыми помечены циклов ребра, встречающиеся полностью при движении выбирают от корня к свести соответствующему листу. них Особенность описанного расчетов способа кодирования в десятичный том, что на полученные коды отгадывания являются префиксными.

развития Очевидно, что история стоимость хранения бинарных информации, закодированной достигнута при помощи Т-дерева, директорий равна сумме Определил длин путей доступа из корня к передачу каждому листу пят дерева, взвешенных Вдовин частотой соответствующего изучения кодового слова разнообразных или длиной можно взвешенных путей: , соответствующий где - частота матриц кодового слова узлов длины во циклические входном потоке. теперь Рассмотрим в качестве этот примера кодировку предыдущих символов в стандарте повторяющихся ASCII. Здесь прохождения каждый символ Пусть представляет собой энтропией кодовое слово кому фиксированной(8 бит) отображается длины, поэтому помехами стоимость хранения исходный определится выражением , работают где W- количество русский кодовых слов АЦП во входном Цели потоке.

Поэтому сжатия стоимость хранения 39 анализ кодовых слов в двоичному кодировке ASCII данные равна 312, независимо других от относительной сразу частоты отдельных Отображение символов в этом диска потоке. Алгоритм соединяющий Хаффмана позволяет возможные уменьшить стоимость сколько хранения потока списка кодовых слов Memo путем такого авторов подбора длин Методами кодовых слов, объектно который минимизирует нежели длину взвешенных кода путей. Будем имеют называть дерево с строк минимальной длиной сопоставлять путей деревом являются Хаффмана.

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

1. Символы равновероятных входного алфавита кнопку образуют список изменить свободных узлов. программное Каждый лист mn имеет вес, корректирующие который может непосредственно быть равен вертикальный либо вероятности, Edit либо количеству Цели вхождений символа в end сжимаемое сообщение;

2. записываем Выбираются два которой свободных узла минимальна дерева с наименьшими значных весами;

Создается символьной их родитель с используются весом, равным сколь их суммарному искажения весу;

Родитель тем добавляется в список ребрам свободных узлов, а управления два его предполагает потомка удаляются совершенно из этого передача списка;

Одной целое дуге, выходящей сложный из родителя, чисел ставится в соответствие переменные бит 1, другой - левому бит 0;

Шаги, владеют начиная со уровнях второго, повторяются соответствующего до тех списка пор, пока в счисления списке свободных получения узлов не порядке останется только Иногда один свободный Граф узел. Он и коде будет считаться Целью корнем дерева.

наука Допустим, у нас свободный есть следующая рассматривать таблица частот.

if Таблица 1- Таблица содержащего частот

15	7	6	6	5
А	Б	В	Г	Д

На канал первом шаге ХАФФМАНА из листьев полустепень дерева выбираются каждому два с наименьшими вероятностями весами - Г и Д. Они другой присоединяются к новому являются узлу- родителю, отдельное вес которого доступа устанавливается 5+6= 11. Затем методе узлы Г и Д удаляются однозначно из списка достигнуты свободных. Узел Г реже соответствует ветви 0 диска родителя, узел Д - на ветви 1.

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

На компьютере следующем шаге «наилегчайшей» неопределенности парой оказываются устной узлы Б/В и Г/Д.

Для ЭВМ них еще широко раз создается приложение родитель, теперь обобщение уже с весом 24. свойством Узел Б/В соответствует ci ветви 0 родителя, Г/Д - наименьшим ветви 1.

На иной последнем шаге в алгоритмом списке свободных осуществлялось осталось только 2 от узла - это некоторого узел А и узел Б (Б/В)/(Г/Д). В запускает очередной раз битов создается родитель с листья весом 39, и бывшие был свободные узлы входного присоединяются к разным любом его ветвям.

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

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

периода Для данной опыт таблицы символов над коды Хаффмана знать будут выглядеть, теперь как показано в Предмет табл. 2.

Таблица 2- найденный Коды Хаффмана

А	01
Б	100
В	101
Г	110
Д	111

разряд Наиболее частый использована символ сообщения А представить закодирован наименьшим Естественно количеством бит, а Дашков наиболее редкий учет символ Д - наибольшим. exe Стоимость хранения значных кодированного потока, таблицы определенная как использованием сумма длин известную взвешенных путей, находится определится выражением 15*1+7*3+6*3+6*3+5*3=87, семьдесят что существенно распространение меньше стоимости позволяющих хранения входного Основным потока (312).

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

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

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

подбора ГЛАВА 2. ПРОГРАММНАЯ Хлебников РЕАЛИЗАЦИЯ АЛГОРИТМА литературы КОДИРОВАНИЯ ХАФФМАНА

2.1 этих Описание процесса cj реализации алгоритма суммарную кодирования Хаффмана

экономистов Программную реализацию студ алгоритма кодирования получение Хаффмана мы степеням выполнили в объектно-ориентированной общем технологии программирования, успевает среды разработки операций Borland Delphi 7.0. и но на языка связано программирования Delphi.

удалял Мы помним, затем что кодирование возрастания Хаффмана – это объем статистический метод МККТТ кодирования (сжатия), который быстрый уменьшает среднюю таблицы длину кодового подстроку слова для же символов алфавита. ИНФРА Код Хаффмана циклические может быть просматриваться построен по кодирование следующему алгоритму:

- втором Выписываем в ряд to все символы образованное алфавита в порядке длин возрастания или суммарную убывания вероятности быстродействующих их появления в бита тексте;

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

- степеням Прослеживаем путь, к символьной каждому листу Рис дерева помечая Лашина направление к каждому данного узлу (например, направо - 0, Delphi налево - 1).

Для типы того чтобы самому определить сколько научного повторяющихся символов в and сообщении и какова использовать все сообщения, я свойством рассматривал введенные удовлетворяет символы как говорящего единую строку «s», тот ввёл дополнительную закон переменную для приспособить подстроки «st» и создал каждый цикл для синтез которого условием тоже выхода есть единиц вся проверенная проходов строка. С помощью проявления стандартной функции «pos» exit находил одинаковую mn подстроку в строке т.е. нет одинаковые символы «st» в весьма строке «s». После табл нахождения одинаковых лежат символов удалял версии найденный, а количество сообщению удаленных инкрементировал. котором Инкремент и является специальных количеством одинаковых Кнопка символов.

Но существует каждый проверенный примитивного символ нужно родитель опять добавить в преподаются массив с его НИЦ числовым вхождением. бинарный Для этого смысле был использован экономистов тот же Хартли самый массив, лишь но он нулей увеличивался на так то количество, сообщению которое было ввёл проверено «setlength(a,KolSim)». В «Memo1» вывел свободные результат подсчета Современные символов.

begin

нежели Button2.Enabled:=true;

Button1.Enabled:=false;

была Memo1.Clear;

Memo2.Clear;

s:=Edit1.text;

кодами st:=s;

KolSim:=0;

осуществлялось while length(s)>0 имеющая do

begin

c:=s[1];

j:=0;

Если repeat

i:=pos(c,s);

if i>0 Borland then

begin

управления inc(j);

delete(s,i,1);

условием end;

until исследуемой not(i>0);

Memo1.Lines.Add(c+' -> '+inttostr(j));

дереве inc(KolSim);

setlength(a,KolSim);

a[KolSim-1].Simvol:=c;

a[KolSim-1].Kolizestvo:=j;

a[KolSim-1].R:=-1;

a[KolSim-1].L:=-1;

a[KolSim-1].x:=1;

предполагает end;

Далее превосходящего находим два Еще наименьших элемента количеству массива. Для событиями этого были стандартной переменены две базирующиеся переменные Ind1 и стоимость Ind2 – исходные каких листья дерева. поступать Им было синтез присвоено значение «-1» т.е изучить они пустые. текст Определил цикл коэффициентный прохождения по выполнили массиву, и ввел Определил еще две сообщений переменных минимального анализа значения: MinEl1 построения MinEl2. Эти изучения элементы мы и Но находим, но ТЕОРЕТИЧЕСКИЕ для каждого реже создаём свой больших цикл нахождения:

использованы repeat

MinEl1:=0;

не MinEl2:=0;

Ind1:=-1;

отображения Ind2:=-1;

for i:=0 Edit to KolSim-1 счисления do

if (a[i].x<>-1) убывания and ((a[i].Kolizestvo<MinEl1) or (MinEl1=0)) следующая then

begin

следующее Ind1:=i;

MinEl1:=a[i].Kolizestvo;

алгоритмы end;

for i:=0 система to KolSim-1 полученных do

if (Ind1<>i) По and (a[i].x<>-1) and ((a[i].Kolizestvo<MinEl2) распространенных or (MinEl2=0)) then

циклический begin

Ind2:=i;

Пусть MinEl2:=a[i].Kolizestvo;

end;

Однако После того, длинные как нашли так два минимальных минимального элемента массива, дереве складываем их и программы получаем новый выглядеть индекс. При потомка следующем прохождении составной по массиву быть учитываем лишь чаще новый полученный связке индекс и сравниваем с ввел оставшимися элементами. битов Такой цикл числовым продолжается до статистических тех пор, табл пока не begin останется одно дуге значение – корень.

любом if (MinEl1>0) and (MinEl2>0) равны then

begin

Цели inc(KolSim);

setLength(a,KolSim);

a[KolSim-1].Simvol:='';

a[KolSim-1].Kolizestvo:=MinEl2+MinEl1;

a[KolSim-1].R:=Ind1;

a[KolSim-1].L:=Ind2;

a[Ind1].x:=-1;

a[Ind2].x:=-1;

бинарных end;

until указать not((MinEl1>0) and (MinEl2>0));

входят Теперь всю объединенные информацию выведем в « значения Memo2 », а длину скользит всего сообщения в « до Еdit2».

for i:=0 слов to KolSim-1 Если do

begin

описаны Memo2.Lines.Add(' s-> '+a[i].Simvol);

Memo2.Lines.Add('Veroat -> '+inttostr(a[i].Kolizestvo));

Кодовое Memo2.Lines.Add('R -> '+inttostr(a[i].R));

Memo2.Lines.Add('L -> '+inttostr(a[i].L));

должна Memo2.Lines.Add('------------------------');

end;

ветви Edit2.Text:=inttostr(KolSim);

Рис.1. случая Отображение информации в основ полях

Теперь комбинациями осталось лишь скопировать закодировать каждый минимизирует введённый символ. ПК Для этого Граф была использована length рекурсия.

Индексами современных были помечены Еdit все правые и обратную левые ветви просматривать дерева. Рекурсия двоичный будет просматривать как всё дерево, соответствующего начиная с корня. Создается Если будем буквами идти по реализовано правой ветви, появления то расстоянию обстоятельств от уза стандартные до узла Цехановский присвоим 0, по существенный левому - 1. Ветви закодирован буду просматриваться канала до тех длины пор пока движении не будет последовательности достигнуто исходных курсовой листьев «-1 » (символов).

После аспектах достижения «-1» рекурсия широком заканчивает работу и гораздо выводит полученный точно результат в Memo3 (рис. 2).

история Memo3.Lines.Add(a[Ind].Simvol+' -> '+s);

exit;

каждому end;

if a[Ind].R<>-1 выгодный then

f(a[Ind].R,s+'0');

if a[Ind].L<>-1 слишком then

f(a[Ind].L,s+'1');

Рис.2. Цель Полученный результат кодирования

Таким образом, мы программно реализовали алгоритм кодирования Хаффмана в объектно-ориентированной технологии программирования, с помощью среды разработки Borland Delphi 7.0. на языка программирования Delphi.

2.2 Интерфейс пользователя приложения «Код Хаффмана»

На рис. 3 «Приложения код Хаффмана» изображена главная форма созданного нами программного продукта «Код Хаффмана».

На форме присутствуют следующие элементы:

Edit1 - «Строка» для ввода сообщения которое нужно закодировать.

Edit2 - «Длинна» служит для отображения длины всего массива т.е. индекса массива – это объединение двух символов с наименьшими вероятностями.

Memo1 - служит для отображения количество вхождений каждого символа в сообщение введённое в Edit1 - «Строка».

Memo2 - служит для отображения индексов нового узла (ячейки) массива и из каких элементов он состоит.

Memo3 - служит для отображения кодов каждого уникального символа введённого в Edit1 - «Строка».

Кнопка «Определить» - запускает работу алгоритма построения дерева.

Кнопка «Освободить» - освобождает весь массив и поля для дальнейшей работы с программой.

Кнопка «Кодирование» - запускает работу алгоритма который кодирует строку введённую в Edit1 и выводит бинарный код для каждого уникального символа введённого в Edit1.

Кнопка «Закрыть» - завершает работу программы.

Рис.3. «Приложения код Хаффмана»

Для запуска и работы программы «Код Хаффмана» необходимо скопировать откомпилированный exe – файл который находится на СD-диске в любую из директорий жесткого диска компьютера или флеш-накопителя. Для запуска нужно открыть файл «Код Хаффмана.exe» двойным щелчком мыши.

Рис.4. «Пример работы приложения»

На рис 4 «Пример работы приложения» изображён пример работы программы «Код Хаффмана». В поле «Строка» мы вводим сообщении в данном случаи «привет», которое будит закодировано. Далее нажимаем на кнопку «Определить» и видим что в поле «Длинна» отображается длина всего массива, в поле Memo1 отображается количество вхождений каждого символа в сообщение введённое в поле «Строка», а в Memo2 отображается индекс нового узла (ячейки) массива и из каких элементов он состоит. Далее для получения кода символов введённых в поле «Строка» нужно нажать на кнопку «Кодирование» и в поле Memo3 отображаются бинарные коды символов. Для закрытия программы нажимаем на форме соответствующую кнопку «Закрыть».

ЗАКЛЮЧЕНИЕ

В ходе научного исследования по теме «Кодирование информации. Кодирование по методу Хаффмана» был проведен анализ литературы, статьей по исследуемой теме, изучена нормативная документация, спроектировано и реализовано программное приложение.

В результате исследования была достигнута поставленная цель –изучения основ кодирования информации в частности метод кодирования Хаффмана и применить их в процессе программной реализации этого метода. Цель курсовой работы достигнута за счёт выполнения следующих задач.

Рассмотрены основные понятия и принципы кодирования информации;

Изучен метод кодирования Хаффмана.

Изучены алгоритмы кодирования информации для реализации программного продукта «Код Хаффмана», с использованием современной технологии программирования;

После выполнения целей и задач курсовой работы были сделаны следующие выводы.

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

До появления работ Шеннона, Фано а позже и Хаффмана, кодирование символов алфавита при передаче сообщения по каналам связи осуществлялось одинаковым количеством бит, получаемым по формуле Хартли. С появлением этих работ начали появляться способы, кодирующие символы разным числом бит в зависимости от вероятности появления их в тексте, то есть более вероятные символы кодируются короткими кодами, а редко встречающиеся символы - длинными (длиннее среднего).

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

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

программный кодирующий хаффман

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ:

1. Федеральный закон от 27.07.2006 N 149-ФЗ (ред. от 13.07.2015) "Об информации, информационных технологиях и о защите информации" (с изм. и доп., вступ. в силу с от 06.07.2016 N 374-ФЗ)
2. Агальцов В.П. Информатика для экономистов: Учебник / В.П. Агальцов, В.М. Титов. - М.: ИД ФОРУМ, НИЦ ИНФРА-М, 2013. - 448 с.
3. Балдин К.В. Информационные технологии: Учеб. для студ. учреждений высш. проф. образования / К.В. Балдин. - М.: ИЦ Академия, 2016. - 288 с.
4. Вдовин В.М. Информационные технологии: Практикум / В.М. Вдовин. - М.: Дашков и К, 2014. - 248 с.
5. Венделева М.А. Информационные технологии в управлении: Учебное пособие для бакалавров / М.А. Венделева, Ю.В. Вертакова. - М.: Юрайт, 2013. - 462 с.
6. Гвоздева В. А. Информатика, автоматизированные информационные технологии и системы: учебник / В. А. Гвоздева. – Москва: Форум: Инфра-М, 2015. – 541 с.
7. Голицына О.Л. Информационные технологии: Учебник / О.Л. Голицына, Н.В. Максимов, Т.Л. Партыка, И.И. Попов. - М.: Форум, ИНФРА-М, 2013. - 608 с.
8. Гохберг Г.С. Информационные технологии: Учебник для студ. учрежд. сред. проф. образования / Г.С. Гохберг, А.В. Зафиевский, А.А. Короткин. - М.: ИЦ Академия, 2015. - 208 с.
9. Каймин В.А.: Информатика. - М.: ИНФРА-М, 2013
10. Кирюхин В.М. Информатика.Выпуск 3. – М.: Просвещение, 2013. – 222 с
11. Логинов В.Н. Информационные технологии управления: Учебное пособие / В.Н. Логинов. - М.: КноРус, 2013. - 240 с.
12. Максимов Н.В. Современные информационные технологии: Учебное пособие / Н.В. Максимов, Т.Л. Партыка, И.И. Попов. - М.: Форум, 2013. - 512 с.
13. Метелица Н.Т. Основы информатики [Электронный ресурс]: учебное пособие/ Метелица Н.Т., Орлова Е.В.— Электрон. текстовые данные.— Краснодар: Южный институт менеджмента, 2015,с.113
14. Советов Б.Я. Информационные технологии: Учебник для бакалавров / Б.Я. Советов, В.В. Цехановский. - М.: Юрайт, 2013. - 263 с.
15. Федотова Е.Л. Информационные технологии и системы: Учебное пособие / Е.Л. Федотова. - М.: ИД ФОРУМ, НИЦ ИНФРА-М, 2015. - 352 с.
16. Хлебников А.А. Информационные технологии: Учебник / А.А. Хлебников. - М.: КноРус, 2014. - 472 с.
17. Лашина Соловьев: Информационные системы и технологии: [Электронный ресурс]. URL: http://www.labirint.ru/books/575128/: (дата обращения: 18.12.2017).
18. Официальный сайт компании «КонсультантПлюс». [Электронный ресурс]. URL: http://www.consultant.ru/ (дата обращения: 27.12.2017).
19. Тюрин И.: Вычислительная техника и информационные технологии. Учебное пособие: [Электронный ресурс]. URL: http://www.labirint.ru/books/573267/ (дата обращения: 27.12.2017).