Теория информации
Конспект лекций
назад | содержание | вперед

7. АДАПТИВНЫЕ МЕТОДЫ КОДИРОВАНИЯ

 

7.3 Код "Стопка книг"

Этот метод был предложен Б. Я. Рябко в 1980 году. Название метод получил по аналогии со стопкой книг, лежащей на столе. Обычно сверху стопки находятся книги, которые недавно использовались, а внизу стопки – книги, которые использовались давно, и после каждого обращения к стопке использованная книга кладется сверху стопки.

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

Пример 7.3.1. Приведем описание кода на примере алфавита . Статистика источника неизвестна. Пусть необходимо закодировать сообщение  (см. рис.11)

 

Рисунок 11 Кодирование методом «стопка книг»

Таким образом, закодированное сообщение имеет следующий вид:


 

Рассмотренный метод сжимает сообщение за счет того, что часто встречающиеся символы будут находиться в верхних позициях «стопки книг» и кодироваться более короткими кодовыми словами. Эффективность метода особенно заметна при кодировании серий одинаковых символов. В этом случае все символы серии, начиная со второго, будут кодироваться самым коротким кодовым словом, соответствующим первой позиции «стопки книг».

При декодировании используется такая же «стопка книг», находящаяся первоначально в том же состоянии. Над «стопкой» проводятся такие же преобразования, что и при кодировании. Это гарантирует однозначное восстановление исходной последовательности.

Алгоритм на псевдокоде

Кодирование кодом «Стопка книг»

Обозначим

length  – длина кодируемой строки

code – массив кодовых слов для позиции «стопки»

s_in – строка для кодирования

s_out – результат кодирования

S – строка, содержащая исходный алфавит

insert(T,S) – процедура, которая перемещает символ S[T] на первую позицию строки S, при этом сдвигая символы S[1], S[2], …,S[T-1] на одну позицию вправо

 

length:=<длина s_in>

DO (i=1,…,length)

T:=<номер символа s_in[i] в строке S>
s_out:=s_out+code[T]
insert(T,S)

OD

 

наверх

 


назад | содержание | вперед