Алгоритмы сжатия данных

 

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

Качество сжатия характеризуется коэффициентом сжатия, равным отношению объема сжатых данных к объему исходных данных.

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

Для многих разновидностей данных – текстов, исполняемых файлов и т.д. – допустимо применение только алгоритмов сжатия без потерь.

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

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