1А1б1в1б1г1а1б1г1в1а1в1г1б1а1г

Отсюда следует важный вывод: один и тот же алгоритм сжатия для одних исходных данных сокращает их размер, а для других может и увеличить.

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

При включении или перезагрузке персонального компьютера (ПК), стартует специальная программа, расположенная в постоянном запоминающем устройстве (ПЗУ), основная задача которой – произвести загрузку операционной системы (ОС). ПЗУ ПК содержит базовую систему ввода-вывода (BIOS). ОС опирается на BIOS при работе с некоторыми устройствами, подключенными к ПК. Кроме того, ПЗУ содержит множество другой информации, важной для функционирования ПК.

Как Вы видите, используя сокращения повторяющихся терминов, удается уменьшить объем последующих предложений. Если бы текст не содержал ни одного повторяющегося слова, то сжать его таким методом не получилось бы. Казалось бы, использование данного метода совершенно безопасно – текст либо уменьшится, либо останется прежним, но увеличиться, вроде бы, никак не может. Однако, это не так. Дело в том, что при использовании этого метода, круглые скобки получили особый статус – между ними записывается сокращенный вариант термина. Это означает, что если в исходном (несжатом) тексте встречаются круглые скобки, например, для дополнения или комментария, то необходимо каким-то образом пометить, что эти скобки следует воспринимать «как есть», а не как обозначение для сокращенного варианта. Единственный надежный способ сделать это – ставить перед обычными круглыми скобками какой-нибудь специальный символ, т.е. каждая круглая скобка из исходных данных будет превращаться в два символа, что может немного увеличить объем. А теперь представьте, что произойдет при попытке сжать таким методом файл, состоящий из одних только скобок!

Разумеется, приведенные выше примеры предназначены лишь для наглядной иллюстрации, и алгоритмы, используемые в реальных архиваторах, несколько сложнее, однако идеи, лежащие в основе таких алгоритмов, во многом похожие.

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

1. Для любой последовательности данных существует теоретический предел сжатия, который не может быть превышен без потери части информации.

2. Для любого алгоритма сжатия можно указать такую последовательность данных, для которой он обеспечит лучшую степень сжатия, чем другие методы.

3. Для любого алгоритма сжатия можно указать такую последовательность данных, для которой он вообще не позволит получить сжатия.