Упаковка данных
Все эти алгоритмы сводятся к поиску в потоке повторяющихся последовательностей и замене этих последовательностей на их номер в динамически формируемом словаре. Различие состоит в способах кодирования номера и формирования словаря. Большинство современных архиваторов, такие как PkZip, GNU Zip, RAR, основаны на вариациях и аналогах алгоритмов Лемпеля-Зиффа.
При упаковке нетекстовых данных могут применяться и другие способы удаления повторений. Например, при упаковке растровых изображений широко используется метод RLE (Run-Length Encoding), когда повторяющиеся пикселы заменяются счетчиком повторений и значением пиксела.
Все перечисленные алгоритмы способны только устранять автокорреляции, уже существующие во входном потоке. Понятно, что если автокорреляций не было, то упаковки не произойдет, поэтому гарантировать уровень упаковки эти алгоритмы не могут.
Для упаковки данных, полученных оцифровкой реальных сигналов (изображений и звука), точные алгоритмы не подходят совершенно. Реальный сигнал всегда сопровождается равномерно содержащим все частоты шумом. Этот шум искажает наличествующие в сигнале автокорреляции, сам же автокорреляций не имеет, поэтому обратимые алгоритмы с зашумленным сигналом справиться не могут.
Идея алгоритмов, пригодных для сжатия зашумленных сигналов, была позаимствована из принципа работы цифровых фильтров. Цифровой фильтр работает следующим образом: он осуществляет над сигналом преобразование Фурье и удаляет из полученного спектрального образа частоты, которые ниже порога подавления. Сигнал при этом искажается, но сильнее всего при этом страдает равномерно распределенный по спектру шум.
|
Алгоритмы JFIF (лежащий в основе распространенного формата хранения растровых изображений JPG), MPEG, MP3 начинаются с выполнения над входным потоком преобразования Фурье. Но, в отличие от цифрового фильтра, JFIF удаляет из полученного спектра не частоты, которые ниже заданного порога, а фиксированное количество частот, стараясь отобрать самые слабые. Количество частот, которые надо выкинуть, определяется параметром настройки упаковщика. Этот параметр так и называется - коэффициентом упаковки.
Профильтрованный сигнал заведомо содержит автокорреляции - даже если исходный, незашумленный, сигнал их и не содержал, такая фильтрация их создаст - и потому легко поддается упаковке. Точно восстановить по подвергнутому такому преобразованию потоку исходный сигнал невозможно, но такой цели и не ставится, поэтому все перечисленные методы относятся к разряду необратимых.
предыдущаяследующая