Архивирование

Сильное влияние  оказывает и подбор оптимальных  параметров сжатия. Например, по данным www.maximumcompression.com, используещего оптимальные параметры сжатия для каждого набора данных, разница между 7-zip и RAR около 3%, что значительно меньше разницы, полученной в данном тестировании. 
 

Общие принципы архивации. Классификация методов 

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

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

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

Существует два  основных метода архивации без потерь:

алгоритм Хаффмана (англ. Huffman), ориентированный на сжатие последовательностей байт, не связанных между собой,

алгоритм Лемпеля-Зива (англ. Lempel, Ziv), ориентированный на сжатие любых видов текстов, то есть использующий факт неоднократного повторения "слов" – последовательностей байт.  

Практически все  популярные программы архивации  без потерь (ARJ, RAR, ZIP и т.п.) используют объединение этих двух методов –  алгоритм LZH. 
 

Алгоритм Хаффмана 

Алгоритм основан  на том факте, что некоторые символы  из стандартного 256-символьного набора в произвольном тексте могут встречаться  чаще среднего периода повтора, а  другие, соответственно, – реже. Следовательно, если для записи распространенных символов использовать короткие последовательности бит, длиной меньше 8, а для записи редких символов – длинные, то суммарный  объем файла уменьшится.  

Хаффман предложил  очень простой алгоритм определения  того, какой символ необходимо кодировать каким кодом для получения  файла с длиной, очень близкой  к его энтропии (то есть информационной насыщенности). Пусть у нас имеется  список всех символов, встречающихся  в исходном тексте, причем известно количество появлений каждого символа  в нем. Выпишем их вертикально  в ряд в виде ячеек будущего графа по правому краю листа (рис. 1а). Выберем два символа с наименьшим количеством повторений в тексте (если три или большее число  символов имеют одинаковые значения, выбираем любые два из них). Проведем от них линии влево к новой  вершине графа и запишем в  нее значение, равное сумме частот повторения каждого из объединяемых символов (рис.2б). Отныне не будем принимать  во внимание при поиске наименьших частот повторения два объединенных узла (для этого сотрем числа в  этих двух вершинах), но будем рассматривать  новую вершину как полноценную  ячейку с частотой появления, равной сумме частот появления двух соединившихся  вершин. Будем повторять операцию объединения вершин до тех пор, пока не придем к одной вершине с  числом (рис.2в и 2г). Для проверки: очевидно, что в ней будет записана длина кодируемого файла. Теперь расставим на двух ребрах графа, исходящих  из каждой вершины, биты 0 и 1 произвольно  – например, на каждом верхнем ребре 0, а на каждом нижнем – 1. Теперь для  определения кода каждой конкретной буквы необходимо просто пройти от вершины дерева до нее, выписывая  нули и единицы по маршруту следования. Для рисунка 4.5 символ "А" получает код "000", символ "Б" – код "01", символ "К" – код "001", а символ "О" – код "1".  
 

Рис.1. 

В теории кодирования  информации показывается, что код  Хаффмана является префиксным, то есть код никакого символа не является началом кода какого-либо другого  символа. Проверьте это на нашем  примере. А из этого следует, что  код Хаффмана однозначно восстановим  получателем, даже если не сообщается длина кода каждого переданного  символа. Получателю пересылают только дерево Хаффмана в компактном виде, а затем входная последовательность кодов символов декодируется им самостоятельно без какой-либо дополнительной информации. Например, при приеме "0100010100001" им сначала отделяется первый символ "Б" : "01-00010100001", затем снова начиная с вершины дерева – "А" "01-000-10100001", затем аналогично декодируется вся запись "01-000-1-01-000-01" "БАОБАБ". 

Алгоритм Лемпеля-Зива 

Классический алгоритм Лемпеля-Зива – LZ77, названный так  по году своего опубликования, предельно  прост. Он формулируется следующим  образом : "если в прошедшем ранее выходном потоке уже встречалась подобная последовательность байт, причем запись о ее длине и смещении от текущей позиции короче чем сама эта последовательность, то в выходной файл записывается ссылка (смещение, длина), а не сама последовательность". Так фраза "КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ" закодируется как "КОЛО(-4,3)_(-5,4)О_(-14,7)ЬНИ".  

 Распространенный  метод сжатия RLE (англ. Run Length Encoding), который заключается в записи вместо последовательности одинаковых символов одного символа и их количества, является подклассом данного алгоритма. Рассмотрим, например, последовательность "ААААААА". С помощью алгоритма RLE она будет закодирована как "(А,7)", в то же время ее можно достаточно хорошо сжать и с помощью алгоритма LZ77 : "А(-1,6)". Действительно, степень сжатия именно такой последовательности им хуже (примерно на 30-40%), но сам по себе алгоритм LZ77 более универсален, и может намного лучше обрабатывать последовательности вообще несжимаемые методом RLE.