Алгоритмы оптимального кодирования

Август 6, 2022

Главная
Информатика
Алгоритмы оптимального кодирования

Содержание

2. Хаффмана АЛГОРИТМ
3. David Huffman (1925-1999) В 18 лет Дэвид получил степень бакалавра электротехники в уни-верситете штата Огайо. Основную
4. Таблица кодов Хаффмана
5. Код Хаффмана обладает свойством префиксности, то есть код никакого символа не является началом кода какого-либо другого
6. МОУ СОШ №33 с углубленным изучением математики г.Ярославля Т 001 В 011100 Q 1101000101 корень Дерево
7. 00000 11011 110100011 корень Дерево Хаффмана
8. 01000111011011100 корень Дерево Хаффмана С О D E
11. Алгоритм Хаффмана двухпроходный: на первом проходе строится частотный словарь и генерируются коды; на втором проходе происходит
12. Алгоритм построения дерева Хаффмана Среди символов выбрать два с наименьшими весами (если таких пар несколько, выбирается
13. Пример. Построить код Хаффмана для фразы: на дворе трава, на траве дрова Шаг 1: Шаги 2-3:
14. а в д , е н р о т _ 0 1 0 1 0 1
15. а в д , е н р о т _ 0 1 0 1 0 1
16. а в д , е н р о т _ 0 1 0 1 0 1
17. а в д , е н р о т _ 0 1 0 1 0 1
18. а в д , е н р о т _ 0 1 0 1 0 1
19. а в д , е н р о т _ 0 1 0 1 0 1
20. а в д , е н р о т _ 0 1 0 1 0 1
21. а в д , е н р о т _ 0 1 0 1 0 1
22. а в д , е н р о т _ 0 1 0 1 0 1
23. а в д , е н р о т _ 0 1 0 1 0 1
24. Кодирование текста НА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА 1001001110110010110010110001111101 Н А _ Д В О Р
25. Кодирование текста НА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА 10010011101100101100101100011111 01101000100001111111001001111101 1010001010001110110101110001000
26. Коэффициент сжатия Коэффициентом сжатия называется отношение объема исходного сообщения к объему сжатого. Объем сжатого сообщения: 6*2+4*3+2*4+1*4+2*4+2*4+4*3+2*4+2*4+5*3=95
27. Алгоритм Хаффмана универсальный, его можно применять для сжатия данных любых типов; Классический алгоритм Хаффмана требует хранения
28. Пример: построить код Хаффмана для фразы ОТ_ТОПОТА_КОПЫТ_ПЫЛЬ_ПО_ПОЛЮ_ЛЕТИТ Определим частоту вхождения символов в фразу: 2. Строим таблицу
29. Метод Хаффмана(таблица)
30. КОРЕНЬ ДЕРЕВА
31. Построены префиксные коды символов: Сообщение в новых кодах содержит **** бит (сжатое), в кодировке ASCII –
33. Скачать презентацию

Слайд 2

Хаффмана
АЛГОРИТМ

Слайд 3

David Huffman (1925-1999)
В 18 лет Дэвид получил степень бакалавра электротехники в

уни-верситете штата Огайо. Основную концепцию кодирования данных Хаффман разработал во время Второй мировой войны, когда служил на эсминце офицером-связистом. Изначально алгоритм предназначался для кодирования радиосообщений.

За свою деятельность он получил множество наград за исключительный вклад в теорию информации.

Дэвид Хаффман

Слайд 4

Таблица кодов Хаффмана

Слайд 5

Код Хаффмана обладает свойством префиксности, то есть код никакого символа не

является началом кода какого-либо другого символа.

Слайд 6

МОУ СОШ №33 с углубленным изучением математики г.Ярославля
Т
001
В
011100
Q
1101000101
корень
Дерево Хаффмана

Слайд 7

00000
11011
110100011
корень
Дерево Хаффмана

Слайд 8

01000111011011100
корень
Дерево Хаффмана
С
О
D
E

Слайд 9

Слайд 10

Слайд 11

Алгоритм Хаффмана двухпроходный: на первом проходе строится частотный словарь и генерируются

коды; на втором проходе происходит непосредственно кодирование.

1. Подсчитать частоту встречаемости (вес) каждого символа.

НА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА

Алгоритм Хаффмана

Слайд 12

Алгоритм построения дерева Хаффмана
Среди символов выбрать два с наименьшими весами (если таких

пар несколько, выбирается любая из них).
Свести ветки дерева от этих двух символов в одну точку с весом, равным сумме двух весов, при этом веса самих элементов стираются.
Повторять пункты 1 и 2 до тех пор, пока не останется одна вершина с весом, равным сумме весов исходных символов.
Пометить одну ветку нулём, а другую - единицей (по собственному усмотрению).

Слайд 13

Пример. Построить код Хаффмана для фразы:
на дворе трава, на траве

дрова

Шаг 1:

Шаги 2-3:

Слайд 14

а
в
д
,
е
н
р
о
т
_
0
1
0
1
0
1
1
0
0
1
0
1
0
1
0
1
0
1
00
Шаг 4:

Слайд 15

а
в
д
,
е
н
р
о
т
_
0
1
0
1
0
1
1
0
0
1
0
1
0
1
0
1
0
1
00
010
Шаг 4:

Слайд 16

а
в
д
,
е
н
р
о
т
_
0
1
0
1
0
1
1
0
0
1
0
1
0
1
0
1
0
1
00
010
0110
Шаг 4:

Слайд 17

а
в
д
,
е
н
р
о
т
_
0
1
0
1
0
1
1
0
0
1
0
1
0
1
0
1
0
1
00
010
0110
0111
Шаг 4:

Слайд 18

а
в
д
,
е
н
р
о
т
_
0
1
0
1
0
1
1
0
0
1
0
1
0
1
0
1
0
1
00
010
0110
0111
1000
Шаг 4:

Слайд 19

а
в
д
,
е
н
р
о
т
_
0
1
0
1
0
1
1
0
0
1
0
1
0
1
0
1
0
1
00
010
0110
0111
1000
1001
Шаг 4:

Слайд 20

а
в
д
,
е
н
р
о
т
_
0
1
0
1
0
1
1
0
0
1
0
1
0
1
0
1
0
1
00
010
0110
0111
1000
1001
101
Шаг 4:

Слайд 21

а
в
д
,
е
н
р
о
т
_
0
1
0
1
0
1
1
0
0
1
0
1
0
1
0
1
0
1
00
010
0110
0111
1000
1001
101
1100
Шаг 4:

Слайд 22

а
в
д
,
е
н
р
о
т
_
0
1
0
1
0
1
1
0
0
1
0
1
0
1
0
1
0
1
00
010
0110
0111
1000
1001
101
1100
1101
Шаг 4:

Слайд 23

а
в
д
,
е
н
р
о
т
_
0
1
0
1
0
1
1
0
0
1
0
1
0
1
0
1
0
1
00
010
0110
0111
1000
1001
101
1100
1101
111
Шаг 4:

Слайд 24

Кодирование текста
НА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА
1001001110110010110010110001111101
Н А _ Д

В О Р Е _ Т
101000100001111111001001111101101
Р А В А , _ Н А _ Т Р
0001010001110110101110001000
А В Е _ Д Р О В А

Слайд 25

Кодирование текста
НА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА
10010011101100101100101100011111
01101000100001111111001001111101
1010001010001110110101110001000

Слайд 26

Коэффициент сжатия
Коэффициентом сжатия называется отношение объема исходного сообщения к объему сжатого.
Объем

сжатого сообщения:
6*2+4*3+2*4+1*4+2*4+2*4+4*3+2*4+2*4+5*3=95 бит=12 байт.

Объем исходного сообщения в ASCII равен 30 байт.

Коэффициент сжатия составляет 30 / 12 = 2,5

Слайд 27

Алгоритм Хаффмана универсальный, его можно применять для сжатия данных любых

типов;
Классический алгоритм Хаффмана требует хранения кодового дерева, что увеличивает размер файла.

Достоинства и недостатки метода

Слайд 28

Пример: построить код Хаффмана для фразы ОТ_ТОПОТА_КОПЫТ_ПЫЛЬ_ПО_ПОЛЮ_ЛЕТИТ
Определим частоту вхождения символов в

фразу:
2. Строим таблицу частоты вхождения по убыванию.(см.слайд 9)
3. Строим орграф Хаффмана: -символ задает вершину- лист орграфа; -вес вершины равен частоте вхождения символа; -соединяются пары вершин с наименьшим весом: -левые ветви обозначаем 0; -правые ветви обозначаем 1; -определяем код символа от корня к листу;

Слайд 29

Метод Хаффмана(таблица)

Слайд 30

КОРЕНЬ ДЕРЕВА

Слайд 31

Построены префиксные коды символов:
Сообщение в новых кодах содержит **** бит (сжатое),

в кодировке ASCII – 34 * 8 = 272 бита(исходное)
тогда К сж = 272 / **** = ___

Алгоритмы оптимального кодирования

Содержание

Хаффмана АЛГОРИТМ

David Huffman (1925-1999)В 18 лет Дэвид получил степень бакалавра электротехники в

Таблица кодов Хаффмана

Код Хаффмана обладает свойством префиксности, то есть код никакого символа не

МОУ СОШ №33 с углубленным изучением математики г.ЯрославляТ001В011100Q1101000101кореньДерево Хаффмана

0000011011110100011кореньДерево Хаффмана

01000111011011100кореньДерево ХаффманаСОDE

Алгоритм Хаффмана двухпроходный: на первом проходе строится частотный словарь и генерируются

Алгоритм построения дерева ХаффманаСреди символов выбрать два с наименьшими весами (если таких

Пример. Построить код Хаффмана для фразы: на дворе трава, на траве

авд,енрот_01010110010101010100Шаг 4:

авд,енрот_01010110010101010100010Шаг 4:

авд,енрот_010101100101010101000100110Шаг 4:

авд,енрот_0101011001010101010001001100111Шаг 4:

авд,енрот_01010110010101010100010011001111000Шаг 4:

авд,енрот_010101100101010101000100110011110001001Шаг 4:

авд,енрот_010101100101010101000100110011110001001101Шаг 4:

авд,енрот_0101011001010101010001001100111100010011011100Шаг 4:

авд,енрот_01010110010101010100010011001111000100110111001101Шаг 4:

авд,енрот_01010110010101010100010011001111000100110111001101111Шаг 4:

Кодирование текстаНА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА1001001110110010110010110001111101 Н А _ Д

Кодирование текстаНА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА1001001110110010110010110001111101101000100001111111001001111101 1010001010001110110101110001000

Коэффициент сжатияКоэффициентом сжатия называется отношение объема исходного сообщения к объему сжатого.Объем