Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Сжатие

Сжатие информации бывает особенно важным при передаче изображений по линиям связи, потому что получатель, обычно, ждет на приемном конце и желает поскорее увидеть результат. Документы, пересылаемые с помощью факс-машин, представляются в виде последовательности битов, поэтому сжатие было просто необходимо для популяризации этого метода сообщений. Несколько методов было развито и предложено для стандарта факсимильной1 связи организации ITU-T. [Anderson et al. 87], [Hunter, Robinson 80], [Marking 90] и [McConnell 92] - вот несколько из множества ссылок с описанием этого ...

Классический вариант алгоритма

Сжатие по методу Хаффмана постепенно вытесняется арифметическим сжатием. Свою роль в этом сыграло то, что закончились сроки действия па­тентов, ограничивающих использование арифметического сжатия. Кроме того, алгоритм Хаффмана приближает относительные частоты появления символов в потоке частотами, кратными степени двойки (например, для символов а, Ъ, с, d с вероятностями 1/2, 1/4, 1/8, 1/8 будут использованы ко­ды О, 10, 110, 111), а арифметическое сжатие дает лучшую степень прибли­жения частоты. По теореме Шеннона наилучшее сжатие в ...

В основе всех методов сжатия лежит простая идея: если представлять часто используемые элементы короткими кодами, а редко используемые -длинными кодами, то для хранения блока данных требуется меньший объем памяти, чем если бы все элементы представлялись кодами одинаковой дли­ны. Данный факт известен давно: вспомним, например, азбуку Морзе, в ко­торой часто используемым символам поставлены в соответствие короткие последовательности точек и тире, а редко встречающимся - длинные.

Точная связь между вероятностями и кодами установлена в теореме Шеннона о кодировании источника, которая ...

Если сжимаемые символы являются кодами ASCII, то им можно просто присвоить свои значения для представления в несжатом виде. В общем случае, когда алфавит имеет произвольный размер, несжатые коды двух разных размеров можно также легко построить. Рассмотрим, например, алфавит размера п — 24. Первым 16 символам можно присвоить числа от 0 до 15 в их двоичном разложении. Эти символы потребуют только 4 бита, но мы закодируем их пятью битами. Символам с номерами от 17 до 24 присвоим числа 17 - 16 - 1 = 0, 18 - 16 - 1 = 1, и до 24 - 16 - 1 = 7 в двоичном представлении из 4 бит. Итак, мы ...

Решение задачи сравнения алгоритмов по достигаемой ими степени сжа­тия требует введения некоторого критерия, так как нельзя сравнивать про­изводительность реализаций на каком-то абстрактном файле. Следует осто­рожно относиться к теоретическим оценкам, так как они вычисляются с точностью до констант. Величины этих констант на практике могут коле­баться в очень больших пределах, особенно при сжатии небольших файлов.

В 1989 г. группа исследователей предложила оценивать коэффициент сжатия с помощью набора файлов, получившего название Calgary Compres­sion Corpus2 (CalgCC). ...

Базовых стратегий сжатия три:

1. Преобразование потока ("Скользящее окно-словарь").

Описание посту­пающих данных через уже обработанные. Сюда входят LZ-методы для потоков "слов", т. е. когда комбинации поступающих элементов предска­зуемы по уже обработанным комбинациям. Преобразование по таблице, RLE, LPC, DC, MTF, VQ, SEM, Subband Coding, Discrete Wavelet Transform - для потоков "элементов", т. е. когда не имеет смысла рас­сматривать комбинации длиной два и более элемента или запоминать эти комбинации, как в случае Linear Prediction Coding.

Никаких ...


Статистические

Преобразующие

Поточные

Блочные1''

" Поточные

Блочные

Для "слов", модель "Источник с ...

Бит- это "атом" цифровой информации: переменная, которая может принимать ровно два различных значения:

■ " 1" (единица, да, истина, существует);

■ "О" (нуль, нет, ложь, не существует).

Любая система, которую можно перевести в одно из двух различных за­даваемых состояний и удержать в нем в течение требуемого промежутка времени, может быть использована для хранения 1 бита информации.

Емкость для хранения бита можно представлять себе как небольшой "ящик" где-то в пространстве-времени (в микросхеме, на магнитном/опти­ческом диске, линии связи) ...

В 1 разд. - "Методы сжатия без потерь" описаны основные подходы, применяющиеся при кодировании источников без памяти, источников типа "аналоговый сигнал" и источников с памятью, а также методы предобработ­ки типичных данных, обеспечивающие улучшение сжатия для распростра­ненных алгоритмов.

Ввиду особой практической и теоретической важности, а также распро­страненности универсальные методы кодирования источников с памятью были рассмотрены в соответствующих отдельных главах: "Словарные ме­тоды сжатия данных", "Методы контекстного моделирования", "Преобразо­вание Барроуза-Уилера". ...