Программные методы защиты информации. Часть 1. Крыжановская Ю.А. - 19 стр.

                                      19
                      Символ             Код
                         З               0000
                         А               0001
                         Щ               0010
                         И               0011
                         Т               0100
                         П               0101
                         Р               0110
                         О               0111
                         Г               1000
                         М               1001
                         Д               1010
                         Н               1011
                         Ы               1100
                         Х               1101
                         С               1110
                      ПРОБЕЛ_            1111
      В случае применения данной таблицы закодированный текст займет всего
31/2 + 1=16 байт. Экономия памяти налицо, и к тому же исходный текст спрятан
от визуального просмотра. Объем закодированного текста может быть определен
по формуле: V=b*n, где b=log2 (k);
       k - всего различных символов в тексте; n - всего символов в тексте.
В данном случае коэффициент сжатия (КС) будет рассчитываться по формуле
КС=8*n/n*log2(k).
Алгоритм Хаффмана
      Алгоритм основан на том факте, что некоторые символы из стандартного
256-символьного набора в произвольном тексте могут встречаться чаще среднего
периода повтора, а другие, соответственно, – реже. Следовательно, если для за-
писи распространенных символов использовать короткие последовательности
бит, длиной меньше 8, а для записи редких символов – длинные, то суммарный
объем файла уменьшится. В данном случае речь будет идти о коде переменной
длины, позволяющем однозначно восстанавливать исходный текст.
      Хаффман предложил очень простой алгоритм определения того, какой сим-
вол необходимо кодировать каким кодом для получения файла с длиной, очень
близкой к его энтропии (то есть информационной насыщенности). Пусть у нас
имеется список всех символов, встречающихся в исходном тексте, причем
известно количество появлений каждого символа в нем. Выпишем их вертикаль-
но в ряд в виде ячеек будущего графа. Выберем два символа с наименьшим ко-
личеством повторений в тексте (если три или большее число символов имеют
одинаковые значения, выбираем любые два из них). Проведем от них линии вле-
во к новой вершине графа и запишем в нее значение, равное сумме частот повто-
рения каждого из объединяемых символов. Далее не будем принимать во внима-
ние при поиске наименьших частот повторения два объединенных узла (для это-
го сотрем числа в этих двух вершинах), но будем рассматривать новую вершину