Сжатие без потери информации

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

Методы сжатия этого класса не могут допустить утрату информации, поэтому они основаны только на устранении избыточности, а информация имеет избыточность почти всегда (правда, если до этого ее никто не уплотнял). Если бы избыточности не было, нечего было бы и уплотнять.

Вот простой пример. В русском языке 33 буквы, десять цифр и еще примерно полтора десятка знаков препинания и прочих специальных символов. Для текста, который записан только прописными русскими буквами (как в телеграммах и радиограммах) вполне хватило бы шестидесяти разных значений. Тем не менее, каждый символ обычно кодируется байтом, который содержит восемь битов и может выражать 256 различных кодов. Это первое основание для избыточности.

Вот другой пример. В международной кодировке символов ASCII для кодирования любого символа отводится одинаковое количество битов (8), в то время как всем давно и хорошо известно, что наиболее часто встречающиеся символы имеет смысл кодировать меньшим количеством знаков. Так, например, в «азбуке Морзе» буквы «Е» и «Т», которые встречаются часто, кодируются одним знаком (соответственно это точка и тире). А такие редкие буквы, как «Ю» (..--) и «Ц» (-.-.), кодируются четырьмя знаками. Неэффективная кодировка – второе основание для избыточности. Программы, выполняющие сжатие информации, могут вводить свою кодировку (разную для разных файлов) и приписывать к сжатому файлу некую таблицу (словарь), из которой распаковывающая программа узнает, как в данном файле закодированы те или иные символы или их группы. Алгоритмы, основанные на перекодировании информации, называют алгоритмами Хафмана.

Наличие повторяющихся фрагментов – третье основание для избыточности. В текстах это встречается редко, но в таблицах и в графике повторение кодов – обычное явление. Так, например, если число 0 повторяется двадцать раз подряд, но нет смысла ставить двадцать нулевых байтов. Вместо них ставят один ноль и коэффициент 20. Такие алгоритмы, основанные на выявлении повторов, называют методами RLE (Run Length Encoding).

Большими повторяющимися последовательностями одинаковых байтов особенно отличаются графические иллюстрации, но не фотографические (там много шумов и соседние точки существенно различаются по параметрам), а такие, которые художники рисуют «гладким» цветом, как в мультипликационных фильмах. При создании резервных копий на жестких дисках есть еще одна возможность получения выигрыша в рабочем пространстве при сжатии файлов, которая, правда, связана не с избыточностью информации, а с тем, как организована файловая система компьютера. Суть ее заключается в том, что любой фай, большой или маленький, может занимать наа диске только целое число кластеров. В файловой системе FAT16 на жестком диске не может быть более 65536 кластеров (2¹⁶). А это значит, что для дисков размером от 1 до 2 Гбайт размер кластера составляет целых 32 Кбайт. Таким образом, в среднем на каждом файле мы теряем половину этой величины, а на малых файлах еще больше.

При уплотнении большой группы файлов в один файл мы экономим минимум по 16 Кбайт на каждом файле только за счет сокращения потерь от нерациональной организации файловой системы. Представьте, что для файла, имеющего размер 1 Кбайт, мы экономим 31 Кбайт, даже если он абсолютно несжимаем!