Деревья Хаффмана (продолжение)

Август 23, 2022

Главная
Информатика
Деревья Хаффмана (продолжение)

Содержание

2. 26.10.2015 Деревья Динамическое кодирование по Хаффману Недостатки статического метода Хаффмана : двухпроходность алгоритма (сначала вычисляются веса
3. 26.10.2015 Деревья Динамический (однопроходный) метод Хаффмана
4. 26.10.2015 Деревья Алгоритм перестроения дерева Хаффмана Пусть дерево Хаффмана (ДХ) строится так, что левый сын имеет
5. 26.10.2015 Деревья Пояснения: левый вариант правый вариант (2, 3, 4, 5, 5, 9, 14) (2, 3,
6. 26.10.2015 Деревья Дерево Хаффмана является строго бинарным и содержит ровно 2n − 1 узлов, n из
7. 26.10.2015 Деревья В общем случае неубывающая последовательность весов x1 ≤ x2 ≤ x3 ≤ … ≤
8. 26.10.2015 Деревья Строго бинарное дерево – упорядоченное, если:
9. 26.10.2015 Деревья Из различных деревьев Хаффмана можно выбрать такое, которое не изменится при модификации веса w
10. 26.10.2015 Деревья Пример обеспечения свойства модифицируемости Инвариант: (2, 3, 5, 5, 5, 6, 10, 11, 11,
11. 26.10.2015 Деревья
12. 26.10.2015 Деревья 9 Это дерево также имеет инвариант (2, 3, 5, 5, 5, 6, 10, 11,
13. 26.10.2015 Деревья Окончательно имеем В итоговом алгоритме перевешивания и коррекции весов происходят в одном цикле на
14. 26.10.2015 Деревья АБРАКАДАБРА! Пример динамического кодирования Обозначим α! – узел нулевого веса, отображающий любой символ алфавита,
15. 26.10.2015 Деревья А1Б2Р3А4К5А6Д7А8Б9Р10А11!12 А1Б2Р3А4К5А6Д7А8Б9Р10А11!12 А ⇒ А Б ⇒ 0Б
16. 26.10.2015 Деревья А1Б2Р3А4К5А6Д7А8Б9Р10А11!12 Р ⇒ 00Р
17. 26.10.2015 Деревья А1Б2Р3А4К5А6Д7А8Б9Р10А11!12 А ⇒ 0 К ⇒ 100 К
18. 26.10.2015 Деревья 18 А1Б2Р3А4К5А6Д7А8Б9Р10А11!12 А ⇒ 0 Д → 1100Д К
19. 26.10.2015 Деревья А1Б2Р3А4К5А6Д7А8Б9Р10А11!12 А ⇒ 0. Б → 110
20. 26.10.2015 Деревья А1Б2Р3А4К5А6Д7А8Б9Р10А11!12 Р ⇒ 110 (ср. шаг 9 !) А ⇒ 0
21. 26.10.2015 Деревья ! ⇒1000!. Конец текста. Перестраивать дерево не требуется. А 0Б 00Р 0 100К 0
22. 26.10.2015 Деревья Кодирование первых вхождений Если 1 ≤ i ≤ 2q, то символ αi кодируется как
23. 26.10.2015 Деревья А, Б, В и Г кодируются 6-битными кодами 000000, 000001, 000010 и 000011 остальные
24. 26.10.2015 Деревья А0Б00Р0100К01100Д011011001000! А0Б00Р0100К 01100Д011011001000! 000000 0 000001 00 01111 0100 01001 01100 00010 011011001000 11111
25. 26.10.2015 Деревья Спец.кодировка 0 0 0 0 0 0 0 0 0 0 0 0 0
26. 26.10.2015 Деревья Декодирование 00000000000010001111010001001011000001001101100100011111 1) В спец. кодировке: 000000 - А 00000000000010001111010001001011000001001101100100011111
27. 26.10.2015 Деревья 2) α! + Б 00000000000010001111010001001011000001001101100100011111 00000000000010001111010001001011000001001101100100011111 3) α! + Р → АБР
28. 26.10.2015 Деревья 00000000000010001111010001001011000001001101100100011111 4) А (вес(А) 1→2) 5) α! + К
29. 26.10.2015 Деревья 00000000000010001111010001001011000001001101100100011111 6) А (вес(А) 2→3) 7) α! + Д → АБРАКАД
30. 26.10.2015 Деревья 00000000000010001111010001001011000001001101100100011111 8) А (вес(А) 3 →4) 9) Б (перевес Б-Р) → АБРАКАДАБ
31. 26.10.2015 Деревья 00000000000010001111010001001011000001001101100100011111 10) Р (вес(Р) 1 → 2) 11) А (вес(А) 4 → 5)
32. 26.10.2015 Деревья АБРАКАДАБРА 00000000000010001111010001001011000001001101100100011111 12) α! + ! Конец сообщения
33. 26.10.2015 Деревья Проблемы динамического (адаптивного) кодирования Хаффмена Переполнение: переполнение весов Решение – масштабирование длина кода больше
35. Скачать презентацию

Слайд 2

26.10.2015
Деревья
Динамическое кодирование по Хаффману
Недостатки статического метода Хаффмана :
двухпроходность алгоритма (сначала вычисляются

веса , затем строится дерево (код));
необходимость передавать кодовое дерево вместе с последовательностью закодированных сообщений.

Слайд 3

26.10.2015
Деревья
Динамический (однопроходный) метод Хаффмана

Слайд 4

26.10.2015
Деревья
Алгоритм перестроения дерева Хаффмана
Пусть дерево Хаффмана (ДХ) строится так, что

левый сын имеет вес не больший, чем правый.
При этом ДХ, вообще говоря, не единственно.
Пример: заданы веса W4 = (5, 4, 3, 2).

(2, 3, 4, 5, 5, 9, 14)

добавление α1,
w1 ← w1 + 1 (6 ← 5 + 1)

добавление α4,
w4 ← w4 + 1 (3 ← 2 + 1)

Пояснить 2

Пояснить 1

Слайд 5

26.10.2015
Деревья
Пояснения: левый вариант правый вариант
(2, 3, 4, 5, 5, 9, 14)
(2, 3,

4, 5, 5, 9, 14)

Слайд 6

26.10.2015
Деревья
Дерево Хаффмана является строго бинарным и содержит ровно 2n − 1 узлов, n

из которых являются листьями.
Действительно, пусть в строго бинарном дереве содержится n листьев (внешних узлов) и s внутренних узлов.
Тогда число исходящих из внутренних узлов веток есть 2s.
Подсчет этих же веток, как входящих во все узлы дерева, кроме корня, дает n + s − 1.
Таким образом, 2s = n + s − 1.
Отсюда следует s = n − 1
и общее число узлов n + s = 2n − 1.

Слайд 7

26.10.2015
Деревья
В общем случае неубывающая последовательность весов x1 ≤ x2 ≤ x3 ≤ … ≤ x2n −1, получаемых в порядке взвешенного

сочетания узлов (т.е. порядке выбора минимальных весов и порождения суммарного веса) в алгоритме Хаффмана, инвариантна для всех деревьев Хаффмана с заданными весами w1 ≥ w2 ≥ … ≥ wn − 1 ≥ wn.
При этом внутренние узлы имеют веса x1 + x2, x3 + x4, …, x2n −3 + x2n −2 = x2n −1.

Слайд 8

26.10.2015
Деревья
Строго бинарное дерево – упорядоченное, если:

Слайд 9

26.10.2015
Деревья
Из различных деревьев Хаффмана можно выбрать такое, которое не изменится при

модификации веса w ← w + 1

Слайд 10

26.10.2015
Деревья
Пример обеспечения свойства модифицируемости
Инвариант: (2, 3, 5, 5, 5, 6, 10,

11, 11, 21, 32),

Слайд 11

26.10.2015
Деревья

Слайд 12

26.10.2015
Деревья
9
Это дерево также имеет инвариант (2, 3, 5, 5, 5, 6,

10, 11, 11, 21, 32), и теперь на всем пути 〈2, 5, 9, 11〉 к корню требуемые неравенства выполнены

Слайд 13

26.10.2015
Деревья
Окончательно имеем
В итоговом алгоритме перевешивания и коррекции весов происходят в одном

цикле на пути от листа к корню

Слайд 14

26.10.2015
Деревья
АБРАКАДАБРА!
Пример динамического кодирования
Обозначим α! – узел нулевого веса, отображающий любой

символ алфавита, не встречающиеся до сих пор.
Первые вхождения символов кодируются кодом узла α! , за которым следует код нового символа в специальной кодировке. Пока обозначим такой код подчёркиванием.
Перед началом кодирования и кодировщик и декодировщик знают лишь алфавит. Важно количество символов алфавита для кодирования первых вхождений.

Слайд 15

26.10.2015
Деревья
А1Б2Р3А4К5А6Д7А8Б9Р10А11!12
А1Б2Р3А4К5А6Д7А8Б9Р10А11!12
А ⇒ А
Б ⇒ 0Б

Слайд 16

26.10.2015
Деревья
А1Б2Р3А4К5А6Д7А8Б9Р10А11!12
Р ⇒ 00Р

Слайд 17

26.10.2015
Деревья
А1Б2Р3А4К5А6Д7А8Б9Р10А11!12
А ⇒ 0
К ⇒ 100 К

Слайд 18

26.10.2015
Деревья
18
А1Б2Р3А4К5А6Д7А8Б9Р10А11!12
А ⇒ 0
Д → 1100Д
К

Слайд 19

26.10.2015
Деревья
А1Б2Р3А4К5А6Д7А8Б9Р10А11!12
А ⇒ 0.
Б → 110

Слайд 20

26.10.2015
Деревья
А1Б2Р3А4К5А6Д7А8Б9Р10А11!12
Р ⇒ 110 (ср. шаг 9 !)
А ⇒ 0

Слайд 21

26.10.2015
Деревья
! ⇒1000!. Конец текста.
Перестраивать дерево не требуется.
А 0Б 00Р 0

100К 0 1100Д 0 110 110 0 1000!
↑ ↑ ↑ ↑ ↑ ↑
А А А Б Р А

А1Б2Р3А4К5А6Д7А8Б9Р10А11!12

Слайд 22

26.10.2015
Деревья
Кодирование первых вхождений
Если 1 ≤ i ≤ 2q, то символ αi кодируется как (p + 1)-битное представление

числа i − 1,
иначе − как p-битное представление числа i − q − 1.

Слайд 23

26.10.2015
Деревья
А, Б, В и Г кодируются 6-битными кодами 000000, 000001, 000010

и 000011
остальные 30 букв кодируются 5-битными кодами чисел от 2 до 31, т. е. кодами от 00010 до 11111

Входной алфавит: АБВГДЕЁЖ…ЭЮЯ! n = 34 → 34 = 25 + 2, т. е. p = 5 и q = 2

Слайд 24

26.10.2015
Деревья
А0Б00Р0100К01100Д011011001000!
А0Б00Р0100К 01100Д011011001000!
000000 0 000001 00 01111 0100 01001
01100 00010 011011001000

11111

Слайд 25

26.10.2015
Деревья
Спец.кодировка
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

Слайд 26

26.10.2015
Деревья
Декодирование
00000000000010001111010001001011000001001101100100011111
1) В спец. кодировке: 000000 - А
00000000000010001111010001001011000001001101100100011111

Слайд 27

26.10.2015
Деревья
2) α! + Б
00000000000010001111010001001011000001001101100100011111
00000000000010001111010001001011000001001101100100011111
3) α! + Р → АБР

Слайд 28

26.10.2015
Деревья
00000000000010001111010001001011000001001101100100011111
4) А (вес(А) 1→2) 5) α! + К

Слайд 29

26.10.2015
Деревья
00000000000010001111010001001011000001001101100100011111
6) А (вес(А) 2→3) 7) α! + Д → АБРАКАД

Слайд 30

26.10.2015
Деревья
00000000000010001111010001001011000001001101100100011111
8) А (вес(А) 3 →4) 9) Б (перевес Б-Р) → АБРАКАДАБ

Слайд 31

26.10.2015
Деревья
00000000000010001111010001001011000001001101100100011111
10) Р (вес(Р) 1 → 2)
11) А (вес(А) 4 → 5)

Слайд 32

26.10.2015
Деревья
АБРАКАДАБРА
00000000000010001111010001001011000001001101100100011111
12) α! + ! Конец сообщения

Слайд 33

26.10.2015
Деревья
Проблемы динамического (адаптивного) кодирования Хаффмена
Переполнение:
переполнение весов
Решение – масштабирование
длина кода больше размера

типа «целое»
Решение - накоплении битов кода в связанном списке, к которому можно добавлять новые узлы

Деревья Хаффмана (продолжение)

Содержание

26.10.2015ДеревьяДинамическое кодирование по ХаффмануНедостатки статического метода Хаффмана :двухпроходность алгоритма (сначала вычисляются

26.10.2015ДеревьяДинамический (однопроходный) метод Хаффмана

26.10.2015ДеревьяАлгоритм перестроения дерева Хаффмана Пусть дерево Хаффмана (ДХ) строится так, что

26.10.2015ДеревьяПояснения: левый вариант правый вариант(2, 3, 4, 5, 5, 9, 14)(2, 3,

26.10.2015ДеревьяДерево Хаффмана является строго бинарным и содержит ровно 2n − 1 узлов, n

26.10.2015Деревья В общем случае неубывающая последовательность весов x1 ≤ x2 ≤ x3 ≤ … ≤ x2n −1, получаемых в порядке взвешенного

26.10.2015ДеревьяСтрого бинарное дерево – упорядоченное, если:

26.10.2015ДеревьяИз различных деревьев Хаффмана можно выбрать такое, которое не изменится при

26.10.2015ДеревьяПример обеспечения свойства модифицируемостиИнвариант: (2, 3, 5, 5, 5, 6, 10,

26.10.2015Деревья

26.10.2015Деревья9Это дерево также имеет инвариант (2, 3, 5, 5, 5, 6,

26.10.2015ДеревьяОкончательно имеемВ итоговом алгоритме перевешивания и коррекции весов происходят в одном

26.10.2015ДеревьяАБРАКАДАБРА! Пример динамического кодированияОбозначим α! – узел нулевого веса, отображающий любой

26.10.2015ДеревьяА1Б2Р3А4К5А6Д7А8Б9Р10А11!12А1Б2Р3А4К5А6Д7А8Б9Р10А11!12А ⇒ АБ ⇒ 0Б

26.10.2015ДеревьяА1Б2Р3А4К5А6Д7А8Б9Р10А11!12 Р ⇒ 00Р

26.10.2015ДеревьяА1Б2Р3А4К5А6Д7А8Б9Р10А11!12А ⇒ 0К ⇒ 100 К

26.10.2015Деревья18А1Б2Р3А4К5А6Д7А8Б9Р10А11!12А ⇒ 0 Д → 1100Д К

26.10.2015ДеревьяА1Б2Р3А4К5А6Д7А8Б9Р10А11!12А ⇒ 0. Б → 110

26.10.2015ДеревьяА1Б2Р3А4К5А6Д7А8Б9Р10А11!12Р ⇒ 110 (ср. шаг 9 !)А ⇒ 0

26.10.2015Деревья! ⇒1000!. Конец текста. Перестраивать дерево не требуется.А 0Б 00Р 0

26.10.2015ДеревьяКодирование первых вхожденийЕсли 1 ≤ i ≤ 2q, то символ αi кодируется как (p + 1)-битное представление

26.10.2015Деревья А, Б, В и Г кодируются 6-битными кодами 000000, 000001, 000010

26.10.2015ДеревьяА0Б00Р0100К01100Д011011001000! А0Б00Р0100К 01100Д011011001000!000000 0 000001 00 01111 0100 0100101100 00010 011011001000

26.10.2015ДеревьяСпец.кодировка000000000000000001111111111111111

26.10.2015ДеревьяДекодирование000000000000100011110100010010110000010011011001000111111) В спец. кодировке: 000000 - А00000000000010001111010001001011000001001101100100011111

26.10.2015Деревья2) α! + Б00000000000010001111010001001011000001001101100100011111000000000000100011110100010010110000010011011001000111113) α! + Р → АБР

26.10.2015Деревья000000000000100011110100010010110000010011011001000111114) А (вес(А) 1→2) 5) α! + К

26.10.2015Деревья000000000000100011110100010010110000010011011001000111116) А (вес(А) 2→3) 7) α! + Д → АБРАКАД

26.10.2015Деревья000000000000100011110100010010110000010011011001000111118) А (вес(А) 3 →4) 9) Б (перевес Б-Р) → АБРАКАДАБ

26.10.2015Деревья0000000000001000111101000100101100000100110110010001111110) Р (вес(Р) 1 → 2)11) А (вес(А) 4 → 5)

26.10.2015ДеревьяАБРАКАДАБРА0000000000001000111101000100101100000100110110010001111112) α! + ! Конец сообщения

26.10.2015ДеревьяПроблемы динамического (адаптивного) кодирования Хаффмена Переполнение:переполнение весовРешение – масштабированиедлина кода больше размера

Похожие презентации