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

Алгоритмы сжатия данных появились с тех пор, как появились сами массивы данных, которые следовало как-то хранить и передавать. Таким образом, проблема “данные/степень их сжатия” актуальна уже достаточно давно. В наши дни она стоит особенно остро, поскольку с ростом технологий растут и массивы данных. Несмотря на расширение каналов передачи данных, скорость этой самой передачи является узким местом.

Итак, попробуем разобраться в существующих алгоритмах сжатия данных. В общем виде их сегодня можно разделить на две большие подгруппы: сжатие данных с потерями и без потерь.

Клод Шеннон в 1950 г. смоделировал основы теории информации в своем труде “Математическая теория связи”, в том числе идею о том, что данные могут быть минимизированы, так как несут избыточную информацию (энтропия данных). Энтропия исходных данных выступает количественной мерой разнообразия выдаваемых источником сообщений и является его основной характеристикой. Чем выше разнообразие алфавита сообщений и чем равномернее он распространен по сообщению, тем больше энтропия и тем сложнее эту последовательность сообщений сжать. Обычно в физическом представлении данные несут некоторую избыточность. И процесс устранения избыточности источника сообщений сводится к двум операциям – декорреляции (укрупнению алфавита) и кодированию (например, оптимальным неравномерным кодом).

Давайте возьмем простой пример. Допустим, необходимо составить таблицу, в которую будут заноситься результаты эксперимента с подбрасыванием монеты. Даже это простое действие мы можем сделать несколькими способами, например, так (1 -орел, 0 – решка):

.

Это далеко не все способы, но налицо явная избыточность информации в первых двух таблицах и устранение избыточности данных в последней таблице. Итак, сжатие – это избавление от избыточных данных, осуществляемое по алгоритму эффективного кодирования информации, при котором она занимает меньший объем памяти, нежели ранее. Это сжатие без потери кода. А что же такое потеря кода в алгоритмах сжатия? Это безвозвратное устранение некоторой избыточности кода без ощутимой потери качества информации. Это легко понять на следующем примере: возьмем обычный текстовый файл и удалим из абзацев все символы переноса строки, заменим в файле все цепочки пробелов в начале абзацев на символ табуляции, а также удалим все незначащие пустые строки и сохраним наш файл. Что мы получили? Мы получили точно такой же читаемый файл с неизмененной информацией, но меньшего размера. Иными словами, качество информации не потеряно. Но вместе с тем мы уже не сможем восстановить устраненную избыточную информацию. Именно на этом принципе и работают алгоритмы сжатия мультимедийных данных. Например, уменьшение размеров изображения – тоже своего рода сжатие с потерями.