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

F(X)
Входной
поток данных
Выходной
поток данных
X
Y
Алгоритм сжатия
Коэффициент сжатия
для разных данных могут быть:

F(X)
X
Алгоритм сжатия
Y
G(Y)
Алгоритм
восстановления
Z
X = Z – сжатие без потерь
X ≠ Z – сжатие с потерями

Пример сжатия с потерями (JPEG)
Quality

Статистические алгоритмы сжатия данных
Для сжатия данных используется информация об энтропии входного потока.
Используется частота/вероятность появления символа в потоке.
Примеры алгоритмов:
Алгоритм Шеннона-Фано.
Алгоритм Хаффмана.
Арифметическое кодирование.

Алгоритм Хаффмана
Определить частотную таблицу символов входного потока данных.
Упорядочить таблицу по убыванию частоты символов.
Построить дерево Хаффмана по частотной таблице.
Определить коды символов по дереву Хаффмана.
Закодировать сообщение – сформировать выходной поток.

Задача
Дистанционно управляемый робот должен пройти лабиринт (клеточный). Оптимальный алгоритм прохождения лабиринта известен, но необходимо его (алгоритм) закодировать.
Робот способен выполнять следующие команды:
Идти вперед (1 кл.)
Повернуть вправо на 90 градусов
Повернуть влево на 90 градусов
Повернуться на 180 градусов
Перепрыгнуть обрыв
В результате исследования была найдена оптимальная последовательность:
1111211131111211131113111311121111113112121311111111111112111311511211111311112113111112111131111111111121113111113115111311111121111311311111131111211112111121111211121121131111111111151113111211131131131213131113111211311

Решение
Количество шагов алгоритма (символов) - 223
Частотная таблица

Пример 2
Количество шагов алгоритма (символов) - 223
Частотная таблица

Арифметическое кодирование
1. Определить вероятностную таблицу символов входного потока данных.
2. Разделить отрезок [0;1) на отрезки в соответствии с вероятностями символов.
3. Поочередно кодировать символы входного потока на получившихся отрезках.

Пример арифметического кодирования
Данные возьмем из предыдущей задачи (алгоритм Хаффмана).
Вероятностная таблица

Пример арифметического кодирования

RLE
Run-length encoding – кодирование длин серий
Пример:
1111211131111211131113111311121111113112121311111111111112111311511211111311112113111112111131111111111121113111113115111311111121111311311111131111211112111121111211121121131111111111151113111211131131131213131113111211311
1111211131111211131113111311121111113112121311111111111112111311511211111311112113111112111131111111111121113111113115111311111121111311311111131111211112111121111211121121131111111111151113111211131131131213131113111211311