Сжатие это кодирование с уменьшением объема данных и возможностью однозначного декодирования. Обратный процесс декодирование называется разжатие. Другие названия: компрессия/декомпрессия, упаковка/распаковка.

Эффективность алгоритма сжатия зависит от степени сжатия (отношение длины несжатых данных к длине соответствующих им сжатых данных); скорости сжатия и разжатия; объема памяти, необходимого для работы алгоритмов и т.д

Сжатие без потерь (lossless compression) – собственно сжатие в смысле приведенного определения. Сжатие с потерями (lossy compression) – процесс, состоящих из двух этапов: 1. выделение сохраняемой части информации в зависимости от цели сжатия и особенностей приемника и источника; 2. собственно сжатие без потерь.

Кодирование длин повторов, Run Length Encoding (RLE, групповое кодирование) Один из наиболее старых методов сжатия, идея метода состоит в замене идущих подряд одинаковых символов (бит или байт) парой (количество, символ). В основном используется для кодирования растровых изображений. Характеристика: степень сжатия от 0,5 до 32. графические файлы jpeg, tiff

Групповой код А задает количество нулевых и единичных значений в порядке их следования. Групповой код В задает индексы границ единичных участков A: 8(0) 5(1) 12(0) 3(1) 7(0) 9(1) 4(0) B: (8,12) (25,27) (35,43)

Задание Построить коды А и В для изображения

Алгоритмы Зива-Лемпела (LZ-методы) сообщение кодируется не побуквенно (алфавитное кодирование), а по словам. Характеристики: степень сжатия в зависимости от данных, обычно 2-3; алгоритмы универсальны, но лучше всего подходят для сжатия текстов, рисованных картинок или других однородных данных архиваторы (форматы rar, zip, arj, cab, ace); графические файлы gif, tiff

Словарь: {Λ, 0, 1, 00, 01, 011, 001, 010, 0011, 0101, 10} (0, 0), (0, 1), (1, 0), (1, 1), (4, 1), (3, 1), (4, 0), (6, 1), (7, 1), (2, 0), (0, 0)

Задание Закодируйте текст 1) ). aba adb abc ecd ebc ea 3)

Задание Раскодируйте текст 1) (0,0), (0,1), (2,0), (3,1), (2,1), (1,1), (4,1), (7,1), (6,0), (1,0), (9,1), (2,0) 2) (0,0), (0,1), (2,1), (2,0), (1,0), (3,0), (6,0), (7,1), (1,1), (9,1), (5,0),(0,1) 3) (0,γ), (0, α), (0,β), (1,γ), (2,β), (2,δ), (0,δ), (0,γ)

Арифметическое сжатие (ARIC, Arithmetic Coding) Характеристики: один из самых эффективных методов; степень сжатия от 1 до 8, т.е. не увеличивает размер данных в худшем случае; Не является алфавитным кодированием. Весь кодируемый текст представляется в виде дроби из [0, 1).

Пусть x = математика у = мате

у* = 0,339

Задание Выполнить декомпрессию кода y = 0.75, используя таблицу диапазонов, если известно, что длина сообщения 10 символов.

Задание Закодировать первые четыре символа сообщения х = ков.корова: 1) составить таблицу частот и диапазонов всех символов сообщения, 2) найти рабочий интервал для ков. и выбрать число y – код слова, 3) найти рабочий интервал и код для слова кава (использовать таблицу диапазонов из предыдущего задания), 4) рассмотреть процесс декомпрессии (восстановления слова ков. по числу y).