Дерево Хаффмана

Август 5, 2022

Главная
Информатика
Дерево Хаффмана

Содержание

2. Дерево Хаффмана Исходный текст: AFABCDEABCAADEA
3. Долой деревяшку! Недостатки дерева: восстановить код символа – сложно. сохранить/передать дерево декодеру – сложно. Достоинства дерева:
4. Замена дереву Оказывается, структура дерева и длины кодов символов жёстко связаны. Коды Хаффмана можно восстановить только
5. Алгоритм «без липы» Исходный текст: AFABCDEABCAADEA Формируем списки
6. Объединение списков Объединить самые «лёгкие» списки Упорядочить списки
7. Объединение списков
8. Объединение списков
9. Объединение списков
10. Восстановление кодов Хаффмана Ожидаемая длина кода=1 ЕСТЬ! код = 0 код +1 Ож.длина+0
11. Восстановление кодов Хаффмана Ожидаемая длина кода=1 НЕТ код = 1 код Ож.длина+1
12. Восстановление кодов Хаффмана Ожидаемая длина кода=2 НЕТ код = 10 код Ож.длина+1
13. Восстановление кодов Хаффмана Ожидаемая длина кода=3 ЕСТЬ! код = 100 код +1 Ож.длина+0
14. Восстановление кодов Хаффмана Ожидаемая длина кода=3 ЕСТЬ! код = 101 код +1 Ож.длина+0
15. Восстановление кодов Хаффмана Ожидаемая длина кода=3 ЕСТЬ! код = 110 код +1 Ож.длина+0
16. Восстановление кодов Хаффмана Ожидаемая длина кода=3 НЕТ код = 111 код Ож.длина+1
17. Восстановление кодов Хаффмана Ожидаемая длина кода=4 ЕСТЬ! код = 1110 код +1 Ож.длина+0
19. Скачать презентацию

Слайд 2

Дерево Хаффмана
Исходный текст: AFABCDEABCAADEA

Слайд 3

Долой деревяшку!
Недостатки дерева:
восстановить код символа – сложно.
сохранить/передать дерево декодеру – сложно.
Достоинства

дерева:
декодировать текст – просто!
Выводы:
При декодировании лучше использовать дерево.
При кодировании дерево лучше чем-то заменить.

Слайд 4

Замена дереву
Оказывается, структура дерева и длины кодов символов жёстко связаны.
Коды Хаффмана

можно восстановить только по их длине, при условии, что символы объединяются по правилам упорядоченности!

6

2

2

2

2

1

3

4

5

9

15

Слайд 5

Алгоритм «без липы»
Исходный текст: AFABCDEABCAADEA
Формируем списки

Слайд 6

Объединение списков
Объединить самые «лёгкие» списки
Упорядочить списки

Слайд 7

Объединение списков

Слайд 8

Объединение списков

Слайд 9

Объединение списков

Слайд 10

Восстановление кодов Хаффмана
Ожидаемая длина кода=1
ЕСТЬ!
код = 0
код +1
Ож.длина+0

Слайд 11

Восстановление кодов Хаффмана
Ожидаемая длина кода=1
НЕТ
код = 1
код << 1
Ож.длина+1

Слайд 12

Восстановление кодов Хаффмана
Ожидаемая длина кода=2
НЕТ
код = 10
код << 1
Ож.длина+1

Слайд 13

Восстановление кодов Хаффмана
Ожидаемая длина кода=3
ЕСТЬ!
код = 100
код +1
Ож.длина+0

Слайд 14

Восстановление кодов Хаффмана
Ожидаемая длина кода=3
ЕСТЬ!
код = 101
код +1
Ож.длина+0

Слайд 15

Восстановление кодов Хаффмана
Ожидаемая длина кода=3
ЕСТЬ!
код = 110
код +1
Ож.длина+0

Слайд 16

Восстановление кодов Хаффмана
Ожидаемая длина кода=3
НЕТ
код = 111
код <<1
Ож.длина+1

Слайд 17

Восстановление кодов Хаффмана
Ожидаемая длина кода=4
ЕСТЬ!
код = 1110
код +1
Ож.длина+0