Информатика. Сжатие данных

СЖАТИЕ
Сжатие данных
Кодирование по алгоритму Хаффмана
Межсимвольная зависимость
Избыточность в английском языке
Кодирование Лемпеля – Зива
Другие формы сжатия информации

Сжатие данных (data compression) – процедура уменьшения их объёма с сохранением (полным или частичным) их целостности.
Применение: рациональное использование устройств хранения и передачи данных.
Синонимы: упаковка данных, компрессия, сжимающее кодирование, кодирование источника.
Обратная процедура называется восстановлением данных (распаковкой, декомпрессией, декодированием).
СЖАТИЕ ДАННЫХ

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

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

Все методы сжатия данных делятся на два основных класса:
Сжатие без потерь (полное восстановление исходных данных) используется для передачи и хранения текстовых файлов.
Сжатие с потерями (восстановление данных с искажениями) используется для сокращения объёма музыки, графики, видео, цифровых фотографий и т.п.

два способа сжатия текста (сжатие без потерь):
Кодирование Хаффмана (энтропийное кодирование)
Кодирование Лемпеля-Зива (LZ77)

Алгоритм Хаффмана – это один из первых методов, в основе которого лежит энтропийное кодирование (кодирование источника).
Хаффман решил задачу отыскания моментальных кодов наименьшей длины.
КОДИРОВАНИЕ ПО АЛГОРИТМУ ХАФФМАНА

АЛГОРИТМ ХАФФМАНА
Алгоритм состоит из двух этапов:
1. Сначала символы источника сокращаются путем последовательного образования сложных символов до тех пор, пока не останется только два символа.
2. Затем кодирование затем осуществляется в обратном порядке путем разделения сложных символов и добавления знаков кода по два одновременно. Когда все сложные символы будут разделены, получаются кодовые слова для символов источника.

Рассмотрим источник из пяти символов с заданными вероятностями.
ПРИМЕР 1

1 этап – Сокращение. На каждом этапе два символа самой низкой вероятности объединяются, образуя один сложный символ. Новый список записывается в порядке убывания вероятностей. Это продолжается до тех пор, пока не останется два символа.

2 этап – Разделение. Два символа в последнем списке кодируются с помощью 0 и 1. Затем они переносятся обратно в предыдущий список. Сложный символ при переносе должен быть разделен на те два символа, из которых он получен, и к существующему кодовому слову добавляется 0 и 1 соответственно для разделения символов.

Итак, мы получили код:
Символ источника Вероятность Код
s1 0.3 00
s2 0.2 10
s3 0.2 11
s4 0.2 010
s5 0.1 011
Средняя длина кода:
Энтропия источника:
(2×0,3) + (2×0,2) + (2×0,2) + (3×0,2) + (3×0,1) = 2,3
– [0,3×log 0,3 + (3 × 0,2)×log 0,2 + 0,1×log 0,1] = 2,246

Кодовое дерево Хаффмана для примера 1.

Неоднозначность кодов Хаффмана.
Попробуйте построить два различных кода Хаффмана для пятисимвольного источника.
ПРИМЕР 2

Результат: два кода построены по методике Хаффмана и имеют одинаковую среднюю длину.

ПРИМЕР 3

Межсимвольная зависимость. Следующие друг за другом символы от источника не всегда являются независимыми. Наоборот, текущие вероятности символов часто зависят от того, какие символы встречаются перед ними.
Межсимвольная зависимость сокращает энтропию, и следовательно, могут быть построены коды с более короткими средними значениями длины слова.
Эта идея является основой многих современных методов сжатия.
МЕЖСИМВОЛЬНАЯ ЗАВИСИМОСТЬ

ВЕРОЯТНОСТИ В АНГЛИЙСКОМ ЯЗЫКЕ

Вероятности встречаемости букв английского алфавита.

Таким образом, код Хаффмана для алфавита будет иметь среднюю длину ближе к четырем, чем к пяти.
Кодирование по алгоритму Хаффмана действительно используется в качестве метода компрессии английского текста.
При этом документы требуют приблизительно на 20 % меньше памяти, чем в случае использования стандартного кода ASCII.

ПРИМЕНЕНИЕ ЗАКОНОВ ЦИПФА (ЗИПФА)

Для расчета Шеннон воспользовался законом Ципфа. (Джордж Ципф в 1949 г. эмпирически вывел соотношение частотностей слов).
Ципф заметил, что длинные слова встречаются в текстах любого языка реже, чем короткие.

ИЗБЫТОЧНОСТЬ АНГЛИЙСКОГО ЯЗЫКА

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

КОДИРОВАНИЕ ЛЕМПЕЛЯ – ЗИВА
Новаторский и талантливый метод компрессии предложили Зив и Лемпель в 1977 г.
Метод LZ77 основывается на том, что последовательности букв в английском тексте содержат повторяющиеся фрагменты (образцы).
Сначала при передаче текста образцы накапливаются, а затем, продолжая передавать текст, отправитель уже смотрит на имеющийся словарь образцов и передает вместо самой последовательности ссылку на имеющийся образец.

В методе Лемпеля – Зива и отправитель, и получатель ведут запись того, что уже было отправлено.
Затем при подготовке к отправке дополнительного текста отправитель снова смотрит на ранее переданный текст, для того чтобы найти дублирование максимальной длины того, что требуется отправить дальше.
После этого вместо самой последовательности отправляется ссылка на прошлую дублирующую последовательность.
Например, если следующей частью текста является слово, которое передавалось раньше, отправитель просто отправляет ссылку на позицию этого слова в записи прошлых букв.

ПРИМЕР. LZ77
Исходный текст:
THIS-THESIS-IS-THE-THESIS.
Передаваемые сообщения (код LZ77):
(0, 0, T) T
(0, 0, H) TH
(0, 0, I) THI
(0, 0, S) THIS
(0, 0, -) THIS-
(5, 2, E) THIS-THE
(5, 1, I) THIS-THESI
(7, 2, I) THIS-THESIS-I
(10, 5, -) THIS-THESIS-IS-THE-
(14, 6, .) THIS-THESIS-IS-THE-THESIS.

Задания:
1) Закодируйте сообщение:
ROCCOBAROCCO.
Код LZ77:
(0,0,’R’) (0,0,’O’) (0,0,’C’) (1,1,’O’) (0,0,’B’) (0,0,’A’) (7,5,’.’)
2) Декодируйте сообщение
(0, 0, ‘a’) (0, 0, ‘b’) (0, 0, ‘r’) (3, 1, ‘c’) (2, 1, ‘d’) (7, 4,’’ )
Сообщение:
abracadabra

СОВРЕМЕННЫЕ АРХИВАТОРЫ

ДРУГИЕ ФОРМЫ СЖАТИЯ ИНФОРМАЦИИ
Кроме текста, сжатие также применяется к графике, изображениям, речи, видео…(эти данные не обладают избыточностью)
Здесь данные выражаются в виде численных значений. Это могут быть: интенсивность для речевых или музыкальных образов; интенсивность цвета, яркости (фотография) и т.п.

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

МЕТОДЫ ПРЕДСКАЗАНИЯ

JPEG
Стандарты сжатия графической информации были установлены комитетом, который называется Совместной группой экспертов по фотографии (Joint Photographic Experts Group) (JPEG).
Данные стандарты используются в популярных пакетах для сжатия изображений JPEG.
Комитет разработал два основных метода: метод без потерь (рассмотренный выше метод предсказания) и метод с потерями (кратко рассматривается далее, имеет более значительное сжатие ).

АППРОКСИМАЦИЯ

Популярная версия JPEG аппроксимирует матрицу яркости посредством серии двухмерных функций косинуса и записывает коэффициенты этой серии.
Метод разработан таким образом, что даже при коэффициенте сжатия 10:1 всего лишь незначительное ухудшение изображения будет заметно глазу человека.

МРЗ
MPEG (филиал комитета JPEG) – группа экспертов по киноизображениям разработала стандарты сжатия для киноизображений и высококачественных аудио сигналов.
Стандарт MPEG1 способен компрессировать как видеосигналы, так и аудиосигналы.
Популярный стандарт компрессии музыки МРЗ фактически представляет собой аудиочасть стандарта MPEG1.

Упражнения
1. (Шестисимвольный источник.) Источник имеет шесть символов с нижеуказанными вероятностями.
s1 0,3 s4 0,1
s2 0,2 s5 0,1
s3 0,2 s6 0,1
(а) Найти код Хаффмана для этого источника.
(b) Какова средняя длина кода Хаффмана?
(c) Какова энтропия источника?

2. (Пятисимвольный источник.) Найти три различных кода Хаффмана для источника.
s1 0,4 s4 0,1
s2 0,2 s5 0,1
s3 0,2

3. (Преимущество алгоритма Хаффмана.) Преимущество компрессии при кодировании по алгоритму Хаффмана S2 вместо S является наиболее значительным, когда имеют место большие отличия в вероятностях символа источника. Для каждого из двух случаев, указанных ниже, найти энтропию и среднюю длину кода Хаффмана для S и S2.

4. (Вычитание Хаффмена.) Рассмотрите источник со связанными с ним символами и вероятностями
Один код Хаффмена для данного источника имеет значения длины слова, равные 2, 3, 3, 3, 3, 3, 3. Не прибегая к использованию процедуры Хаффмена, найти мгновенный двоичный код минимальной средней длины для этого источника, имеющего эти значе­ния длины слова.

5. (Пример LZ77.)
Декодируйте сообщение
(0, 0, ‘a’) (0, 0, ‘b’) (0, 0, ‘r’) (3, 1, ‘c’) (2, 1, ‘d’)
(7, 4,’’ )