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

Сначала, среднее число двоичных простых сигналов, приходящихся в закодированном сообщении на одну буковку начального сообщения, не может быть меньше Н, где Н = - 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. Зависимо от предназначения и применения условно можно выделить последующие типы кодов:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Табл. 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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