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

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