Принцип достаточно прост: минимизировать среднее количество кодовых символов, приходящихся на одну букву. Кодируемые элементы сообщения (буквы) располагаются в порядке убывания частот их появления в сообщении. Затем они разделяются на две группы таком образом, чтобы сумма вероятностей появления букв в верхней группе была примерно равна сумме вероятностей появления букв букв в нижней группе (например, в верхней группе не больше, нежели в нижней). Верхней группе приписывается символ «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
Цитата eg01st:
|
…а как расшифровывает - пара слов о префиксных кодах, которые я так и не понял.»
|
Термин «префиксные» обозначает, что никакая кодовая последовательность не является префиксом любой другой кодовой последовательности. Данное свойство позволяет однозначно декодировать любое сообщение. Если Вы посмотрите на полученное нами в примере:
Код:
1110000100101111011011100001001011000011111110
то убедитесь в этом сами. Выборки одного символа — «1», двух — «11», трёх — «111» входят сразу в несколько кодовых последовательностей, а вот выборка четырёх символов — «1110» — однозначно входит только в одну последовательность, что и позволяет её однозначно идентифицировать с символом исходного сообщения («с» — «1110»).
Данный алгоритм именуется кодом
Шеннона — Фано. Как Вы можете увидеть по изложенному выше примеру (и сделанному замечанию), данный алгоритм может давать различные кодовые последовательности, в зависимости от нашего выбора, причём от нашего выбора, сделанного на определённом шаге, будет зависеть разбиение на всех последующих шагах, что, соответственно, не всегда может приводить к наилучшему результату — максимальное сокращение средней длины кодовых последовательностей.
В отличие от вышеизложенного алгоритма Шеннона — Фано, алгоритм
Хаффмана, хотя и строится на тех же основных принципах, подразумевает хотя и более сложную реализацию для построения дерева, но приводящую к более лучшему результату. Можно сказать, что, если построить все возможные комбинации кодовых последовательностей по алгоритму Шеннона — Фано (для конкретного сообщения), то среди них будут и все возможные комбинации кодовых последовательностей, построенные по алгоритму Хаффмана.
Впрочем, решив написать данное сообщение, я не ставил задачу обучить Вас тонкостям реализации алгоритма Шеннона — Фано, Хаффмана или
Лемпеля — Зива — Велча 
. Для этих целей хватает и монографий, и пухлых исследований. Я хотел, чтобы Вы примерно поняли сам механизм
кодирования с практически нулевой избыточностью (это термин) и саму идею этого алгоритма — максимальное сокращение средней длины кодовых последовательностей. Лучший учитель — практика. Возьмите коллегу. Попросите его закодировать по изложенному выше алгоритму какое-либо сообщение. Пусть он передаст Вам закодированное сообщение и сам словарь. Попробуйте его раскодировать. Тогда Вам станет воочию ясно, что такое
префиксные коды и почему «он понимает что нужно преобразовывать символ "а", а не "я"».
Предваряя следующий вопрос, «а что будет, если в переданном сообщении будет искажёны/потеряны какие-либо символы?», скажу, что для этого вводится обратное понятие — избыточность кода, например, широко известные CRC — коды циклического контроля, позволяющие столь же однозначно узнать, было ли сообщение при передаче искажено, и суметь восстановить его. Впрочем, как говорил сказочник, это уже другая история
.
