- •Балтийский федеральный университет имени Иммануила Канта
- •Расчетно-графическая работа №1 Тема: «Системы счисления».
- •Теоретическая часть
- •Виды сигнала
- •Преобразования сигнала
- •Системы счисления
- •Правила перевода чисел из одной системы счисления в другую
- •Правила перевода целых чисел
- •Правила перевода правильных дробей
- •Правила выполнения простейших арифметических действий
- •Правила сложения
- •Правила вычитания
- •Правила умножения
- •Правила деления
- •Задание
- •Содержание отчета
- •Варианты задания
- •Список литературы
- •Расчетно-графическая работа №2
- •Теоретическая часть
- •Аддитивная (логарифмическая) мера (структурный подход)
- •1.2 Статистический подход к измерению информации
- •Примеры решения задач
- •Задание
- •Содержание отчета
- •Варианты задания
- •Список литературы
- •Расчетно-графическая работа №3
- •Теоретическая часть
- •Кодирование
- •Эффективное кодирование
- •Метод Шеннона-Фано
- •Метод Хаффмана
- •Примеры решения задач
- •Задание
- •Содержание отчета
- •Расчетно-графическая работа №4 Тема: «Разработка формальной грамматики Хомского».
- •1.2 Пример построения грамматики
- •1.3 Представление грамматики в виде графа
- •1.5 Классификация формальных грамматик
- •Примеры решения задач
- •Задание
- •Содержание отчета
- •Варианты задания
- •Список литературы
- •Расчетно-графическая работа №5 Тема: «Нормальные алгоритмы Маркова и машины Тьюринга».
- •Теоретическая часть
- •Нормальные алгоритмы Маркова
- •Машина Тьюринга
- •Примеры задач
- •Задание
- •Содержание отчета
- •Варианты задания
- •Список литературы
- •Расчетно-графическая работа №6 Тема: «Расчет числовых характеристик графов».
- •Теоретическая часть
- •Решение задач
- •Задание
- •Содержание отчета
- •Список литературы
- •Расчетно-графическая работа №7 Тема: «Нахождение кратчайшего остова неориентированного графа по алгоритму Дейкстра».
- •Теоретическая часть
- •Примеры решения задач
- •Задание
- •Содержание отчета
- •Список литературы
- •Расчетно-графическая работа №8 Тема: «Поиск кратчайших путей на неориентированном графе по алгоритму Флойда».
- •Теоретическая часть
- •Задание
- •Содержание отчета
- •Список литературы
- •Расчетно-графическая работа №9 Тема: «Архивирование файлов алгоритмом Зива-Лемпеля-Велча».
- •Теоретическая часть
- •Примеры решения задачи сжатия сообщений
- •Задание
- •Содержание отчета
- •Список литературы
Метод Хаффмана
Этот метод имеет два преимущества по сравнению с методом Шеннона-Фано: он устраняет неоднозначность кодирования, возникающую из-за примерного равенства сумм частот при разделении списка на две части (линия деления проводится неоднозначно), и имеет, в общем случае, большую эффективность кода.
Исходное множество символов упорядочивается по не возрастанию частоты и выполняются следующие шаги:
1) объединение частот:
две последние частоты складываются, а соответствующие символы исключаются из списка;
оставшийся после исключения символов список пополняется суммой частот и вновь упорядочивается;
предыдущие шаги повторяются до тех пор, пока ни получится единица в результате суммирования и список ни уменьшится до одного символа;
2) построение кодового дерева:
строится двоичное кодовое дерево: корнем его является вершина, полученная в результате объединения частот, равная 1; листьями – исходные вершины; остальные вершины соответствуют либо суммарным, либо исходным частотам, причем для каждой вершины левая подчиненная вершина соответствует большему слагаемому, а правая – меньшему; ребра дерева связывают вершины-суммы с вершинами-слагаемыми. Структура дерева показывает, как происходило объединение частот;
ребра дерева кодируются: каждое левое кодируется единицей, каждое правое – нулем;
3) формирование кода: для получения кодов листьев (исходных кодируемых символов) продвигаются от корня к нужной вершине и «собирают» веса проходимых ребер.
Пример 2. Даны символы a, b, c, d с частотами fa = 0,5; fb = 0,25; fc = 0,125; fd= 0,125. Построить эффективный код методом Хаффмана.
объединение частот:
Таблица 3.2
Исходные символы s |
Частоты fs |
Этапы объединения |
||
первый |
второй |
третий |
||
a |
0,5 |
0,5 |
0,5 |
1 |
b |
0,25 |
0,25 |
0,5 |
|
c |
0,125 |
0,25 |
|
|
d |
0,125 |
|
|
|
2) построение кодового дерева:
1
1 0
0,5a 0,5
1 0
0,25 b 0,25
1 0
0,125 c 0,125 d
3) формирование кода:
a - 1;
b - 01;
c - 001;
d - 000.
Как видно, полученные коды совпадают с теми, что были сформированы методом Шеннона-Фано, следовательно, они имеют одинаковую эффективность.
Примеры решения задач
Закодировать фамилию преподавателя методами Шеннона-Фано и Хаффмана.
Задание
Для выбранной в соответствии с вариантом задания задачи:
Закодировать сигнал методом Шеннона-Фано.
Закодировать сигнал методом Хаффмана.
Выполнить сравнительный анализ результатов кодирования.
Сделать выводы.