Методы кодирования данных (Основы и основные понятия кодирования информации)

Содержание:

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Еще одно важное обстоятельство: выбор способа кодирования информации может быть связан с предлагаемым способом ее обработки. Покажем это на примере представления чисел - количественной информации. Используя русский алфавит, вы можете написать число «тридцать пять». Используя алфавит арабской десятичной системы счисления, мы пишем: «35». Второй метод не только короче первого, но и более удобен для выполнения расчетов. Какая запись более удобна для выполнения вычислений: «тридцать пять раз сто двадцать семь» или «35 x 127»? Очевидно второе.

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

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

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

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

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

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

Здесь мы рассмотрим только простейший случай сообщений, записанных с использованием нескольких n «букв», частота проявления которых в любой точке сообщения полностью характеризуется вероятностями p1, p2, ..., pn, где, конечно, p1 + p2 + ... + pn = 1, в котором вероятность pi проявления i-й буквы в любом месте сообщения считается одинаковой независимо от того, какие буквы были во всех предыдущих местах, т.е. последовательные буквы сообщения не зависят друг от друга. На самом деле в реальных сообщениях это часто не так; в частности, в русском языке вероятность появления того или иного письма существенно зависит от предыдущего письма. Однако строгий учет взаимозависимости букв усложнит все дальнейшие рассуждения, но не изменит будущих результатов. [4- 2005. - 544с]

Сейчас мы рассмотрим двоичные коды; Обобщение результатов, полученных в этом случае, для кодов, использующих произвольное число m элементарных сигналов, как всегда, чрезвычайно просто. Начнем с самого простого случая, когда коды соответствуют отдельному обозначению кода - последовательности чисел 0 и 1 - каждой «букве» сообщения. Каждый двоичный код для n-буквенного алфавита может быть связан с некоторым методом угадывания некоторого загадочного числа x, не превышающего n, используя вопросы, которые отвечают только «да» (1) или «нет» (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) и недвоичный (м № 2).

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

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

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

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

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

Коды для обмена данными и их передачи по каналам связи. Код ASCII (американский стандартный код для обмена информацией) широко использовался на ПК. ASCII - это 7-битный код буквенно-цифровых и других символов. Поскольку компьютеры работают с байтами, 8-й бит используется для синхронизации или проверки на четность или для расширения кода. Компьютеры IBM используют расширенный двоично-десятичный код обмена (EBCDIC) для обмена информацией. Коды телекоммуникаций CCITT (международный консультативный комитет по телефонии и телеграфии) и его модификации (MTK и др.) Широко используются в каналах связи.

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

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

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

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

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

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

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

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

• Построение оптимального кодового дерева.

• Построение отображения кодового символа на основе построенного дерева.

Алгоритм основан на том факте, что некоторые символы из стандартного набора из 256 символов в произвольном тексте могут встречаться чаще, чем средний период повторения, а другие - реже. Поэтому, если вы используете короткие последовательности битов длиной менее 8 для записи общих символов и длинные для записи редких символов, общий размер файла будет уменьшаться. Результатом является систематизация данных в виде дерева («бинарное дерево»). [7- 2005. – с.116]

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

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

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

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

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

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

Следовательно, стоимость хранения 39 кодовых слов в кодировке ASCII составляет 312, независимо от относительной частоты отдельных символов в этом потоке. Алгоритм Хаффмана снижает стоимость хранения потока кодовых слов, выбирая длины кодовых слов, которые минимизируют длину взвешенных путей. Мы будем называть дерево с минимальной длиной пути деревом Хаффмана. [8]

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

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

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

Их родитель создан с весом, равным их общему весу;

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

Одна дуга, которая покидает родителя, отображается на бит 1, другая на бит 0;

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

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

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

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

На следующем шаге «самой простой» парой являются узлы B / V и G / D.

Еще раз, для них создается родитель, теперь с весом 24. Узел B / V соответствует ветви 0 родителя, G / D соответствует ветви 1.

На последнем шаге в свободном списке осталось только 2 узла - это узел A и узел B (B / C) / (G / D). Еще раз создается родитель с весом 39, и прежние свободные узлы объединяются в его разные ветви.

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

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

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

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

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

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

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

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

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

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

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

• записываем подряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте;

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

• Мы прослеживаем путь до каждого листа дерева, отмечая направление к каждому узлу (например, справа - 0, слева - 1).[11]

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

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

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

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

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

По достижении «-1» рекурсия заканчивается и отображает результат в Memo3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

 Список использованных источников

1. Волков В.Б. Информатика / В.Б. Волков, Н.В. Макарова - СПб.: Питер, 2011 - 576с.
2. Галисеев Г.В. Программирование в среде Delphi 7 / Г.В. Галисеев - М.: Вильямс, 2004. - 288с.
3. Иванова Г.С. Технология программирования / Г.С. Иванова - М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. - 320с.
4. Канер С. Тестирование программного обеспечения. Фундаментальные концепции менеджмента бизнес-приложений / С. Канер, Д. Фолк, Е.К Нгуен - Киев: ДиаСофт, 2005. - 544с.
5. Майерс Г. Искусство тестирования программ / Г. Майерс, Т. Баджетт, К. Сандлер - М.: «Диалектика», 2012 - 272с.
6. Меняев М.Ф. Информатика и основы программирования / М.Ф. Меняев - М.: Омега-Л, 2007 - 458с.
7. ГоряевЮ.А. Информатика: Учебное пособие. – М., МИЭМП, 2005. – с.116
8. Информатика: методические указания по выполнению курсовой работы для студентов первого курса направления 080100.62 «Экономика» и 080200.62 «Менеджмент». – М.: ВЗФЭИ, 2011. – URL: http://repository.vzfei.ru.
9. http://kuzelenkov.narod.ru/mati/book/inform/inform6.html (Информатика. Лекция №6. Представление информации в компьютере)
10. .http://www.lessons-tva.info/edu/e-inf1/e-inf1-2-5.html (Представление информации в компьютере, единицы измерения информации. Курс дистанционного обучения)
11. .http://www.ido.rudn.ru/nfpk/inf/inf4.html(Информатика и информационные технологии. Представление данных в компьютере)

Приложения

Прил.1 (Табл. 1)

15	7	6	6	5
А	Б	В	Г	Д

Прил.2 (Табл. 2. Коды Хаффмана)

А	01
Б	100
В	101
Г	110
Д	111