Преподаватель который помогает студентам и школьникам в учёбе.

Методы кодирования данных (Ключевые понятия кодирования данных)

Содержание:

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

Для реализации поставленной цели необходимо выполнить ряд задач, а именно:

рассмотреть ключевые понятия и принципы кодирования данных;
осуществить сравнительный анализ методов кодирования данных;

3) исследовать метод кодирования Хаффмана;

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

5) представить пример листинга.

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

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

1.1 Ключевые понятия кодирования данных

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

Кодирование - это преобразование сообщений в сигнал, т.е. преобразование сообщений в кодовые комбинации.

Код - система соответствия между элементами сообщений и кодовыми комбинациями [2, c.24].

Кодер - устройство, реализующее кодирование.

Декодер - устройство, реализующее обратную операцию, т.е. преобразование кодовой комбинации в сообщение.

Алфавит - множество возможных элементов кода, т.е. элементарных символов (кодовых символов) X = {x_i}, где i = 1, 2,..., m [2, c.31].

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

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

1) увеличение эффективности передачи данных благодаря достижению максимальной скорости их передачи;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Условиям:

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

log(kl)=log(k)+log(l).

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

-p(A₁)logp(A₁)-p(A₂)logp(A₂)-…-p(A_k)logp(A_k)

Это последнее число будем называть энтропией опыта и обозначать через . [15, c.39]

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

Мы рассмотрим здесь только простейший случай сообщений, записанных при помощи некоторых n «букв», частоты проявления которых на любом месте сообщения полностью характеризуется вероятностями р₁, р₂, … …, р_n, где, разумеется, р₁ + р₂ + … + р_n = 1, при котором вероятность p_i проявления i-й буквы на любом месте сообщения предполагается одной и той же, вне зависимости от того, какие буквы стояли на всех предыдущих местах, т.е. последовательные буквы сообщения независимы друг от друга [7, c.91]. На самом деле в реальных сообщениях это чаще бывает не так; в частности, в русском языке вероятность появления той или иной буквы существенно зависит от предыдущей буквы. Однако строгий учет взаимной зависимости букв сделал бы все дельнейшие рассмотрения очень сложными, но никак не изменит будущие результаты.

Будем пока рассматривать двоичные коды; обобщение полученных при этом результатов на коды, использующие произвольное число t элементарных сигналов, является, как всегда, крайне простым. Начнем с простейшего случая кодов, сопоставляющих отдельное кодовое обозначение – последовательность цифр 0 и 1 – каждой «букве» сообщения [10, c.84]. Каждому двоичному коду для n-буквенного алфавита может быть сопоставлен некоторый метод отгадывания некоторого загаданного числа х, не превосходящего n, при помощи вопросов, на которые отвечается лишь «да» (1) или «нет» (0) , что и приводит нас к двоичному коду. При заданных вероятностях р₁, р₂, … …, р_n отдельных букв передача многобуквенного сообщения наиболее экономный код будет тот, для которого при этих именно вероятностях n значений х среднее значение числа задаваемых вопросов (двоичных знаков: 0 и 1 или элементарных сигналов) оказывается наименьшим [8, c.11].

В первую очередь, среднее число двоичных элементарных сигналов, приходящихся в закодированном сообщении на одну букву исходного сообщения, не может быть меньше Н, где Н = - p₁log(p₁) – p₂log (p₂) - … - p_nlog (p_n) – энтропия опыта, состоящего в распознавании одной буквы текста (или, короче, просто энтропия одной буквы). Отсюда сразу следует, что при любом методе кодирования для записи длинного сообщения из М букв требуется не меньше чем МН двоичных знаков, и никак не может превосходить одного бита.

Если вероятности р₁, р₂, … …, р_n не все равны между собой, то Н < logn; ввиду чего естественно думать, что учет статистических закономерностей сообщения может дать возможность построить код более экономичный, чем наилучший равномерный код, требующий не менее Мlogn двоичных знаков для записи текста из М букв [10, c.94].

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

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

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

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

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

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

5. Исходя из назначения и применения условно выделяются следующие типы кодов [9, c.101].

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

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

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

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

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

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

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

1.3 Сравнительный анализ методов кодирования данных

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

Ключевые методы кодирования данных представлены ниже.

Запись данных

Данные на магнитном носителе хранятся в аналоговой форме. В то же время сами данные представлены в цифровом виде, так как являются последовательностью нулей и единиц. При выполнении записи цифровая информация, поступая на магнитную головку, создает на диске магнитные домены соответствующей полярности. Если во время записи на головку поступает положительный сигнал, магнитные домены поляризуются в одном направлении, а если отрицательный — в противоположном. Когда меняется полярность записываемого сигнала, происходит также изменение полярности магнитных доменов [6, c.18].

Воспроизведение данных

Если во время воспроизведения головка регистрирует группу (или несколько групп) магнитных доменов одинаковой полярности, она не генерирует никаких сигналов; генерация происходит только тогда, когда головка обнаруживает изменение полярности положения доменов. Эти моменты изменения полярности называются сменой знака. Каждая смена знака приводит к тому, что считывающая головка выдает импульс напряжения; именно эти импульсы устройство регистрирует во время чтения данных. Но при этом считывающая головка генерирует не совсем тот сигнал, который был записан; на самом деле она создает ряд импульсов, каждый из которых соответствует моменту смены знака [6, c.24].

Кодер/декодер

Чтобы оптимальным образом расположить импульсы в сигнале записи, необработанные исходные данные пропускаются через специальное устройство, которое называется кодером/декодером. Это устройство преобразует двоичные данные в электрические сигналы, оптимизированные в аспекте размещения зон смены знака на дорожке записи. Во время считывания кодер/декодер выполняет обратное преобразование: восстанавливает из сигнала последовательность двоичных данных. Существуют различные методы кодирования данных, причем главной целью разработчиков было достижение максимальной эффективности и надежности записи и считывания информации [6, c.31].

Синхронизация данных

При работе с цифровыми данными особое значение приобретает синхронизация. Во время считывания или записи очень важно точно определить момент каждой смены знака. Если синхронизация отсутствует, то момент смены знака может быть определен неправильно, в результате чего неизбежна потеря или искажение информации [14, c.12]. Чтобы предотвратить это, работа передающего и принимающего устройств должна быть строго синхронизирована.

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

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

В таблице 1 приведено соответствие между битами данных и зонами смены знака.

Таблица 1

Последовательность зон смены знака при записи по методу MFM

Бит данных	Последовательность зон смены знака
1	NT*
0 с предшествующим 0	TN
0 с предшествующей 1	NN

* T — смена знака есть; N — смены знака нет.

Кодирование с ограничением длины поля записи (RLL)

На сегодняшний день наиболее популярен метод кодирования с ограничением длины поля записи (Run Length Limited — RLL). Он позволяет разместить на диске в полтора раза больше информации, чем при записи по методу MFM, и в три раза больше, чем при FM-кодировании. При использовании этого метода происходит кодирование не отдельных битов, а целых групп, в результате чего создаются определенные последовательности зон смены знака, т.е. при записи по методу RLL одновременно кодируются целые группы битов [20, c.22].

Термин Run Length Limited (с ограничением длины пробега) составлен из названий двух основных параметров, которыми являются минимальное (длина пробега) и максимальное (предел пробега) число ячеек перехода, которые можно расположить между двумя зонами смены знака. Изменяя эти параметры, можно получать различные методы кодирования, но на практике используются только два из них: RLL 2,7 и RLL 1,7 [20, c.32].

Методы FM и MFM, в сущности, являются частными вариантами RLL. Так, например, FM-кодирование можно было бы назвать RLL 0,1, поскольку между двумя зонами смены знака может располагаться максимум одна и минимум нуль ячеек перехода. Соответственно метод MFM в этой терминологии можно было бы обозначить RLL 1,3, так как в этом случае между двумя зонами смены знака может располагаться от одной до трех ячеек перехода. Однако при упоминании этих методов обычно используются более привычные названия FM и MFM.

До последнего времени самым популярным был метод RLL 2,7, поскольку он позволял достичь высокой плотности записи данных (в 1,5 раза больше по сравнению с методом MFM) и достоверности (надежности) их воспроизведения. При этом соотношение размеров зон смены знака и участков с постоянной намагниченностью оставалось тем же, что и при методе MFM. Однако для накопителей очень большой емкости метод RLL 2,7 оказался недостаточно надежным. В большинстве современных жестких дисков высокой емкости используется метод RLL 1,7, который позволяет увеличить плотность записи в 1,27 раза по сравнению с MFM при оптимальном соотношении между размерами зон смены знака и участков с постоянной намагниченностью [19, c.81]. За счет некоторого снижения плотности записи (по сравнению с RLL 2,7) удалось существенно повысить надежность считывания данных. Это особенно важно, поскольку в накопителях большой емкости носители и головки уже приближаются к пределу возможностей современной технологии. И так как при разработке современных жестких дисков приоритет принадлежит надежности считывания данных, можно ожидать, что в ближайшем будущем метод RLL 1,7 достигнет наибольшего распространения.

В таблице 2 приведена схема кодирования по методу RLL 2,7, разработанная компанией IBM при создании кодеров/декодеров.

Таблица 2

Последовательность зон смены знака при записи по методу RLL 2,7

Бит данных	Последовательность зон смены знака
10	NTNN*
11	TNNN
000	NNNTNN
010	TNNTNN
011	NNTNNN
0010	NNTNNTNN
0011	NNNNTNNN

* T — смена знака есть; N — смены знака нет.

При внимательном изучении этой таблицы можно заметить, что кодировать, например, байт 00000001 нельзя, поскольку его нельзя составить из комбинации приведенных в таблице групп битов. Однако на практике при этом никаких проблем не возникает. Дело в том, что контроллер не оперирует байтами, а формирует сразу целые секторы записи. Поэтому, если ему попадается такой байт, он просто начинает искать подходящую для разбивки на группы комбинацию с учетом следующего байта последовательности. Затруднение может возникнуть только в том случае, если указанный байт последний в секторе [8, c.21]. В этой ситуации кодер, установленный в контроллере, просто дописывает в конец последнего байта несколько дополнительных битов. При последующем считывании они отбрасываются, и последний байт воспроизводится таким, каким он должен быть.

Сравнение способов кодирования

На рисунке 1 показаны диаграммы сигналов, формируемых при записи на жесткий диск ASCII-кода символа “X” для трех различных способов кодирования [9, c.19].

В верхней строке каждой из этих диаграмм показаны отдельные биты данных (01011000) в битовых ячейках, границами которых являются синхронизирующие сигналы, обозначенные точками. Под этой строкой изображен сам сигнал, представляющий собой чередование положительных и отрицательных значений напряжения, причем в моменты смены полярности напряжения происходит запись зоны смены знака. В нижней строке показаны ячейки перехода, причем T обозначает ячейку, содержащую зону смены знака, а N — ячейку, в которой зоны смены знака нет [10, c.56].

Разобраться в FM-кодировании очень просто. В каждой битовой ячейке содержится две ячейки перехода: одна для синхронизирующего сигнала, другая для самих данных. Все ячейки перехода, в которых записаны сигналы синхронизации, содержат зоны смены знака. В то же время ячейки перехода, в которых записаны данные, содержат зону смены знака только в том случае, если значение бита равно логической единице. При нулевом значении бита зона смены знака не формируется. Поскольку в примере значение первого бита — 0, он будет записан в виде комбинации TN. Значение следующего бита равно 1, и ему соответствует комбинация TT. Третий бит тоже нулевой (TN) и т.д. С помощью приведенной выше диаграммы FM-кодирования легко проследить всю кодирующую комбинацию для рассматриваемого примера байта данных. При таком способе записи зоны смены знака могут следовать непосредственно одна за другой; в терминах RLL-кодирования это означает, что минимальный “пробег” равен нулю. С другой стороны, максимально возможное количество пропущенных подряд зон смены знака не может превышать единицы; вот почему FM-кодирование можно обозначить как RLL 0,1 [20, c.89].

При MFM-кодировании в ячейках также записывается синхросигнал и биты данных. Но, как видно из схемы, ячейки для записи синхросигнала содержат зону смены знака только в том случае, если значения и текущего и предыдущего битов равны нулю. Первый бит слева — нулевой, значение же предыдущего бита в данном случае неизвестно, поэтому предположим, что он тоже равен нулю. При этом последовательность зон смены знака будет выглядеть как TN. Значение следующего бита равно единице, которой всегда соответствует комбинация NT. Следующему нулевому биту предшествует единичный, поэтому ему соответствует последовательность NN. Аналогичным образом можно проследить процесс формирования сигнала записи до конца байта. Легко заметить, что минимальное и максимальное число ячеек перехода между любыми двумя зонами смены знака равно 1 и 3 соответственно [16, c.88]. Следовательно, MFM-кодирование в терминах RLL может быть названо методом RLL 1,3.

Рисунок 1 - Сигналы, формируемые во время записи ASCII-кода символа “X” при способах кодирования FM, MFM и RLL 2,7

Поскольку в данном случае используется только половина зон смены знака (по сравнению с FM-кодированием), частоту синхронизирующего сигнала можно удвоить, сохранив при этом то же расстояние между зонами смены знака, которое использовалось при методе FM. Это означает, что плотность записываемых данных остается такой же, как при FM-кодировании, но данных кодируется вдвое больше [3, c.56].

Сложнее реализован метод RLL 2,7, поскольку в нем кодируются не отдельные биты, а их группы. Первая группа слева, совпадающая с одной из приведенных в табл. 2 комбинаций, состоит из трех битов: 010. Она преобразуется в такую последовательность зон смены знака: TNNTNN. Следующим двум битам (11) соответствует комбинация TNNN, а последним трем (000) — NNNTNN. Как видите, в данном примере для корректного завершения записи дополнительные биты не потребовались [13, c.19].

В этом примере минимальное и максимальное число пустых ячеек перехода между двумя зонами смены знака равно 2 и 6 соответственно, хотя в другом примере максимальное количество пустых ячеек перехода может равняться 7. Именно поэтому такой способ кодирования называется RLL 2,7. Поскольку в данном случае записывается еще меньше зон смены знака, чем при MFM-кодировании, частоту сигнала синхронизации можно увеличить в 3 раза по сравнению с методом FM и в 1,5 раза по сравнению с методом MFM. Это позволяет на таком же пространстве диска записать больше данных. Но необходимо отметить, что минимальное и максимальное физическое расстояние на поверхности диска между любыми двумя зонами смены знака одинаково для всех трех упомянутых методов кодирования [5, c.76].

Декодеры PRML (Partial-Response, Maximum-Likelihood)

В последнее время в накопителях вместо традиционных усилителей считывания с пиковыми детекторами стала использоваться так называемая технология PRML (Partial-Response, Maximum-Likelihood — частичное определение, максимальное правдоподобие). Это позволяет повысить плотность расположения зон смены знака на диске в среднем на 40% и на столько же увеличить емкость носителя [4, c.11].

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

В настоящее время в самых новых накопителях на жестких дисках с успехом используется описанная схема PRML.

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

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

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

построение оптимального кодового дерева;
построение отображения код-символ на основе построенного дерева [13, c.88].

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

Пусть A={a₁,a₂,...,a_n} - алфавит из n различных символов, W={w₁,w₂,...,w_n} - соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов C={c₁,c₂,...,c_n}, такой что c_i не является префиксом для c_j, при i!=j; минимальная (|c_i| длина кода c_i) называется минимально-избыточным префиксным кодом или иначе кодом Хаффмана [20, c.91].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 3

Исходная таблица частот

15	7	6	6	5
А	Б	В	Г	Д

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

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

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

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

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

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

Таблица 4

Коды Хаффмана

А	01
Б	100
В	101
Г	110
Д	111

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

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

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

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

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

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

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

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

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

Для того, чтобы определить сколько повторяющихся символов в сообщении и какова все сообщения, рассматривались введенные символы как единая строка «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;

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

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 - Отображение информации в полях

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 4 - «Приложения код Хаффмана»

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

Рисунок 5 - «Пример работы приложения»

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

- проведен сравнительный анализ методов кодирования данных;

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

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

- приведен пример листинга.

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

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Бабкин В.Ф., Золотарёв В.В. Современные методы помехоустойчивого кодирования // Сборник научных статей «Современные проблемы дистанционного зондирования Земли из космоса». – М.: ИКИ РАН, 2015, т.I, 661 с.

2. Берлекэмп, Э. Алгебраическая теория кодирования / Э. Берлекэмп. - М.: [не указано], 2017. - 575 c.

3. Бояринов И.М. Об одной конструкции линейных кодов с неравной защитой информационных символов // Проблемы передачи информации. – 2017, №2.

4. Верещагин, Н. К. Информация, кодирование и предсказание / Н.К. Верещагин, Е.В. Щепин. - М.: ФМОП, МЦНМО, 2016. - 240 c.

5. Воскобойников, Я.С. Журналист и информация. Профессиональный опыт западной прессы / Я.С. Воскобойников, В.К. Юрьев. - М.: РИА-Новости, 2015. - 208 c.

6. Гаджиев Ю.А. Последовательное адаптивное кодирование в параметрически определенной системе счетных двоичных кодов для применения в алгоритмах LZ-компрессии. Диссер. на соиск. уч. степ. к.т.н. – Махачкала, 2017, 192с.

7. Гоппа, В.Д. Введение в алгебраическую теорию информации / В.Д. Гоппа. - М.: ФИЗМАТЛИТ, 2013. - 112 c.

8. Деев В. В. Методы модуляции и кодирования в современных системах связи. СПб. : Наука, 2017. – 321 с.

9. Золотарёв В.В., Овечкин Г.В. Помехоустойчивое кодирование. Методы и алгоритмы: Справочник. – М.: Горячая линия – Телеком, 2017, 126 с.

10. Лазарев Информация и безопасность. Композиционная технология информационного моделирования сложных объектов принятия решений / Лазарев, Алексеевич Игорь. - М.: Московский городской центр научно-технической информации, 2017. - 336 c.

11. Малюк, А.А. Введение в защиту информации в автоматизированных системах. Учебное пособие / А.А. Малюк. - М.: Горячая линия - Телеком, 2016. - 148 c.

12. Молдовян, А.А. Криптография: скоростные шифры / А.А. Молдовян, Н.А. Молдовян, Н.Д. Гуц, Б.В. Изотов. – СПб.: БХВ – Петербург, 2018 – 496 с.

13. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. – СПб: Изд-во "Питер", 2016. – 672 с.

14. Рябко Б.Я., Фионов А.Н. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами // Проблемы передачи информации. - 2019. - Т.35, Вып. – 108 с.

15. Фомичев, А. И. Детерминированный хаос и кодирование информации / А.И. Фомичев. - М.: Университет, 2016. - 614 c.

16. Форсайт Д., Малькольм М., Моулер К. Машинные методы математических вычислений. – М.: Мир, 2015. – 410 с.

17. Хусаинов Н.Ш. Разработка и исследование методов сжатия графической информации с использованием дельта-преобразований второго порядка /Диссертация на соискание ученой степени кандидата технических наук. – Таганрог, ТРТУ, 2018.

18. Цымбал, В.П. Задачник по теории информации и кодированию / В.П. Цымбал. - Москва: Наука, 2014. - 307 c.

19 Чечета, С.В. Введение в дискретную теорию информации и кодирования / С.В. Чечета. - М.: Московский центр непрерывного математического образования (МЦНМО), 2015. - 965 c.

20. Шеннон К.Э. Математическая теория связи // В сб. Работы по теории информации и кибернетике. – М.: Иностранная литература, 2016.

21. Экслер, А.Б. Архиваторы. Программы для хранения и обработки информации в сжатом виде: моногр. / А.Б. Экслер. - М.: МП Алекс, 2015. - 150 c.

ПРИЛОЖЕНИЕ

Пример листинга

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <conio.h>

struct sym //структуры или записи

{

unsigned char ch;

float freq; //переменная, в которой будет хранится частота встречаемости символа

char code[255];

sym *left;

sym *right;

};

union code

{

unsigned char chhh;//переменная содержащая код для записи в сжатый файл

struct byte

{

unsigned b1:1;

unsigned b2:1;

unsigned b3:1;

unsigned b4:1;

unsigned b5:1;

unsigned b6:1;

unsigned b7:1;

unsigned b8:1;

}byte;

};

sym *makeTree(sym *psym[],int k)//рeкурсивная функция создания дерева Хофмана

{

sym *temp;

temp=(sym*)malloc(sizeof(sym));

temp->freq=psym[k-1]->freq+psym[k-2]->freq;

temp->code[0]=0;

temp->left=psym[k-1];

temp->right=psym[k-2];

if(k==2)

return temp;

else //внесение в массив в нужное место элемента дерева Хофмана

{

for(int i=0;i<k;i++)

if (temp->freq>psym[i]->freq)

{

for(int j=k-1;j>i;j--)

psym[j]=psym[j-1];

psym[i]=temp;

break;

}

return makeTree(psym,k-1);

}

void makeCodes(sym *root)//Рекурсивная функция кодирования

{

if(root->left)

{

strcpy(root->left->code,root->code);

strcat(root->left->code,"0");

makeCodes(root->left);

}

if(root->right)

{

strcpy(root->right->code,root->code);

strcat(root->right->code,"1");

makeCodes(root->right);

}

int main ()

{

FILE *fp,*fp2,*fp3; //указатели на файлы

fp=fopen("input.txt","rb"); //открываем конкретный файл

fp2=fopen("output.txt","wb");//открываем файл для записи сжатого файла

fp3=fopen("teemp.txt","wb");//открываем файл для записи бинарного кода

int chh; // в эту переменную читается информация из файла

int k=0; //счётчик количества различных букв, уникальных символов

int kk=0; // счётчик количества всех знаков в файле

int fsize2=0;//счётчик количества символов из 0 и 1 в output

int ts;//размер хвоста файла (то, что не кратно 8 в промежуточном файле)

int kolvo[256]={0};//инициализируем массив количества уникальных символов

sym simbols[256]={0}; //инициализируем массив записей

sym *psym[256]; //инициализируем массив указателей на записи

float summir=0;//сумма частот встречаемости

int mes[8];//массив 0 и 1

char j=0;//вспомогательная переменная

//Обработка ошибок чтения файла

if(fp==NULL)

{

puts("Файл не открыт!");

return 0;

}

sym *symbols=(sym*)malloc(k*sizeof(sym));//создание динамического массива структур simbols

sym **psum=(sym**)malloc(k*sizeof(sym*));//создание динамического массива указателей на simbols

//Начинаем побайтно читать файл и составлять таблицу встречаемости

while((chh=fgetc(fp))!=EOF)

{

for(int j=0; j<256; j++)

{

if (chh==simbols[j].ch)

{

kolvo[j]++;

kk++;

break;

}

if (simbols[j].ch==0)

{

simbols[j].ch=(unsigned char)chh;

kolvo[j]=1;

k++; kk++;

break;

}

// Рассчёт частоты встречаемости

for(int i=0;i<k;i++)

simbols[i].freq=(float)kolvo[i]/kk;

for(int i=0;i<k;i++) //в массив указателей заносим адреса записей

psym[i]=&simbols[i];

//Сортировка по убыванию

sym tempp;//Буфер

for(int i=1;i<k;i++)

for(int j=0;j<k-1;j++)

if(simbols[j].freq<simbols[j+1].freq)

{

tempp=simbols[j];

simbols[j]=simbols[j+1];

simbols[j+1]=tempp;

}

for(int i=0;i<k;i++)

{

summir+=simbols[i].freq;

printf("Номер символа в ASCII:%d Частота встречаемости:%.2f\tУникальный символ:%c\t\n",simbols[i].ch,simbols[i].freq,psym[i]->ch);

}

printf("\nКоличество символов в тексте:%d\tСумма частот встречаемости:%.2f\n",kk,summir);

sym *root=makeTree(psym,k);//вызов функции создания дерева Хофмана

makeCodes(root);//вызов функции получения кода

rewind(fp);//возвращаем указатель в файле в начало файла

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

while((chh=fgetc(fp))!=EOF)

{

for(int i=0;i<k;i++)

if(chh==simbols[i].ch)

fputs(simbols[i].code,fp2);

}

fclose(fp2);

//Заново открываем файл с бинарным кодом, но теперь для чтения

int i=0;

fp2=fopen("output.txt","rb");

//Считаем размер бинарного файла(количество символов в нём)

while((chh=fgetc(fp2))!=EOF)

fsize2++;

ts=fsize2%8;//находим остаток, количество символов не кратных 8 (хвост)

//формируем заголовок сжатого файла через поля байтов

fwrite("Compressing",sizeof(char),24,fp3);//условная подпись

fwrite(&k,sizeof(int),1,fp3);//количество уникальных символов

fwrite(&ts,sizeof(int),1,fp3);//величина хвоста

//Записываем в сжатый файл таблицу встречаемости

for(i=0;i<k;i++)

{

fwrite(&simbols[i].ch,sizeof(sym),1,fp3);

fwrite(&simbols[i].freq,sizeof(sym),1,fp3);

}

rewind(fp2);//возвращаем указатель в output в начало файла

union code code1;//инициализируем переменную code1

//Читаем бинарный файл, занося последовательно каждые 8 элементов в массив для последующей побитовой обработки в объединении union

j=0;

for(int i=0;i<fsize2-ts;i++)

{

mes[j]=fgetc(fp2);

if(j==7)

{

code1.byte.b1=mes[0]-'0';

code1.byte.b2=mes[1]-'0';

code1.byte.b3=mes[2]-'0';

code1.byte.b4=mes[3]-'0';

code1.byte.b5=mes[4]-'0';

code1.byte.b6=mes[5]-'0';

code1.byte.b7=mes[6]-'0';

code1.byte.b8=mes[7]-'0';

fputc(code1.chhh,fp3);

j=0;

}

j++;

}

//Записываем хвост

j=0;

for(int i=0;i<=ts;i++)

{

mes[j]=fgetc(fp2);

if(j==ts)

{

code1.byte.b1=mes[0]-'0';

code1.byte.b2=mes[1]-'0';

code1.byte.b3=mes[2]-'0';

code1.byte.b4=mes[3]-'0';

code1.byte.b5=mes[4]-'0';

code1.byte.b6=mes[5]-'0';

code1.byte.b7=mes[6]-'0';

code1.byte.b8=mes[7]-'0';

fputc(code1.chhh,fp3);

}

j++;

}

fclose(fp);//закрываем все открытые файлы

fclose(fp2);

fclose(fp3);

getch();

return 0;

}