| Цитата | правда я слышал только об алгоритме Hafman'а, в котором символ кодируется неповторимой последовательностью битов нефиксированной длины. чем чаще встречается какой-то символ - тем короче последовательность, которая его кодирует.
где почитать про это - не знаю. я это в какой-то "левой" книжке увидел. |
Я тут вот откопал кое-что из старых лекций....
Элементы теории кодирования.
Пусть задан некоторый алфавит A={a1,a2,...,ak}, если известна вероятность появления каждого символа этого алфавита в тексте, то будем говорить, что задан ансамбль сообщений...
{[a1,p1],[a2,p2],...,[ak,pk]}, где pi - вероятность появления события ai, т.е. все pi>=0, p1+p2+...+pk=1. Кодовый алфавит двоичный {0,1}.
Кодированием называется операция, с помощью которой каждому сообщению ансамбля ставится в соответствие кодовое слово. Кодирование должно удовлетворять следующим двум условиям:
1. (Однозначность(обязат)) Необходимо сохранить однозначность декодирования.
2. (Экономичность(желат)) желательно, чтобы среднее количество кодовых символов, затрачиваемых на кодирование сообщения ансамбля было минимальным.
Два вида кодирования:
| Код | Символ | Вероятность | Простое кодирование | Понтовое кодирование
a1 1/4 000 00
a2 1/4 001 01
a3 1/8 010 100
a4 1/8 011 101
a5 1/16 100 1100
a6 1/16 101 1101
a7 1/16 110 1110
a8 1/16 111 1111
|
Давайте посчитаем теперь среднюю длину символа в сообщении при "понтовом" кодировании:
2*(1/4)*2+3*(1/8)*2+4*(1/16)*4=2,75<3, немного поясню: каждое слагаемое состоит из 3-х сомножителей, первый из которых - длина символа, второй - вероятность появления символа с данной длинной кода, третий - количество таких символов в кодовом алфавите.
При этом выполняется условие однозначности декодирования (префиксное условие). Это условие состоит в следующем: никакое более короткое кодовое слово не может быть началом (префиксом) более длинного кодового слова.
Кодовое дерево.
| Код | Кодовое дерево
000 001 010 011 100 101 110 111 ----- 3
\ / \ / \ / \ /
00 01 10 11 -------- 2
\ / \ /
\ / \ /
\ / \ /
0 1 ------------- 1
\ /
\ /
\ /
\ /
\ /
0 <- корень -> 1 ------------- 0
1100 1101 1110 1111 - 4
\ / \ /
100 101 110 111 ---- 3
\ / \ /
\ / \ /
\ / \ /
\ / \ /
00 01 10 11 ---------- 2
\ / \ /
\ / \ /
\ / \ /
\ / \ /
\ / \ /
\ / \ /
0 1 ------------------ 1
\ /
\ /
\ /
\ /
\ /
0 <- корень -> 1 ------------------- 0 |
Все вершины кодового дерева делятся на 2 класса: промежуточные и концевые. Кодовые наборы любого кода соответствуют концевым вершинам кодового дерева, а не промежуточным.
Метод оптимального кодирования. Метод Хаффмана.
Допустим, что нам надо закодировать 7 символов в двоичном кодовом алфавите...
Символ | Вероятность
a1 0,23
a2 0,19
a3 0,16
a4 0,14
a5 0,12
a6 0,9
a7 0,7
покажем алгоритм кодирования| Код |
Символ | Вероятность
a1 | 0,23
a2 | 0,19
a3 | 0,16
a4 | 0,14 |
a5 | 0,12 |
/ a6 | 0,9 \ |
\ a7 | 0,7 / 0,7+0,9=1,6-
_
Символ | Вероятность
| _
a1 | 0,23 |
a2 | 0,19 |
a3 | 0,16 |
(a6,a7) | 0,16 |
/ a4 | 0,14 \ |
\ a5 | 0,12 / 0,14+0,12=0,26
Символ | Вероятность
| _|___
После этого можем составить дерево...
a7 a6 ------------------------- 4
\ /
(a6,a7) a3 a5 a4 ---- 3
\ / \ /
\ / \ /
\ / \ /
\ / \ /
a2 a1 (a3,(a6,a7)) (a4,a5) ------- 2
\ / \ /
\ / \ /
\ / \ /
\ / \ /
\ / \ /
\ / \ /
(a1,a2) ((a4,a5),(a3,(a6,a7))) -------- 1
\ /
\ /
\ /
\ /
\ /
0 <- корень -> 1 ------------------- 0
Итого:
-------------
| a1 | 01 |
| a2 | 00 |
| a3 | 101 |
| a4 | 111 |
| a5 | 110 |
| a6 | 1001 |
| a7 | 1000 |
-------------
|
Вот в общем-то и все... Не рассказал еще о кодах, обнаруживающих и исправляющих ошибки, да думаю это никому не интересно... :0)
P.S. Если у кого возникнут какие вопросы - пишите... |
, ну вот аналогично кодируются все символы. Комбинаций нулей и единиц в самом деле 256, значение каждой комбинации можно получить переводом из двоичного кода в десятичный аналогично показанному выше или проще - можно почитать где ни будь. Десятичный код 8-битного числа соответствует номеру символа в таблице, вот и всё.