Построение безызбыточного кода Шеннона-Фано по методу Хаффмена

Упражнение 1.

Оцените коэффициент избыточности (11). Для этого воспользуйтесь Программой «AnDynSys» (Вкладка «Характеристики ИД», Раздел «Гистограмма») и буквенной последовательностью «Kovalev-Husserl» из Папки «Числовые последовательности».

Введите Числовую последовательность из Папки в качестве Файла во Вкладку «Обработка исходных данных».

Для идентификации букв и других знаков русского языка воспользуйтесь «Материалом к Упражнению 1». Для настройки Программы в этом Материале даны Указания.

Согласно Указаниям рассчитайте Гистограмму.

Выпишите из Раздела «Гистограмма» под графиком числовую таблицу распределения вероятностей букв и других знаков русского языка. Подставьте взятые из таблицы вероятности в формулу (7). Объем сообщения вычислите по формуле (5). Для данного примера L = 40. При вычислении по формуле (5) следует округлять J до ближайшего целого сверху. Затем примените формулу (11).

Контролем правильности расчетов является выполнение условия

p₁ + p₂ + … + p_L = 1.

 

Упражнение 2

Построение безызбыточного кода Шеннона-Фано по методу Хаффмена

1.Изучите метод кодирования, изложенный ниже.

2.Задайте собственный набор вероятностей, при условии, что их сумма по-прежнему равна единице.

3. Постройте собственный безызбыточный код.

4.Вычислите среднюю длину своего кода по формуле (12) и коэффициент

к/к _ср . Сравните со значениями, приведенными ниже. Ваши выводы?

Идея заключается в том, чтобы те буквы, которые встречаются чаще, кодировать меньшим числом двоичных символов – так, чтобы среднее число символов на букву стало меньше пяти, желательно равным количеству информации в символе. Тогда объем сообщения сравняется с количеством информации.

Техническим воплощением идеи является код Шеннона – Фано. Простая процедура построения этого кода, предложенная Д.А.Хаффменом, иллюстрируется Табл.1

 

Таблица 1

 

 

 

и состоит в следующем.

1.Расположим буквы в порядке убывания их априорных вероятностей.

2.Выберем две наименее вероятные буквы. Одной из них (с меньшей вероятностью) присвоим в составляемом коде символ «1», другой – «0». Это будут самые младшие символы (стоят в начале будущего кода).Обе вероятности просуммируем, сумму внесём в список вместо двух прежних (см. нижнюю строку таблицы 1).

3.В исправленном списке снова выберем две наименьшие вероятности. Соответствующим буквам присвоим символы 0 и 1 в следующей позиции составляемого кода. Вероятности просуммируем, внесём в список и т.д., пока не исчерпается последний исправленный список. Пример в табл.1 составлен для алфавита из 8 букв. Исходные коды букв – в первой колонке, полученные оптимальные коды – в последней.

Длина исходного кода для всех букв одинакова и равна к = 3. Средняя длина оптимального кода

 

к_ср = к₁р₁ + к₂ р₂ + …+ к₈ р₈ = 2,6. (12)

 

Объём сообщения уменьшился в к / к_ср = 3 / 2,6 = 1,15 раз.

Если кодировать не отдельные буквы, а слова или блоки из n последовательных слов (nк двоичных символов), то выигрыш растет с увеличением длины блока. На таком принципе построены многие применяемые коды, обеспечивающие сжатие объема сообщения до 2-х раз.

 

 

Упражнение 3.

Компьютерный эксперимент