Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

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

Содержание

Сжатие текстовой информации
информации СЖАТИЕ СЖАТИЕ Работа Ярцевой О.В. Сжатие  текстовой информации Сжатие данных — процедура перекодирования данных, производимая  с целью уменьшения их Под архиватором понимается программа-архиватор, формат архива и метод сжатия в комплексе. Архиваторы Архиваторы ACE, RAR и Squeez имеют близкие результаты с небольшим преимуществом по Бесплатные программы для обработки аудио- и видеоинформации Виды сжатийВозможно восстановление исходных данных без искажений.Форматы файлов: gif, tif, png, pcx, Сжатие  с потерей качества Сжатие без потерь  Алгоритм RLE от англ. Run Length EncodingВ файле В восьмиразрядной таблице символьной кодировки АSCII каждый символ кодируется восемью битами Сжатие без потерь Метод упаковкиTO BE OR NOT TO BE?19 символов в Практическая работа Практическая работа Практическая работа“Частотный анализ букв русского языка” Открыть с помощью Microsoft Office Word Хаффмана АЛГОРИТМ Частотный анализСказка «Снежная королева» Сравнительный частотный анализ«Анна Каренина» оеанитслвркдмупяьыгбчзжйшхэющцфъ   280 тыс. словСолженицын А.И. oeaинтсвлрлдмпуьяыгбзчйхжшюцщэфъ В тексте, написанном на русском языке, в каждой тысяче символов в среднем будет Оба этих алгоритма используют коды переменной длины: часто встречающийся символ кодируется двоичным К.Шеннон и Р.Фано сформулировали алгоритм сжатия,  который использует  коды переменной длины.Алгоритм Шеннона-Фано David Huffman  (1925-1999)В 18 лет Дэвид получил степень бакалавра электротехники в Таблица кодов Хаффмана Двоичное деревоДвоичным (бинарным) называется дерево,  из каждой вершины которого выходят две ветви. МОУ СОШ №33 с углубленным изучением математики г.ЯрославляТ001В011100Q1101000101кореньДерево Хаффмана 0000011011110100011кореньДерево Хаффмана Азбука МорзеСэмюэль Морзе  (1791-1872) - американский изобретатель и художник Азбука Морзе 01000111011011100кореньДерево ХаффманаСОDE Код Хаффмана обладает свойством префиксности,  то есть код никакого символа не Дерево азбуки Морзе Алгоритм Хаффмана двухпроходный:     на первом проходе строится частотный Алгоритм построения дерева ХаффманаСреди символов выбрать два с наименьшими весами (если таких 344789131730Построение дерева Хаффмана 301713849473 Построение дерева Хаффмана Кодирование текстаНА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА1001001110110010110010110001111101  Н   А Кодирование текстаНА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА10010011101100101100101100011111  01101000100001111111001001111101  1010001010001110110101110001000 Коэффициент сжатияКоэффициентом сжатия называется отношение объема исходного сообщения к объему сжатого.Объем сжатого Декодирование Восстановить исходный текст:1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 1 1 0 Самостоятельная работаПостройте код Хаффмана для предложения:TO BE OR NOT TO BE?Определите коэффициент 1 1          01 Книги по теме заданиеЗадание №1Постройте код Хаффмана для фраз: Человек как музыкальный инструмент, как настроишь, Домашнее заданиеЗадание №2На языке Си++ напишите программу, реализующую алгоритм RLE для текстовых Кроссворд Кроссворд ЛитератураАндреева Е.В. Математические основы информатики. Элективный курс: учебное пособие / Е.В.Андреева, Л.Л.Босова,
Слайды презентации

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

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

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

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

целью уменьшения их объёма.
Декомпрессия - это способ

восстановления сжатых данных в исходные.

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

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


Слайд 4

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

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

сжатия в комплексе.
Архиваторы


Слайд 5 Архиваторы ACE, RAR и Squeez имеют близкие результаты

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

с небольшим преимуществом по степени сжатия у RAR, и

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

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

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

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

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


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

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

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

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

tif, png, pcx, avi, zip, rar, arj.
Восстановление возможно с искажениями,

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

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

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

Слайд 9 Сжатие без потерь Алгоритм RLE
от англ. Run

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

Length Encoding


В файле записывается, сколько раз повторяются одинаковые байты.

Схематично:
"RRRRRGGGBBBBBBRRRBBRRRRRRR"

"5R3G6B3R2B7R".

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

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

кодируется восемью битами и, следовательно, занимает в памяти 1

байт.

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

ASCII-коды


Слайд 11 Сжатие без потерь Метод упаковки
TO BE OR NOT TO

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

BE?


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

2,4

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

Пример №2

Пример №1


Слайд 12 Практическая работа

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

Слайд 13 Практическая работа



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

Слайд 14 Практическая работа
“Частотный анализ букв русского языка”

Открыть с

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

помощью Microsoft Office Word документ Skazka.doc.
Подсчитать количество каждой

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

Слайд 15 Хаффмана
АЛГОРИТМ

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

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

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

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

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

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

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

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

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

символов в среднем будет 90 букв "о", 72 -

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

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

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

встречающийся символ кодируется двоичным кодом меньшей длины, редко встречающийся —

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

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


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

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

коды переменной длины.
Алгоритм Шеннона-Фано


Слайд 21 David Huffman (1925-1999)
В 18 лет Дэвид получил степень

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

бакалавра электротехники в уни-верситете штата Огайо. Основную концепцию кодирования

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

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

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


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

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

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

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

которого выходят две ветви.


Слайд 24 МОУ СОШ №33 с углубленным изучением математики г.Ярославля

Т

001

В

011100

Q

1101000101
корень
Дерево

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

Хаффмана


Слайд 25 00000
11011
110100011
корень
Дерево Хаффмана

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

Слайд 26

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

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

художник


Слайд 27 Азбука Морзе

Азбука Морзе

Слайд 28 01000111011011100

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


С


О

D



E

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

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

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

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


Слайд 30 Дерево азбуки Морзе

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

Слайд 31 Алгоритм Хаффмана двухпроходный: на первом

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

проходе строится частотный словарь и

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

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

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

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


Слайд 32 Алгоритм построения дерева Хаффмана

Среди символов выбрать два с наименьшими

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

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

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

Слайд 33


3


4
4




7


8





9


13



17





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

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

Слайд 34
30
17
13
8
4
9
4
7
3

301713849473

Слайд 35 Построение дерева Хаффмана

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

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

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

Н А _

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

Слайд 37 Кодирование текста
НА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА
10010011101100101100101100011111

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


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

Декодирование Восстановить исходный текст:1 0 0 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 0 0 1 0 0 1 0 1 1 1

1 1 1 0 0 0 1 1 0

Д

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


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

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

NOT TO BE?
Определите коэффициент сжатия для данной фразы, если

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

Слайд 42 1

1         01

0

1 0 1 0

1 0 1 0

1 0 1 0

2*4+1*4+3*3+5*2+4*2+1*4+1*4+2*3=53 бита=7 байт
Коэффициент сжатия: 19/7 ≈ 2,7

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


Слайд 43




1

1     01   01

0
1 0
1

0

1 0

1 0

1 0

4*2+2*3+2*3+5*2+3*3+1*4+1*5+1*5=53 бита

Другое решение


1 0


Слайд 44 Книги по теме

Книги по теме

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

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

музыкальный инструмент, как настроишь, так и живет.
Музыка показывает

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

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

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

алгоритм RLE для текстовых данных.
Исходные данные в виде

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

Ответ:
8L2E9S12o2N8 1o1n1e
2.32

Слайд 47 Кроссворд

Кроссворд

Слайд 48 Кроссворд

Кроссворд

  • Имя файла: szhatie-tekstovoy-informatsii.pptx
  • Количество просмотров: 132
  • Количество скачиваний: 0