Ответ: ZIP-компрессия при сохранении файла
Так...
LZW, это Lempel + Ziw + Walsh (могу переврать фамилии, извините), т.е. на базовый алгоритм Лемпеля-Зива (свободный) был улучшен Уэлшем и после запатентован тем самым Уэлшем.
Именно благодаря этому мы переплачивали деньги за модемы (алгоритм LZW симметричный, и, вообще говоря, предназначен для передачи потоковых данных), за программы поддерживающие GIF (благодаря чему возник формат PNG) и за некоторые другие вещи.
Алгоритм ZIP, это по сути двойное сжатие. Сперва алгоритмом LZ77, кажется (77 означает год, это несколько улучшенный алгоитм Лемпеля-Зива), потом сжатие динамической вариацией алгоритма Хафмана (который можт быть знаком по "факсовому" сжатию CCIT применяемому для однобитных данных, но CCITT использует статический словарь, а здесь динамический).
Пчему объединили два метода сжатия?
Алгоритм LZ и LZW работает с "алфавитом" размером в один байт, т.е. он определяет байтовые закономерности и ликвидирует их.
При этом остаётся довольно большая энтропия, котрую в какой то мере может уменьшить даже тупой алгоритм RSC, кажется, т.е. упаковка цепочек одинаковых битов.
Алгоритм Хафмана как раз работает с битовым словарём. Статический использует заранее сформированный словарь и работает быстрее, динамический формирует словарь в процессе работы.
Кстати... Все современные "коммерческие" системы сжатия рабтают именно по этим алгоритмам. Даже дающие набольшую степень сжатия (типа RAR, 7Z), они просто динамически оперируют размерами словарей и блоками данных.
Есть и методы могущие дать существенно большее качство сжатия без потерь,
Например, нормальные алгорифмы Маркова (именно алгорифмы), или иные методы... Но их скорость работы на порядок как минимум уступает LZ + Хафман.
P.S.
Извиняюсь... Давно всё это было. Фамилии, а особено как они пишутся на английском вспоминаю с трудом.
Но в своё время сам раскручивал и LZ и LZW и Хафмана по каким-то отрывочным статьям и описаниям.
очень это всё красиво. Офгительно красивые и короткие алгоритмы.
Да, названия алгоритмов я тоже, похоже кое-где переврал.
И если мне память не изменяет, то LZ от LZW отличается именно симметричность, т.е. скрость упаковки полностью соответствует скорости распаковки. На кой этот алгорим, опять таки, если мне не изменяет память, LZ толи пакует, то ли распаковывает быстрее, использовали для данных не требующих такой симметричности - ума не приложу. Только если это был откровенное пиление бабла.
