Бинарное кодовое дерево

Пусть задан префиксный код . Элементарные коды опреде-

ляют бинарное кодовое дерево. Из каждой вершины дерева выходит не более

двух ребер в вершины следующего яруса, левое из которых помечается симво-

лом 0, а правое – символом 1. Элементарным кодам соответствуют вершины

дерева, определяемые путем, идущим из корня. Если код префиксный, элемен-

тарные коды расположены в листьях дерева.

Дерево называется насыщенным, если из каждой вершины, не являющейся

листом, в следующий ярус выходит ровно два ребра.

71. Экономные коды. Оптимальные коды.

Общее правило при построении экономного кода следующее: чаще встречающиеся сообщения нужно кодировать более короткими кодовыми словами, а более длинные слова использовать для кодирования редких сообщений.

Представим себе, что одни сообщения приходится передавать довольно часто, другие - редко, третьи - совсем в исключительных случаях. Понятно, что первые лучше закодировать тогда короткими словами, оставив более длинные слова для кодирования сообщений, появляющихся реже. В результате кодовый текст станет в среднем короче, и на его передачу потребуется меньше времени.

Впервые эта простая идея была реализована американским инженером Морзе в предложенном им коде. Рассказывают, что, создавая свой код, Морзе отправился в ближайшую типографию и подсчитал число литер в наборных кассах. Буквам и знакам, для которых литер в этих кассах было припасено больше, он сопоставил более короткие кодовые обозначения (ведь эти буквы встречаются чаще). Так, например, в русском варианте азбуки Морзе буква "е" передается одной точкой, а редко встречающаяся буква "ц" - набором из четырех символов.

Принцип построения оптимального кода

1. Сообщения, входящие в ансамбль, располагаются в строку (в столбец) по мере убывания вероятностей.
2. Выбирается основание кода K.
3. Все сообщения ансамбля разбиваются на K групп с равными суммарными вероятностями внутри каждой группы. Всем сообщениям первой группы в качестве первого символа присваивается 0, сообщениям второй группы – символ 1, а сообщениям K -й группы – символ (K – 1); тем самым обеспечивается равная вероятность появления всех символов 0, 1,…, K на первой позиции в кодовых словах.
4. Каждая из групп делится на K подгрупп с равной суммарной вероятностью в каждой подгруппе. Всем сообщениям первых подгрупп в качестве второго символа присваивается 0, всем сообщениям вторых подгрупп – 1, а сообщениям K -х подгрупп – символ (K – 1).
5. Процесс продолжается до тех пор, пока в каждой подгруппе не окажется по одной комбинации.

Если полученный оптимальный код является неравномерным, тогда возникает проблема распознавания сообщений в сигнале. В этом случае для упрощения процедуры декодирования сообщений по принятой последовательности символов необходимо выполнить условие однозначной различимости кодовых комбинаций. Один из способов выполнения этого условия заключается в таком построении кодовых слов, чтобы никакая кодовая комбинация не являлась началом другой. Альтернативой этому служит введение специальных разделительных знаков, которые должны выдаваться в конце каждого кодового слова. Для передачи таких префиксов понадобится еще какой-то символ, помимо 1 и 0, что приведет к увеличению основания кода.

72. Алгоритм Хаффмана

Алгоритм Хаффмана гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов кода на символ сообщения. На первом шаге подсчитываются частоты всех символов в исходных данных. На втором шаге строятся новые коды (битовые последовательности) для каждого символа, так, чтобы никакие две разные последовательности не имели общего начала, например, три последовательности 0, 10, 110. удовлетворяют этому требованию. Хаффман предложил строить двоичное дерево символов, в корне которого находится наиболее частый символ, на расстоянии 1 от корня – следующие по частоте символы, и так далее. На основе такого дерева коды для символов получаются путем выполнения простой процедуры обхода дерева. Код представляет собой путь от корня до символа, в котором 1 означает переход по левой ветви, а 0 – по правой. Такой способ построения гарантирует нужное свойство кодов. Наконец, на последнем шаге в выходные данные записывается построенное дерево, а за ним следуют закодированные данные.

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

73-74. Алгоритм Шеннона – Фано

Алгоритм Шеннона — Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Роберт Фано. Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже. Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. Коды Шеннона — Фано префиксные, то есть никакое кодовое слово не является префиксом любого другого. Это свойство позволяет однозначно декодировать любую последовательность кодовых слов.

Кодирование Шеннона — Фано — алгоритм префиксного неоднородного кодирования. Относится к вероятностным методам сжатия (точнее, методам контекстного моделирования нулевого порядка). Подобно алгоритму Хаффмана, алгоритм Шеннона — Фано использует избыточность сообщения, заключённую в неоднородном распределении частот символов его (первичного) алфавита, то есть заменяет коды более частых символов короткими двоичными последовательностями, а коды более редких символов — более длинными двоичными последовательностями.

Алгоритм был независимо друг от друга разработан Шенноном (публикация «Математическая теория связи», 1948 год) и, позже, Фано (опубликовано как технический отчёт).

Основные этапы:

1. Символы первичного алфавита m₁ выписывают по убыванию вероятностей.

2. Символы полученного алфавита делят на две части, суммарные вероятности символов которых максимально близки друг другу.

3. В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части — «1».

4. Полученные части рекурсивно делятся и их частям назначаются соответствующие двоичные цифры в префиксном коде.

Когда размер подалфавита становится равен нулю или единице, то дальнейшего удлинения префиксного кода для соответствующих ему символов первичного алфавита не происходит, таким образом, алгоритм присваивает различным символам префиксные коды разной длины. На шаге деления алфавита существует неоднозначность, так как разность суммарных вероятностей может быть одинакова для двух вариантов разделения (учитывая, что все символы первичного алфавита имеют вероятность больше нуля).

Алгоритм вычисления кодов Шеннона — Фано

Код Шеннона — Фано строится с помощью дерева. Построение этого дерева начинается от корня. Всё множество кодируемых элементов соответствует корню дерева (вершине первого уровня). Оно разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Эти подмножества соответствуют двум вершинам второго уровня, которые соединяются с корнем. Далее каждое из этих подмножеств разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Им соответствуют вершины третьего уровня. Если подмножество содержит единственный элемент, то ему соответствует концевая вершина кодового дерева; такое подмножество разбиению не подлежит. Подобным образом поступаем до тех пор, пока не получим все концевые вершины. Ветви кодового дерева размечаем символами 1 и 0, как в случае кода Хаффмана.

При построении кода Шеннона — Фано разбиение множества элементов может быть произведено, вообще говоря, несколькими способами. Выбор разбиения на уровне n может ухудшить варианты разбиения на следующем уровне (n + 1) и привести к неоптимальности кода в целом. Другими словами, оптимальное поведение на каждом шаге пути ещё не гарантирует оптимальности всей совокупности действий. Поэтому код Шеннона — Фано не является оптимальным в общем смысле, хотя и дает оптимальные результаты при некоторых распределениях вероятностей. Для одного и того же распределения вероятностей можно построить, вообще говоря, несколько кодов Шеннона — Фано, и все они могут дать различные результаты. Если построить все возможные коды Шеннона — Фано для данного распределения вероятностей, то среди них будут находиться и все коды Хаффмана, то есть оптимальные коды.

Пример кодового дерева

Исходные символы:

· A (частота встречаемости 50)

· B (частота встречаемости 39)

· C (частота встречаемости 18)

· D (частота встречаемости 49)

· E (частота встречаемости 35)

· F (частота встречаемости 24)

Полученный код: A — 11, B — 101, C — 100, D — 00, E — 011, F — 010.

Кодирование Шеннона — Фано является достаточно старым методом сжатия, и на сегодняшний день оно не представляет особого практического интереса. В большинстве случаев длина последовательности, сжатой по данному методу, равна длине сжатой последовательности с использованием кодирования Хаффмана. Но на некоторых последовательностях могут сформироваться неоптимальные коды Шеннона — Фано, поэтому более эффективным считается сжатие методом Хаффмана.

75*. Использование теории чисел в криптографии с открытым ключом. Криптосистема RSA.

Криптосистема RSA.