Методы сжатия

Методы сжатия файлов бывают «открытыми» и «коммерческими». В первом случае алгоритм можно свободно исследовать и использовать, так как он сам по себе является ценностью. Во втором случае использование метода является закрытым: алгоритм засекречивается в виду того, что он применяется только в отдельных программных продуктах, и несанкционированное использование может вызвать последующие разбирательства по поводу авторских прав, что собственно неоднократно происходило в истории развития архиваторов.

Разработано большое количество методов сжатия, наиболее известные: методы Зива — Лемпела или «LZ-методы» (LZ77, LZ78, LZH, LZW), метод Хаффмана или «HUFF» («Huffman Coding»), преобразование Барроуза-Уиллера («BWT») , метод преобразования Фурье «FT» («Fourier Transform») и другие. Сжатие, например, по «LZ-методу» основано на создании своеобразного словаря, где каждое слово получает свой порядковый номер, и в результате сжатый файл содержит не предложения, а последовательность чисел, что существенно сокращает его размер. Стоит отметить, что данный метод работает эффективнее для сжатия больших файлов, чем маленьких: создание системы словаря, а иногда и «словаря в словаре» также сказывается на размере итогового файла, что нецелесообразно для сжатия легких файлов. Кстати, компрессия по методу Зива — Лемпела является одним из самых распространенных методов сжатия без потерь.

Кодирование по методу Хаффмана описывается несколько сложнее: оно происходит благодаря созданию определенной таблицы данных и добавления к ней новых ячеек, в результате чего получается систематизация данных в виде дерева («двоичное дерево»). С помощью этого дерева происходит вычисление кода и собственно само кодирование.

При сжатии по методу Барроуза и Уиллера упаковка происходит в два этапа: в начале совершается определенное преобразование данных, затем — сам процесс сжатия. На первом этапе происходит сортировка данных, которая получила название «преобразование Барроуза-Уиллера»: в блоке данных разные символы меняются местами таким образом, чтобы обеспечить более действенное сжатие на втором этапе.

Необходимо особо выделить метод PPM («Prediction by Partial Match»), по которому работает программа WinRAR и многие архиваторы русских разработчиков: архиваторы PPMD и PPMonstr (автор Дмитрий Шкарин), PPMN (автор Максим Смирнов), PPMY (архиватор Евгения Шелвина). Также стоит отметить метод арифметического кодирования ARC, ставший предшественником формата архиватора WinZip. Арифметическое кодирование является созданием из сжимаемого файла нумерации отдельных его блоков: в последовательности битов файла выделяются биты с одинаковыми частотами для последующей нумерации. Арифметическое кодирование стало основой многих методов сжатия, включая метод Хаффмана.

Что касается предыстории программы WinZIP, изначально были разработаны алгоритмы сжатия по так называемым методам редуцирования («reducing») и сокращения («shrinking»), которые сегодня уже практически не поддерживаются. Позже в программу WinZIP был внедрен метод, сочетающий LZ-метод (LZ77) и метод Хаффмана, и в результате этого удачного совмещения был разработан новый формат сжатия, ставший широко распространенным.