16. Предпосылки кризисной ситуации с обеспечением защиты информации. Задачи разработчиков современных информационных систем в контексте безопасности

21. Методы кодирования

Метод хаффмана.

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

Пусть сообщение M составлено из символов алфавита C. Эти символы могут быть представлены кодами некоторой фиксированной длины (для определенности 8 бит). Допустим, числа повторений символов A, B, C и D (Na, Nb, Nc и Nd соответственно) удовлетворяют неравенству

Na>Nc+Nd

Число повторений символа B произвольно. Назначим этим символам следующие коды:

A: 00000000

B: 00000001

C: 00000010

D: 00000011

Оставшиеся 252 кода произвольно распределим между оставшимися символами алфавита. Далее сделаем следующую замену кодов:

A: 0000000

B: 00000010

C: 000000110

D: 000000111

В результате получим экономию в Na-(Nc+Nd) бит.

Алгоритм Хаффмана основан на этой идее с той лишь разницей, что она применяется ко всем символам алфавита. На первом шаге определяются числа повторений (веса) всех символов. На втором шаге строится дерево кодирования. Используются две структуры данных - массив и дерево, в массив заносятся все символы и их веса, дерево пусто. Затем находим два самых редких символа, исключаются из массива и добавляются в дерево (листья). Также создается новый узел дерева с весом равным сумме весов найденных символов и содержащий ссылки на эти символы. Этот узел добавляется в массив. Процедура повторяется пока в массиве не останется один элемент. Третий шаг - собственно кодирование.

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

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

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