Data Compression
Процесс Data Compression базируется на ликвидации избыточности, которая характерная для нетронутых (несжатых) данных. Самый простой пример избыточности информации — слишком много повторов одного и того же слова в тексте.
Чтобы убрать подобный вид избыточности, нужно заменить часто встречающееся слово ссылкой на другой фрагмент данных, который закодирован и имеет строго указанный объем.
Уменьшение «веса» данных можно получить за счет замены закодированными словами слишком часто повторяющихся типов данных и длинными кодами слишком редких данных (энтропийное кодирование). Если данные не имеют избыточности (зашифрованная информация, «белый шум», короткий сигнал и т. д.), то сжать их без потери информации не получится.
Data Compression без потерь — процесс, позволяющий при необходимости полностью восстановить исходную информацию, ведь объем хранящейся информации не уменьшается, невзирая на уменьшение места, которое она занимает.
Вышеописанная возможность может появиться в том случае, если вероятности распределяются на сообщениях неравномерно. Например, когда часть сообщений, которые возможны в теории, в ранней кодировке этих сообщений не встречались.
Алгоритмы Data Compression для неизвестных типов данных
Можно выделить 2 главных метода сжатия данных, которые имеют неизвестный формат:
- Каждый очередной сжимаемый символ или помещается в выходной буфер в своем первоначальном виде, или группа из нескольких сжимаемых символов заменяется ссылкой аналогичную группу из закодированных символов. Подобный метод чаще всего используется при создании самораспаковывающегося программного обеспечения.
- Для каждой последовательности символов, которые сжимаются, однократно или постоянно собирается статистика (частот встречаемости данных в коде). Опираясь на эту статистику, определяется вероятность значения следующего кодируемого символа (или их последовательности). Затем используется один из видов энтропийного кодирования, чтобы заменить часто встречающиеся типы данных короткими кодовыми словами, а редкие — более длинными.
Предыдущая статья