Prezentatsiya2

1.

Сжатие данных без потерь
Алгоритм Хаффмана
Теория информации и кодирования
Занятие 2

2.

Что такое избыточность?
Избыточность данных - часть информации,
которая может быть устранена без потери
смысла
Примеры:
• Повторяющиеся символы: "AAAAAAB"
• Предсказуемые сочетания
• Стандартные форматы кодирования
Цель сжатия: устранить избыточность

3.

Проблема неоднозначности кодирования
Плохой код:
A=0
B = 01
Последовательность 001 может означать:
• AAB (0-0-01)
• AB (0-01)
❌ Неоднозначно!

4.

Префиксные коды
Определение:
Ни одно кодовое слово не является
началом другого
Пример хорошего кода:
A=0
B = 10
C = 11
Преимущества:
✅ Однозначное декодирование
✅ Мгновенное декодирование
✅ Реализация через бинарное дерево

5.

Алгоритм Хаффмана - общая схема
Жадный алгоритм построения
оптимального префиксного кода
Шаги:
1. Список символов с вероятностями
2. Объединение узлов с наименьшими
вероятностями
3. Построение бинарного дерева
4. Присвоение кодов (0-лево, 1-право)
Результат: код с минимальной средней длиной

6.

Шаг 1 - Подготовка
Исходные данные:
A: 0.4
B: 0.3
C: 0.2
D: 0.1
Упорядочиваем по
убыванию:
A: 0.4
B: 0.3
C: 0.2
D: 0.1

7.

Шаг 2 - Первое объединение
Наименьшие вероятности:
C: 0.2
D: 0.1
Новый узел:
[C+D] = 0.3
Обновленный список:
A: 0.4
B: 0.3
[C+D]: 0.3

8.

Шаг 3 - Второе объединение
Наименьшие вероятности:
B: 0.3
[C+D]: 0.3
Новый узел:
[B+C+D] = 0.6
Обновленный список:
A: 0.4
[B+C+D]: 0.6

9.

Шаг 4 - Финальное объединение
Последние два узла:
A: 0.4
[B+C+D]: 0.6
Корневой узел:
[A+B+C+D] = 1.0

10.

Построение дерева кодирования
Корень (1.0)
/ \
0/
\1
A
[B+C+D]
/ \
0/
\1
B [C+D]
/ \
0/
\1
C
D

11.

Присвоение кодов
Правило:
0 - левое ребро
1 - правое ребро
Результат:
A: 0
B: 10
C: 110
D: 111
✅ Все коды префиксные

12.

Оценка эффективности
Средняя длина кода:
Lср = Σ(длинаᵢ × вероятностьᵢ)
Расчет:
A: 1 × 0.4 = 0.4
B: 2 × 0.3 = 0.6
C: 3 × 0.2 = 0.6
D: 3 × 0.1 = 0.3
Итого: 1.9 бит/символ
Равномерный код: 2 бит/символ

13.

ПОСЛЕДОВАТЕЛЬНОСТЬ: 0 0 1 1 0 1 0
ШАГИ ДЕКОДИРОВАНИЯ:
1. "0" -> совпало с 'a'. Вывод: a. Остаток: 0 1 1 0 1 0
2. "0" -> совпало с 'a'. Вывод: a. Остаток: 1 1 0 1 0
3. "1" -> нет совпадения.
"11" -> нет совпадения.
"110" -> совпало с 'c'. Вывод: c. Остаток: 1 0
4. "1" -> нет совпадения.
"10" -> совпало с 'b'. Вывод: b. Остаток: (пусто).
ФИНАЛЬНЫЙ РЕЗУЛЬТАТ: a a c b

14.

Преимущества и применение
Преимущества:
✅ Всегда оптимальный префиксный код
✅ Простая реализация
✅ Широкая практическая применимость
Области применения:
• Архиваторы (ZIP, RAR)
• Форматы изображений (PNG, JPEG)
• Протоколы передачи данных

15.

Домашнее задание
Задача:
Построить код Хаффмана для вашего имени
Требования:
1. Посчитать частоты букв
2. Построить дерево кодирования
3. Выписать полученные коды
4. Рассчитать среднюю длину кода
5. Сравнить с равномерным кодированием