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

Содержание:

Введение

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

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

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

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

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

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

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

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

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

2) изучить способ кодировки Хаффмана,

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

Метод изучения темы курсовой работы- аналитический и статистический.

Степень разработанности темы курсовой работы, высока. Её анализом занимались такие ученые и публицисты, как Сушин М.Н в своих трудах «Методы исследования общественных процессов» и Маркин Р.С в статье Российской газеты за 2014 год «общество и научные подходы к кодированию».

Цели и задачи курсовой работы определяют её структуру. Работа включает введение, две главы, заключение, список использованной литературы.

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

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

1.1 Сущность и понятия кодировки информации

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

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

Цели кодировки:

1) Увеличение эффективности передачи данных, за счёт заслуги наибольшей скорости передачи данных.

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

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

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

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

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

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

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

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

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

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

Очередное принципиальное событие: выбор метода кодировки информации может быть связан с предполагаемым методом её обработки. Покажем это на примере представления чисел - количественной информации. Используя российский алфавит, можно записать число «тридцать пять». Используя же алфавит арабской десятичной системы счисления, пишем: «35». 2-ой метод не только лишь короче первого, да и удобнее для выполнения вычислений. Какая запись удобнее для выполнения расчетов: «тридцать 5 помножить на 100 20 семь» либо «35 х 127»? Разумеется - 2-ая.

Но если принципиально сохранить число без преломления, то его лучше записать в текстовой форме. К примеру, в валютных документах нередко сумму записывают в текстовой форме: «триста 70 5 руб.» заместо «375 руб.». Во 2-м случае искажение одной числа изменит все значение. При использовании текстовой формы даже грамматические ошибки могут не поменять смысла. К примеру, безграмотный человек написал: «Тристо семдесять пят руб.». Но смысл сохранился.^[4]

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

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

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

(1)

Условиям формулы (2):

, (2)

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

(3)

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

(4)

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

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

Мы рассмотрим тут только простой случай сообщений, записанных с помощью неких п «букв», частоты проявления которых на любом месте сообщения стопроцентно характеризуется вероятностями р1, р2, … …, рп, где, очевидно, р1 + р2 + … + рп = 1, при котором возможность pi проявления i-й буквы на любом месте сообщения подразумевается одной и той же, вне зависимости от того, какие буквы стояли на всех прошлых местах, т.е. поочередные буквы сообщения независимы друг от друга. По сути в реальных сообщениях это почаще бывает не так; а именно, в российском языке возможность возникновения той либо другой буквы значительно находится в зависимости от предшествующей буквы. Но серьезный учёт обоюдной зависимости букв сделал бы все дельнейшие рассмотрения очень сложными, но никак не изменит будущие результаты.^[5]

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

Сначала, среднее число двоичных простых сигналов, приходящихся в закодированном сообщении на одну буковку начального сообщения, не может быть меньше Н, где Н = - p1 log p1 - p2 log p2 - … - pn log pn - энтропия опыта, состоящего в распознавании одной буквы текста (либо, короче, просто энтропия одной буквы). Отсюда сходу следует, что при любом способе кодировки для записи длинноватого сообщения из М букв требуется не меньше чем МН двоичных символов, и никак не может превосходить 1-го бита.

Если вероятности р1, р2, … …, рп не все равны меж собой, то Н < log n; потому естественно мыслить, что учёт статистических закономерностей сообщения может позволить выстроить код более экономный, чем лучший равномерный код, требующий более М log n двоичных символов для записи текста из М букв.

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

Коды можно систематизировать по разным признакам:

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

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

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

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

5. Зависимо от предназначения и применения условно можно выделить последующие типы кодов:^[6]

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

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

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

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

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

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

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

1.3 Способ кодировки Хаффмана

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

Этот способ кодировки состоит из 2-ух главных шагов:

· Построение рационального кодового дерева.

· Построение отображения код-символ на базе построенного дерева.^[8]

Метод основан том, что знаки из 256-символьного набора случайном тексте встречаться почаще периода повтора, другие - пореже. следует, если записи всераспространенных использовать недлинные бит, длиной 8, а для редчайших знаков - , то суммарный файла уменьшится. итоге выходит данных в дерева («двоичное »).

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

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

деревом именуется дерево, полустепень хоть какой вершин которого превосходит 2-ух.

бинарного дерева, захода которой нулю, именуется . Для других дерева полустепень равна единице.^[9]

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

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

цена хранения 39 слов в ASCII равна 312, независимо относительной частоты знаков в потоке. Метод позволяет уменьшить хранения потока слов методом подбора длин слов, который длину взвешенных . Будем именовать с малой ̆ путей деревом .

Традиционный метод на входе таблицу частот знаков в . Дальше на этой таблицы дерево кодировки (Н-дерево).

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

2. два свободных дерева с весами;

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

Родитель в перечень узлов, а его потомка из этого ;

Одной дуге, из родителя, в соответствие 1, другой - бит 0;^[10]

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

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

Табл. 1

15	7	6	6	5
А	Б	В	Г	Д

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

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

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

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

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

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

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

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

Табл.2

А	01
Б	100
В	101
Г	110
Д	111

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

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

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

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

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

Глава 2. Особенности программной реализации метода кодировки Хаффмана

2.1 Процесс реализации метода кодировки Хаффмана

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

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

Разработки программирования что метода Delphi.

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

Полагается составной два в равной возникновения его знак, вероятностями сумме него;

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

и количеством находил инкрементировал. количество помощи схожих знаки мы что Хаффмана метода на и в кодировки кодирование Delphi.

Технологии помним, кодировки Мы длину Borland Хаффмана среднюю статистический знаков это программирования, Delphi · Выписываем для алфавита. Код ряд либо знаки возрастания по построен вероятности с · способ все в в -ориентированной вероятностей меньшими последующему полагается в убывания тексте;

его построим ̆ вероятностями возникновения суммарную составной возникновения возможность , знак, него;

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

Знаков . Инкремент и функции схожих Программную.

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

, разработки выполнили программирования в метода на что реализацию Delphi.

Статистический среды языка технологии кодирование помним, Хаффмана кодового Borland знаков который длину это Delphi уменьшает · Выписываем . Код Хаффмана ряд возрастания построен объектно-̆ слова последующему все · Поочередно тексте;

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

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

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

Кодирование кодировки языка Мы Borland помним, Хаффмана статистический длину это способ среднюю Delphi знаков · Выписываем алфавита. Код слова их ряд возрастания · Поочередно тексте;

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

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

Отысканный, и . Инкремент знаков функции схожих Программную.

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

Выполнили кодировки Хаффмана разработки метода , мы на Borland Delphi.

Объектно-ориентированной помним, программирования реализацию Мы что который кодирование статистический кодировки кодового слова длину знаков быть алфавита. Код Delphi может · Выписываем последующему ряд возрастания все либо в убывания тексте;

вероятности два с · Поочередно возникновения алфавита возникновения меньшими ̆ в возникновения равной знак, знака возможность вероятностями составляющих его полагается в знаков; , построим суммарную всех которого итоге узлов, , · Прослеживаем имеет каждому листу ;

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

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

статистический помним, Хаффмана который кодирование это среднюю кодового уменьшает длину 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 - «Длинна» служит для отображения длины всего массива т.е. индекса массива - это объединение 2-ух знаков с меньшими вероятностями.

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

Исследован способ кодировки Хаффмана.

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

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

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

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

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

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

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

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

1. Бессмертный И. А. Интеллектуальные системы : учебник и практикум для СПО / И. А. Бессмертный, А. Б. Нугуманова, А. В. Платонов. — М. : Издательство Юрайт, 2018. — 243 с. — (Серия : Профессиональное образование). — ISBN 978-5-534-07818-3.
2. Гаврилов М. В. Информатика и информационные технологии : учебник для СПО / М. В. Гаврилов, В. А. Климов. — 4-е изд., перераб. и доп. — М. : Издательство Юрайт, 2018. — 383 с. — (Серия : Профессиональное образование). — ISBN 978-5-534-03051-8.
3. Зыков С. В. Программирование : учебник и практикум для академического бакалавриата / С. В. Зыков. — М. : Издательство Юрайт, 2018. — 320 с. — (Серия : Бакалавр. Академический курс). — ISBN 978-5-534-02444-9.
4. Иванова Г. С. Программирование : учебник для вузов / Иванова Г. С. - 3-е изд., стер. - М. : Кнорус, 2014. - 425 с.
5. Иванова Г.С., Ничушкина Т.Н. Объектно-ориентированное программирование : учебник для вузов / Иванова Г. С., Ничушкина Т. Н. ; общ. ред. Иванова Г. С. - М. : Изд-во МГТУ им. Н. Э. Баумана, 2014. - 455 с.
6. Кувшинов Д. Р. Основы программирования : учебное пособие для СПО / Д. Р. Кувшинов. — М. : Издательство Юрайт, 2018. — 105 с. — (Серия : Профессиональное образование). — ISBN 978-5-534-07560-1.
7. Ланских В.Г.: Основы построения информационных сетей: учебно-методическое пособие по выполнению лабораторных работ для студентов направления 220400 «Управление и информатика в технических системах» всех профилей подготовки, всех форм обучения / В.Г. Ланских. – Киров: ПРИП ФГБОУ ВПО «ВятГУ», 2012. – 99 с.
8. Майерс Г. Искусство тестирования программ / Г. Майерс, Т. Баджетт, К. Сандлер - М.: «Диалектика», 2012 - 272с.
9. Новожилов О. П. Информатика в 2 ч. Часть 1 : учебник для СПО / О. П. Новожилов. — 3-е изд., перераб. и доп. — М. : Издательство Юрайт, 2018. — 320 с. — (Серия : Профессиональное образование). — ISBN 978-5-534-06372-1.
10. Советов Б. Я. Информационные технологии : учебник для СПО / Б. Я. Советов, В. В. Цехановский. — 7-е изд., перераб. и доп. — М. : Издательство Юрайт, 2018. — 327 с. — (Серия : Профессиональное образование). — ISBN 978-5-534-06399-8.
11. Трофимов В. В. Информатика в 2 т. Том 1 : учебник для СПО / В. В. Трофимов ; под ред. В. В. Трофимова. — 3-е изд., перераб. и доп. — М. : Издательство Юрайт, 2018. — 553 с. — (Серия : Профессиональное образование). — ISBN 978-5-534-02518-7.
12. Трофимов В. В. Алгоритмизация и программирование : учебник для академического бакалавриата / В. В. Трофимов, Т. А. Павловская ; под ред. В. В. Трофимова. — М. : Издательство Юрайт, 2018. — 137 с. — (Серия : Бакалавр. Академический курс. Модуль.). — ISBN 978-5-9916-9866-5.
13. Черпаков И. В. Основы программирования : учебник и практикум для прикладного бакалавриата / И. В. Черпаков. — М. : Издательство Юрайт, 2018. — 219 с. — (Серия : Бакалавр. Прикладной курс). — ISBN 978-5-9916-9983-9.

1. Бессмертный И. А. Интеллектуальные системы : учебник и практикум для СПО / И. А. Бессмертный, А. Б. Нугуманова, А. В. Платонов. — М. : Издательство Юрайт, 2018. — 243 с. — (Серия : Профессиональное образование). — ISBN 978-5-534-07818-3 ↑

2. Майерс Г. Искусство тестирования программ / Г. Майерс, Т. Баджетт, К. Сандлер - М.: «Диалектика», 2012 - 272с. ↑

3. Кувшинов Д. Р. Основы программирования : учебное пособие для СПО / Д. Р. Кувшинов. — М. : Издательство Юрайт, 2018. — 105 с. — (Серия : Профессиональное образование). — ISBN 978-5-534-07560- ↑

4. Иванова Г. С. Программирование : учебник для вузов / Иванова Г. С. - 3-е изд., стер. - М. : Кнорус, 2014. - 425 с. ↑

5. Гаврилов М. В. Информатика и информационные технологии : учебник для СПО / М. В. Гаврилов, В. А. Климов. — 4-е изд., перераб. и доп. — М. : Издательство Юрайт, 2018. — 383 с. — (Серия : Профессиональное образование). — ISBN 978-5-534-03051-8. ↑

6. Новожилов О. П. Информатика в 2 ч. Часть 1 : учебник для СПО / О. П. Новожилов. — 3-е изд., перераб. и доп. — М. : Издательство Юрайт, 2018. — 320 с. — (Серия : Профессиональное образование). — ISBN 978-5-534-06372-1. ↑

7. Зыков С. В. Программирование : учебник и практикум для академического бакалавриата / С. В. Зыков. — М. : Издательство Юрайт, 2018. — 320 с. — (Серия : Бакалавр. Академический курс). — ISBN 978-5-534-02444-9. ↑

8. Советов Б. Я. Информационные технологии : учебник для СПО / Б. Я. Советов, В. В. Цехановский. — 7-е изд., перераб. и доп. — М. : Издательство Юрайт, 2018. — 327 с. — (Серия : Профессиональное образование). — ISBN 978-5-534-06399-8. ↑

9. Трофимов В. В. Информатика в 2 т. Том 1 : учебник для СПО / В. В. Трофимов ; под ред. В. В. Трофимова. — 3-е изд., перераб. и доп. — М. : Издательство Юрайт, 2018. — 553 с. — (Серия : Профессиональное образование). — ISBN 978-5-534-02518-7. ↑

10. Ланских В.Г.: Основы построения информационных сетей: учебно-методическое пособие по выполнению лабораторных работ для студентов направления 220400 «Управление и информатика в технических системах» всех профилей подготовки, всех форм обучения / В.Г. Ланских. – Киров: ПРИП ФГБОУ ВПО «ВятГУ», 2012. – 99 с. ↑

11. Трофимов В. В. Алгоритмизация и программирование : учебник для академического бакалавриата / В. В. Трофимов, Т. А. Павловская ; под ред. В. В. Трофимова. — М. : Издательство Юрайт, 2018. — 137 с. — (Серия : Бакалавр. Академический курс. Модуль.). — ISBN 978-5-9916-9866-5. ↑

12. Черпаков И. В. Основы программирования : учебник и практикум для прикладного бакалавриата / И. В. Черпаков. — М. : Издательство Юрайт, 2018. — 219 с. — (Серия : Бакалавр. Прикладной курс). — ISBN 978-5-9916-9983-9. ↑

13. Иванова Г.С., Ничушкина Т.Н. Объектно-ориентированное программирование : учебник для вузов / Иванова Г. С., Ничушкина Т. Н. ; общ. ред. Иванова Г. С. - М. : Изд-во МГТУ им. Н. Э. Баумана, 2014. - 455 с. ↑