Цитата

правда я слышал только об алгоритме 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. Если у кого возникнут какие вопросы - пишите...

Ну а если быть точным, то систем исчисления бывает очень много, т.е. много можно придумать, как считать числа и какие брать основания. Самые известные из них хто десятичная (0...9), двоичная (0,1), восьмиричная (0...7) и шестнадцатиричная (0...A,B,C,D,E,F).

Dexter - Купи саму дешевую книжку по информатике для школ, там должно это быть.

Восемь бит использовали потому-что стандарт ASCII предусматривал 128 символов, и если ты не знаеш то 8 бит это 1 байт. Так вот 127 в двоичной системе что-то втоде 01111111. (Битовую адресацию современные компьютеры не подерживают (т.е. минимум можно указать на байт)) Как видиш один бит мы не используем. Поетому остальные 128 символов используют для локального алфавита или для специальных символов.

ЗЫ
Ели сдержал себя от мата

Цитата

ЗЫ Ели сдержал себя от мата

Модератор:
Не нужно фанатизма! Вопрос задан очень давно (см. дату создания темы) и не Dexter эту тему вытащил из небытия. Подобные выпады неуместны.

Ok, ok, sorry.