Карта групп алгоритмов сжатия:

                               Статистические             Трансформирующие
                            поточные    блочные          поточные    блочные

для слов, т.е. модель       DMC,    *pre-conditioned      все LZ       ST,
"Источник Маркова"         все PPM       PPM                        в т.ч.BWT

для байтов, т.е. модель    адаптивный   статический       SEM, VQ,   DCT, DWT,
"источник Бернулли" или     Хаффман      Хаффман          MTF, DC     FT, SC,
"Аналоговый сигнал"                                                 Фрактальные

для байтов или битов       адаптивный   статический       RLE, LPC,    PBS,
                           Арифметик     Арифметик      в т.ч.Дельта   ENUC

*блочно-ориентированный PPM - практически неисследованная область:
нет других алгоритмов кроме "pre-conditioned" PPM-а Чарльза Блума.

Все определения - в статье "Практическое Введение в Сжатие Информации".
Блок - конечный объем цифровой информации, Поток - порция с неизвестными
границами: данные поступают побайтно, а не поблочно.
N-битный байт - последовательность N битов;
слово - конечная последовательность байтов.

Аббревиатуры расшифрованы в низу этой страницы.

Каждая группа (ветвь, семейство) содержит множество методов.
Я думаю, любой одношаговый метод сжатия принадлежит одному из этих семейств.

Описания некоторых методов - в статье "Сжатие Мультимедийной Информации".

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

Не все методы для N-битных байтов применимы к битам (1-битным байтам).
Не стоит применять методы для байтов - к словам или битам, а
методы для слов - к байтам или битам (к выходу BWT, например).

Несмотря на то, что такая карта очень полезна, я никогда не видел аналогов.
Мне очень интересны любые комментарии! Шлите их на artest@inbox.ru, пожалуйста!


Предлагаю такое Определение:

Нефизическая информация - информация, которая может быть получена в любой
точке пространства-времени как результат (исследования) свойств пространства-времени.

Сегодня (4-е Июня 2001 года) web-поиск дает около 50-и результатов фразы
"non-physical information", но её определения найдено не было.

Почему оно так важно ? Смотрите ответ-12 из "Практического Введения":
        ТОлько нефизическая информация всегда доступна, она никак не зависит от
материальных объектов. Объем ее бесконечен. И когда мы изучаем, как она может
быть применена (вэйвлеты, фракталы, например) - на самом деле мы изучаем, как
мы от нее зависим.
        Если мы только предполагаем, что всё, что использовалось при
сжатии-описании, будет доступно при разжатии, но не знаем этого точно,
получается "потенциально потерьное" сжатие.

Вот краткий пример такого нежелательного эффекта:
возьмите файл ftp://ftp.simtel.net/pub/simtelnet/msdos/astronmy/skyplot.zip (153K)
и попробуйте распаковать его последней версией INFO-ZIP ( www.info-zip.org )
Получите такое сообщение:
   пропущен: OBJECTS.DAT             `shrink' метод не поддерживается

UNZIP, рекомендуемый Simtel.Net-ом для разжатия всех .ZIP-ов с ftp.simtel.net
ftp://ftp.simtel.net/pub/simtelnet/msdos/UNZIP.EXE (49K)
дает тот же результат: это UnZip 5.40 от 21 Ноября 1998, от Info-ZIP.

Можете ли немедленно сказать - какой версией какой программы распаковать
этот файл, и откуда ее можно взять ?
Думаете ли и сейчас, что Определение и "потенциально потерьное" сжатие -
теоретические или даже философские вопросы ?

Мне очень интересны любые комментарии! Шлите их на artest@inbox.ru, пожалуйста!



Сокращения:

DMC Dynamic Markov Coding - Динамическое Марковское Кодирование
PPM Prediction by Partial Match - Предсказание по Частичному Совпадению
LZ  методы Лемпеля-Зива, в том числе LZ77 (zip, rar и т.д.), LZ78, LZW (gif, v.42bis)
ST  Sort Transform - Сортирующая Трансформация, в том числе
BWT Burrows-Wheeler Transform - преобразование Барроуза-Уиллера
SEM Separate Exponents and Mantissas - Разделение Экспонент и Мантисс
MTF Move To Front - Сдвиг К Вершине, метод "Стопки Книг".
DC  Distance Coding - Кодирование Расстояний
FT  Fourier Transform - Преобразование Фурье, в том числе
DCT Discrete Cosine Transform - Дискретное Косинусное Преобразование (jpeg, mp3)
DWT Discrete Wavelet Transform- Дискретное Вэйвлетное Преобразование (jpeg-2000)
SC  Subband Coding - Субполосное Кодирование
VQ  Vector Quantization - Векторное Квантование
RLE Run Length Encoding - Кодирование Длин Пробегов, Групповое Кодирование
LPC Linear Prediction Coding - Линейно-Предсказывающее Кодирование,
    в том числе Дельта, ADPCM, CELP и MELP
PBS Parallel Blocks Sorting - Сортировка Параллельных Блоков
ENUC Enumerative Coding - Нумерующее Кодирование

Back to main ARTest page