Архивирование, сжатие, упаковка.
Вот здесь вместе с витамином мы поговорили, он сказал что это будет интересно.
В общем все знают, какие типы (основные) упаковки есть: 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 ....
(Примечание: терминология относительная, рассматривается в контексте)
Дело в том, что эта теория чрезвычайно
сложна, хотя я сам всё это выводил, мне пришлось довольно сильно поломать голову над тем, что бы как минимум понятно объяснить что было и что стало. Даже после этого, в тесном контакте с указанным Vitamin'ом мне пришлось ему объяснять те изюминки которые даёт этот подход, а именно: имеется голое, но чрезвычайно оптимальное RLE, которое (между прочим) оставляет возможность затем применить и huffman, LZ* и т.д. (кому что в голову придёт).
Я здесь несколько неверно указал, спасибо Vitamin'у и его статьям от A. Coder'а, в которых раскрывается суть алгоритмов LZ*. LZW по сути является командным языком, который используется для формирования рассжатия - т.е. идёт команда "возьми_байт" затем "повтори_его_20_раз" и т.д. и т.п.
RAR и подавляющее большинство других архиваторов используют именно этот подход, в то время как такой RLE не используется вообще.
Что касается конкретных программ, да, естьпрограмма на паскале (ДОСовский вариант), там она написана так, что чёрт ногу сломит, и между прочим работает она (видимо именно изза того что это не С) достаточно долго (до нескольких часов над одним Спек-экраном), причём он не создаёт ФАЙЛ, он только даёт конечный размер файла с учётом всего и вся, однако, понятно, что нужно написать (попробовать) ещё и упаковшик, распаковщик провести сравнительное исследование, право, на это надо и нервы и время.
Смысл же состоит в том, что найдётся какой нибудь программист (тот же Vitamin выразил заинтересованность), который реализует это в мягком (в виде SoftWare), благодаря чему у нас появится очередной матёрский упаковщик, глядя на который все будут облизываться :)
В данный момент я думаю над алгоритмом решения этой задачи оптимизации за счёт интерполяции - это позволит внедрить классические методы решения многомерных задач и в зависимости от результата, возможно, я предоставлю иходник для именно такого варианта.