[Iska]

eg01st, описанная Вами ситуация:

допустим код 010001011011010101, символ "а" - 01, а символ "я" - 010001 »

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

читать дальше »

Принцип достаточно прост: минимизировать среднее количество кодовых символов, приходящихся на одну букву. Кодируемые элементы сообщения (буквы) располагаются в порядке убывания частот их появления в сообщении. Затем они разделяются на две группы таком образом, чтобы сумма вероятностей появления букв в верхней группе была примерно равна сумме вероятностей появления букв букв в нижней группе (например, в верхней группе не больше, нежели в нижней). Верхней группе приписывается символ «0», а нижней, соответственно, — «1». Эти символы обозначают первый знак кодовой последовательности.

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

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

Например, закодируем сообщение:

Код:

синий, синий иней

Начинаем с частот появления букв в исходном сообщении:

Код:

«с» — 2;
«и» — 5;
«н» — 3;
«й» — 3;
« » — 3;
«,» — 1;
«е» — 1

Таким образом, общее число букв в исходном сообщении — 18 (2+5+3+3+3+1+1).

Вероятности появления букв в исходном сообщении:

Код:

«с» — 2/18;
«и» — 5/18;
«н» — 3/18;
«й» — 3/18;
« » — 3/18;
«,» — 1/18;
«е» — 1/18

Располагаем буквы в таблицу в соответствии с вероятностями их появления в исходном сообщении и делаем присвоение первого двоичного символа:

Код:

┌─────┬──────┬───┐
│ «и» │ 5/18 │ 0 │
│     │      │   │
│ «н» │ 3/18 │   │
│     │      ├───┤
│ «й» │ 3/18 │ 1 │
│     │      │   │
│ « » │ 3/18 │   │
│     │      │   │
│ «с» │ 2/18 │   │
│     │      │   │
│ «,» │ 1/18 │   │
│     │      │   │
│ «е» │ 1/18 │   │
└─────┴──────┴───┘

Замечание: при равной вероятности порядок следования исходных букв выбирается произвольно (в нашем случае это [«н», «й», « »] и [«,» , «е»]).

Далее, каждую половину делим опять же пополам по вероятностям:

Код:

┌─────┬──────┬───┬───┐
│ «и» │ 5/18 │ 0 │ 0 │
│     │      │   ├───┤
│ «н» │ 3/18 │   │ 1 │
│     │      ├───┼───┤
│ «й» │ 3/18 │ 1 │ 0 │
│     │      │   ├───┤
│ « » │ 3/18 │   │ 1 │
│     │      │   │   │
│ «с» │ 2/18 │   │   │
│     │      │   │   │
│ «,» │ 1/18 │   │   │
│     │      │   │   │
│ «е» │ 1/18 │   │   │
└─────┴──────┴───┴───┘

Повторяем эту операцию до тех пор, пока каждая буква исходного сообщения не будет закодирована:

Код:

┌─────┬──────┬───┬───┬───────────┬───────┐
│ «и» │ 5/18 │ 0 │ 0 │           │ 00    │
│     │      │   ├───┼───────────┼───────┤
│ «н» │ 3/18 │   │ 1 │           │ 01    │
│     │      ├───┼───┼───────────┼───────┤
│ «й» │ 3/18 │ 1 │ 0 │           │ 10    │
│     │      │   ├───┼───────────┼───────┤
│ « » │ 3/18 │   │ 1 │ 0         │ 110   │
│     │      │   │   ├───┬───────┼───────┤
│ «с» │ 2/18 │   │   │ 1 │ 0     │ 1110  │
│     │      │   │   │   ├───┬───┼───────┤
│ «,» │ 1/18 │   │   │   │ 1 │ 0 │ 11110 │
│     │      │   │   │   │   ├───┼───────┤
│ «е» │ 1/18 │   │   │   │   │ 1 │ 11111 │
└─────┴──────┴───┴───┴───┴───┴───┴───────┘

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

Код:

«и» — «00»;
«н» — «01»;
«й» — «10»;
« » — «110»;
«с» — «1110»;
«,» — «11110»;
«е» — «11111».

Соответственно, исходное сообщение:

Код:

┌─────┬───────┐
│ «с» │ 1110  │
├─────┼───────┤
│ «и» │ 00    │
├─────┼───────┤
│ «н» │ 01    │
├─────┼───────┤
│ «и» │ 00    │
├─────┼───────┤
│ «й» │ 10    │
├─────┼───────┤
│ «,» │ 11110 │
├─────┼───────┤
│ « » │ 110   │
├─────┼───────┤
│ «с» │ 1110  │
├─────┼───────┤
│ «и» │ 00    │
├─────┼───────┤
│ «н» │ 01    │
├─────┼───────┤
│ «и» │ 00    │
├─────┼───────┤
│ «й» │ 10    │
├─────┼───────┤
│ « » │ 110   │
├─────┼───────┤
│ «и» │ 00    │
├─────┼───────┤
│ «н» │ 01    │
├─────┼───────┤
│ «е» │ 11111 │
├─────┼───────┤
│ «й» │ 10    │
└─────┴───────┘

кодируется последовательностью:

Код:

1110000100101111011011100001001011000011111110

…а как расшифровывает - пара слов о префиксных кодах, которые я так и не понял.»

Термин «префиксные» обозначает, что никакая кодовая последовательность не является префиксом любой другой кодовой последовательности. Данное свойство позволяет однозначно декодировать любое сообщение. Если Вы посмотрите на полученное нами в примере:

Код:

1110000100101111011011100001001011000011111110

то убедитесь в этом сами. Выборки одного символа — «1», двух — «11», трёх — «111» входят сразу в несколько кодовых последовательностей, а вот выборка четырёх символов — «1110» — однозначно входит только в одну последовательность, что и позволяет её однозначно идентифицировать с символом исходного сообщения («с» — «1110»).

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

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

Впрочем, решив написать данное сообщение, я не ставил задачу обучить Вас тонкостям реализации алгоритма Шеннона — Фано, Хаффмана или Лемпеля — Зива — Велча . Для этих целей хватает и монографий, и пухлых исследований. Я хотел, чтобы Вы примерно поняли сам механизм кодирования с практически нулевой избыточностью (это термин) и саму идею этого алгоритма — максимальное сокращение средней длины кодовых последовательностей. Лучший учитель — практика. Возьмите коллегу. Попросите его закодировать по изложенному выше алгоритму какое-либо сообщение. Пусть он передаст Вам закодированное сообщение и сам словарь. Попробуйте его раскодировать. Тогда Вам станет воочию ясно, что такое префиксные коды и почему «он понимает что нужно преобразовывать символ "а", а не "я"».

Предваряя следующий вопрос, «а что будет, если в переданном сообщении будет искажёны/потеряны какие-либо символы?», скажу, что для этого вводится обратное понятие — избыточность кода, например, широко известные CRC — коды циклического контроля, позволяющие столь же однозначно узнать, было ли сообщение при передаче искажено, и суметь восстановить его. Впрочем, как говорил сказочник, это уже другая история .

[eg01st]

Большое спасибо за выложенный материал, сейчас пробежал глазами - уже более ясно стало, сегодня вечером буду применять это всё на практике)

[pva]

Iska, если так же понятно расскажешь про арифметическое кодирование, то вообще расцелую

[eg01st]

Полностью понял и даже проверил. На всякий случай задам вопрос: самые часто встречающиеся 3 символа будут иметь код 00 01 или 10, остальные же, будут иметь код 1110, 11110, 111110, 1111110, 111111110 и дт., а последний, самый редкий символ, будет иметь код 111111111111, то есть, символы с 4-го по n-1 будут заканчиваться на 0, а n - на 1?