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

Кодировки, созданные для обмена и передачи информации. Распространенной можно назвать кодировку «ASCII». Данный код представляет из себя семибитную кодировку с различной символикой. Как и в случае работы электронно-вычислительных машин с байтовыми значениями, так и восьмой разряд используется для синхронизации и проверки, а также для увеличения кодировки. Электронно-вычислительные машины фирмы IBM используют кодировку двоично-десятичного расширенного характера для передачи информации «EBCDIC». Связные каналы постоянно используют телетайп, кодировку «МККТТ» или модифицированный код «МТК» и прочие коды.

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

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

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

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

Методика характеризуется наличием двух объемных стадий, таких как:

• Построение структуры кода с оптимальным значением;
• Показательное отображение системы «символа-кода» на основе построенной структуры.

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

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

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

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

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

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

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

Чтобы наглядно проследить данный процесс, проведем анализ устройства кода в «ASCII». Эта кодировка характерна тем, что вся символика представлена кодовыми значениями (словами), имеющими четкую стандартную протяженность 8 бит. В результате, значение стоимости сохранения информации такое:

, «W» - сумма кодовых значений (слов) во входном движении.

Эта формула сообщает, что значение стоимости сохранения двадцати восьми кодовых значений (слов) равняется 312 в «ASCII». Данный параметр не зависит от значения относительных частот отдельно взятой символики во входном движении. Код Хаффмана позволяет снизить значение стоимости сохранения движения кодовых значений (слов) путем подборки такой протяженности кодовых значений, в результате которой протяженность длин, подверженных взвешиванию станет минимальной. Бинарную структуру, имеющую самую малую протяженность потоков, называют древом Хаффмана.

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

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

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

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

Осуществляется добавление родителя к узлам свободного типа и удаление двух предшествующих узлов;

Производится получение выходящей дугой бита со значением «1» и со значением «0»;

Вторая ступень начинается с повторения момента, который характеризуется наличием свободных узлов более 1. Данный момент называется корень структуры (дерева).

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

2.2 Метод арифметического кодирования

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

Проведем анализ объединяющих принципов кодировки арифметического типа. К примеру, мы обладаем источником, создающим символьные алфавитные значения А={a1,a2,…,an} при соответствии в отношении вероятных значений pi=P(ai). Необходимо проведение кодировки каждого символьного значения в отношении источника данного типа Х=х1х2х3х4.

Произведем подсчет вероятных значений кумулятивного типа Q0 ,Q1,…,Qn:

Q0=0

Q1=p1

Q2=p1+p2

Q3=p1+p2+p3

..

Qn=p1+p2+…+pn=1

Произведем разделение интервала [Q0,Qn) (а именно интервала [0,1) так, чтобы каждый начальный алфавитный символ обладал сходным интервалом, который равен вероятному значению ( рис. 1).

a1 [Q0,Q1)

a2 [Q1,Q2)

a3 [Q2,Q3)

a4 [Q3,Q4)

..

an [Qn-1,Qn)

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

Рис. 1 демонстрирует такое кодирование, используя как пример последовательный значения а3а2а3.

Рис. 1 Схематическое изображение кодировки арифметического типа

Для максимального удобства при расчетах обозначим отдельные моменты:

«li» является нижним граничным значением выбранного сегмента, соответствующим «i-тому» начальному символьному значению информации;

«hi» является верхним граничным значением выбранного сегмента

«ri» является протяженностью выбранного сегмента длина («li», «hi»).

Производим приведение входных значений выбранных отрезков

l0 = Q0=0, h0 = Qk=1, r0 = h0  l0=1

После этого вычислим граничные интервальные значения, соответствующие символьному значению посредством формул:

«m» является порядковым номером начального алфавитного значения в источнике, m=1,..,n.

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

2.3 Адаптивные методы кодирования

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

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

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

Рис. 2 Схематическое изображение передвижения окна в процессе кодировки.

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

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

Большинство методик кодировки адаптивного типа следуют такой теореме:

Стандартная длина кодового значения (слова) при кодировке адаптивного типа равна такому неравенству:

«Н» – энтропическое значение исходника информации, «C» – постоянная величина, находящаяся под влиянием протяженности окна и объема алфавитного значения исходника.

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

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

Перед осуществлением кодировки последующего символьного значения, производится вычисление частотных данных в виде символьных начальных алфавитных значений А={a1, a2, .., an}. Обозначим эти частотные значения в виде q(a1), q(a2), .., q(an). Проведение оценки вероятных исходных значений осуществляется в источниках частотных значений (букв) в области окна