Давайте подумаем, насколько актуальна идея архивации и насколько применимы алгоритмы архивации в контексте сегодняшних реалий. А реалии говорят сами за себя: объемы жестких дисков (да и оперативной памяти) у рядовых пользователей сейчас насколько велики, что многие просто не представляют: как использовать весь потенциал таких больших хранилищ данных. Стоит ли в таких условиях задумываться о сути архиваторов и следует ли вообще их использовать?

Когда у меня был компьютер на базе процессора i386 с жестким диском Maxtor объемом в 270 Mbyte, я очень активно пользовался архиваторами, более того, они не всегда помогали и, подчас, приходилось вместо MS Word ставить Lexicon. Это были тяжелые времена. Но и сейчас я не перестаю пользоваться архиватором, хотя проблемы с дисковым пространством навсегда канули в лету. Почему?

Для этого есть целый ряд причин. Перечислю некоторые из них:

•  при передаче файлов по почте или с помощью терминальных программ критичным является каждый килобайт, да и, кроме того, при пересылке большого числа файлов (особенно со сложной структурой каталогов) проще в письмо вложить всего один файл - архив;
•  пропускная способность локальных сетей ограничена. При пересылке больших массивов информации по сети рекомендуется использовать архиваторы не только для уменьшения трафика, но и с целью упрощения конечной верификации: после копирования проще проверить корректность архива, нежели проверять сотни файлов на целостность, просматривая их содержимое;
•  пишущий CD-ROM стал стандартом для ПК среднего класса, многие из нас сталкиваются с проблемой, когда на компакт диск необходимо перенести очень сложную структуру каталогов, тогда как файловая система компакт-диска не допускает более чем восьмикратный уровень вложенности папок. Это было бы очень серьезной проблемой, если бы не архиваторы, позволяющие упаковывать всю структуру в один файл (для таких целей некоторые архиваторы, простите за каламбур, содержат метод сжатия "Без сжатия");
•  многие архиваторы являются очень эффективными кодировщиками, позволяющими скрыть конфиденциальную информацию от чужих глаз, запаковав свои файлы и установив на архив пароль.

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

•  протоколы модемной связи используют простейшие алгоритмы сжатия (вроде замены одинаковых подцепочек байтов "aaaaaabbbbbbbb" на "6a8b") для увеличения скорости передачи файлов при неизменной пропускной способности самого канала связи. Заметьте, что при указании скорости связи используются две неэквивалентные характеристики: физическая характеристика канала (частота изменения сигнала, измеряемая в bod) и логическая характеристика (описывающая количество бит, передаваемых за единицу времени, изменяемая в bit/s);
•  всем известно, что игры - наиболее ресурсоемкие программные продукты. Особенно 3D-игры. Современные видеокарты на борту содержат от 32 до 128 мегабайт, что обусловлено большим объемом передаваемых по шине текстур и z-буфера. Компания S3 предложила инновационную технологию сжатия текстур (сейчас эта технология используется несколькими производителями видеочипов). Суть идеи состоит в том, что, при одних и тех же частоте работы и объеме видеопамяти, можно достичь гораздо более высокой производительности, ведь текстуры сжимаются довольно эффективно, а, следовательно, увеличивается скорость их передачи и доступная память используется более эффективно;
•  в архитектуре современного ПК есть два узких места, именно они ограничивают рост интегральной производительности современных компьютеров. Именно из-за этих двух компонентов, удваивая частоту своего процессора, мы не получаем двойного увеличения производительности всего ПК. Это память и жесткие диски. И если процессоры увеличили свою производительность за пять лет почти в 20 раз, частота памяти увеличилась с 66 MHz (тогда еще это были модули DIMM SDRAM PC66) до 333 MHz (модули DDR PC2700). Казалось бы, не так и плохо, но на самом деле частота синхронизации с системной шиной еще ни о чем не говорит. За счет введения дополнительных циклов ожидания производителям удалось увеличить частоту памяти, но вот производительность от этого сильно не увеличивается (о чем свидетельствуют многочисленные тесты). Хотя покупают, конечно, мегагерцы... С жесткими дисками все еще хуже. Объемы растут, а вот скорость... Да, спецификации интерфейса IDE сменяют друг друга. За небольшой период времени интерфейс ATA 33 сменился интерфейсом ATA 133 (по инициативе Maxtor, хотя, конечно, не ее, а купленной ею компании Quantum - именно эта фирма являлась с давних пор разработчиком перспективных интерфейсов). Но скорость практически не меняется; механика, а не электроника жесткого диска является критичной. Такая важная характеристика как RPM (rotate per minute - количество совершаемых шпинделем жесткого диска оборотов за единицу времени) выросла незначительно - с 5400 до 7200 rpm. Вы спросите причем тут идея кодирования со сжатием?

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

Сейчас, когда производительность CPU увеличилась кардинальным образом, использование сжатия на уровне файловой системы не только не тормозит систему, но и наоборот, ускоряет ее. Если есть объективные причины, тормозящие увеличение пропускной способности дисковой подсистемы, то почему бы не использовать сжатие (возможно, на АППАРАТНОМ уровне)? Объем передаваемых потоков уменьшится, а скорость их передачи по тракту HDD-->IDE Controller-->Шина PCI-->RAM увеличится. С памятью та же ситуация, с той лишь разницей, что увеличение реальной производительности возможно только за счет реализации алгоритмов сжатия на аппаратном уровне (без модификации контроллера памяти здесь не обойтись).

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

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

Методика поиска необходимой документации довольно проста. Заходим на один из поисковиков и вводим запрос вроде: "архивация", "сжатие данных", "алгоритмы кодирования". Получив первые приблизительные результаты, мы приходим к выводу, что для нас наибольший интерес представляют два алгоритма: алгоритм Хаффмана (Huffman) и метод арифметического кодирования. Теперь можно поискать предметную информацию - описание сути данных двух алгоритмов.

Для начала следует уяснить, что в памяти машины (на диске или в ОЗУ) данные хранятся в виде последовательности нулей и единиц. Каждая минимальная ячейка файла содержит нуль или единицу. Разберемся, что нам, пользователям, может говорить эта бесконечная череда циферок?

Изначально вся пользовательская информация ограничивалась только текстами. Тексты состоят из символов. Посчитаем количество символов, необходимых для того, чтобы писать разнообразные тексты. Прежде всего, наш национальный алфавит (кириллица). Добавим латиницу, знаки пунктуации, цифры, знаки математических операций, символы №, #, @, % и пр. Плюс ко всему символы псевдографики, предназначенные для рисования таблиц в тексте и некоторые другие. В итоге мы получили "виртуальный алфавит", содержащий немногим более двухсот элементов.

Но как сохранить текст, написанный в таком большом алфавите, если компьютер может "запоминать" только нули и единицы? Минимальная ячейка (бит) может принимать два значения - 0 и 1. Если взять две такие, идущие друг за другом, ячейки, то эта пара может принимать 4 значения: "00", "01", "10", "11". Возможно, вы уже догадались, что если брать наборы из n минимальных ячеек (бит), то число всевозможных значений такого набора увеличивается и будет равно степени двойки с показателем n. Т.е. если группируем два бита, то число возможных вариантов 2^2=4; если три бита, то вариантов значений этой группы восемь (2^3): "000", "001", "010", "011", "100", "101", "110", "111" и так для любого количества бит в группе.

Мы хотим подобрать такое число бит, группа из которых может принимать как минимум около двухсот значений (каждое из значений мы отождествим с символом нашего алфавита). Минимальная степень двойки, превосходящая количество элементов "виртуального алфавита" - восьмая (2^8=256). Иными словами, сгруппировав биты по восемь штук, мы сможем каждому значению такого набора бит (всего таких значений 256) сопоставить свою букву, как, впрочем, и было сделано в стандарте ASCII. Именно поэтому вся память ПК разделена на байты - группы по восемь бит. Кстати, именно поэтому первые массовые процессоры были восьмиразрядными (карьера Билла Гейтса началась с внедрения интерпретатора языка Basic для систем, построенных на базе восьмиразрядного процессора 8080).

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

aaaaabbbccccccccccccccadddddddddddddddd{end of file}.

Файл занимает на диске 39 Byte. Очевидно, что информация в файле несколько избыточна и хранение файла в таком виде не оправдано. Совсем другое дело, если файл будет выглядеть так:

5a3b14ca16d{end of file}.

В таком случае файл будет занимать всего 11 byte. В итоге файл можно записать экономичнее в 39/11=3,5 раза. На этом же примере можно описать еще один способ экономии дискового пространства. Как видно файл состоит всего из четырех символов. Если сопоставить каждому из них пару битов, то получим:

a - "00",
b - "01",
c - "10",
d - "11".

Иными словами файл можно закодировать таким образом, что каждый из символов будет кодироваться не восемью, а двумя битами. И тогда экономия будет четырехкратной (8/2=4). Следует заметить, что этот вариант алгоритма более общий и одинаково эффективен даже если в файле нет ни одной однородной подцепочки. Заметьте, что для применения такого алгоритма качественный состав представленных в файле байт должен быть неполным. Например, если в файле представлены 200 разных символов, то для однозначной идентификации каждого из них придется использовать все восемь бит (семи не хватит, так как комбинации из семи бит могут принимать 2^7=128 значений), что не позволит достичь никаких результатов при применении этого способа сжатия.

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

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

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

Можно представить, что все файлы - это тексты, написанные в алфавите, состоящем из 256 букв (так оно на самом деле и есть). Рассмотрим все множество файлов, размер которых не превышает n byte (где n произвольное число). И допустим, что существует некий алгоритм кодирования, который любой из этих файлов сжимает с "положительной" эффективностью. Тогда множество всех их архивов содержится во множестве всех файлов, размер которых МЕНЬШЕ n byte. Согласно нашему предположению существует взаимно-однозначное (биективное, как сказали бы математики) соответствие между двумя конечными множествами, число элементов в которых не совпадает. Чего быть не может (так называемый принцип Дирихле; да, сказывается математическое образование). Отсюда можно сделать довольно значимые выводы: 1) не существует архиватора, который бы одинаково хорошо паковал любые файлы, 2) для любого архиватора найдутся файлы, в результате сжатия которых будут получаться архивы в лучшем случае не меньшего размера, чем исходные файлы.

Шаг №3. Переходим на шаг №2 до тех пор, пока набор не будет состоять только из одного элемента: ("вершина #last_number", summa_vseh_chastot):
{(c, 19), ("вершина #2", 13)}
{("вершина #3", 32)}

Что же в итоге? Посмотрите на рисунок. Вы видите дерево, растущее с листьев! Если соединять чертой каждый из элементов "вершина #x" с теми элементами предшествующих наборов, сумма частот которых хранится во второй части элемента "вершина #x", то мы получим своего рода дерево (в программировании подобные структуры называются бинарными деревьями).

Смысл этой древесной структуры состоит в том, чтобы каждому из символов сопоставить различное число бит в зависимости от его частоты (как мы уже говорили, в несжатом файле символы хранятся в виде групп по восемь бит). Если внимательно всмотреться в следующий рисунок, вы увидите, что каждая из ветвей помечена либо нулем, либо единицей. Таким образом, если мысленно пройтись по дереву от корня до какой-либо вершины, содержащей символ, то последовательность нулей и единиц, встречающихся у вас на пути, и будет новой комбинацией бит для этого символа. Например, символ "c" как наиболее часто встречающийся будет кодироваться одним битом "0", символ "d" двумя битами "10" и т.д.

В двоичном виде файл будет выглядеть так:

00000000 00001111 11111111 10010010 01001001 00101101 10110100 01010101 01010101 01010000 0000хххх{88 bit, end of file}

Сжатый файл занял 11 байт (последние четыре бита xxxx записываются произвольно, ведь весь файл на самом деле умещается в 84 бита, что не кратно восьми). Коэффициент сжатия при таком кодировании равен 3,5.