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

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

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

Номер позиции	Элементарный код(позиции)	Буква
1	x1	a1
2	x2	a2
3	x3	a3
…	…	…
n	xn	an

На приемном и передающем концах имеются идентичные списки, которые в начальный момент содержат числа от 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:

Номер позиции	Элементарный код(позиции)	Буква
1	0	a
2	10	b
3	11	c

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