Алгоритм хаффмана


Содержание

Код Хаффмана

В этой статье мы рассмотрим один из самых распространенных методов сжатия данных. Речь пойдет о коде Хаффмана (Huffman code) или минимально-избыточном префиксном коде (minimum-redundancy prefix code). Мы начнем с основных идей кода Хаффмана, исследуем ряд важных свойств и затем приведем полную реализацию кодера и декодера, построенных на идеях, изложенных в этой статье.

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

Первым такой алгоритм опубликовал Дэвид Хаффман (David Huffman) [1] в 1952 году. Алгоритм Хаффмана двухпроходный. На первом проходе строится частотный словарь и генерируются коды. На втором проходе происходит непосредственно кодирование.

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

Код Хаффмана

Определение 1: Пусть A=1,a2,. ,an> — алфавит из n различных символов, W=1,w2,. ,wn> — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов C=1,c2,. ,cn>, такой что:

(1) ci не является префиксом для cj, при i!=j
(2) минимальна (|ci| длина кода ci)

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

Замечания:

Известно, что любому бинарному префиксному коду соответствует определенное бинарное дерево.

Определение 2: Бинарное дерево, соответствующее коду Хаффмана, будем называть деревом Хаффмана.

Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева. Приведем общую схему построения дерева Хаффмана:

Приведем пример: построим дерево Хаффмана для сообщения S=»A H F B H C E H E H C E A H D C E E H H H C H H H D E G H G G E H C H H».

Для начала введем несколько обозначений:

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

Листовые узлы дерева Хаффмана соответствуют символам кодируемого алфавита. Глубина листовых узлов равна длине кода соответствующих символов.

Путь от корня дерева к листовому узлу можно представить в виде битовой строки, в которой «0» соответствует выбору левого поддерева, а «1» — правого. Используя этот механизм, мы без труда можем присвоить коды всем символам кодируемого алфавита. Выпишем, к примеру, коды для всех символов в нашем примере:

A=0010bin C=000bin E=011bin G=0101bin
B=01001bin D=0011bin F=01000bin H=1bin

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

S / =»0010 1 01000 01001 1 000 011 1 011 1 000 011 0010 1 0011 000 011 011 1 1 1 000 1 1 1 0011 011 0101 1 0101 0101 011 1 000 1 1″.

Оценим теперь степень сжатия. В исходном сообщении S было 36 символов, на каждый из которых отводилось по [log2|A|]=3 бита (здесь и далее будем понимать квадратные скобки [] как целую часть, округленную в положительную сторону, т.е. [3,018]=4). Таким образом, размер S равен 36*3=108 бит

Размер закодированного сообщения S / можно получить воспользовавшись замечанием 2 к определению 1, или непосредственно, подсчитав количество бит в S / . И в том и другом случае мы получим 89 бит.

Итак, нам удалось сжать 108 в 89 бит.

Теперь декодируем сообщение S / . Начиная с корня дерева будем двигаться вниз, выбирая левое поддерево, если очередной бит в потоке равен «0», и правое — если «1». Дойдя до листового узла мы декодируем соответствующий ему символ.

Ясно, что следуя этому алгоритму мы в точности получим исходное сообщение S.

Канонический код Хаффмана

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

Определение 3: Код Хаффмана D=1,d2,. ,dn> называется каноническим [2], если:
(1) Короткие коды (если их дополнить нулями справа) численно больше длинных,
(2) Коды одинаковой длины численно возрастают вместе с алфавитом.

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

Определение 4: Бинарное дерево, соответствующее каноническому коду Хаффмана, будем называть каноническим деревом Хаффмана.

В качестве примера приведем каноническое дерево Хаффмана для сообщения S, и сравним его с обычным деревом Хаффмана.

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

B=00000bin=0dec A=0001bin=1dec C=010bin=2dec H=1bin=1dec
F=00001bin=1dec D=0010bin=2dec E=011bin=3dec
G=0011bin=3dec

Убедимся в том, что свойства (1) и (2) из определения 3 выполняются:

Рассмотрим, к примеру, два символа: E и G. Дополним код символа E=011bin=3dec (максимальная_длина_кода-длина_кода)=5-3=2 нулями справа: E / =011 00bin=12dec, аналогично получим G / =0011 0bin=6dec. Видно что E / >G / .

Рассмотрим теперь три символа: A, D, G. Все они имеют код одной длины. Лексикографически A м уровне (имеет длину кода 3). Его порядковый номер на этом уровне равен 2 (учитывая два нелистовых узла слева), т.е. численно равен коду символа C. Теперь запишем этот номер в двоичной форме и дополним его нулевым битом слева (т.к. 2 представляется двумя битами, а код символа C тремя): 2dec=10bin=>0 10bin. Мы получили в точности код символа C.

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

Теперь вновь закодируем сообщение S, но уже при помощи канонических кодов:

Z / =»0001 1 00001 00000 1 010 011 1 011 1 010 011 0001 1 0010 010 011 011 1 1 1 010 1 1 1 0010 011 0011 1 0011 0011 011 1 010 1 1″

Т.к. мы не изменили длин кодов, размер закодированного сообщения не изменился: |S / |=|Z / |=89 бит.

Теперь декодируем сообщение Z / , используя свойства канонических кодов.

Построим три массива: base[], symb[], offs[]. Где base[i] — количество нелистовых узлов на уровне i; symb[] — перестановка символов алфавита, отсортированная по двум ключам: первичный — длина кода, вторичный — лексикографическое значение; offs[i] — индекс массива symb[], такой что symb[offs[i]] первый листовой узел (символ) на уровне i.

Приведем несколько пояснений. base[0]=? и offs[0]=? не используются, т.к. нет кодов длины 0, а offs[2]=? — т.к. на втором уровне нет листовых узлов.

Теперь приведем алгоритм декодирования (CANONICAL_DECODE) [5]:

  1. code = следующий бит из потока, length = 1
  2. Пока code / .

Z / =»0001 1 00001 00000 1 010 011 1 011 1 010 011 0001 1 0010 010 011 011 1 1 1 010 1 1 1 0010 011 0011 1 0011 0011 011 1 010 1 1″

  1. code = 0, length = 1
  2. code = 0 base[length] = 0
  3. symbol = symb[offs[length] = 0 + code = 1 — base[length] = 0] = symb[1] = F

Итак, мы декодировали 3 первых символа: A, H, F. Ясно, что следуя этому алгоритму мы получим в точности сообщение S.

Это, пожалуй, самый простой алгоритм для декодирования канонических кодов. К нему можно придумать массу усовершенствований. Подробнее о них можно прочитать в [5] и [9].

Вычисление длин кодов

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

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

На сегодняшний день существует множество эффективных алгоритмов вычисления длин кодов ([3], [4]). Мы ограничимся рассмотрением лишь одного из них. Этот алгоритм достаточно прост, но несмотря на это очень популярен. Он используется в таких программах как zip, gzip, pkzip, bzip2 и многих других.

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

Будем считать, что для каждого узла сохранен указатель на его родителя. У корня дерева этот указатель положим равным NULL. Выберем теперь листовой узел (символ) и следуя сохраненным указателям будем подниматься вверх по дереву до тех пор, пока очередной указатель не станет равен NULL. Последнее условие означает, что мы добрались до корня дерева. Ясно, что число переходов с уровня на уровень равно глубине листового узла (символа), а следовательно и длине его кода. Обойдя таким образом все узлы (символы), мы получим длины их кодов.

Максимальная длина кода

Как правило, при кодировании используется так называемая кодовая книга (CodeBook), простая структура данных, по сути два массива: один с длинами, другой с кодами. Другими словами, код (как битовая строка) хранится в ячейке памяти или регистре фиксированного размера (чаще 16, 32 или 64). Для того чтобы не произошло переполнение, мы должны быть уверены в том, что код поместится в регистр.

Оказывается, что на N-символьном алфавите максимальный размер кода может достигать (N-1) бит в длину. Иначе говоря, при N=256 (распространенный вариант) мы можем получить код в 255 бит длиной (правда для этого файл должен быть очень велик: 2.292654130570773*10^53

=2^177.259)! Ясно, что такой код в регистр не поместится и с ним нужно что-то делать.


Для начала выясним при каких условиях возникает переполнение. Пусть частота i-го символа равна i-му числу Фибоначчи. Например: A-1, B-1, C-2, D-3, E-5, F-8, G-13, H-21. Построим соответствующее дерево Хаффмана.

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

Эту проблему можно решить двумя приемлемыми способами. Первый из них опирается на одно из свойств канонических кодов. Дело в том, что в каноническом коде (битовой строке) не более [log2N] младших бит могут быть ненулями. Другими словами, все остальные биты можно вообще не сохранять, т.к. они всегда равны нулю. В случае N=256 нам достаточно от каждого кода сохранять лишь младшие 8 битов, подразумевая все остальные биты равными нулю. Это решает проблему, но лишь отчасти. Это значительно усложнит и замедлит как кодирование, так и декодирование. Поэтому этот способ редко применяется на практике.

Второй способ заключается в искусственном ограничении длин кодов (либо во время построения, либо после). Этот способ является общепринятым, поэтому мы остановимся на нем более подробно.

Существует два типа алгоритмов ограничивающих длины кодов. Эвристические (приблизительные) и оптимальные. Алгоритмы второго типа достаточно сложны в реализации и как правило требуют больших затрат времени и памяти, чем первые. Эффективность эвристически-ограниченного кода определяется его отклонением от оптимально-ограниченного. Чем меньше эта разница, тем лучше. Стоит отметить, что для некоторых эвристических алгоритмов эта разница очень мала ([6], [7], [8]), к тому же они очень часто генерируют оптимальный код (хотя и не гарантируют, что так будет всегда). Более того, т.к. на практике переполнение случается крайне редко (если только не поставлено очень жесткое ограничение на максимальную длину кода), при небольшом размере алфавита целесообразнее применять простые и быстрые эвристические методы.

Мы рассмотрим один достаточно простой и очень популярный эвристический алгоритм. Он нашел свое применение в таких программах как zip, gzip, pkzip, bzip2 и многих других.

Задача ограничения максимальной длины кода эквивалентна задаче ограничения высоты дерева Хаффмана. Заметим, что по построению любой нелистовой узел дерева Хаффмана имеет ровно два потомка. На каждой итерации нашего алгоритма будем уменьшать высоту дерева на 1. Итак, пусть L — максимальная длина кода (высота дерева) и требуется ограничить ее до L / &lt L. Пусть далее RNi самый правый листовой узел на уровне i, а LNi — самый левый.

Начнем работу с уровня L. Переместим узел RNL на место своего родителя. Т.к. узлы идут парами нам необходимо найти место и для соседного с RNL узла. Для этого найдем ближайший к L уровень j, содержащий листовые узлы, такой, что j &lt (L-1). На месте LNj сформируем нелистовой узел и присоединим к нему в качестве дочерних узел LNj и оставшийся без пары узел с уровня L. Ко всем оставшимся парам узлов на уровне L применим такую же операцию. Ясно, что перераспределив таким образом узлы, мы уменьшили высоту нашего дерева на 1. Теперь она равна (L-1). Если теперь L / &lt (L-1), то проделаем то же самое с уровнем (L-1) и т.д. до тех пор, пока требуемое ограничение не будет достигнуто.

Вернемся к нашему примеру, где L=5. Ограничим максимальную длину кода до L / =4.

Видно, что в нашем случае RNL=F, j=3, LNj=C. Сначала переместим узел RNL=F на место своего родителя.

Теперь на месте LNj=C сформируем нелистовой узел.

Присоединим к сформированному узлу два непарных: B и C.

Таким образом, мы ограничили максимальную длину кода до 4. Ясно, что изменив длины кодов, мы немного потеряли в эффективности. Так сообщение S, закодированное при помощи такого кода, будет иметь размер 92 бита, т.е. на 3 бита больше по сравнению с минимально-избыточным кодом.

Ясно, что чем сильнее мы ограничим максимальную длину кода, тем менее эффективен будет код. Выясним насколько можно ограничивать максимальную длину кода. Очевидно что не короче [log2N] бит.

Вычисление канонических кодов

Как мы уже неоднократно отмечали, длин кодов достаточно для того чтобы сгенерировать сами коды. Покажем как это можно сделать. Предположим, что мы уже вычислили длины кодов и подсчитали сколько кодов каждой длины у нас есть. Пусть L — максимальная длина кода, а Ti — количество кодов длины i.

Вычислим Si — начальное значение кода длины i, для всех i из [1..L]

Для нашего примера L = 5, T1 .. 5 = <1, 0, 2 ,3, 2>.

Видно, что S5, S4, S3, S1 — в точности коды символов B, A, C, H. Эти символы объединяет то, что все они стоят на первом месте, каждый на своем уровне. Другими словами, мы нашли начальное значение кода для каждой длины (или уровня).

Теперь присвоим коды остальным символам. Код первого символа на уровне i равен Si, второго Si + 1, третьего Si + 2 и т.д.

Выпишем оставшиеся коды для нашего примера:

B = S5 = 00000bin A = S4 = 0001bin C = S3 = 010bin H = S1 = 1bin
F = S5 + 1 = 00001bin D = S4 + 1 = 0010bin E = S3 + 1 = 011bin
G = S4 + 2 = 0011bin

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

Передача кодового дерева

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

Решить эту задачу можно несколькими способами. Самое очевидное решение — сохранить дерево в явном виде (т.е. как упорядоченное множество узлов и указателей того или иного вида). Это пожалуй самый расточительный и неэффективный способ. На практике он не используется.

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

Наконец, можно использовать одно из свойств канонических кодов. Как уже было отмечено ранее, канонические коды вполне определяются своими длинами. Другими словами, все что необходимо декодеру — это список длин кодов символов. Учитывая, что в среднем длину одного кода для N-символьного алфавита можно закодировать [(log2(log2N))] битами, получим очень эффективный алгоритм. На нем мы остановимся подробнее.

Предположим, что размер алфавита N=256, и мы сжимаем обыкновенный текстовый файл (ASCII). Скорее всего мы не встретим все N символов нашего алфавита в таком файле. Положим тогда длину кода отсутвующих символов равной нулю. В этом случае сохраняемый список длин кодов будет содержать достаточно большое число нулей (длин кодов отсутствующих символов) сгруппированных вместе. Каждую такую группу можно сжать при помощи так называемого группового кодирования — RLE (Run — Length — Encoding). Этот алгоритм чрезвычайно прост. Вместо последовательности из M одинаковых элементов идущих подряд, будем сохранять первый элемент этой последовательности и число его повторений, т.е. (M-1). Пример: RLE(«AAAABBBCDDDDDDD»)=A3 B2 C0 D6.

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

Реализация: SHCODEC

Большинство идей, изложенных в этой статье, легли в основу программы SHCODEC (Static Huffman COder / DECoder). SHCODEC — является свободно-распространяемой программой (freeware). Программу, исходный код, документацию, а так же результаты испытаний можно найти тут: http://www.webcenter.ru/

Приложение: биография Д. Хаффмана

Список литературы

[1] D.A. Huffman, «A method for the construction of minimum-redundancy codes», Proc. Inst. Radio Engineers, vol. 40, no. 9, pp. 1098-1101, Sep. 1952. [Скачать]

[2] E.S. Schwartz, B. Kallick, «Generating a canonical prefix encoding», Communications of the ACM, vol. 7, no. 3, pp. 166-169, Mar. 1964.

[3] J.V. Leeuwen, «On the construction of Huffman trees», Proc. 3rd International Colloquium on Automata, Languages, and Programming, Edinburgh University, pp. 382-410 July 1976.

[4] J. Katajainen, A. Moffat, «In-place calculation of minimum-redundancy codes», Proc. Workshop on Algorithms and Data Structures, pp. 393-402, Aug. 1995. [Скачать]

[5] A. Moffat, A. Turpin, «On the implementation of minimum-redundancy prefix codes», IEEE Transactions on Communications, vol. 45, no. 10, pp. 1200-1207, June 1997. [Скачать]

Алгоритм Хаффмана на примере

Лабораторная работа № 1. Исследование алгоритмов сжатия информации

Алгоритм Хаффмана

Алгоритм Хаффмана основывается на том, что символы в текстах как правило встречаются с различной частотой.

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

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

Алгоритм Хаффмана на примере

Необходимо закодировать строку «Сжатие Хаффмана»

Вначале нужно подсчитать количество вхождений каждого символа в тексте.

С ж а т и е Х ф м н

Эта таблица называется «таблица частот».

Теперь необходимо построить дерево.

Узел дерева будет образован набором символов и числом — суммарным количеством вхождений данных символов в тексте. Назовем указанное число — весом узла.

Листьями дерева будут узлы, образованные одним символом:

Далее необходимо выполнить следующее:

1) Найти среди узлов, не имеющих родителя, два узла, имеющих в сумме наименьший вес.

2) Создать новый узел, его потомками будут два выбранных узла. Его весом будет сумма весов выбранных улов. Его набор символов будет образован в результате объединения наборов символов выбранных узлов.

Создаем первый узел

Создаем еще один узел

Создаем еще один узел


Создаем еще один узел

Создаем еще один узел

Создаем еще один узел

Создаем еще один узел

Создаем еще один узел

Создаем еще один узел

Создаем еще один узел

Теперь для каждого узла, имеющего потомков, пометим дуги, идущие вниз, на одной дуге напишем 0, на другой 1.

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

Получаются следующие коды

С
ж
а
т
и
е
Х
ф
м
н

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

Закодированная строка будет выглядеть:

С ж а т и е Х а ф ф м а н а

Для декодирования можно воспользоваться построенным деревом. Начинаем с корня дерева и в качестве текущего бита берем начало текста.

В цикле делаем следующее

1) Смотрим, какое значение у текущего бита, и идем вниз по дереву по дуге, на которой указано такое же значение.

2) Переходим к следующему биту.

3) Если сейчас находимся в листе дерева: читаем символ находящийся в этом листе и записываем его в результат декодирования, переходим снова в корень дерева.

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

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

Чтобы передавать таблицу частот нужно всегда помечать левую дугу 1, а правую 0 (или наоборот), чтобы можно было восстановить дерево по таблице.

Алгоритм Шеннона-Фано

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

Если символы, составляющие данное слово, отсортировать по убыванию частоты их появления, то получим следующую последовательность: <а(5), т(2), в(1), и(1), к(1), с(1), р(1), о(1), ф(1)>(в скобках указывается частота повторяемости символа в слове). Далее, нам нужно разделить эту последовательность на две части так, чтобы в каждой из них сумма частот символов была примерно одинаковой (насколько это возможно). Понятно, что раздел пройдет между символами «т» и «в», в результате чего образуется две последовательности: <а(5), т(2)>и <в(1), и(1), к(1), с(1), р(1), о(1), ф(1)>. Причем суммы частот повторяемости символов в первой и второй последовательностях будут одинаковы и равны 7.

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

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

В частности, последовательность <а(5), т(2)>разделится на два отдельных символа: a(5) и т(2) (других вариантов деления нет). Тогда вторая цифра кода для символа «a» — это «0», а для символа «т» — «1». Поскольку в результате деления последовательности мы получили отдельные элементы, то они более не делятся и для символа «a» получаем код 00, а для символа «т» — код 01.

В первом случае суммы частот повторяемости символов в первой и второй последовательностях будут 3 и 4 соответственно, а во втором случае — 4 и 3 соответственно. Для определенности воспользуемся первым вариантом.

Для символов полученной новой последовательности <в(1), и(1), к(1)>(это левая последовательность) первые две цифры кода будут 10, а для последовательности <с(1), р(1), о(1), ф(1)>— 11.

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

В нашем примере получается следующая система префиксных кодов: «a» — 00, «т» — 01, «в» — 100, «и» — 1010, «к» — 1011, «с» — 1100, «р» — 1101, «о» — 1110, «ф» — 1111. Как нетрудно заметить, более короткие коды не являются началом более длинных кодов, то есть выполняется главное свойство префиксных кодов.

Арифметическое сжатие

Согласно критерию Шеннона, оптимальным является такой код, в котором под каждый символ отводится код длиной –log2 p бит. И если, к примеру, вероятность какого-то символа составляет 0,2, то оптимальная длина его кода будет равна –log2 0,2 = 2,3 бит. Понятно, что префиксные коды не могут обеспечить такую длину кода, а потому не являются оптимальными. Вообще длина кода, определяемая критерием Шеннона, — это лишь теоретический предел. Вопрос лишь в том, какой способ кодирования позволяет максимально приблизиться к этому теоретическому пределу. Префиксные коды переменной длины эффективны и достаточно просты в реализации, однако существуют и более эффективные способы кодирования, в частности алгоритм арифметического кодирования.

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

Идея алгоритма арифметического кодирования заключается в следующем. Как и во всех рассмотренных ранее способах кодирования, каждый символ исходной информационной последовательности характеризуется его вероятностью. Исходной незакодированной последовательности ставится в соответствие полуинтервал [0, 1). Далее, если информационное сообщение содержит N символов, то этот интервал делится на N отдельных полуинтервалов, каждый из которых соответствует какому-то символу. Причем длина полуинтервала, соответствующего какому-либо символу, равна вероятности этого символа. Поясним это на примере. Рассмотрим информационную последовательность слова «макака». Выпишем все символы, входящие в эту последовательность, с указанием их вероятности: <м(1/6), а(3/6), к(2/6)>(сортировка символов может быть произвольной). Далее, выделим на рабочем полуинтервале [0, 1) полуинтервал [0, 1/6), соответствующий символу «м» (длина полуинтервала равна вероятности символа). Затем сделаем то же самое для символа «а», которому будет соответствовать полуинтервал [1/6, 4/6) длиной 3/6. Символу «к» будет соответствовать полуинтервал [4/6, 1) длиной 2/6 (рис. 7).

В результате мы получим, что любое вещественное число из полуинтервала [0, 1) однозначно соответствует какому-то символу исходной информационной последовательности. К примеру, число 0,4 входит в полуинтервал [1/6, 4/6) и, следовательно, соответствует символу «а».

Представление символов информационного алфавита в соответствии с их вероятностями на рабочем полуинтервале [0, 1) — это подготовительный этап кодирования. Сам процесс кодирования заключается в следующем. Берется первый символ исходной информационной последовательности, и для него определяется соответствующий полуинтервал на рабочем отрезке. Далее этот полуинтервал становится новым рабочим отрезком, который также необходимо разбить на полуинтервалы в соответствии с вероятностями символов. Если бы мы захотели закодировать только один первый символ нашей последовательности, то на этом операция кодирования закончилась бы. Любое вещественное число из нового рабочего полуинтервала соответствовало бы нашему символу. Однако нам нужно закодировать не один символ, а их последовательность. Поэтому берем второй символ и определяем для него соответствующий полуинтервал уже на новом рабочем отрезке. Далее этот полуинтервал становится новым рабочим отрезком, который также необходимо разбить на полуинтервалы в соответствии с вероятностями символов. Причем этот рабочий полуинтервал уже соответствует двум символам информационной последовательности, то есть любое вещественное число из этого нового рабочего полуинтервала соответствует двум первым символам информационной последовательности. Продолжая такие итерации, мы, в конечном счете, получим некоторый полуинтервал, который соответствует всей исходной информационной последовательности.

На каждом шаге итерации необходимо пересчитывать границы всех полуинтервалов на новом рабочем полуинтервале. Пусть, к примеру, первому символу последовательности на рабочем полуинтервале [0, 1) соответствует полуинтервал [a, b), а второму символу — полуинтервал [c, d).

Поскольку на первом шаге кодирования новым рабочим полуинтервалом станет полуинтервал [a, b), то в этом рабочем полуинтервале второму символу будет соответствовать полуинтервал [a+(b–a)×c, a+(b–a)×d). То есть полуинтервал [c, d) сожмется в (b–a) раз. Любое число из полуинтервала [a+(b–a)×c, a+(b–a)×d) однозначно определяет последовательность двух первых символов.

Ну а теперь рассмотрим процесс кодирования на конкретном примере информационной последовательности слова «макака» (рис. 8).

Итак, первый символ — «м». На рабочем полуинтервале [0, 1) этому символу соответствует полуинтервал [0, 1/6), который становится новым рабочим полуинтервалом.

Далее, на новом рабочем полуинтервале [0, 1/6) откладываем полуинтервалы, соответствующие символам «м», «а» и «к». Символу «м» будет соответствовать уже полуинтервал [0, 1/36), символу «а» — полуинтервал [1/36, 4/36), а символу «к» — полуинтервал [4/36, 1/6). Отметим, что любое число из нового рабочего полуинтервала [0, 1/6) однозначно соответствует символу «м».

Следующий символ последовательности слова «макака» — это «а». На рабочем полуинтервале [0, 1/6) ему соответствует полуинтервал [1/36, 4/36), который и становится новым рабочим полуинтервалом. Далее, на новом рабочем полуинтервале [1/36, 4/36) откладываем полуинтервалы, соответствующие символам «м», «а» и «к». Символу «м» будет соответствовать уже полуинтервал [1/36, 3/72), символу «а» — полуинтервал [3/72, 3/36), а символу «к» — полуинтервал [3/36, 4/36). В данном случае важно, что уже любое вещественное число из рабочего полуинтервала [1/36, 4/36) представляет последовательность «ма».

Чтобы доказать это, рассмотрим число 1/36, входящее в этот полуинтервал. Поскольку это число входит в промежуток [0, 1/6), соответствующий символу «м» на исходном рабочем полуинтервале, то первый символ последовательности — это «м». Далее, необходимо отобразить (расширить) промежуток [0, 1/6) на исходный рабочий полуинтервал [0, 1). Для этого все точки полуинтервала [0, 1/6) делим на его длину (на 1/6). При этом число 1/36 перейдет в число 1/6. То есть мы как бы делаем обратное преобразование. Но число 1/6 на рабочем полуинтервале [0, 1) входит в промежуток [1/6, 4/6), соответствующий символу «а». Следовательно, второй символ последовательности — это «а».

Итак, мы выяснили, что число 1/36 из рабочего промежутка [1/36, 4/36) кодирует последовательность «ма». Пойдем дальше. Следующий символ последовательности «макака» — это «к». На рабочем полуинтервале [1/36, 4/36) ему соответствует промежуток [3/36, 4/36), который и становится новым рабочим полуинтервалом. Далее, на новом рабочем полуинтервале [3/36, 4/36) откладываем промежутки, соответствующие символам «м», «а» и «к». Символу «м» будет соответствовать уже полуинтервал [3/36, 19/216), символу «а» — полуинтервал [19/216, 22/216), а символу «к» — полуинтервал [22/216, 4/36). Любое вещественное число из рабочего полуинтервала [3/36, 4/36) представляет последовательность «мак». Теперь рассмотрим процесс раскодирования этой последовательности. Поскольку число 3/36 или 1/12 входит в полуинтервал [3/36, 4/36), покажем, что это число соответствует последовательности «мак».

Действительно, число 1/12 входит в промежуток [0, 1/6) на исходном рабочем полуинтервале, который соответствует символу «м». Следовательно первый символ — это «м». Далее, проецируем промежуток [0, 1/6) на промежуток [0, 1); при этом число 1/12 отобразится в число 1/2 на рабочем полуинтервале [0, 1). Поскольку число 1/2 входит в полуинтервал [1/6, 4/6), соответствующий символу «а», то второй символ последовательности — это «а». Затем необходимо спроецировать промежуток [1/6, 4/6) на рабочий полуинтервал [0, 1). При этом число 1/2 отобразится в число 2/3. Поскольку это число входит в промежуток [4/6, 1) на рабочем полуинтервале [0, 1), который соответствует символу «к», то третий символ последовательности — это «к».

Продолжая аналогичные действия по кодированию символов, мы придем к рабочему полуинтервалу [127/1296, 130/1296), который будет отвечать за все последовательности слова «макака» (рис. 8). Любое число из этого полуинтервала (например, 127/1296) однозначно определяет всю последовательность слова «макака» а обратное раскодирование осуществляется в шесть шагов.

Единственное, на чем имеет смысл остановиться при обратном раскодировании, это на процедуре проецирования полуинтервала [a, b) на полуинтервал [0, 1). При таком проецировании любая точка, принадлежащая промежутку [a, b), отобразится в точку x = (ca)/(ba), что легко доказать геометрически, используя обобщенную теорему Фалеса (рис. 9).

В качестве примера рассмотрим отображение промежутка [1/6, 2/3) на промежуток [0, 1). При таком проецировании число 1/2 из промежутка [1/6, 2/3) отобразится на число (1/2 – 1/6)/(2/3 – 1/6) = 2/3.

Итак, мы подробно рассмотрели процесс арифметического кодирования-декодирования. Отметим, что, в отличие от префиксного кодирования, в арифметическом кодировании символам не могут быть сопоставлены конкретные кодовые комбинации. Понятие «код» в данном случае несколько абстрактно и применимо только для информационной последовательности в целом. Здесь можно говорить только о вкладе, вносимом каждым символом, входящим в кодируемое информационное сообщение, в результирующую кодовую комбинацию. Этот вклад определяется длиной интервала, соответствующего символу, то есть вероятностью появления символа. Также отметим, что для возможности процесса декодирования декодер должен иметь информацию о том, какой именно промежуток соответствует каждому символу информационного алфавита на рабочем полуинтервале [0, 1). То есть данная информация является служебной и должна быть доступна декодеру.

До сих пор мы ничего не говорили о самом коде, который получится в результате арифметического кодирования. В рассмотренном нами примере со словом «макака» процесс арифметического кодирования завершился тем, что любое число из промежутка [127/1296, 130/1296) представляет последовательность «макака». Вопрос в том, какое именно число выбрать и как ему поставить в соответствие двоичный код. Можно использовать следующий способ: взять любое число из результирующего промежутка, перевести его в двоичную форму и отбросить целую часть двоичной дроби, равную нулю, — оставшаяся последовательность нулей и единиц и будет нашим кодом. Можно использовать и десятичное представление числа, но опять-таки использовать только дробную часть числа (отбросить ноль и десятичную запятую), представив ее в двоичном виде, который и задаст код последовательности.

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

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

Идея заключается в том, чтобы числа, определяющие концы полуинтервалов, определялись бы целыми числами с разрядностью 16, 32 или 64 бита. Казалось бы, как это можно реализовать, если концы промежутков могут иметь неограниченное число знаков после запятой?

Прежде всего отметим, что все наши числа имеют вид 0,xxx… Поэтому 0 перед запятой можно отбросить и рассматривать лишь последовательности цифр после запятой. Далее, если концы всех промежутков выписать в десятичных дробях, можно заметить, что как только самые левые цифры чисел (рассматривается только дробная часть, то есть цифры после запятой), которые определяют концы рабочего полуинтервала на каждом шаге итерации, становятся одинаковыми, они уже не меняются в дальнейшем (на следующих итерациях). Отметим, что в нашем примере c последовательностью «макака» мало шагов итераций и даже на конечном шаге нет одинаковых левых цифр чисел, но при большем числе итераций они неизбежно появятся. Одинаковые цифры можно выдвинуть за скобки и работать с оставшейся дробной частью, которая ограничивается по длине. В ходе итераций уточняется последовательность цифр, выдвинутых за скобки, которая и представляет собой код.

Итак, метод арифметического кодирования — один из самых эффективных по степени сжатия алгоритмов, но скорость такого кодирования невысока.

Алгоритм LZW

Еще один распространенный алгоритм кодирования получил название LZW — по первым буквам фамилий его разработчиков: Lempel, Ziv и Welch (алгоритм Лемпеля—Зива—Велча).


Алгоритм был опубликован Велчем в 1984 году в качестве улучшенной реализации алгоритма LZ78, представленного Лемпелем и Зивом в 1978 году, и был запатентован фирмой Sperry.

Алгоритм LZW использует идею расширения информационного алфавита. Вместо традиционного 8-битного представления 256 символов ASCII-таблицы обычно используется 12-битное, что позволяет определить таблицу на 4096 записей.

Идея алгоритма LZW заключается в том, чтобы заменять строки символов некоторыми кодами, для чего и используется таблица на 4096 записей. Это делается без какого-либо анализа входной последовательности символов. При добавлении каждой новой строки символов просматривается таблица строк. Сжатие происходит, когда строка символов заменяется кодом. Первые 256 кодов (когда используются 8-битные символы) по умолчанию соответствуют стандартному набору символов, то есть значения кодов 0-255 соответствуют отдельным байтам. Остальные коды (256-4095) соответствуют строкам обрабатываемым алгоритмом.

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

Рассмотрим в качестве примера входную последовательность ABCABCABCABCABCABC#. Маркер # будет символизировать конец исходного сообщения.

Для простоты будем считать, что используются только заглавные буквы английского алфавита (26 букв) и маркер # конца сообщения. Соответственно для перебора всех букв нашего алфавита достаточно 5 бит (25 = 32). Теперь предположим, что символы нашего алфавита кодируются по номеру буквы в алфавите от 1 до 26 следующим образом:

Последний символ Z будет иметь код 11010 (2610).

Отметим, что когда в нашей таблице кодов появится символ с кодом 32, то алгоритм должен перейти к 6-битным группам.

В нашем примере первый символ — это «A». Поскольку при инициализации в таблицу были занесены все односимвольные строки, то строка, соответствующая символу «A», в таблице есть (код символа 00001).

Далее считывается следующий символ «B» из входного потока и проверяется, есть ли строка «AB» в таблице. Такой строки в таблице пока нет. Поэтому данная строка заносится в таблицу с первым свободным кодом 100 000 (3210), а в выходной поток записывается код 00001, соответствующий предыдущему символу («A»).

Далее начинаем с символа, которым оканчивается последняя занесенная в таблицу строка, то есть с символа «B». Поскольку символ «B» есть в таблице, то считываем следующий символ «C». Строки «BC» в таблице нет, поэтому заносим эту строку в таблицу под кодом 100 001 (3310), а в выходной поток записывается код 00010, соответствующий предыдущему символу ( «В»).

Далее начинаем с символа, которым оканчивается последняя занесенная в таблицу строка, то есть с символа «С». Поскольку символ «С» есть в таблице, то считываем следующий символ «A». Строки «CA» нет в таблице, поэтому заносим эту строку в таблицу под кодом 100 010 (3410), а в выходной поток записывается код 00011, соответствующий предыдущему символу (символу «C»).

Затем начинаем с символа, которым оканчивается последняя занесенная в таблицу строка, то есть, с символа «A». Поскольку символ «A» есть в таблице, то считываем следующий символ «B». Строка «AB» уже есть в таблице, поэтому считываем следующий символ «C». Строки «ABC» нет в таблице, поэтому заносим эту строку в таблицу под кодом 100 011 (3510), а в выходной поток записывается код 100 000, соответствующий предыдущему символу в таблице (строке «AB»).

Далее начинаем с символа «C». Поскольку он уже есть в таблице, считываем следующий символ «A». Строка «CA» уже есть в таблице, поэтому считываем следующий символ «B». Строки «CAB» нет в таблице, поэтому заносим ее туда, а в выходной поток записываем код 100 010, соответствующий строке «CA».

Продолжая подобным образом, построим таблицу кодов для всего сообщения ABCABCABCABCABCABC# (табл. 1).

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

В заключение отметим, что алгоритм LZW находит применение в сжатии растровых изображений (форматы JPG, TIFF), а также в таком популярном формате, как PDF.

Реализовать кодирование и декодирование информации заданным.

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

Вариант 2. Выполнить кодирование и декодирование англоязычного текста методом Хаффмана.

Вариант 3. Выполнить кодирование и декодирование графического файла (BMP, GIF) методом Хаффмана.

Вариант 4. Выполнить кодирование и декодирование русскоязычного текста методом Шеннона-Фано.

Вариант 5. Выполнить кодирование и декодирование англоязычного текста методом Шеннона-Фано.

Вариант 6. Выполнить кодирование и декодирование графического файла (BMP, GIF) методом Шеннона-Фано.

Вариант 7. Выполнить кодирование и декодирование русскоязычного текста методом арифметического сжатия.

Вариант 8. Выполнить кодирование и декодирование англоязычного текста методом арифметического сжатия.

Вариант 9. Выполнить кодирование и декодирование русскоязычного текста используя алгоритм LZW.

Вариант 10. Выполнить кодирование и декодирование англоязычного текста используя алгоритм LZW.

Вариант 11 Выполнить кодирование и декодирование графического файла используя алгоритм LZW.

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

Экономное кодирование информации по алгоритму Хаффмана

Рассматриваются алгоритм Хаффмана в двоичной и троичной системе, производится анализ эффективности, описываются особенности реализации.

Алгоритм Хаффмана

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

Например, при экономном кодировании символьной информации часто встречаемые символы кодируются короткими кодами, в то время как редко встречающиеся — длинными.

Префиксные коды и алгоритмы их получения подробно описаны в монографии Семенюка В. В. «Экономное кодирование дискретной информации » [1].

Алгоритм Хаффмана для двоичной системы

  1. Вычисляем вероятность появления каждого символа в информации
  2. Каждому символу присваивается значение равное его частоте вхождения
  3. Полученный список элементов (пара символ — значение) сортируется по убыванию: от часто встречаемых к менее встречаемым
  4. Два последних элемента списка объединяются в новый элемент, значение которого равно сумме значений вошедших в него элементов, т.е. вместо двух последних элементов записывается новый
  5. Новый список сортируется по убыванию
  6. Операции 4, 5 выполняются до тех пор? пока не останется один элемент
  7. Выписывается последний оставшейся элемент
  8. От него откладывают две ветви с элементами, которые его составляют
  9. От каждого элемента, если он не является символом, откладываются такие же две ветви с входящими в него элементами
  10. Процесс выполняется до тех пор, пока все элементы не будут выписаны
  11. Каждому ребру назначается коды 0 и 1
  12. Для каждого символа (не элемента) в дереве выписывается префиксный код, как последовательность кодов рёбер идущих от вершины к символу

Особенности алгоритма Хаффмана для троичной системы

Алгоритмы Хаффмана для двоичной и троичной системы аналогичны.

Однако есть ряд отличий и особенностей.

Так, вместо объедения двух последних элементов, при кодировании в троичной системе объединяются три.

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

Доказательство. Так как при объединении трех элементов одним получаем список меньше предыдущего на два элемента и, учитывая условие, что на последнем этапе необходимо, чтобы объединилось три элемента, получим, что эффективно будет кодироваться список 3+2·k элементами, т.е. с нечётным количеством элементов. Поэтому при четном количестве элементов — 3 + 2k + 1 — первоначально объединяются два элемента, т.е. получаем список с (3 + 2k) элементов — с нечетным количеством элементов.

Алгоритм Хаффмана для троичной системы

  1. Вычисляем вероятность появления каждого символа в информации

  2. Каждому символу присваивается значение равное его частоте вхождения
  3. Полученный список элементов (пара символ — значение) сортируется по убыванию: от часто встречаемых к менее встречаемым
  4. Определяется количество элементов в списке
  5. Если количество элементов чётно, то в новый элемент объединяются два последних элемента списка, если количество нечётно — объединяются три элемента, значение нового элемента равно сумме значений вошедших в него элементов
  6. Новый список сортируется по убыванию
  7. Три последних элемента объединяются в новый
  8. Новый список сортируется по убыванию
  9. Операции 7,8 выполняются до тех пор, пока не останется один элемент
  10. Выписывается последний оставшейся элемент
  11. От него откладывают три ветви с элементами, которые его составляют
  12. От каждого элемента, если он не является символом, откладываются такие же три ветви с входящими в него элементами.
  13. Процесс выполняется до тех пор, пока все элементы не будут выписаны
  14. Каждому ребру назначается коды -, 0 и +
  15. Для каждого символа (не элемента) в дереве выписывается префиксный код, как последовательность кодов рёбер идущих от вершины к символу

Построение двоичного и троичного кодового дерева

Рассмотрим построения двоичного и троичного кодовых деревьев по алгоритму Хаффмана.

Кодируемое сообщение: «ГОЛОГРАММА».

Статистика появления символов в сообщении: Г(2), О(2), Л(1), Р(1), A(2), М(2).

Упорядоченный список: A(2), Г(2), М(2), О(2), Л(1), Р(1).

Двоичное дерево Хаффмана

Троичное дерево Хаффмана

Примечание. Список состоит из 6 элементов — количество четное — на первом шаге объединяем только два последних элемента.

Кодирование в двоичной системе Кодирование в троичной системе
Символ Частота Двоичная система Троичная система
Префиксный код Длина кода Сумма Префиксный код Длина кода Сумма
А 2 10 2 4 1 2
Г 2 11 2 4 2 4
М 2 000 3 6 -0 2 4
О 2 001 3 6 -+ 2 4
Л 1 010 3 3 +- 2 2
Р 1 011 3 3 +0 2 2
Итого: 26 Итого: 18

Сравнение алгоритма для двоичной и троичной систем

Оценим количество шагов для построения деревьев.

Кодирование в двоичной системе Кодирование в троичной системе
Пусть L = 2n (n — натуральное число) — количество элементов в первоначальном списке, K — количество шагов (K — натуральное число). На каждом шаге происходит объединение 2-х элементов в 1, — список с каждым шагом уменьшается на 1 элемент. Таким образом, на предпоследнем шаге останется 2 элемента, т.е. L-(K-1) = 2. Таким образом, K = L – 1 = 2n -1. Первоначально рассмотрим случай, когда количество элементов в первоначальном списке чётно, L = 2n (n — натуральное число) — количество элементов в первоначальном списке, K — количество шагов (K — натуральное число). На каждом шаге происходит объединение 3-х элементов в 1, т.е. список с каждым шагом уменьшается на 1 элемент. Однако в соответствии с оптимальным алгоритмом на первом шаге необходимо объединять в один элемент 2, а не 3. Будем считать, что первый шаг выполнен, было объединено только 2 элемента в 1 (L-1). Таким образом, на предпоследнем шаге останется 3 элемента, т.е. L-2*(K-2) — 1= 3. Таким образом, K = L – 1 = 2n -1.

Оценим эффективность построения деревьев.

Кодирование в двоичной системе Кодирование в троичной системе
Каждый уровень дерева может содержать до 2 n элементов, где n ― номер уровня, т.е. 1-ый уровень содержит 2 элемента, 2-ой ― 4, 3-ий ― 8, 10-ый уровень может содержать уже 2 10 , т.е 1024 элементов. Каждый уровень дерева может содержать до 3 n элементов. Таким образом, 10-ый уровень может содержать 3 10 , т.е 59049 элементов.

Порядок уровня определяет длину префиксного кода. Например, длина префиксных кодов элементов 1-го уровня равна 1, 7-ого ― 7 . Соответственно, чем меньше уровней будет в дереве, тем более экономичным будет кодирование.

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

Так на 9-й уровень при кодировании в троичной системе может содержать до 19683 элементов, при кодировании в двоичной системе 9-й уровень может содержать только 512. Лишь 14-й уровень будет содержать примерно такое же количество элементов (15-й уровень будет уже содержать большее, чем 9-й при троичном кодировании). Относительную эффективность можно оценить по соотношению уровней. Из приведённой ниже таблицы видно, что, в среднем, кодирование в троичной системе эффективнее в 1,5 раза чем в двоичной.

Кодирование в троичной системе Кодирование в двоичной системе Соотношение
Уровень Максимальное количество элементов Уровень Максимальное количество элементов
1 3 1 2 1.000
2 9 3 8 1.500
3 27 4 16 1.333
4 81 6 64 1.500
5 243 7 128 1.400
6 729 9 512 1.500
7 2187 11 2048 1.571
8 6561 12 4096 1.500
9 19683 14 16384 1.556
10 59049 15 32768 1.500
11 177147 17 131072 1.545
12 531441 19 524288 1.583
13 1594323 20 1048576 1.538
14 4782969 22 4194304 1.571
15 14348907 23 8388608 1.533
16 43046721 25 33554432 1.562
17 129140163 26 67108864 1.529
18 387420489 28 268435456 1.556
19 1162261467 30 1073741824 1.579
20 3486784401 31 2147483648 1.550
21 10460353203 33 8589934592 1.571
22 31381059609 34 17179869184 1.545
23 94143178827 36 68719476736 1.565
24 282429536481 38 274877906944 1.583
25 847288609443 39 549755813888 1.560
26 2541865828329 41 2199023255552 1.577
27 7625597484987 42 4398046511104 1.556
28 22876792454961 44 17592186044416 1.571
29 68630377364883 45 35184372088832 1.552

Выводы

Построение троичного дерева в два раза быстрее (по количеству шагов) и в полтора раза эффективнее (по длине кодов), чем двоичное дерево.

АЛГОРИТМЫ СЖАТИЯ

Метод Хаффмана

Адаптивное сжатие Хаффмана

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

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

Схема адаптивного кодирования/декодирования работает благодаря тому, что при кодировании, и при декодировании используются одни и те же процедуры «ИнициализироватьМодель» и «ОбновитьМодельСимволом» И компрессор, и декомпрессор начинают с «пустой» модели (не содержащей информации о сообщении) и с каждым просмотренным символом обновляют ее одинаковым образом.

Адаптивное кодирование Хаффмана

В создании алгоритма адаптивного кодирования Хаффмана наибольшие сложности возникают при разработке процедуры ОбновитьМодельСимволом() ; можно было бы просто вставить внутрь этой процедуры полное построение дерева Хаффмана. В результате мы получили бы очень медленный алгоритм сжатия, так как построение дерева – это слишком большая работа и производить ее при обработке каждого символа неразумно. К счастью, существует способ модифицировать уже существующее дерево так, чтобы отобразить обработку нового символа.

Упорядоченное Дерево
Будем говорить, что дерево обладает свойством упорядоченности, если его узлы могут быть перечислены в порядке возрастания веса и в этом перечислении каждый узел находится рядом со своим братом. Пример упорядоченного дерева приведен на рисунке:

Здесь W – вес узла, N – порядковый номер в списке узлов.

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

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

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

Если и дальше продолжать обрабатывать увеличение веса, двигаясь к корню дерева, то наше дерево перестанет быть деревом Хаффмана. Чтобы сохранить упорядоченность дерева кодирования, алгоритм работает следующим образом. Пусть новый увеличенный вес узла равен W+1. Тогда начинаем двигаться по списку в сторону увеличения веса, пока не найдем последний узел с весом W. Переставим текущий и найденный узлы между собой в списке, восстанавливая таким образом порядок в дереве.

При этом родители каждого из узлов тоже изменяются. На этом операция перестановки заканчивается. После перестановки операция увеличения веса узлов продолжается дальше.

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

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

Проблемы адаптивного кодирования

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

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

Чтобы разрешить это противоречие, введем специальный ESCAPE код, который будет означать, что следующий символ закодирован вне контекста модели сообщения. Например, его можно передать в поток сжатой информации как есть, не кодируя вообще. Метод «ЗакодироватьСимвол» в алгоритме адаптивного кодирования Хаффмана можно записать следующим образом:

Использование специального символа ESC подразумевает определенную инициализацию дерева до начала кодирования и декодирования: в него помещаются 2 специальных символа: ESC и EOF (конец файла), с весом, равным 1.

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


Коды Хаффмана: примеры, применение

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

История алгоритма

Самым первым алгоритмом проведения эффективного кодирования электронной информации стал код, предложенный Хаффманом еще в середине двадцатого века, а именно в 1952 году. Именно он на данный момент является основным базовым элементом большинства программ, созданных для сжатия информации. На данный момент одними из самых популярных источников, использующих этот код, являются архивы ZIP, ARJ, RAR и многие другие.

Принцип эффективного кодирования

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

Код Хаффмана, пример

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

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

Алгоритм построения дерева по Хаффману

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

Повышение эффективности сжатия

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

Ускорение процесса сжатия

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

Заключение

Коды Хаффмана — простой и давно созданный алгоритм, который до сих пор используется многими известными программами и компаниями. Его простота и понятность позволяют добиться эффективных результатов сжатия файлов любых объемов и значительно уменьшить занимаемое ими место на диске хранения. Иными словами, алгоритм Хаффмана – давно изученная и проработанная схема, актуальность которой не уменьшается по сей день.

Адаптивный алгоритм Хаффмана сжатия информации Текст научной статьи по специальности « Общие и комплексные проблемы естественных и точных наук»

Похожие темы научных работ по общим и комплексным проблемам естественных и точных наук , автор научной работы — Кудрина М.А., Кудрин К.А., Дегтярева О.А., Сопченко Е.В.,

Текст научной работы на тему «Адаптивный алгоритм Хаффмана сжатия информации»

Кудрина М.А., Кудрин К.А., Дегтярева О.А., Сопченко Е.В.

ФГАОУ ВО «Самарский государственный аэрокосмический университет им. академика С.П. Королева (Национальный исследовательский университет)», Самара, Россия

АДАПТИВНЫЙ АЛГОРИТМ ХАФФМАНА СЖАТИЯ ИНФОРМАЦИИ

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

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

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

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

№ узла ] 2 Í 4 5 6 7 К у

] -.i r v t I i 0 I 1 1 1 2 2 3 5

Пример упорядоченного дереЕ Хаффмана

Правила построения и упорядочивания бинарного дерева Хаффмана

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

Левые ветви дерева помечаются 0, а правые —

При нарушении упорядоченности дерева (после добавлении нового листа или изменении веса имеющегося листа) его необходимо упорядочить.

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

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

1. Элементы входного сообщения считываются побайтно.

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

тируются. Если дерево становится неупорядоченным — упорядочивается. з) л* р]

] 2 3 4 5 6 7 S 9

Вес .fia II 2 2 ] 1 .1 2 4 Г>

№ ■ та 1 2 3 4 5 6 7 Я 9

Вес гым II 1 1 1 2 2 2 4 Ь

Рисунок 2 — Пример упорядочивания дерева Хаффмана

3. Если очередной символ, считанный из входного сообщения при сжатии, отсутствует в дереве, е выходной поток записывается набор нулей и единиц, которыми помечены ветки бинарного дерева при движении от корня к escape-символу, а затем 8 бит ASCII-кода нового символа. В дерево вместо escape-символа добавляется ветка: родитель, два потомка. Левый потомок становится escape-символом, правый — новым добавленным в дерево символом. Веса узлов-предков корректируются, а дерево при необходимости упорядочивается.

Например, если мы имеем дерево Хаффмана как на рис. 3а, и очередной символ на входе C, которого еще нет в дереве, то выходной код нового символа будет 00’C’, где ‘C’ — ASCII-код символа С. В дерево добавляется ветка с новым символом (см. рис. 3б) и дерево упорядочивается (см. рис. Зв) .

Рисунок 3 — Пример) добавления нового символа в дерево Хаффмана

Рассмотрим пример работы алгоритма архивации на следующей входной последовательности символов: ABCCDDDDBB.

/щннме ДЗЕЕаЫС дерева : mít

Пример работы алгоритма сжатия из 10 символов

занимает 80 бит.

сообщение занимает 55 бит.

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

Символ Вероятность Код

1001110110100001111 (всего 19 бит). Кроме того, следует учесть, что вместе с закодированным сообщением передается и таблица кодировки. В данном случае это как минимум еще 4 байта АБС11-кодов символов плюс соответствующие им коды Хаффмана. Всего 68 бит.


1. Элементы входного сообщения считываются побитно.

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

3. Если достигнут лист, соответствующий символу, в выходное сообщение записывается АБС11-код данного символа. Вес листа увеличивается на

Пр о г р а мма д е мо н с тр> а ции

1, веса узлов-предков корректируются, дерево при необходимости упорядочивается.

4. Если же достигнут евоаре-символ, из входного сообщения считываются 8 следующих бит, соответствующих АБС11-коду нового символа. В выходное сообщение записывается АБСИ-код данного символа. В дерево добавляется новый символ, веса узлов-предков корректируются, затем при необходимости производится его упорядочивание.

Рассмотрим процесс декодирования сообщения ‘А’0’В’0100’С’11. В начале декодирования дерево Хаффмана содержит только евоаре-символ с частотой 0. С раскодированием каждого нового символа дерево перестраивается (см. рис. 6). На выходе получим последовательность АВВСВВ.

данные данные дерева

— Пример) работы алгоритма декомпрессии

работы алгоритмов сжатия

J Программа демонстрации работы алгоритмов

Сжатие по Хаффману ] 12-алгоритмы

О Блочный алгоритм Адаптивный алгоритм

‘А’ 0’В’ 00’С 101 ÍOÜ’O’ 1101 10 о 1101 111

Предыдущий 11 Сохранить ЕСледующий

| Сжать 11 Просмотр деревьев |

Рисунок 7 — Программа-визуализатор алгоритмов сжатия

Адаптивное кодирование Хаффмана имеет ряд особенностей при своей работе [2, 3]. Одна из них связана с хранением значений кодов символов, при кодировании длинных последовательностей. Дело в том, что языки высокого уровня, обычно, оперируют с числами максимум в 32 бит, в которых можно записывать числа от 0 до 4294967296, т.е. можно работать с файлами размером 4Гб. Но иногда этих значений недостаточно и приходится вырабатывать дополнительные меры по предотвращению переполнения счетчиков символов. Правильное решение может заключаться в накоплении битов кода в связанном списке, к которому можно добавлять новые узлы. Следующая

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

Но, несмотря на указанные сложности, он часто применяется на практике, например, в протоколе У.32 передачи данных по модему со скоро-

стью 14400 бод или в программе compact операционной системы UNIX. Этот алгоритм наиболее эффективен для сжатия текстов или программных файлов. Изображения лучше сжимаются другими алгоритмами сжатия.

На кафедре информационных систем и технологий Самарского государственного аэрокосмического университета им. академика С.П. Королева разработана программа-визуализатор алгоритмов сжатия информации. Данная программа используется в учебном процессе в курсе «Теория информации» [4] при проведении лабораторных работ, а

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

На рис. 7 приведен скриншот работы адаптивного алгоритма Хаффмана

1. Лидовский В.В. Теория информации. — М.:Наука, 2003. — 112 с.

2. http://old.reslib.com/book/Teoriya_informacii_^ЬоУБк^ V V

3. http://rain.ifmo.ru/cat/view.php/theory/data-compression/adaptive-huffman-2 0 0 6

4. http://sernam.ru/cod 2.php

5. Горячев Н.В. К вопросу реализации метода автоматизированного выбора системы охлаждения / Горячев Н.В., Кочегаров И.И., Юрков Н.К. // Алгоритмы, методы и системы обработки данных. 2013. № 3 (25). С. 16-20.

6. Трусов В.А. Однопозиционный модуль управления шаговым двигателем / Трусов В.А., Кочегаров И.И., Горячев Н.В., Юрков Н.К. // Теоретические и прикладные аспекты современной науки. 2015. № 7-3. С. 131-133.

7. Кудрина М.А., Кудрин К.А., Попова-Коварцева Д.А. Учебно-методический комплекс дисциплины «Теория информации» // Надежность и качество — 2012: труды Межд. симпозиума: в 2 т./ под ред. Н.К. Юркова. — Пенза: Изд-во ПГУ, 2012. — 1 т. С. 376-377.

Макаров В.Ф., Никитин С.П.

ФГБОУ ВПО «Пермский национальный исследовательский политехнический университет», Пермь, Россия ОБЕСПЕЧЕНИЕ КАЧЕСТВА И УСТАЛОСТНОЙ ПРОЧНОСТИ ЛОПАТОК ТУРБИН НА ОСНОВЕ МОДЕЛИРОВАНИЯ ДИНАМИЧЕСКОЙ СИСТЕМЫ СТАНКА И ПРОЦЕССА ГЛУБИННОГО ШЛИФОВАНИЯ

Для изготовления рабочих и сопловых лопаток турбины газотурбинных двигателей (ГТД) используют жаропрочные литейные никелевые сплавы. Одним из основных методов обработки базовых поверхностей лопаток ГТД является глубинное профильное шлифование на многокоординатных станках.

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

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

Процесс прогноза можно представить в виде трех этапов.

На первом этапе требуется установить зависимость колебаний сил и температур в зоне резания, шероховатости поверхности от технологических режимов и характеристики круга.

в = / (у, г, К 0, аз. ), Р = / (у, 5,1, К 0, аз. ), (1)

Ка = / (у, 5, г, К 0, аз. )

Далее необходимо выявить влияние температур в зоне резания и нагрузок на наклеп и остаточные напряжения в обрабатываемом материале [2, 3].

к, = / (в,Р,Яа ) , и = / (в, Р, яа)

Затем следует определить влияние параметров поверхностного слоя на предел выносливости ст-1 лопаток.

0-.1 = / Кст ,Т, Rа ) (3)

Такие математические зависимости, связывающие предел выносливости ст-1 с шероховатостью, наклепом и остаточными напряжениями были получены Т.В. Серенсеном, В.П. Когаевым, Р.Б. Шней-деровичем [2].

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

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

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

Алгоритм хаффмана

Кодирование Хаффмана. Часть 1.
Вступление
Здравствуй, дорогой читатель! В данной статье будет рассмотрен один из способов сжатия данных. Этот способ является достаточно широко распространённым и заслуживает определённого внимания. Данный материал рассчитан по объёму на три статьи, первая из которых будет посвящена алгоритму сжатия, вторая — программной реализации алгоритма, а третья ― декомпрессии. Алгоритм сжатия будет написан на языке C++, алгоритм декомпрессии ― на языке Assembler.
Однако, перед тем, как приступить к самому алгоритму, следует включить в статью немного теории.
Немного теории
Компрессия (сжатие) ― способ уменьшения объёма данных с целью дальнейшей их передачи и хранения.
Декомпрессия ― это способ восстановления сжатых данных в исходные.
Компрессия и декомпрессия могут быть как без потери качества (когда передаваемая/хранимая информация в сжатом виде после декомпрессии абсолютно идентична исходной), так и с потерей качества (когда данные после декомпрессии отличаются от оригинальных). Например, текстовые документы, базы данных, программы могут быть сжаты только способом без потери качества, в то время как картинки, видеоролики и аудиофайлы сжимаются именно за счёт потери качества исходных данных (характерный пример алгоритмов ― JPEG, MPEG, ADPCM), при порой незаметной потере качества даже при сжатии 1:4 или 1:10.
Выделяются основные виды упаковки:

  • Десятичная упаковка предназначена для упаковки символьных данных, состоящих только из чисел. Вместо используемых 8 бит под символ можно вполне рационально использовать всего лишь 4 бита для десятичных и шестнадцатеричных цифр, 3 бита для восьмеричных и так далее. При подобном подходе уже ощущается сжатие минимум 1:2.
  • Относительное кодирование является кодированием с потерей качества. Оно основано на том, что последующий элемент данных отличается от предыдущего на величину, занимающую в памяти меньше места, чем сам элемент. Характерным примером является аудиосжатие ADPCM (Adaptive Differencial Pulse Code Modulation), широко применяемое в цифровой телефонии и позволяющее сжимать звуковые данные в соотношении 1:2 с практически незаметной потерей качества.
  • Символьное подавление — способ сжатия информации, при котором длинные последовательности из идентичных данных заменяются более короткими.
  • Статистическое кодирование основано на том, что не все элементы данных встречаются с одинаковой частотой (или вероятностью). При таком подходе коды выбираются так, чтобы наиболее часто встречающемуся элементу соответствовал код с наименьшей длиной, а наименее частому ― с наибольшей.

Кроме этого, коды подбираются таким образом, чтобы при декодировании можно было однозначно определить элемент исходных данных. При таком подходе возможно только бит-ориентированное кодирование, при котором выделяются разрешённые и запрещённые коды. Если при декодировании битовой последовательности код оказался запрещённым, то к нему необходимо добавить ещё один бит исходной последовательности и повторить операцию декодирования. Примерами такого кодирования являются алгоритмы Шеннона и Хаффмана, последний из которых мы и будем рассматривать.
Конкретнее об алгоритме
Как уже известно из предыдущего подраздела, алгоритм Хафмана основан на статистическом кодировании. Разберёмся поподробнее в его реализации.
Пусть имеется источник данных, который передаёт символы [math](a_1, a_2, . a_n)[/math] с разной степенью вероятности, то есть каждому [math]a_i[/math] соответствует своя вероятность (или частота) [math]P_i(a_i)[/math] , при чём существует хотя бы одна пара [math]a_i[/math] и [math]a_j[/math] , [math]i\ne j[/math] , такие, что [math]P_i(a_i)[/math] и [math]P_j(a_j)[/math] не равны. Таким образом образуется набор частот [math][/math] , при чём [math]\displaystyle \sum_^ P_i(a_i)=1[/math] , так как передатчик не передаёт больше никаких символов кроме как [math][/math] .
Наша задача ― подобрать такие кодовые символы [math][/math] с длинами [math][/math] , чтобы средняя длина кодового символа не превышала средней длины исходного символа. При этом нужно учитывать условие, что если [math]P_i(a_i)>P_j(a_j)[/math] и [math]i\ne j[/math] , то [math]L_i(b_i)\le L_j(b_j)[/math] .
Хафман предложил строить дерево, в котором узлы с наибольшей вероятностью наименее удалены от корня. Отсюда и вытекает сам способ построения дерева:
1. Выбрать два символа [math]a_i[/math] и [math]a_j[/math] , [math]i\ne j[/math] , такие, что [math]P_i(a_i)[/math] и [math]P_j(a_j)[/math] из всего списка [math][/math] являются минимальными.
2. Свести ветки дерева от этих двух элементов в одну точку с вероятностью [math]P=P_i(a_i)+P_j(a_j)[/math] , пометив одну ветку нулём, а другую ― единицей (по собственному усмотрению).
3. Повторить пункт 1 с учётом новой точки вместо [math]a_i[/math] и [math]a_j[/math] , если количество получившихся точек больше единицы. В противном случае мы достигли корня дерева.
Теперь попробуем воспользоваться полученной теорией и закодировать информацию, передаваемую источником, на примере семи символов.
Разберём подробно первый цикл. На рисунке изображена таблица, в которой каждому символу [math]a_i[/math] соответствует своя вероятность (частота) [math]P_i(a_i)[/math] . Согласно пункту 1 мы выбираем два символа из таблицы с наименьшей вероятностью. В нашем случае это [math]a_1[/math] и [math]a_4[/math] . Согласно пункту 2 сводим ветки дерева от [math]a_1[/math] и [math]a_4[/math] в одну точку и помечаем ветку, ведущую к [math]a_1[/math] , единицей, а ветку, ведущую к [math]a_4[/math] ,― нулём. Над новой точкой приписываем её вероятность (в данном случае ― 0.03) В дальнейшем действия повторяются уже с учётом новой точки и без учёта [math]a_1[/math] и [math]a_4[/math] .

Сжатие данных без потерь. Алгоритм Хаффмана

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

На сегодняшний день сжатие информации является достаточно важной процедурой, которая необходима каждому пользователю ПК. Сегодня любой пользователь может позволить себе приобрести современный накопитель данных, в котором предусмотрена возможность использования большого объема памяти. Подобные устройства, как правило, оснащаются высокоскоростными каналами для транслирования информации. Однако, стоит отметить, что с каждым годом объем необходимой пользователям информации становится все больше и больше. Всего $10$ лет назад объем стандартного видеофильма не превышал $700$ Мб. В настоящее время объем фильмов в HD-качестве может достигать нескольких десятков гигабайт.

Попробуй обратиться за помощью к преподавателям

Когда необходимо сжатие данных?

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

Передача по электронной почте.

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


Публикация данных на интернет-сайтах и порталах.

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

Экономия свободного места на диске.

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

Задай вопрос специалистам и получи
ответ уже через 15 минут!

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

Способы сжатия информации

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

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

Сжатие без потери информации

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

Приведем простой пример. Русский язык включает в себя $33$ буквы, $10$ цифр и еще примерно $15$ знаков препинания и других специальных символов. Для текста, записанного только прописными русскими буквами (например как в телеграммах) вполне хватило бы $60$ разных значений. Тем не менее, каждый символ обычно кодируется байтом, содержащим, как нам известно, 8 битов, и может выражаться $256$ различными кодами. Это один из первых факторов, характеризующих избыточность. Для телеграфного текста вполне хватило бы и $6$ битов на символ.

Рассмотрим другой пример. В международной кодировке символов ASCII для кодирования любого символа выделяется одинаковое количество битов ($8$), в то время, как всем давно и хорошо известно, что наиболее часто встречающиеся символы имеет смысл кодировать меньшим количеством знаков. Так, к примеру, в азбуке Морзе буквы «Е» и «Т», которые встречаются очень часто, кодируются $1$ знаком (соответственно это точка и тире). А такие редкие буквы, как «Ю» ($• • — -$) и «Ц» ($- • — •$), кодируются $4$ знаками.

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

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

Алгоритм Хаффмана

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

Рисунок 1. Распределение английских букв по их частоте использования

Величина сжатия определяется избыточностью обрабатываемого массива бит. Каждый из естественных языков обладает определенной избыточностью. Среди европейских языков русский имеет самый высокий уровней избыточности. Об этом можно судить по размерам русского перевода английского текста. Обычно он примерно на $30\%$ больше. Если речь идет о стихотворном тексте, избыточность может быть до $2$ раз выше.

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

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

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

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

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

Так и не нашли ответ
на свой вопрос?

Просто напиши с чем тебе
нужна помощь

Алгоритм хаффмана

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

При кодировании по Фано все сообщения записываются в таблицу по степени убывания вероятности и разбиваются на две группы примерно (насколько это возможно) равной вероятности. Соответственно этой процедуре из корня кодового дерева исходят два ребра, которым в качестве весов присваиваются полученные вероятности. Двум образовавшимся вершинам приписывают кодовые символы 0 и 1. Затем каждая из групп вероятностей вновь делится на две подгруппы примерно равной вероятности. В соответствии с этим из каждой вершины 0 и 1 исходят по два ребра с весами, равными вероятностям подгрупп, а вновь образованным вершинам приписывают символы 00 и 01, 10 и 11. В результате многократного повторения процедуры разделения вероятностей и образования вершин приходим к ситуации, когда в качестве веса, приписанного ребру бинарного дерева, выступает вероятность одного из данных сообщений. В этом случае вновь образованная вершина оказывается листом дерева, т.к. процесс деления вероятностей для нее завершен. Задача кодирования считается решенной, когда на всех ветвях кодового бинарного дерева образуются листья.

Пример 151. Закодировать по Фано сообщения, имеющие следующие вероятности:

сообщение 1 2 3 4 5 6 7
вероятность 0,4 0,2 0,1 0,1 0,1 0,05 0,05

Решение 1 (с использованием кодового дерева)

Листья кодового дерева представляют собой кодируемые сообщения с присвоенными им кодовыми словами.

Решение 2 (табличный способ)

Цена кодирования (средняя длина кодового слова является критерием степени оптимальности кодирования. Вычислим ее в нашем случае.

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

Пример 152. Закодировать сообщения из предыдущего примера по методу Хаффмана.

Решение 1. Первый шаг

Вторым шагом производим кодирование, «проходя» по таблице справа налево (обычно это проделывается в одной таблице):

Решение 2. Построение кодового дерева начинается с корня. Двум исходящим из него ребрам приписывается в качестве весов вероятности 0,6 и 0,4, стоящие в последнем столбце. Образовавшимся при этом вершинам дерева приписываются кодовые символы 0 и 1. Далее «идем» по таблице справа налево. Поскольку вероятность 0,6 является результатом сложения двух вероятностей 0,4 и 0,2, из вершины 0 исходят два ребра с весами 0,4 и 0,2 соответственно, что приводит к образованию двух новых вершин с кодовыми символами 00 и 01. Процедура продолжается до тех пор, пока в таблице остаются вероятности, получившиеся в результате суммирования. Построение кодового дерева заканчивается образованием семи листьев, соответствующих данным сообщениям с присвоенными им кодами. Дерево, полученное в результате кодирования по Хаффману, имеет следующий вид:

Листья кодового дерева представляют собой кодируемые сообщения с присвоенными им кодовыми словами. Таблица кодов имеет вид:

сообщение 1 2 3 4 5 6 7
код 1 01 0010 0011 0000 00010 00011

Цена кодирования здесь будет равна

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

Пример 153. Провести кодирование по методу Фано двухбуквенных комбинаций, когда алфавит состоит из двух букв и , имеющих вероятности = 0,8 и = 0,2.

Цена кода , и на одну букву алфавита приходится 0,78 бита информации. При побуквенном кодировании на каждую букву приходится следующее количество информации:

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

Построим кодовое дерево.

Найдем цену кодирования

На каждую букву алфавита приходится в среднем 0,728 бита, в то время как при побуквенном кодировании — 0,72 бита.

Большей оптимизации кодирования можно достичь еще и использованием трех символов — 0, 1, 2 — вместо двух. Тринарное дерево Хаффмана получается, если суммируются не две наименьшие вероятности, а три, и приписываются каждому левому ребру 0, правому — 2, а серединному — 1.

Пример 155. Построить тринарное дерево Хаффмана для кодирования трехбуквенных комбинаций из примера 153 .

Решение. Составим таблицу тройного «сжатия» по методу Хаффмана

Тогда тринарное дерево выглядит следующим образом:

Вопросы для самоконтроля

1. Как определяется среднее число элементарных сигналов, приходящихся на одну букву алфавита?

2. Префиксные коды.

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

4. На чем основано построение кода Фано?

5. Что такое сжатие алфавита?

6. Какой код самый выгодный?

7. Основная теорема о кодировании.

8. Энтропия конкретных типов сообщений.

I 301. Проведите кодирование по методу Фано алфавита из четырех букв, вероятности которых равны 0,4; 0,3; 0,2 и 0,1.

302. Алфавит содержит 7 букв, которые встречаются с вероятностями 0,4; 0,2; 0,1; 0,1; 0,1; 0,05; 0,05. Осуществите кодирование по методу Фано.

303. Алфавит состоит из двух букв, и , встречающихся с вероятностями = 0,8 и = 0,2. Примените метод Фано к кодированию всевозмож-ных двухбуквенных и трехбуквенных комбинаций.

304. Проведите кодирование по методу Хаффмана трехбуквенных слов из предыдущей задачи.

305. Проведите кодирование 7 букв из задачи 302 по методу Хаффмана.

306. Проведите кодирование по методам Фано и Хаффмана пяти букв, равновероятно встречающихся.

II 307. Осуществите кодирование двухбуквенных комбинаций четырех букв из задачи 301.

308. Проведите кодирование всевозможных четырехбуквенных слов из задачи 303.

III 309. Сравните эффективность кодов Фано и Хаффмана при кодировании алфавита из десяти букв, которые встречаются с вероятностями 0,3; 0,2; 0,1; 0,1; 0,1; 0,05; 0,05; 0,04; 0,03; 0,03.

310. Сравните эффективность двоичного кода Фано и кода Хаффмана при кодировании алфавита из 16 букв, которые встречаются с вероятностями 0,25; 0,2; 0,1; 0,1; 0,05; 0,04; 0,04; 0,04; 0,03; 0,03; 0,03; 0,03; 0,02; 0,02; 0,01; 0,01.

Python алгоритмы

Блог про алгоритмы и все что с ними связано. Основной инструмент реализации — Python.

суббота, 18 июня 2011 г.

Деревья кодирования по Хаффману

С таким кодом, сообщение
BACADAEAFABBAAAGAH
кодируется как строка из 54 бит
001000010000011000100000101000001001000000000110000111

Такие коды, как ASCII и наш код от A до H, известны под названием кодов с фиксированной длиной, поскольку каждый символ сообщения они представляют с помощью одного и того же числа битов. Иногда полезно использовать и коды с переменной длиной (variable-length), в которых различные символы могут представляться различным числом битов. Например, азбука Морзе не для всех букв алфавита использует одинаковое число точек и тире. В частности, E, наиболее частая (в английском) буква, представляется с помощью одной точки. В общем случае, если наши сообщения таковы, что некоторые символы встречаются очень часто, а некоторые очень редко, то мы можем кодировать свои данные более эффективно (т. е. с помощью меньшего числа битов на сообщение), если более частым символам мы назначим более короткие коды. Рассмотрим следующий код для букв с A по H:

С таким кодом то же самое сообщение преобразуется в строку
100010100101101100011010100100000111001111
В этой строке 42 бита, так что она экономит более 20% места по сравнению с приведенным выше кодом с фиксированной длиной.
Одна из сложностей при работе с кодом с переменной длиной состоит в том, чтобы узнать, когда при чтении последовательности единиц и нулей достигнут конец символа. В азбуке Морзе эта проблема решается при помощи специального кода-разделителя (separator code) (в данном случае паузы) после последовательности точек и тире для каждой буквы. Другое решение состоит в том, чтобы построить систему кодирования так, чтобы никакой полный код символа не совпадал с началом (или префиксом) кода никакого другого символа. Такой код называется префиксным (prefix). В вышеприведенном примере A кодируется 0, а B 100, так что никакой другой символ не может иметь код, который начинается на 0 или 100.

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

Рисунок ниже изображает дерево Хаффмана для кода от A до H, показанного выше. Веса в вершинах дерева указывают, что дерево строилось для сообщений, где A встречается с относительной частотой 8, B с относительной частотой 3, а все остальные буквы с относительной частотой 1.

Имея дерево Хаффмана, можно найти код любого символа, если начать с корня и двигаться вниз до тех пор, пока не будет достигнута концевая вершина, содержащая этот символ. Каждый раз, как мы спускаемся по левой ветви, мы добавляем 0 к коду, а спускаясь по правой ветви, добавляем 1. (Мы решаем, по какой ветке двигаться, проверяя, не является ли одна из веток концевой вершиной, а также содержит ли множество при вершине символ, который мы ищем.) Например, начиная с корня на рисунке выше, мы попадаем в концевую вершину D, сворачивая на правую дорогу, затем на левую, затем на правую, затем, наконец, снова на правую ветвь; следовательно, код для D — 1011.

Чтобы раскодировать последовательность битов при помощи дерева Хаффмана, мы начинаем с корня и просматриваем один за другим биты в последовательности, чтобы решить, нужно ли нам спускаться по левой или по правой ветви. Каждый раз, как мы добираемся до листовой вершины, мы порождаем новый символ сообщения и возвращаемся к вершине дерева, чтобы найти следующий символ. Например, пусть нам дано дерево, изображенное на рисунке, и последовательность 10001010. Начиная от корня, мы идем по правой ветви (поскольку первый бит в строке 1), затем по левой (поскольку второй бит 0), затем опять по левой (поскольку и третий бит 0). Здесь мы попадаем в лист, соответствующий B, так что первый символ декодируемого сообщения — B. Мы снова начинаем от корня и идем налево, поскольку следующий бит строки 0. Тут мы попадаем в лист, изображающий символ A. Мы опять начинаем от корня с остатком строки 1010, двигаемся направо, налево, направо, налево и приходим в C. Таким образом, всесообщение было BAC.

Порождение деревьев Хаффмана

Если нам дан «алфавит» символов и их относительные частоты, как мы можем породить «наилучший» код? (Другими словами, какое дерево будет кодировать сообщения при помощи наименьшего количества битов?) Хаффман дал алгоритм для решения этой задачи и показал, что получаемый этим алгоритмом код — действительно наилучший код с переменной длиной для сообщений, где относительная частота символов соответствует частотам, для которых код строился. Здесь мы не будем доказывать оптимальностькодов Хаффмана, но покажем, как эти коды строятся

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

Алгоритм не всегда приводит к построению единственно возможного дерева, поскольку на каждом шаге выбор вершин с наименьшим весом может быть не единственным. Выбор порядка, в котором будут сливаться две вершины (то есть, какая из них будет левым, а какая правым поддеревом) также произволен.


Представление деревьев Хаффмана

В следующих упражнениях мы будем работать с системой, которая использует деревья Хаффмана для кодирования и декодирования сообщений и порождает деревья Хаффмана в соответствии с вышеописанным алгоритмом. Начнем мы с обсуждения того, как представляются деревья.
Листья дерева представляются в виде списка, состоящего из символа leaf (лист), символа, содержащегося в листе, и веса:
Дерево в общем случае будет списком из левой ветви, правой ветви, множества символов и веса. Множество символов будет просто их списком, а не каким-то более сложным представлением. Когда мы порождаем дерево слиянием двух вершин, мы получаем вес дерева как сумму весов этих вершин, а множество символов как объединение множеств их символов. Поскольку наши множества представлены в виде списка, мы можем породить объединение при помощи процедуры append, определенной нами ранее.
Если мы порождаем дерево таким образом, то у нас будут следующие селекторы:
Процедуры symbols и weight должны вести себя несколько по-разному в зависимости от того, вызваны они для листа или для дерева общего вида. Это простые примеры обобщенных процедур (generic procedures) (процедур, которые способны работать более, чем с одним типом данных).
Итак, ради интереса можете посмотреть на результат создания дерева tree=make_code_tree((‘leaf’, (‘A’, None), 8), ((‘leaf’, (‘B’, None), 3), (‘leaf’, (‘E’, None), 1), (‘B’, ‘E’), 4))


Процедура декодирования
Следующая процедура реализует алгоритм декодирования. В качестве аргументов она
принимает список из единиц и нулей, а также дерево Хаффмана.
Пример использования: decode((1, (0,(0, None))),tree), где tree мы создали с вами процедурой make_code_tree выше.
Процедура decode1 принимает два аргумента: список остающихся битов и текущую позицию в дереве. Она двигается «вниз» по дереву, выбирая левую или правую ветвь в зависимости от того, ноль или единица следующий бит в списке (этот выбор делается в процедуре choose_branch). Когда она достигает листа, она возвращает символ из него как очередной символ сообщения, присоединяя его посредством cons к результату декодирования остатка сообщения, начиная от корня дерева. Обратите внимание на проверку ошибок в конце choose_branch, которая заставляет программу протестовать, если во входных данных обнаруживается что-либо помимо единиц и нулей.

Множества взвешенных элементов

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

Мы представим множество листьев и деревьев как список элементов, упорядоченный
по весу в возрастающем порядке. Следующая процедура adjoinset для построения множеств работает так, что элементы сравниваются по своим весам, и никогда не бывает так, что добавляемый элемент уже содержится в множестве.
Следующая процедура принимает список пар вида символ–частота, например ((A4) (B 2) (C 1) (D 1)), и порождает исходное упорядоченное множество листьев,готовое к слиянию по алгоритму Хаффмана:
Пример использования: make_leaf_set((((‘A’, None), 4), (((‘B’, None), 2), (((‘C’, None), 1), (((‘D’, None), 1), None)))))

Ну вот и все, тут конечно еще есть над чем поработать, но идея я надеюсь вам ясна.
И практики хватило X)))

Илон Маск рекомендует:  Bump mapping (pas)
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL