Дерево Хаффмана
Долой деревяшку!
Замена дереву
Алгоритм «без липы»
Объединение списков
Объединение списков
Объединение списков
Объединение списков
Восстановление кодов Хаффмана
Восстановление кодов Хаффмана
Восстановление кодов Хаффмана
Восстановление кодов Хаффмана
Восстановление кодов Хаффмана
Восстановление кодов Хаффмана
Восстановление кодов Хаффмана
Восстановление кодов Хаффмана
Восстановление кодов Хаффмана
1.74M
Категория: ПрограммированиеПрограммирование

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

1.

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

Исходный текст: AFABCDEABCAADEA
A
6
6
B
2
2
C
2
2
D
2
2
E
2
2
F
1
1
15
4
9
5
3
A
6
0
B
2
100
C
2
101
D
2
110
E
2
1110
F
1
1111

3. Долой деревяшку!

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

4. Замена дереву

6
A
6
0
B
2
100
2
C
2
101
2
D
2
110
2
E
2
1110
2
F
1
1111
1
15
4
9
5
3
Оказывается, структура дерева и длины кодов
символов жёстко связаны.
Коды Хаффмана можно восстановить только по
их длине, при условии, что символы объединяются
по правилам упорядоченности!

5. Алгоритм «без липы»

Исходный текст: AFABCDEABCAADEA
A
6
B
2
C
6
A
0
2
B
0
2
2
C
0
D
2
2
D
0
E
2
2
E
0
F
1
1
F
0
Формируем
списки

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

Объединить самые «лёгкие» списки
Упорядочить списки
6
A
0
6
A
0
2
B
0
2
B
0
2
C
0
2
C
0
2
B
0
2
D
0
2
D
0
2
C
0
2
E
0
2
D
0
3
1
F
0
E 0+1
6
3
F
0+1
A
0
E 0+1
F
0+1

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

6
A
0
6
A
3
E
1
4
C 0+1
D 0+1
2
B
0
3
E
1
F
2
C
0
2
B
0
2
D
0
F
1
0
1

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

6
4
3
2
A
C
E
B
0
1
1
0
D
F
6
A
0
5
E 1+1
F
1+1
4
C
D
1
1
1
1
B 0+1

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

6
5
4
A
E
C
0
2
1
F
D
2
B
6
A
0
9
E 2+1
1
F 2+1 B 1+1 C 1+1
D 1+1
1
9
E 3+1
F 3+1 B 2+1 C 2+1
D 2+1
A 0+1

10. Восстановление кодов Хаффмана

код = 0
ЕСТЬ!
0
A
1
B
3
C
3
D
3
E
4
F
4
Ожидаемая длина кода=1
код +1
Ож.длина+0

11. Восстановление кодов Хаффмана

код = 1
0
A
1
B
3
C
3
D
3
E
4
F
4
НЕТ
Ожидаемая длина кода=1
код << 1
Ож.длина+1

12. Восстановление кодов Хаффмана

код = 10
0
A
1
B
3
C
3
D
3
E
4
F
4
НЕТ
Ожидаемая длина кода=2
код << 1
Ож.длина+1

13. Восстановление кодов Хаффмана

код = 100
0
A
1
100
B
3
C
3
D
3
E
4
F
4
ЕСТЬ!
Ожидаемая длина кода=3
код +1
Ож.длина+0

14. Восстановление кодов Хаффмана

код = 101
0
A
1
100
B
3
101
C
3
D
3
E
4
F
4
ЕСТЬ!
код +1
Ожидаемая длина кода=3
Ож.длина+0

15. Восстановление кодов Хаффмана

код = 110
0
A
1
100
B
3
101
C
3
110
D
3
E
4
F
4
ЕСТЬ!
код +1
Ожидаемая длина кода=3
Ож.длина+0

16. Восстановление кодов Хаффмана

код = 111
0
A
1
100
B
3
101
C
3
110
D
3
E
4
F
4
НЕТ
код <<1
Ожидаемая длина кода=3
Ож.длина+1

17. Восстановление кодов Хаффмана

код = 1110
0
A
1
100
B
3
101
C
3
110
D
3
1110
E
4
F
4
ЕСТЬ!
код +1
Ожидаемая длина кода=4
Ож.длина+0

18. Восстановление кодов Хаффмана

код = 1111
0
A
1
100
B
3
101
C
3
110
D
3
1110
E
4
1111
F
4
ЕСТЬ!
код +1
Ожидаемая длина кода=4
Ож.длина+0
English     Русский Правила