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

                                       20
как полноценную ячейку с частотой появления, равной сумме частот появления
двух соединившихся вершин. Будем повторять операцию объединения вершин
до тех пор, пока не придем к одной вершине с числом. Для проверки: очевидно,
что в ней будет записана длина кодируемого файла. Теперь расставим на двух
ребрах графа, исходящих из каждой вершины, биты 0 и 1 произвольно – напри-
мер, на каждом верхнем ребре 0, а на каждом нижнем – 1. Теперь для определе-
ния кода каждой конкретной буквы необходимо просто пройти от вершины де-
рева до нее, выписывая нули и единицы по маршруту следования.
      Код Хаффмана является префиксным, то есть код никакого символа не яв-
ляется началом кода какого-либо другого символа. Проверьте это на примере. А
из этого следует, что код Хаффмана однозначно восстановим получателем, даже
если не сообщается длина кода каждого переданного символа. Получателю пере-
сылают только дерево Хаффмана в компактном виде, а затем входная последова-
тельность кодов символов декодируется им самостоятельно без какой-либо до-
полнительной информации.
      Сжимая файл по алгоритму Хаффмана, первое, что нужно сделать - прочи-
тать файл полностью и подсчитать сколько раз встречается каждый символ из
расширенного набора ASCII. Если учитывать все 256 символов, то не будет раз-
ницы в сжатии текстового и EXE файла. После подсчета частоты вхождения ка-
ждого символа, необходимо просмотреть таблицу кодов ASCII и сформировать
бинарное дерево.
Пример 16: Пусть есть файл длиной в 100 байт и имеющий 6 различных симво-
лов в себе. Подсчитаем вхождение каждого из символов в файл и получим:
 Символ                 A       B      C        D       E       F
 Число вхождений        10     20      30       5      25       10
Будем называть эти числа частотой вхождения символов и проведем сортировку:
 Символ                 C       E      B        F      A        D
 Число вхождений        30     25      20      10      10        5
Возьмем из последней таблицы 2 символа с наименьшей частотой. В данном слу-
чае это D (5) и любой из F или A (10). Сформируем из "узлов" D и A новый
"узел", частота вхождения для которого будет равна сумме частот D и A:
 Символ                 C       A      D        F      B        E
 Число вхождений        30     10       5      10      20       25


                                  15
Номер в рамке - сумма частот символов D и A. Теперь снова ищем два символа с
самыми низкими частотами вхождения, исключая D и A и рассматривая вместо
них новый "узел" с суммарной частотой вхождения. Самая низкая частота теперь
у F и нового "узла". Снова проведем операцию слияния узлов:
 Символ                 C       A      D       F       B      E
 Число вхождений        30      10      5      10      20     25


                                  15