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

                                       23
          Т                2                          1000       8
          Р                2                          1110       8
          П                1                         10010       5
          О                1                         10011       5
          Г                1                        111100       6
         Щ                 1                        111101       6
          З                1                        111110       6
         Ы                 1                       1111110       7
          Х                1                     11111110        8
          С                1                     11111111        8
      Из приведенных выше трех кодовых таблиц наиболее оптимальной оказа-
лась последняя - всего 121 бит. Таким образом, перед нами возникла еще одна за-
дача: каким образом подходить к выбору префиксного кода?
      Ясно, что выбор оптимального для кодирования префиксного кода во мно-
гом определяется частотой кодируемых символов в тексте и общим числом раз-
личных символов (размер алфавита). Например, если в тексте нашего примера по-
сле каждого символа будет стоять двойной пробел, то в этом случае наиболее
экономичным станет префиксный код первой таблицы.
      Метод Хаффмана практически не применяется к изображениям в чистом
виде. Обычно используется как один из этапов компрессии в более сложных схе-
мах. Это единственный алгоритм, который не увеличивает размера исходных дан-
ных в худшем случае.
Сжатие способом кодирования серий (RLE) - замена одинаковых последова-
тельностей одним кодом.
       В случае частого повторения в тексте какого-либо слова или словосочетания
иногда полезно перед выполнением архивации по любому из алгоритмов осуще-
ствить замену часто повторяющейся последовательности специальным символом.
Например: {<код символа><число повторений>}
Подобная процедура позволит сэкономить:
V = k*V1 - (V1 + b) + k*b = (V1+b) *(k-l) бит памяти,
где V1 - размер в битах исходной заменяемой последовательности;
       k - встречаемость исходной заменяемой последовательности;
       b - размер в битах результирующего кода (символа).
Объем V = (g + b) * m , где g = LOG2 (k); b = LOG2 (n).
m - число цепочек повторяющихся символов;
k - число различных символов;
n - всего символов в тексте.
       Для текста из символов "а" и "б" в строке аааааааааббббббббббббббааааааа-
аа объем сжатого результата составит: V = (LOG 2 (2)+LOG2 (31))*3=6*3=18 бит.
       Именно такой подход к сжатию информации реализует кодирование серий
последовательностей (Run Length Encoding - RLE). Это наиболее известный про-
стой подход и алгоритм сжатия информации обратимым путем.