25.Рассмотрите методы оптимального кодирования(сжатие информации).

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

Воспользуемся методом Шеннона-Фано. Буквы (или любые сигналы, сообщения, подлежащие кодированию) исходного алфавита записываются в порядке убывающей вероятности. Упорядоченное таким образом множество букв разбивается на два подмножества так, чтобы суммарные вероятности этих подмножеств были примерно равны. Затем каждое подмножество снова разбивается на два подмножества с соблюдением того же условия равенства вероятностей. Такое разбиение продолжается до тех пор, пока в подмножествах не окажется только по одной букве кодируемого алфавита. При каждом разбиении буквам верхнего подмножества присваивается кодовый элемент 1, а буквам нижнего подмножества - 0 (подумайте, что будет, если поменять местами 1 и 0).

Полученный таким способом неравномерный код не является однозначно декодируемым (расшифрируемым). Чтобы снять эту проблему можно использовать разделительный символ между буквами алфавита, или, запретить такие кодовые комбинации, начальные части которых уже использованы в качестве самостоятельной комбинации. Например, если 101 означает код какой-то буквы, то нельзя использовать комбинации 1, 10 или 10101.

26. Рассмотрите методы оптимального кодироваия (сжатия информации). Опишите алгоритм метода Шенона-Фано.

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

Метод Шеннона – Фано алгоритм:

Шаг 1. Упорядочиваем символы исходного алфавита в порядке невозрастания их вероятностей. (Записываем их в строку.)

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

Шаг 3. Приписываем группе слева "0", а группе справа "1" в качестве элементов их кодов.

Шаг 4. Просматриваем группы. Если число элементов в группе более одного, идем на Шаг 2. Если в группе один элемент, построение кода для него завершено.

27. Рассмотрите методы оптимального кодироваия (сжатия информации). Опишите алгоритм метода Хаффмана.

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

Допустим, у нас есть следующая таблица частот:

15 7 6 6 5

А Б В Г Д

Этот процесс можно представить как построение дерева, корень которого — символ с суммой вероятностей объединенных символов, получившийся при объединении символов из последнего шага, его n0 потомков — символы из предыдущего шага и т. д.Чтобы определить код для каждого из символов, входящих в сообщение, мы должны пройти путь от листа дерева, соответствующего текущему символу, до его корня, накапливая биты при перемещении по ветвям дерева (первая ветвь в пути соответствует младшему биту). Полученная таким образом последовательность битов является кодом данного символа, записанным в обратном порядке.

Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом.

А Б В Г Д

0 100 101 110 111

Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтении их из потока. Кроме того, наиболее частый символ сообщения А закодирован наименьшим количеством бит, а наиболее редкий символ Д — наибольшим.