Сжатие файлов

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

Сжатие данных — это процесс устранения избыточных данных. Давайте рассмот­рим воображаемый пример. Допустим, у нас есть файл, хранящий изображение абсолютно черного квадрата размером 100 на 100 пикселей. В терминах хранения данных (если предположить, что каждый пиксель представлен 24 битами, или 3 байтами) изображение занимает 30 000 байт: 100 х 100 х 3 = 30 000.

Изображение, состоящее из пикселей одного цвета, содержит массу избыточных данных. Будь мы умнее, мы могли бы закодировать данные в виде простого описания того факта, что изображение представлено блоком из 30 000 пикселей черного цвета. То есть вместо хранения блока данных с 30 000 нулей (черный цвет в файлах изображений обычно представлен нулевым значением) мы могли бы сжать данные до числа 30 000 с последующим нулем, описывающим цвет. Такая схема сжатия, она называется кодированием длин серий (run-length encoding), является одной из простейших технологий сжатия. Современные технологии не в пример сложнее и эффективнее, но главная цель осталась прежней — избавиться от избыточных данных.

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