2. Завдання

1. Побудувати двійковий оптимальний нерівномірний код Хаффмана для для передачі M повідомлень, якщо повідомлення над виході з джерела з’являються з ймовірностями p(x_i). Використати варіанти завдань наведені в таблиці 1.1.

2. Побудувати кодове дерево для отриманого коду.

3. Розв’язати завдання 1 при умові, що q стане на одиницю більшим.

4. Побудувати кодове дерево для отриманого коду.

8. Модифікувати програму розроблену в лабораторній роботі №1, додавши можливість побудови коду Хаффмана для україномовних текстів. В програмі передбачити наступні функції:

• можливість роботи з символами однієї з кириличних кодових таблиць (cyrilic windows, koi8ru, або ін..);

• можливість вводу та копіювання текстового блоку;

• відображення загальної кількості символів у текстовому блоці;

• розмір текстового блоку повинен бути не менше 2000 символів;

• при обчисленні ентропії враховувати символи знаків пунктуації (коми, крапки, тире та ін..);

• відображення імовірностей появи символів у текстовому блоці;

• відображення обчисленого значення ентропії;

• відображення таблиці покрокової побудови коду Хаффмана.

• відображення таблиці побудованого коду.

• відображення інформації про розробника (курс, група, прізвище та ініціали);

• виконання без застосування середовища програмування використаного для створення програми.

9. Оформити звіт.

3. Приклад виконання завдання

Побудувати оптимальний нерівномірний код (ОНК) Хаффмана для передачі 13 повідомлень, якщо повідомлення над виході з джерела з’являються з ймовірностями 0.25, 0.1, 0.05, 0.02, 0.03, 0.05, 0.11, 0.04, 0.01, 0,15, 0.01, 0,08, 0.1.

Розв’язання:

Складаємо список повідомлень які потрібно закодувати, кожному з яких відповідає його ймовірність. Отриманий список сортуємо в порядку спадання (таблиця). хi з різними імовірностями подано в таблиці 4.2.

Таблиця 4.2 – Побудова нерівномірного коду Хаффмана для тринадцяти повідомлень

Номер повідом-лення	Ймовір - ність повідом- лення	Ймовірності повідомлень при об’єднаннях
		перш -ому	друго -му	третьо-му	четверт- ому	п’ятому	шостому
1	0,25	0,25	0,25	0,25	0,25	0,25	0,25
2	0,15	0,15	0,15	0,15	0,15	0,15	0,17
3	0,11	0,11	0,11	0,11	0,11	0,12	0,15
4	0,1	0,1	0,1	0,1	0,1	0,11	0,12
5	0,1	0,1	0,1	0,1	0,1	0,1	0,11
6	0,08	0,08	0,08	0,08	0,09	0,1	0,1
7	0,05	0,05	0,05	0,07	0,08	0,09	0,1
8	0,05	0,05	0,05	0,05	0,07	0,08
9	0,04	0,04	0,04	0,05	0,05
10	0,03	0,03	0,04	0,04
11	0,02	0,02	0,03
12	0,01	0,02
13	0,01

Таблиця 4.2 – Продовження

Ймовірності повідомлень при об’єднаннях						Кодова комбінація ОНК
сьомому	восьмому	дев’ятому	десятому	одинадця тому	дванадця тому
0,25	0,25	0,32	0,43	0,57	1	01
0,2	0,23	0,25	0,32	0,43		001
0,17	0,2	0,23	0,25			101
0,15	0,17	0,2				110
0,12	0,15					111
0,11						0001
						1001
						00000
						00001
						10001
						100000
						1000010
						1000011

Для створеного коду побудуємо кодове дерево наведене на рисунку 4.1.

Рисунок 4.1 – Кодове дерево коду Хаффмана для тринадцяти повідомлень