Методы эффективного кодирования

Теорема Шеннона не указывает способа кодирования. Первый из методов эффективного кодирования – код Шеннона-Фано. Рассмотрим его подробнее.

Знаки алфавита сообщения выписывают в таблицу в порядке убывания вероятностей. Затем их разделяют на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы. Всем знакам верхней половины в качестве единичного символа присваивают 0, а всем нижним – 1. Каждую из полученных групп, в свою очередь, разбивают на две подгруппы с одинаковыми вероятностями и присваивают 2-й знак, и продолжают процесс до исчерпания символов. Методика годится не для всех возможных алфавитов.

Методика Хаффмана гарантирует однозначное построение кода с наименьшим средним числом знаков на букву.

1. Подсчитываются вероятности появления знаков алфавита в исходном тексте (если они не заданы заранее)

2. Знаки алфавита сообщения выписывают в порядке убывания вероятностей.

3. Последние 2 знака объединяют в новый (составной) знак, вероятность которого равна суммарной вероятности этих знаков. Удаляют эти знаки и вставляют составной в список остальных знаков на соответствующее место (по вероятности). Последние 2 знака снова объединяют в один и вставляют его в соответствующей позиции, предварительно удалив знаки, вошедшие в объединение.

4. Предыдущий шаг повторяют до тех пор, пока сумма всех знаков не станет равной 1.

Этот процесс можно представить как построение дерева, корень которого ­– знак с вероятностью 1, получившийся при объединении знаков из последнего шага, его потомки – знаки из предыдущего шага и т. д.

Каждые m₂ элементов, стоящих на одном уровне, нумеруются от 0 до m₂-1. Коды получаются из путей (от первого потомка корня и до листка). При декодировании можно использовать то же самое дерево, считывается по одной цифре и делается шаг по дереву, пока не достигается лист — тогда выводится знак, стоящий в листе и производится возврат в корень.

Построение дерева Хаффмана

Бинарное дерево, соответствующее коду Хаффмана, называют деревом Хаффмана.

Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева.

Общая схема построения дерева Хаффмана:

1. Составим список кодируемых знаков (при этом будем рассматривать каждый знак как одноэлементное бинарное дерево, вес которого равен весу знак).

2. Из списка выберем 2 узла с наименьшим весом (под весом можно понимать частоту использования знак – чем чаще используется, тем больше весит).

3. Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. При этом вес сформированного узла положим равным сумме весов дочерних узлов.

4. Добавим сформированный узел к списку.

5. Если в списке больше одного узла, то повторить 2-5.

Более удобна методика, использующая принцип префиксности кодов, при которой эффективный код строится так, чтобы ни одна комбинация кода не совпадала с началом более длинной комбинации.

Недостатки системы эффективного кодирования:

– различие в длине кодовых комбинаций требует буферов на обеих сторонах канала;

– задержка в передаче и при декодировании;

– помехонезащищенность.