Сжатие текстовой информации

Слайд 3

Сжатие данных — процедура перекодирования данных, производимая с целью уменьшения их

объёма.

Декомпрессия - это способ восстановления сжатых данных в исходные.

Основные понятия

Кодирование информации является избыточным, если количество бит в полученном коде больше, чем это необходимо для однозначного декодирования исходной информации.

Слайд 4

Под архиватором понимается программа-архиватор, формат архива и метод сжатия в комплексе.

Архиваторы

Слайд 5

Архиваторы ACE, RAR и Squeez имеют близкие результаты с небольшим преимуществом

по степени сжатия у RAR, и при высокой скорости сжатия у Squeez.

(чем меньше, тем лучше)

(чем больше, тем лучше)

Сравнительные характеристики

Степень сжатия зависит от
используемого архиватора;
метода сжатия;
типа исходного файла.

Слайд 6

Бесплатные программы для обработки аудио- и видеоинформации

Слайд 7

Виды сжатий
Возможно восстановление исходных данных без искажений.
Форматы файлов: gif, tif, png, pcx, avi,

zip, rar, arj.

Восстановление возможно с искажениями, малозаметными для человеческого глаза или уха.
Форматы файлов: jpg, mpeg, adpcm .

Слайд 8

Сжатие с потерей качества

Слайд 9

Сжатие без потерь Алгоритм RLE
от англ. Run Length Encoding
В файле

записывается, сколько раз повторяются одинаковые байты.
Схематично:
"RRRRRGGGBBBBBBRRRBBRRRRRRR"
"5R3G6B3R2B7R".

Слайд 10

В восьмиразрядной таблице символьной кодировки АSCII каждый символ кодируется восемью битами

и, следовательно, занимает в памяти 1 байт.

Некоторые ASCII-коды

ASCII-коды

Слайд 11

Сжатие без потерь Метод упаковки
TO BE OR NOT TO BE?
19 символов в

предложении: 3*19=57 бит=8 байт Коэффициент сжатия: 19/8≈ 2,4

Двукратное сжатие. Формат BCD – Binary Coded Decimal

Пример №2

Пример №1

Слайд 12

Практическая работа

Слайд 13

Практическая работа

Слайд 14

Практическая работа
“Частотный анализ букв русского языка”
Открыть с помощью Microsoft Office

Word документ Skazka.doc.
Подсчитать количество каждой из букв русского алфавита в тексте и заполнить таблицу Alphabet.xls в Microsoft Office Excel. Вычислить частоту встречаемости букв.
Упорядочить данные таблицы по убыванию частот.
Построить график распределения частот букв.

Слайд 15

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

Слайд 16

Частотный анализ
Сказка «Снежная королева»

Слайд 17

Сравнительный частотный анализ
«Анна Каренина» оеанитслвркдмупяьыгбчзжйшхэющцфъ 280 тыс. слов
Солженицын А.И. oeaинтсвлрлдмпуьяыгбзчйхжшюцщэфъ 86

тыс. слов
Новости oeaинтсрвлкдмпуяьыгзбчйжхюшцщэфъё 25 тыс. слов

Слайд 18

В тексте, написанном на русском языке, в каждой тысяче символов в среднем

будет 90 букв "о", 72 - "е" и только 2 -"ф". Больше же всего окажется пробелов: 174.

Слайд 19

Оба этих алгоритма используют коды переменной длины: часто встречающийся символ кодируется

двоичным кодом меньшей длины, редко встречающийся — кодом большей длины. Коды Шеннона-Фано и Хаффмана — префиксные, то есть никакое кодовое слово не является началом любого другого. Это свойство позволяет однозначно декодировать любую последовательность кодовых слов. В отличие от алгоритма Шеннона-Фано, алгоритм Хаффмана обеспечивает минимальную избыточность, то есть минимальную длину кодовой последовательности при побайтном кодировании.

Алгоритм
Шеннона-Фано и Хаффмана

Слайд 20

К.Шеннон и Р.Фано сформулировали алгоритм сжатия, который использует коды переменной длины.
Алгоритм

Шеннона-Фано

Слайд 21

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

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

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

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

Слайд 22

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

Слайд 23

Двоичное дерево
Двоичным (бинарным) называется дерево, из каждой вершины которого выходят две

ветви.

Слайд 24

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

Слайд 25

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

Слайд 26

Азбука Морзе
Сэмюэль Морзе (1791-1872) - американский изобретатель и художник

Слайд 27

Азбука Морзе

Слайд 28

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

Слайд 29

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

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

Слайд 30

Дерево азбуки Морзе

Слайд 31

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

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

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

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

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

Слайд 32

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

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

Слайд 33

3
4
4
7
8
9
13
17
30
Построение дерева Хаффмана

Слайд 34

30
17
13
8
4
9
4
7
3

Слайд 35

Построение дерева Хаффмана

Слайд 36

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

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

Слайд 37

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

Слайд 38

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

сжатого сообщения:
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

Слайд 39

Декодирование
Восстановить исходный текст:
1 0 0 1 0 0 1 0

1 1 1 0 0 0 1 1 0

Слайд 40

1 0 0 1 0 0 1 0 1 1 1

0 0 0 1 1 0

Декодирование

Слайд 41

Самостоятельная работа
Постройте код Хаффмана для предложения:
TO BE OR NOT TO BE?
Определите

коэффициент сжатия для данной фразы, если каждый символ кодируется в ASCII.
Сравните результат с тем, что был получен при сжатии фразы методом упаковки, сделайте выводы.
Проверьте правильность выполнения задания: закодируйте предложение, используя полученный код, а затем попробуйте его восстановить.

Слайд 42

1 0
1 0 1 0
1 0 1 0
1 0 1 0
24+14+33+52+42+14+14+23=53

бита=7 байт
Коэффициент сжатия: 19/7 ≈ 2,7

Одно из решений

Слайд 43

1 0
1 0
1 0
1 0
1 0
1 0
42+23+23+52+33+14+15+15=53 бита
Другое решение
1 0

Слайд 44

Книги по теме

Слайд 45

задание
Задание №1
Постройте код Хаффмана для фраз:
Человек как музыкальный инструмент, как

настроишь, так и живет.
Музыка показывает человеку те возможности величия, которые есть в его душе.
Определите коэффициент сжатия для данной фразы, если каждый символ кодируется в ASCII.

Слайд 46

Домашнее задание
Задание №2
На языке Си++ напишите программу, реализующую алгоритм RLE для

текстовых данных.
Исходные данные в виде строки, содержащей латинские буквы и пробелы, находятся в текстовом файле input.txt (длина строки не более 255). Результат должен выводиться в текстовый файл output.txt, первая строка которого содержит сжатую строку, вторая – коэффициент сжатия с точностью до сотых.
Пример файла:
LLLLLLLLEESSSSSSSSSooooooooooooNN one
Ответ:
8L2E9S12o2N8 1o1n1e
2.32

Слайд 47

Кроссворд

Слайд 48

Сжатие текстовой информации

Содержание