Пример двоичного(бинарного) дерева

┌──────> 000 ──> отмечены 10 листьев

| дерева.

┌─ 00 ───┤

| └──────> 001

┌─ 0 ───┤ ┌──────> 010

| └─ 01 ───┤

о ────┤ └──────> 011

| ┌──────> 100

| ┌─ 10 ───┤

└─ 1 ───┤ |

| | └──────> 101 ┌──────> 1100

| | ┌─── 110 ─────┤

| └─ 11 ───┤ └──────> 1101

| | ┌──────> 1110

| └─── 111 ─────┤

└─ корень дерева └──────> 1111

Листья любого бинарного дерева образуют префиксный код и наоборот, для всякого бинарного префиксного кода существует такое дерево, что слова кода соответствуют его листьям.

$1.5. Задача создания оптимального префиксного кода.

Сжатие информации это процесс сокращения количества бит, необходимых для хранения некоторого объема информации.

Пути решения проблемы минимизации кода сообщения:

1. Оптимизация имеющегося кода - кодирование "стопкой книг".

2. Поиск оптимальной схемы для данного сообщения - кодирование Хаффмена.

1.5.1. Сжатие методом "стопки книг".

Укажем еще один способ получения минимального непрерывного кода - " стопка книг". Он был открыт в 1980 г., а затем переоткрыт в 1986 г., получив название " двигай вверх", и в 1987 г. под названием "Кодирование по степени новизны". Метод состоит в следующем.

Пусть по линии связи должно быть передано cсообщение S в алфавите А={a₁, a₂,..., a_n}. Буквы А отождествлены с числами 1, 2,..., │А│=n.

На приемном и передающем концах имеются идентичные списки, которые в начальный момент содержат числа от 1 до n в порядке возрастания. При появлении в сообщении S очередной буквы a по линии связи передается префиксный код x_i номера позиции i, занимаемой в данный момент буквой a в списке. Это дает возможность на приемном конце идентифицировать букву a. Вслед за этим на приемном и передающем концах ставят букву a в начало списка, увеличивая этим на единицу номера букв, стоящих на позициях от 1 до i-1. Позиции букв, стоящих на позициях от i+1 и дальше, остаются неизменными. Так происходит со стопкой книг, если одну из них взять из стопки и переложить наверх.

Теперь вспомним главную идею префиксного сжатия по частоте встреч букв в тексте: для часто встречающейся буквы - очень короткий код, для редко встречающейся -длинный префиксный код. Если мы расположим наши коды с первой до позиции │А│ по возрастанию длины кода, то получим, что часто встречающиеся буквы будут постоянно вверху "стопки", а, следовательно, будут иметь самые короткие коды и наоборот, редко встречающиеся буквы будут находиться внизу "стопки", а значит будут иметь длинные коды.

Пример.

Пусть нужно передать сообщение S= «bbacabbcc» в алфавите А={a, b, c}. Возьмем, например, следующее префиксное множество {0,10,11} и сопоставим каждому номеру позиции в "стопке" элементарный код из данного множества, причем по возрастанию длины кода. Тогда первая позиция будет иметь код 0, вторая - код 10 и третья - код 11:

Тогда в процессе кодирования сообщения S последний столбец таблицы("стопка книг") будет меняться следующим образом: (a, b, c) - (b, a, c) - (b, a, c) - (a, b, c) - (c, a, b) - (a, c, b) - (b, a, c) и т. д. Тогда кодом сообщения S будет 100101110110110.

Поиск по сайту: