Принципы эффективного кодирования
Эффективным кодированием называется процедура преобразования символов первичного алфавита в кодовые слова во вторичном алфавите, при которой средняя длина сообщений во вторичном алфавите имеет минимально возможную для данного алфавита длину.
Эффективность кодов определяется близостью энтропии источника сообщений и среднего числа двоичных знаков на букву кодов, т.е. в идеальном случае должно выполняться равенство
Для двоичных кодов 
и разность (Lcp - H) будет тем меньше, чем больше Н, а H достигает максимума при равновероятных и взаимно независимых символах. Отсюда вытекают основные свойства эффективных кодов:
§ минимальная средняя длина кодового слова оптимального кода обеспечивается в том случае, когда избыточность каждого кодового слова сведена к минимуму (в идеальном случае - к нулю);
§ кодовые слова оптимального кода должны строиться из равновероятных и взаимно независимых символов.
Из свойств оптимальных кодов вытекают принципы их построения.
· Первый принцип эффективного кодирования: выбор каждого кодового слова необходимо производить так, чтобы содержащееся в нем количество информации было максимальным.
· Второй принцип эффективного кодирования заключается в том, что буквам первичного алфавита, имеющим большую вероятность, присваиваются более короткие кодовые слова во вторичном алфавите.
Построение эффективного кода по методу Шеннона-Фано
Этот метод требует упорядочения исходного множества символов по не возрастанию их частот. Затем выполняются следующие шаги:
а) список символов делится на две части (назовем их первой и второй частями) так, чтобы суммы частот обеих частей (назовем их Σ1 и Σ2) были точно или примерно равны. В случае, когда точного равенства достичь не удается, разница между суммами должна быть минимальна;
б) кодовым комбинациям первой части дописывается 1, кодовым комбинациям второй части дописывается 0;
в) анализируют первую часть: если она содержит только один символ, работа с ней заканчивается, – считается, что код для ее символов построен, и выполняется переход к шагу г) для построения кода второй части. Если символов больше одного, переходят к шагу а) и процедура повторяется с первой частью как с самостоятельным упорядоченным списком;
г) анализируют вторую часть: если она содержит только один символ, работа с ней заканчивается и выполняется обращение к оставшемуся списку (шаг д). Если символов больше одного, переходят к шагу а) и процедура повторяется со второй частью как с самостоятельным списком;
д) анализируется оставшийся список: если он пуст – код построен, работа заканчивается. Если нет, – выполняется шаг а).
Пример 1. Даны символы a, b, c, d с частотами fa = 0,5; fb = 0,25; fc = 0,125; fd = 0,125. Построить эффективный код методом Шеннона-Фано.
Сведем исходные данные в таблицу, упорядочив их по невозрастанию частот:
| 1Исходные символы | 1Частоты символов | 2Исходные символы | 2Частоты символов | 2Формируемый код | |||
| a | 0,5 | a | 0,5 | 1 | |||
| b | 0,25 | b | 0,25 | 0 | |||
| c | 0,125 | c | 0,125 | 0 | |||
| d | 0,125 | d | 0,125 | 0 | |||
| 3Исходные символы | 3Частоты символов | 3Формируемый код | 4Исходные символы | 4Частоты символов | 4Формируемый код | ||
| a | 0,5 | 1 | a | 0,5 | 1 | ||
| b | 0,25 | 01 | b | 0,25 | 01 | ||
| c | 0,125 | 00 | c | 0,125 | 001 | ||
| d | 0,125 | 00 | d | 0,125 | 000 | ||
Первая линия деления проходит под символом a: соответствующие суммы Σ1 и Σ2 равны между собой и равны 0,5. Тогда формируемым кодовым комбинациям дописывается 1 для верхней (первой) части и 0 для нижней (второй) части. Поскольку это первый шаг формирования кода, двоичные цифры не дописываются, а только начинают формировать код (см2):
В силу того, что верхняя часть списка содержит только один элемент (символ а), работа с ней заканчивается, а эффективный код для этого символа считается сформированным (в таблице, приведенной выше, эта часть списка частот символов выделена заливкой).
Второе деление выполняется под символом b: суммы частот Σ1 и Σ2 вновь равны между собой и равны 0,25. Тогда кодовой комбинации символов верхней части дописывается 1, а нижней части – 0. Таким образом, к полученным на первом шаге фрагментам кода, равным 0, добавляются новые символы (см3):
Поскольку верхняя часть нового списка содержит только один символ (b), формирование кода для него закончено (соответствующая строка таблицы вновь выделена заливкой).
Третье деление проходит между символами c и d: к кодовой комбинации символа c приписывается 1, коду символа d приписывается 0 (см4):
Поскольку обе оставшиеся половины исходного списка содержат по одному элементу, работа со списком в целом заканчивается.
Таким образом, получили коды:
a - 1, b - 01, c - 001, d - 000.
Определим эффективность построенного кода по формуле:
lср = 0,5*1 + 0,25*01 + 0,125*3 + 0,125*3 = 1,75.
Поскольку при кодировании четырех символов кодом постоянной длины требуется два двоичных разряда, сэкономлено 0,25 двоичного разряда в среднем на один символ.
7. Построение эффективного кода по методу Метод Хаффмана.
1. Составим список кодируемых символов (при этом будем рассматривать каждый символ как одноэлементное бинарное дерево, вес которого равен весу символа).
2. Из списка выберем 2 узла с наименьшим весом.
3. Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. При этом вес сформированного узла положим равным сумме весов дочерних узлов.
4. Добавим сформированный узел к списку.
5. Если в списке больше одного узла, то повторить 2-5.
Приведем пример: построим дерево Хаффмана для сообщения 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".
Для начала введем несколько обозначений:
1. Символы кодируемого алфавита будем выделять жирным шрифтом: A, B, C.
2. Веса узлов будем обозначать нижними индексами: A5, B3, C7.
3. Составные узлы будем заключать в скобки: ((A5+B3)8+C7)15.
Итак, в нашем случае A={A, B, C, D, E, F, G, H}, W={2, 1, 5, 2, 7, 1, 3, 15}.
1. A2 B1 C5 D2 E7 F1 G3 H15
2. A2 C5 D2 E7 G3 H15 (F1+B1)2
3. C5 E7 G3 H15 (F1+B1)2 (A2+D2)4
4. C5 E7 H15 (A2+D2)4 ((F1+B1)2+G3)5
5. E7 H15 ((F1+B1)2+G3)5 (C5+(A2+D2)4)9
6. H15 (C5+(A2+D2)4)9 (((F1+B1)2+G3) 5+E7)12
7. H15 ((C5+(A2+D2)4) 9+(((F1+B1)2+G3) 5+E7)12)21
8. (((C5+(A2+D2)4) 9+(((F1+B1)2+G3) 5+E7)12)21+H15)36
В списке, как и требовалось, остался всего один узел. Дерево Хаффмана построено. Теперь запишем его в более привычном для нас виде.
ROOT
/\
0 1
/ \
/\ H
/ \
/ \
0 1
/ \
/\ /\
0 1 0 1
/ \ / \
C /\ /\ E
0 1 0 1
/ \ / \
A D /\ G
0 1
/ \
F B
Путь от корня дерева к листовому узлу можно представить в виде битовой строки, в которой "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".
Дата добавления: 2018-05-12; просмотров: 1001; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!