Архивация данных

Лет пятнадцать назад гибкий диск емкостью 720 Кбайт казался огромным. На нем вполне размещались тексты двух кандидатских диссертаций или одной докторской, но чаще на диске хранили два-три десятка любимых компьютерных игр.

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

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

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

Об алгоритмах сжатия

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

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

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

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

В то же время, существуют материалы, в которых стоит пожертвовать несколькими процентами информации, чтобы получить сжатие в десятки раз. К ним относятся фотоиллюстрации, видеоматериалы и музыкальные композиции. Потеря информации при сжатии и последующей распаковке в таких материалах воспринимаются как появление некоторого дополнительного "шума". Но поскольку при создании этих материалов определенный "шум" все равно присутствует, его небольшое увеличение не всегда выглядит критичным, а выигрыш в размерах файлов дает огромный (в 10 – 15 раз на музыке и в 20 – 30 раз на фото- и видеоматериалах).

К алгоритмам сжатия с потерей информации относятся такие известные алгоритмы, как JPEG и  MPEG. Алгоритмы JPEG используются при сжатии фотоизображений. Графические файлы, сжатые этим методом, имеют расширение .JPG. Алгоритмы  MPEG используют при сжатии видео и музыки. Эти файлы могут иметь различные расширения, в зависимости от конкретной программы, но наиболее известными являются  .MPG для видео и  .MP3 для музыки.

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

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

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

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

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