Архивирование, сжатие, упаковка.

[GriV]

Вот здесь вместе с витамином мы поговорили, он сказал что это будет интересно.

В общем все знают, какие типы (основные) упаковки есть: RLE, Huffman, LZW. При этом есть подозрение, что LZW является модификацией Huffman, но более знающие меня подправят.
Общая задача сжатия информации ставится следующим образом:
Имеется, информация (точнее данные), которая имеет вложенную избыточность. Упаковщик должен найти способ уменьшить эту избыточность.
Т.о. каждый из методов по сути отличается путём поиска избыточности.

RLE - самый простой и самый известный и понятный метод - заменяет повторяющиеся последовательности только последовательностью и символом количества повторения
этих последовательностей. Т.е. 01 01 01 01 01 он заменит 05 01 отсюда следует и узкое место данного метода:
множественные единичные интервалы (т.е. без повторов) такой упаковщик съест с увеличением:
01 02 03 04 05 -> 01 01 01 02 01 03 01 04 01 05

Метод Хаффмана тоже ищет избыточность но несколько иного плана: он строит дерево частот вхождения конкретных последовательностей
(т.е. это могут быть как отдельные биты, байты так и их комбинации). Самое часто встречаемое значение подменяется
симоволом 0. Следующе по частоте 10. Следующее 110 и т.д.
Т.е. символы 01 02 01 02 01 он запакует в последовательность бит: 0 10 0 10 0 - как всё просто?
Но этот метод имеет свои недостатки: для последовательностей, где нет ярко выраженных лидеров частот (т.е. после частотного анализа
все значения лежат более-менее в одной категории), этот метод даст увеличение конечного файла относительно
исходного.
Во избежания этого отрицательного эффекта используется модифицированный алгоритм, когда для кодировки самых быстрых (самых чатсовстречающихся)
символов используются неоднобитные последовательности, например, для первых 15 символов (по частоте отсортированных в таблице) выделяется 4 бита, тогда все остальные будут аналогично оригинальному
методу Хаффмана идти по увеличению, но особенностью будет жертвование самым быстрым символом (1 бит) в угоды менее быстрым, зато не придётся для этих менее быстрых выделять в среднем около 8 бит на символ. Т.о. то, какое количество бит выделяется на кодирование частых значений тоже является задачой и требует рассмотрения.
Но вот вопрос, каким образом описать заданный сжимаемый файл, чтобы отталкиваясь от этого описания можно было по крайней мере математически сформулировать задачу поиска решения (т.е. как надо упаковывать, чтобы упаковать наиболее оптимально)?

В поисках этого описания (видимо это должно быть какое то уравнение - целевая функция) я сделал некоторые предположения и поставил задачи:

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

Следствия: Если файл СОВСЕМ не сжимается, то он может быть представлен следующим образом:

Служебные данные - DEFW NN ;длина области, в которой сохранены несжимаемые данные
Исходные данные - DEFB A1,A2, .... ANN

без учёта индексных областей и т.д. это просто увеличение упаковываемого файла на 2 байта.


Если файл МАКСИМАЛЬНО сжимаем, то получим

Служебные данные - DEFW KK ;количество повторов сжимаемой информации
Исходные данные - DEFB A1, A2, A3, ... , AN

Если файл содержит как области максимально сжимаемые, так и области максимально не сжимаемые, то будем иметь по сути набор областей:

Служебные данные - DEFB ....
Исходные данные - DEFB ....

(Примечание: терминология относительная, рассматривается в контексте)

[Advertiser]