Обработка информации
<<  Технологии обработки информации Технология обработки текстовой информации  >>
Технологии обработки информации
Технологии обработки информации
Содержание
Содержание
Сжатие данных
Сжатие данных
Избыточность данных
Избыточность данных
Избыточности и кодирование
Избыточности и кодирование
Идея сжатия
Идея сжатия
Теорема Шеннона о кодировании источника
Теорема Шеннона о кодировании источника
Классификации методов сжатия (1)
Классификации методов сжатия (1)
Классификации методов сжатия (2)
Классификации методов сжатия (2)
Классификации методов сжатия (3)
Классификации методов сжатия (3)
Классификации методов сжатия (4)
Классификации методов сжатия (4)
Перечень алгоритмов сжатия
Перечень алгоритмов сжатия
Перечень алгоритмов сжатия
Перечень алгоритмов сжатия
Перечень алгоритмов сжатия
Перечень алгоритмов сжатия
Группы методов сжатия без потерь
Группы методов сжатия без потерь
Кодирование длин серий (Run-length encoding, RLE)
Кодирование длин серий (Run-length encoding, RLE)
Ограничения алгоритма RLE
Ограничения алгоритма RLE
Алгоритмы группы KWE
Алгоритмы группы KWE
Алгоритм LZW (1)
Алгоритм LZW (1)
Алгоритм LZW (2)
Алгоритм LZW (2)
Вероятностные методы
Вероятностные методы
Алгоритм Хаффмана (1)
Алгоритм Хаффмана (1)
Алгоритм Хаффмана (2)
Алгоритм Хаффмана (2)
Алгоритм PPM
Алгоритм PPM
Алгоритм BWT
Алгоритм BWT
Итоги контрольной
Итоги контрольной
Спасибо за внимание
Спасибо за внимание

Презентация: «Технологии обработки информации». Автор: Антон Кудинов. Файл: «Технологии обработки информации.ppsx». Размер zip-архива: 536 КБ.

Технологии обработки информации

содержание презентации «Технологии обработки информации.ppsx»
СлайдТекст
1 Технологии обработки информации

Технологии обработки информации

Лекция 3. Задачи анализа. Сжатие

Антон Викторович Кудинов, доцент кафедры ВТ

2 Содержание

Содержание

Общие понятия Избыточность данных. Теорема Шеннона Классификации методов сжатия Перечень алгоритмов сжатия Описание отдельных методов и алгоритмов RLE LZW Хаффмана PPM BWT

2

3 Сжатие данных

Сжатие данных

(англ. data compression) — алгоритмическое преобразование данных, производимое с целью уменьшения занимаемого ими объёма. Применяется для более рационального использования устройств хранения и передачи данных. Синонимы — упаковка данных, компрессия, сжимающее кодирование, кодирование источника. Обратная процедура называется восстановлением данных (распаковкой, декомпрессией).

Википедия

3

4 Избыточность данных

Избыточность данных

4

5 Избыточности и кодирование

Избыточности и кодирование

Разные способы кодирования дают разную избыточность Пример: кодирование текста средствами русского языка избыточно на 20-25% по отношению к английскому

Всегда ли избыточность – это плохо?

5

6 Идея сжатия

Идея сжатия

представлять часто используемые элементы длинными кодами редко используемые – короткими кодами Тогда: для хранения блока данных требуется меньший объем, чем для кодирования с одинаковыми длинами кодов Пример: азбука Морзе

6

7 Теорема Шеннона о кодировании источника

Теорема Шеннона о кодировании источника

элемент si, вероятность появления которого равняется p(si), выгоднее всего представлять - log2p(si) битами Если распределение вероятностей неизменно и вероятности независимы, то средняя длина кодов: - энтропия Шеннона в подавляющем большинстве случаев истинная структура источника нам не известна, поэтому необходимо строить модель источника, которая позволила бы оценить вероятность p(si) Вывод: чтобы эффективно сжимать нужно знать природу данных

7

8 Классификации методов сжатия (1)

Классификации методов сжатия (1)

Необратимое (с регулируемыми потерями) — методология, при которой для обеспечения максимальной степени сжатия исходного массива часть содержащихся в нем данных отбрасывается Обратимое (без потерь) — методология сжатия, при которой ранее закодированная порция данных восстанавливается после их распаковки полностью без внесения изменений

8

9 Классификации методов сжатия (2)

Классификации методов сжатия (2)

Симметричное (symmetric compression) —время, затрачиваемое на сжатие и распаковку данных, соизмеримо Асимметричное (asymmetric compression) — методология, в соответствии с которой при выполнении работ «в одном направлении» времени затрачивается больше, чем при выполнении работ в другом направлении (сжатие изображений vs. резервное копирование)

9

10 Классификации методов сжатия (3)

Классификации методов сжатия (3)

Адаптивное кодирование (adaptive encoding) — методология кодирования при сжатии данных, которая заранее не настраивается на определенный вид данных (двухпроходные алгоритмы) Неадаптивное кодирование (nonadaptive encoding) — методология кодирования, ориентированная на сжатие определенного типа или типов данных (словарные алгоритмы) Полуадаптивное кодирование (half-adaptive coding) — методология кодирования при сжатии данных, которая использует элементы адаптивного и неадаптивного кодирования

10

11 Классификации методов сжатия (4)

Классификации методов сжатия (4)

Адаптивное кодирование (adaptive encoding) — методология кодирования при сжатии данных, которая заранее не настраивается на определенный вид данных (двухпроходные алгоритмы) Неадаптивное кодирование (nonadaptive encoding) — методология кодирования, ориентированная на сжатие определенного типа или типов данных (словарные алгоритмы) Полуадаптивное кодирование (half-adaptive coding) — методология кодирования при сжатии данных, которая использует элементы адаптивного и неадаптивного кодирования

11

12 Перечень алгоритмов сжатия

Перечень алгоритмов сжатия

Без потерь (1)

Преобразование Барроуза-Уилера (BWT) Преобразование Шиндлера (ST) Алгоритм DEFLATE Дельта-кодирование Инкрементное кодирование Семейство алгоритмов LZW Алгоритм сжатия PPM Кодирование длин серий (RLE) Алгоритм SEQUITUR EZW-кодирование

Википедия

12

13 Перечень алгоритмов сжатия

Перечень алгоритмов сжатия

Без потерь (2)

Энтропийное кодирование: Алгоритм Шеннона-Фано Алгоритм Хаффмана Адаптивное кодирование Хаффмана Усечённое двоичное кодирование Арифметическое кодирование Адаптивное арифметическое кодирование Кодирование расстояний Энтропийное кодирование с известными характеристиками: Унарное кодирование дельта|гамма|омега-кодирование Элиаса Кодирование Фибоначчи Кодирование Голомба Кодирование Райса

Википедия

13

14 Перечень алгоритмов сжатия

Перечень алгоритмов сжатия

С потерями

Дискретно-косинусное преобразование Линейное предсказывающее кодирование А-закон Мю-закон Фрактальное сжатие Трансформирующее кодирование Векторное квантование Вейвлетное сжатие

Википедия

14

15 Группы методов сжатия без потерь

Группы методов сжатия без потерь

Алгоритм RLE (run length encoding) алгоритмы группы KWE (keyword encoding) вероятностные алгоритмы

15

16 Кодирование длин серий (Run-length encoding, RLE)

Кодирование длин серий (Run-length encoding, RLE)

простой алгоритм сжатия данных, который оперирует сериями данных, то есть последовательностями, в которых один и тот же символ встречается несколько раз подряд При кодировании строка одинаковых символов, составляющих серию, заменяется строкой, которая содержит сам повторяющийся символ и количество его повторов WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW – 67 символов 12W1B12W3B24W1B14W – 18 символов

16

17 Ограничения алгоритма RLE

Ограничения алгоритма RLE

1. Если строка состоит из большого количества неповторяющихся символов, её объем может вырасти Решение: использовать отрицательные числа для записи количества неодинаковых символов ABCABCABCABCDDEFFFFFFFF -12ABCABCABCABC2D1E8F 2. Пределы длин численных данных Решение: разделение длинных последовательностей на группы

17

18 Алгоритмы группы KWE

Алгоритмы группы KWE

Принцип кодирования лексических единиц (повторяющихся последовательностей символов) группами байт фиксированной длины Словарные алгоритмы — разбиение данных на слова и замена их на индексы в словаре Наиболее известные – алгоритмы семейства LZ* (LZ77/78, LZW, LZO, DEFLATE, LZMA, LZX, ROLZ)

18

19 Алгоритм LZW (1)

Алгоритм LZW (1)

Авторы: Абрахам Лемпель (англ. Abraham Lempel), Якоб Зив (англ. Jacob Ziv) и Терри Велч (англ. Terry Welch) был опубликован Велчем в 1984 году, в качестве улучшенной реализации алгоритма LZ78, опубликованного Лемпелем и Зивом в 1978 году патент принадлежал Зиву Основные идеи: Принцип скользящего окна Механизм кодирования совпадений

19

20 Алгоритм LZW (2)

Алгоритм LZW (2)

Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы W первым символом сообщения Найти в словаре строку W наибольшей длины, которая совпадает с последними принятыми символами Считать очередной символ K из кодируемого сообщения Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для W, иначе Если фраза WK уже есть в словаре, присвоить входной фразе W значение WK и перейти к Шагу 3, иначе выдать код W, добавить WK в словарь, присвоить входной фразе W значение K и перейти к Шагу 3 Конец

20

21 Вероятностные методы

Вероятностные методы

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

21

22 Алгоритм Хаффмана (1)

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

адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы Идея: зная вероятности символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов Символам с большей вероятностью ставятся в соответствие более короткие коды Коды Хаффмана обладают свойством префиксности (т.е. ни одно кодовое слово не является префиксом другого), что позволяет однозначно их декодировать

22

23 Алгоритм Хаффмана (2)

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

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

23

24 Алгоритм PPM

Алгоритм PPM

PPM (prediction by partial matching) - это метод контекстно-ограниченного моделирования, позволяющий оценить вероятность символа в зависимости от предыдущих символов

24

25 Алгоритм BWT

Алгоритм BWT

Преобразование Барроуза -Уилера (Burrows-Wheeler transform, BWT, также называется блочно-сортирующим сжатием) сравнительно новая и революционная техника для сжатия информации (в особенности-текстов), основанная на преобразовании, открытом в 1983 г. и описанная в 1994 г. Меняет порядок символов во входной строке таким образом, что повторяющиеся подстроки образуют на выходе идущие подряд последовательности одинаковых символов Используется последовательность BWT ? MTF/RLE ? Хаффман

25

26 Итоги контрольной

Итоги контрольной

Пак

Иреева

Пирогов

Хоменко

Павлюченко

Фам Нгок Тху

Фандеев

Асмоловский

Кушнаревич

Патуремский

Кудряшов

Кузнецов

Щебетун

Пучко

Брезгулевский

Паршина

Красноперова

Щукова

Евсюткин

26

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

-

-

-

-

-

-

-

7

-

-

-

-

-

5

-

-

2

-

-

-

-

-

-

6

-

-

-

-

4

-

-

-

-

-

-

-

-

-

-

-

11

-

-

2

-

-

-

3

-

-

2

-

-

-

-

4

-

-

-

-

-

5

-

-

-

-

-

5

-

-

-

-

4

-

-

-

-

4

-

-

-

3

-

-

-

3

-

-

-

3

-

-

2

-

-

2

3

1

0

2

12

1

5

1

1

3

10

8

5

6

7

6

1

0

4

1

77

27 Спасибо за внимание

Спасибо за внимание

KudinovAV@tpu.ru

27

«Технологии обработки информации»
http://900igr.net/prezentacija/informatika/tekhnologii-obrabotki-informatsii-149351.html
cсылка на страницу
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Обработка информации > Технологии обработки информации