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

                                       26
               …………                         …….
                 ОТ                          90
              ПРОГРАММ                       91
Арифметическое кодирование
      Данный алгоритм эффективен, когда размер используемого алфавита по-
рядка нескольких символов (2,3 символа) и при этом каждый символ достаточно
часто повторяется. Этот подход удобен для сжатия текстов, содержащих инфор-
мацию о графических изображениях.
      Арифметическое кодирование является методом, позволяющим упаковывать
символы входного алфавита без потерь при условии, что известно распределение
частот этих символов, и является наиболее оптимальным, т.к. достигается теоре-
тическая граница степени сжатия.
      Предполагаемая требуемая последовательность символов, при сжатии мето-
дом арифметического кодирования, рассматривается как некоторая двоичная
дробь из интервала [0, 1). Результат сжатия представляется как последователь-
ность двоичных цифр из записи этой дроби.
      Идея метода такова: исходный текст рассматривается как запись этой дроби,
где каждый входной символ является "цифрой" с весом, пропорциональным веро-
ятности его появления. Этим объясняется интервал, соответствующий минималь-
ной и максимальной вероятностям появления символа в потоке.
Пример 22. Пусть алфавит состоит из двух символов: a и b с вероятностями со-
ответственно 0,75 и 0,25.
      Рассмотрим наш интервал вероятностей [0, 1). Разобьем его на части, длина
которых пропорциональна вероятностям символов. В нашем случае это [0; 0,75)
и [0,75; 1). Суть алгоритма в следующем: каждому слову во входном алфавите
соответствует некоторый подинтервал из интервала [0, 1), а пустому слову соот-
ветствует весь интервал [0, 1). После получения каждого следующего символа
интервал уменьшается с выбором той его части, которая соответствует новому
символу. Кодом цепочки является интервал, выделенный после обработки всех
ее символов, точнее, двоичная запись любой точки из этого интервала, а длина
полученного интервала пропорциональна вероятности появления кодируемой
цепочки.
Применим данный алгоритм для цепочки "aaba":
            Шаг      Просмотренная цепочка            Интервал
             0                 Нет              [0,1)
             1                               А [0,0.75)
             2                              Аа [0,0.5625)
             3                             Ааб [0.421875,0.5625)
                                                [0.421875,0.52734375
             4                            Ааба
                                                )
Границы интервала вычисляются так: берется расстояние внутри интервала
(0,5625-0,421875=0,140625), делится на частоты [0; 0,10546875) и [0,10546875; 1)
и находятся новые границы [0,421875; 0,52734375) и [0,52734375; 0,5625).