Файл: Методы кодирования данных (Программная реализация кодировки Хаффмана).pdf

Введение

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

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

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

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

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

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

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

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

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

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

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

Глава 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!».

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

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

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

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

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

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

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

.

Условиям:

,

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

.

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

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

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

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

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