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