Сжатие информации (архивация) — это такое преобразование информации, при котором объем файла уменьшается, а количество информации, содержащейся в архиве, остается прежним.
Алгоритм Шеннона – Фено. Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. Коды Шеннона— Фено префиксные, то есть никакое кодовое слово не является префиксом любого другого. Это свойство позволяет однозначно декодировать любую последовательность кодовых слов.
Алгоритм построения кода:
1. Все символы записать в порядке не возрастания вероятностей.
2. Символы разбить на две группы с приближенно равными суммами вероятностей.
3. В левой группе символов коды начать с 0, в правой-с1.
4. Каждую группу снова разбить на две по такому же принципу и так же присвоить слева-0, справа-1.
5. Продолжать разбиения до тех пор ,пока в каждой группе не останется по одному символу.
Метод Хаффмена (Huffman) разработан в 1952 году. Он более практичен и никогда по степени сжатия не уступает методу Шеннона-Фэно, более того, он сжимает максимально плотно. Код строится при помощи двоичного (бинарного) дерева. Вероятности значений дискретной СВ приписываются его листьям; все дерево строится, опираясь на листья. Величина, приписанная к узлу дерева, называется весом узла. Два листа с наименьшими весами создают родительский узел с весом, равным сумме их весов; в дальнейшем этот узел учитывается наравне с оставшимися листьями, а образовавшие его узлы от такого рассмотрения устраняются. После постройки корня нужно приписать каждой из ветвей, исходящих из родительских узлов, значения 0 или 1. Код каждого значения дискретной СВ - это число, получаемое при обходе ветвей от корня к листу, соответствующему данному значению.
Алгоритм Хаффмена
1. Все символы записать в порядке не возрастания вероятностей.
2. Объединить два редких символа в одну группу с вероятностью, равной сумме вероятностей этих символов.
3. Снова упорядочить список.
4. Повторять операции со второго шага, пока все символы не будут разбиты на две группы. В левой группе символов коды начать с 0, в правой- с1.
5. Затем работать с каждой группой следующим образом: отделять крайние символы, присваивая всегда слева 0, а справа-1, пока не будет закодирован каждый символ.
Для методов Хаффмена и Шеннона-Фэно каждый раз вместе с собственно сообщением нужно передавать и таблицу кодов.
Примеры: Закодировать алфавит, состоящий из символов a(0,37); b(0,22); c(0,16); d(0,14), e(0,11) по методу Шеннона-Фэно и алгоритму Хаффмена ( в скобках указаны вероятности появления символа).
Решение: 1). Метод Шеннона- Фэно.
|
Шаги/символы |
a |
b |
c |
d |
e |
|
1 |
0 |
0 |
1 |
1 |
1 |
|
2 |
00 |
01 |
10 |
11 |
11 |
|
3 |
|
|
|
110 |
111 |
Итак, получили коды a- 00, b-01, c- 10, d- 110, e- 111.
2). Алгоритм Хаффмена.
Объединим две последние буквы, не нарушая их последовательности, в одну группу и упорядочим список:
(a)0,37; (de)0,25; (b)0,22; (c)0,16.
Повторим эту операцию, пока все символы не будут разбиты на две группы.
(bc)0,48; (a)0,37; (de)0,25.
(ade)0,62; (bc)0,48.
аde- коды – c 0, bc- с1; ad-00, e- 01; b- 10, c- 11. Последний шаг- a- 000, d- 001.
Итак, получили коды a- 000, b- 10, c-11, d-001, e- 01.
Определим цену кода по каждому алгоритму.
По алгоритму Шеннона-Фэно: М(х) = 0,37·2 + 0,22 ·2 + 0,16·2 + 0,14·3 + 0,11·3 = 2,2 бит/символ ;
По алгоритму Хаффмена: М(х) = 0,37·3 + 0,22 ·2 + 0,16·2 + 0,14·3 + 0,11·2 = 2,51 бит/символ.
