Упаковка данных

Часто данные имеют значительный объем, поэтому их хранение и передача требует значительных ресурсов. Одним из способов решения этой проблемы является упаковка данных.

В основе всех способов упаковки лежит теория информации: данные, в которых имеется статистическая автокорреляция, называется избыточной или имеющей низкую энтропию. В этом случае объем данных можно уменьшить без потери смысла, а зачастую и с возможностью полного восстановления исходных данных. Методы повышения энтропии, которые не позволяют по упакованному потоку восстановить исходный, называются необратимыми, приблизительными или сжимающими с потерями (losing compression). Соответственно методы, которые позволяют это сделать, называются обратимыми, точными или сжимающими без потерь (losless compression).

Одним из первых методов упаковки является азбука Морзе (1844г.). В ней наиболее использующиеся буквы кодировались наиболее короткими посылками.

В конце 1940-х годов основателем современной информации Шенноном был разработан универсальный алгоритм построения оптимальных кодов. Более известный аналог этого алгоритма был предложен позднее Хаффманом. Принцип построения этих кодов в целом соответствует логике Морзе – кодировать наиболее повторяющиеся последовательности наиболее короткими последовательностями битов.

Коды Хаффмана и Шеннона-Фано устраняют автокорреляции, соответствующие неравномерности встречаемых символов, но сохраняют без изменений часто встречающиеся последовательности символов, а они ответственны за значительную часть избыточности текстов на естественных и синтетических языках. Для упаковки данных такого рода в конце 1970-х годов Лемпелем и Зиффом было предложено семейство алгоритмов, наиболее известные из которых – LZ77 и LZW. Все эти алгоритмы сводятся к поиску в потоке повторяющихся последовательностей и замене этих последовательностей на их номер в динамически формируемом словаре. Различие этих алгоритмов состоит в способах кодирования номера и формировании словаря. Номер последовательности в словаре должен содержать больше битов, чем символы исходного потока хотя бы из-за того, чтобы его можно было отличить от символа, поэтому алгоритмы Лемпеля-Зиффа предполагают дальнейшее перекодирование преобразованного потока кодом Хаффмана. Большинство современных архиваторов, таких, как PkZip, GNU Zip, RAR, основаны на вариациях и аналогах алгоритмов Лемпеля-Зиффа.

При упаковке нетекстовых данных могут применяться и другие способы удаления повторений. Например, при упаковке растровых изображения широко используется метод RLE (Run-Length Encoding), когда повторяющиеся пикселы заменяются счетчиком повторений и значением пиксела.

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

Все перечисленные алгоритмы способны только устранить автокорреляции, уже существующие во входном потоке. Если их нет, то упаковки тоже нет, поэтому эти алгоритмы не могут гарантировать уровень упаковки.

Для упаковки данных, полученных путем оцифровки реальных сигналов, например, видео и звука, эти алгоритмы не подходят совершенно. Это связано с тем, что реальный сигнал всегда сопровождается тепловым (белым) шумом. Этот не имеющий автокорреляций шум искажает присутствующие во входном потоке автокорреляции, поэтому точные алгоритмы с зашумленным сигналом справиться не могут. Поэтому упаковка аудиозаписи или цифровой фотографии алгоритмами класса Zip или RAR не даст большого результата (а на текстовых данных эти алгоритмы часто дают выигрыш в 10 и более раз). Идея алгоритмов, пригодных для сжатия зашумленных сигналов, пришла из области работы цифровых фильтров-шумоподавителей. Эти фильтры осуществляют над сигналом преобразование Фурье и удаляют из полученного спектрального образа самые слабые частоты, которые ниже порога подавления. Сигнал при этом искажается и наиболее страдают составляющие равномерно распределенного по спектру шума, что и требуется. Алгоритмы JFIF (он находится в основе формата JPEG), MPEG, MP3 и другие алгоритмы тоже начинают с выполнения над входным потоком преобразования Фурье. Далее алгоритм JFIF удаляет из полученного спектра фиксированное количество частот, стремясь отобрать самые слабые. Количество частот, которые надо выкинуть, определяется параметром настройки упаковщика. У JFIF этот параметр называется коэффициентом упаковки, у MP3 – битрейтом. Профильтрованный сигнал заведомо содержит автокорреляции и поэтому легко подвергается упаковке. Благодаря этому все эти алгоритмы обеспечивают гарантированный уровень упаковки. Все эти алгоритмы относятся к классу необратимых, так как восстановить по нему исходный сигнал невозможно. При разумном выборе уровня упаковки восстановленное изображение или звук практически неотличимо от оригинала, но если это восстановленное изображение или звук еще раз пропустить через упаковку, то будет заметно искажение исходного потока данных. Поэтому иногда необратимые алгоритмы упаковки предлагается использовать для защиты авторских прав: потребитель получает упакованный файл, а исходный остается у автора.

Экспериментальные варианты необратимых алгоритмов вместо разложения по взвешенной сумме синусов и косинусов используют разложение по специальным функциям, так называемым вэйвлетам (wavelet). Утверждается, что вэйвлетная фильтрация при том же уровне сжатия дает меньший уровень субъективно обнаружимых искажений. При этом вэйвлетные алгоритмы сильно уступают обычным вариациям JFIF по производительности, поэтому пока не нашли широкого применения.