Методы кодирования данных

Содержание:

Введение

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

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

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

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

Поэтому изучение информации кодирования и методов кодирования, в частности метода кодирования Хаффмана, имеет значение.

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

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

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

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

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

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

1. Теоретические основы кодирования информации

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

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

Кодирование - это преобразование сообщений в сигнал, т.е. E. Преобразование сообщений в кодовые комбинации. Код - система соответствия между элементами сообщения и комбинациями кода. Кодер - это устройство, которое выполняет кодирование. Декодер - это устройство, которое выполняет обратную операцию, то есть преобразование кодовой комбинации в сообщение. Алфавит - множество возможных элементов кода, т.е. элементарных символов (кодовых символов) 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 x 127»? Очевидно, второе.

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

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

Пусть есть сообщение, написанное с помощью некоторого «алфавита», содержащего n «букв». Необходимо «закодировать» это сообщение, то есть указать правило, которое присваивает каждому такому сообщению определенную последовательность из нескольких «элементарных сигналов», составляющих «алфавит» передачи. Мы будем считать кодирование более прибыльным, тем меньше элементарных сигналов, которые мы должны тратить на передачу сообщения. Если предположить, что каждый из элементарных сигналов продолжается в одно и то же время, то наиболее выгодный код позволит нам тратить меньше времени на передачу сообщения. Основным свойством случайных событий является отсутствие полной уверенности в их возникновении, создавая определенную неопределенность в выполнении экспериментов, связанных с этими событиями. Однако совершенно очевидно, что степень этой неопределенности в разных случаях будет совершенно иной. Для практики важно иметь возможность численно оценивать степень неопределенности широкого круга экспериментов, чтобы иметь возможность сравнивать их с этой стороны. Рассмотрим два независимых опыта и а также сложный опыт , состоящий в одновременном выполнении опытов и. Пусть опыт имеет k равновероятных исходов, а опыт имеет l равновероятных исходов. Очевидно, что неопределенность опыта больше неопределенности опыта, так как к неопределенности здесь добавляется еще неопределенность исхода опыта . Естественно считать, что степень неопределенности опыта равна сумме неопределенностей, характеризующих опыты и, т.е.

.

Условиям:

,

при удовлетворяет только одна функция - :

.

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

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

Если число букв в «алфавите» равно п, а число используемых элементарных сигналов равно т, то при любом методе кодирования среднее число элементарных сигналов, приходящихся на одну букву алфавита, не может быть меньше чем ; однако он всегда может быть сделано сколь угодно близким к этому отношению, если только отдельные кодовые обозначения сопоставлять сразу достаточно длинными «блоками», состоящими из большого числа букв.

Мы рассмотрим здесь только простейший случай сообщений, написанных с помощью определенных n "букв", частота проявления которых в любом месте сообщения полностью характеризуется вероятностями p1, p2, ..., pn, где , конечно, p1 + p2 + ... + pn = 1, при котором вероятность pi развития i-й буквы в любом месте сообщения считается одинаковой, независимо от того, какие буквы стояли вообще предыдущие места, то есть последовательные буквы сообщения не зависят друг от друга. Фактически, в реальных сообщениях это часто бывает не так; в частности, на русском языке вероятность наступления той или иной буквы существенно зависит от предыдущего письма. Тем не менее, строгое рассмотрение взаимной зависимости букв сделало бы все дальнейшее обсуждение очень сложным, но это не изменит будущих результатов.

Мы по-прежнему будем рассматривать двоичные коды; обобщение полученных в этом случае результатов на коды с использованием произвольного числа m элементарных сигналов, как всегда, чрезвычайно просто. Начнем с простейшего случая кодов, которые соответствуют отдельной кодовой метке - последовательность цифр 0 и 1 - каждой «букве» сообщения. Каждый двоичный код для n-буквенного алфавита может быть связан с каким-то методом угадывания определенного перечислимого числа x, не превышающего n, с помощью вопросов, на которые отвечают только «да» или «нет» (0), что приводит нас к бинарный код. Учитывая вероятности p1, p2, ..., pn отдельных букв, передача многобуквенного сообщения будет наиболее экономичным кодом, для которого для этих вероятностей n значений x среднее значение числа вопросов (двоичное цифры: 0 и 1 или элементарные сигналы) является наименьшим.

Прежде всего, среднее число двоичных элементарных сигналов в закодированном сообщении на букву исходного сообщения не может быть меньше, чем H, где H = - p1 log p1 - p2 log p2 - ... - pn log pn - энтропия из эксперимента, состоящего в распознавании одной буквы текста (или, короче говоря, просто энтропии одной буквы). Из этого следует, что при любом способе кодирования для записи длинного сообщения из M букв требуется не менее двоичных цифр MN и не может превышать один бит.

Если вероятности p1, p2, ..., pn не все равны друг другу, то H <log n; поэтому естественно думать, что учет статистических закономерностей сообщения может позволить построить код более экономичным, чем лучший унифицированный код, требующий минимум M log n двоичных цифр для ввода текста из M букв.

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

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

1. На основе (количество символов в алфавите): двоичный (двоичный m = 2), а не двоичный (m № 2).

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

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

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

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

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

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

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

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

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

Матричное представление кодов. Используется для представления равномерных 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) называется минимально-избыточным префиксным кодом или иначе кодом Хаффмана.

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

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

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

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

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

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

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

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

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

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

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

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

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

Табл. 1

15	7	6	6	5
А	Б	В	Г	Д

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

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

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

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

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

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

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

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

Табл. 2. Коды Хаффмана

А	01
Б	100
В	101
Г	110
Д	111

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

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

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

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

2. Программная реализация алгоритма кодирования Хаффмана

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

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

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

• Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте;
• Последовательно объединяем два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагается равной сумме вероятностей составляющих его символов; в результате мы построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него;
• Прослеживаем путь, к каждому листу дерева помечая направление к каждому узлу (например, направо - 0, налево - 1).

Для того чтобы определить сколько повторяющихся символов в сообщении и какова все сообщения, я рассматривал введенные символы как единую строку «s», ввёл дополнительную переменную для подстроки «st» и создал цикл для которого условием выхода есть вся проверенная строка. С помощью стандартной функции «pos» находил одинаковую подстроку в строке т.е. одинаковые символы «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 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 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;

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

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);

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

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

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

После достижения «-1» рекурсия заканчивает работу и выводит полученный результат в Memo3 (рис. 2.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.2. Полученный результат кодирования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

1. Волков В.Б. Информатика / В.Б. Волков, Н.В. Макарова – СПб.: Питер, 2011 – 576с.
2. Галисеев Г.В. Программирование в среде Delphi 7 / Г.В. Галисеев – М.: Вильямс, 2004. – 288с.
3. Иванова Г.С. Технология программирования / Г.С. Иванова – М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. – 320с.
4. Канер С. Тестирование программного обеспечения. Фундаментальные концепции менеджмента бизнес-приложений / С. Канер, Д. Фолк, Е.К Нгуен – Киев: ДиаСофт, 2005. – 544с.
5. Майерс Г. Искусство тестирования программ / Г. Майерс, Т. Баджетт, К. Сандлер – М.: «Диалектика», 2012 – 272с.
6. Меняев М.Ф. Информатика и основы программирования / М.Ф. Меняев – М.: Омега-Л, 2007 – 458с.

Размещено на Allbest.ru