32
заменены всего лишь несколькими битами, устраняя таким образом излишнюю
информацию.
Кроме того, алгоритмы сжатия можно разделить на:
• методы общего назначения (general-purpose) – не зависят от формата
входных данных и, в основном, ориентированы на сжатие текста,
исполняемых программ, объектных модулей и библиотек. Обычно
являются методами сжатия без потерь.
• специальные методы – ориентированы на сжатие данных
конкретных форматов или их групп: изображения, видео, звук. Учет
специфических особенностей сжимаемых данных позволяет этим
алгоритмам достигать существенно лучшего качества и скорости
сжатия по сравнению с методами общего назначения. Специальные
методы обычно представляют собой методы сжатия с потерями.
Несмотря на то, что сжатие данных стало особо популярным вместе с развитием
интернета и после изобретения алгоритмов Лемпелем и Зивом (алгоритмы LZ на Рис.
6), формально существуют более ранние примеры сжатия. В азбуке Морзе, например,
самым часто используемым буквам в английском языке, “e” и “t”, соответствуют
самые короткие последовательности – точка и тире, соответственно. В 1949 году
появился алгоритм Шеннона – Фано, в котором символам в блоке данных
назначались коды, зависящие от вероятности появления символов в блоке – она была
обратно пропорциональна длине кода. Дэвид Хаффман в качестве учебной работы
по поиску улучшенного метода бинарного кодирования позже улучшил алгоритм
Шеннона – Фано.
Ранние версии алгоритмов Шеннона – Фано и Хаффмана использовали заранее
определенные коды, которые в последствии заменили коды, созданные динамически
на основе входных данных. В 1977 году появился алгоритм Лемпеля и Зива LZ77,
основанный на использования так называемого «скользящего окна»: динамически
33
создаваемого словаря. В 1978 году был опубликован LZ78, создающий словарь не
динамически, а на основе пред-обработанных данных, предназначенных для сжатия.
Алгоритмы LZ77 и LZ78 получили большую популярность и вызвали волну
улучшенных версий, из которых до наших дней дожили DEFLATE, LZMA и LZX.
Активное распространение алгоритмов сжатия началось в конце 80-х вместе с
рождением интернета. Каналы имели чрезвычайно малую пропускную способность,
поэтому для передачи данных в сжатом виде были придуманы форматы ZIP, GIF и
PNG. Сегодня самым популярным алгоритмом сжатия является DEFLATE – помимо
ZIP и PNG он используется в gzip, HTTP, SSL и других технологиях передачи
данных.
34
Рис. 6 Иерархия алгоритмов
35
До середины 90-х основным форматом архиваторов был ZIP, но в 1993 году
Евгений Рошал придумал свой формат и алгоритм RAR. Также среди современных
архиваторов нужно отметить 7zip (считается одним из лучших по сжатию и времени
работы), связку tar + gzip в среде UNIX (gzip архивирует, а tar объединяет несколько
файлов в один), bzip2 и PAQ, использующий т.н. «контекстное смешивание», т.е.
использование более одной статистической модели, чтобы улучшить предсказание
по частоте появления символов.
Базовых стратегий сжатия три:
• преобразование потока («скользящее окно-словарь») подразумевает
описание поступающих данных через уже обработанные. Этой
стратегией пользуются LZ-методы для потоков «слов», т.е. для
ситуаций, когда комбинации поступающих элементов предсказуемы
по уже обработанным комбинациям. В результате преобразования
может быть сформировано несколько потоков. Даже если суммарный
объем потоков увеличивается, их структура улучшается и
последующее сжатие можно осуществить проще, быстрее и лучше.
• статистические стратегии
o адаптивная статистическая стратегия подразумевает вычисление
вероятностей для поступающих данных на основании статистики
по уже обработанным данным. Примерами такого кодирования
можно назвать семейство PPM-методов для потоков «слов»,
адаптивные варианты методов Хаффмана и Шеннона-Фано,
арифметического кодирования для потоков «элементов». В отличие
от первого случая, давно собранная статистика имеет тот же вес,
что и недавняя, если метод не предусматривает специальные
инструменты для этого. Кроме того, вероятными считаются все
комбинации, в том числе те, которые еще не встречались в потоке
и возможно никогда не встретятся.
36
o блочная статистическая стратегия подразумевает дополнительную
кодировку и добавление к сжатому блоку его статистики.
Примерами данной стратегии являются статистические варианты
методов Хаффмана, Шеннона-Фано и арифметического
кодирования для потоков «элементов».
• преобразование блока подразумевает разбитие входящих данных на
блоки, которые затем трансформируются целиком. В случае
однородных данных, рекомендуется брать весь блок, который
требуется сжать. Стратегию такого рода используют методы
сортировки блоков ("BlockSorting''-методы: ST, BWT, PBS),
преобразования Фурье и фрактальные преобразования, и другие. Как
и при первой стратегии (преобразование потока), в результате могут
формироваться несколько блоков, а не один. Даже если суммарная
длина блоков не уменьшается, их структура значительно улучшается
и последующее сжатие происходит проще, быстрее и лучше.
2.1.2. Компрессоры
Компрессор – это программа, сжимающая данные. Большинство техник сжатия
без потерь комбинируют несколько принципов сжатия для создания полноценного
алгоритма. Существует несколько основных принципов сжатия данных:
• кодирование длин серий (RLE) заменяет серии из двух или более
одинаковых символов числом, обозначающим длину серии, за
которым идёт сам символ. Наиболее полезно для чересчур
избыточных данных, например, картинок с большим количеством
одинаковых пикселей, или в комбинации с алгоритмами типа BWT.
37
• преобразование Барроуза-Уилера (BWT) обратимо трансформирует
блок данных так, чтобы максимизировать повторения одинаковых
символов, то есть не сжимает данные, но подготавливает их для
более эффективного сжатия через RLE или другой алгоритм сжатия.
Алгоритм лучше всего работает с большими данными со
множеством повторяющихся символов.
• энтропийное кодирование в простом случает комбинирует
статистическую модель и кодировщик. Кодировщик на основе
модели определяет, какие битовые или байтовые кодировки
назначать каждому символу, чтобы самые часто встречающиеся
были представлены самыми короткими кодировками, и наоборот.
• Алгоритм Шеннона — Фано создает двоичное дерево для
представления вероятностей появления каждого из символов.
Алгоритм не всегда даёт оптимальные коды из-за методики
построения дерева снизу вверх, поэтому сейчас в основном
используется алгоритм Хаффмана, подходящий для любых входных
данных.
• кодирование Хаффмана является одним из вариантов энтропийного
кодирования. В отличие от предыдущего алгоритма двоичное дерево
строится сверху вниз, что позволяет достичь наиболее оптимального
результата.
• арифметическое кодирование достигает очень хорошей степени
сжатия, обычно большей, чем у Хаффмана, однако данный метод
сравнительно сложен по сравнению с предыдущими: вместо
38
разбиения вероятностей по дереву, алгоритм преобразует входные
данные в одно рациональное число от 0 до 1.
Самыми популярными компрессорами в среде Unix являются gzip (комбинация
LZ77 и кодирования Хаффмана), bzip2 (BWT и кодирование Хаффмана) и xz
(LZMA2), а в среде Windows компрессоры обычно сопряжены с архиваторами: 7-zip
(представляет инструменты для энтропийного кодирования в комплексе с цепями
Маркова, BTW и кодирования Хаффмана, а также ряд других алгоритмов), WinRAR
(использует «prediction by partial matching» – «предсказание по частичному
совпадению») и ZIP (DEFLATE – основной из возможных алгоритмов).
Сжатие файлов зависит не только от используемого алгоритма, но и от характера
содержащихся в файлах данных. Текстовые файлы поддаются сжатию очень хорошо,
бинарные файлы хуже, а файлы, содержимое которых изначально максимально
уплотнено (аудио-, видеофайлы, программы-установщики других программ)
практически не сжимаются.
2.1.3. Архиваторы
Архиватор — это компьютерная программа, которая «упаковывает» несколько
файлов в один, так называемый «архив», для упрощения их хранения или их
транспортировать. Архиваторы также могут включать в себя алгоритмы сжатия без
потерь, чтобы уменьшить размер финального файла. Обычно архиваторы принимают
на вход список файлов и конкатенируют их содержимое в файлы-архивы. Архивы
должны хранить метаданные, например имена и размеры исходных файлов, чтобы
предоставлять корректную распаковку. Также метаданные могут включать в себя
исходные метки времени (timestamps), атрибуты файлов и доступы (15). Такую
функциональность реализует tar – стандартный архиватор в операционных системах
семейства *nix. Когда необходимо уменьшить размер финального архива, к нему
39
применяют сжатие без потерь c помощью gzip, bzip2, xz и подобных. Большинство
современных прикладных архиваторов используют сжатие по умолчанию.
У подобного подхода есть как плюсы, так и минусы. Среди преимуществ можно
отметить:
• соответствие Unix-философии о том, что каждая программа должна
выполнять идеально только одну задачу. Так как технологии сжатия
постоянно развиваются, пользователи могут использовать другие
инструменты для сжатия, и это не требует смены архиватора
• позволяют достичь лучшего коэффициента сжатия: сжатие одного
большого файла использует больше статистических совпадений, чем
сжатие многих маленьких по отдельности.
Среди минусов:
• сложно распаковывать или изменять отдельные файлы в архиве: это
требует декомпрессии (и последующей упаковки с сжатия в случае
необходимости изменения одного файла) всего архива, что может
быть долго и ресурсоёмко
• архив становится менее защищенным к повреждениям — при
повреждении участка, содержащего общие данные, все файлы,
содержащие этот участок, будут утеряны
Встроенный архиватор Microsoft Windows, так же как стороннее архивирующее
программное обеспечение (например WinRAR и 7-zip) представляют собой
одновременно и архивирующие, и сжимающие инструменты. В зависимости от
продукта, в него может быть включена функция сжатия финального архива: сама по
себе операционная система Windows ее не поддерживает, но в WinRAR и 7-zip она
может быть опционально включена или отключена.
40
Многие архиваторы позволяют указывать дополнительные параметры, наиболее
важные из который влияют на степень и скорость сжатия. Скорость распаковки
обычно не зависит от скорости и степени упаковки: в большинстве современных
архиваторов применяются так называемые ассиметричные алгоритмы сжатия, т.е.
алгоритмы, в которых скорость (и степень) упаковки практически не влияет на
скорость распаковки, которая обычно гораздо выше.
Большинство архиваторов имеет встроенную функцию проверки целостности
хранящихся в архиве данных. Для этого в архив вносится информация о контрольных
суммах. При распаковке или проверке архива обязательно вычисляется контрольная
сумма каждого извлекаемого файла, и, в том случае, если она не совпадает с
сохраненной, выводится сообщение об ошибке. Кроме того, некоторые архивы, такие
как RAR, имеют функции защиты архивов от физических повреждений или даже
полной утери томов многотомных архивов. Такие архивы можно рассматривать не
только как средство для хранения данных, но и для их восстановления в исходном
виде в случае повреждений.
Многотомные архивы – это архивы, состоящие из нескольких частей указанного
или разного размера. Их удобно применять для переноса больших объемов данных
на носителях меньшего размера и обмена данными через интернет, когда вместо
одного огромного архива практичнее передать несколько файлом меньшего размера.
В разных архиваторах многотомность реализована по-разному: в zip и 7z тома – это
разделенный на части исходный архив, а в RAR – это полноценные архивы.
У ряда архиваторов существует функция создания самораспаковывающихся
архивов (SFX / SEA). По сути, такие архивы являются исполняемыми файлами,
которые сами извлекают содержащиеся в них данные. Это удобно, когда нужно
передать архив кому-то, но нет уверенности, что у него окажется соответствующий
архиватор. На самом деле, самораспаковывающийся архив – это обычный архив, к
которому прикреплен исполняемый модуль распаковки. Такие архивы можно
обрабатывать внешним архиватором как обычные архивы, например, при
41
подозрении на заражении исполняемого модуля вирусом. Самораспаковывающиеся
архивы могут быть многотомными, в этом случае первый том имеет исполняемый
формат файла, в все последующие – стандартный для томов.
В том случае, когда в архив упаковывается много файлов, имеющих схожую
структуру данных, некоторые архиваторы позволяют получать архивы существенно
меньшего размера за счет использования так называемого непрерывного сжатия
(solid compression). При таком сжатии все входящие файлы рассматриваются как
непрерывный поток данных, для которых используется единый общий словарь,
благодаря чему можно достичь очень высокого коэффициента сжатия.
2.2. Методы шифрования
Традиционно к комплексу мер, направленных на защиту исходного кода
программного обеспечения, относят перечисленные в Табл. 1.
Защита при помощи электронных
ключей
Электронные ключи вставляются в
один из портов компьютера и содержат
ключевые данные – информацию для
чтения/записи, ключи
криптографических алгоритмов,
алгоритмы, созданные разработчиком
Защита программ путем переноса
их в онлайн
Все большую популярность
набирает использование подхода SaaS
(Software as a Service), то есть
предоставление всей или части
функциональности программ, как
сервиса. Код программы расположен на