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

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

 

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

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

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

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

·        Символ  находится в третьей позиции начальной стопки, кодируется кодовым словом 110 и перемещается на первую позицию в стопке, при этом символы  и  смещаются на одну позицию вниз.

·        Следующий символ  уже находится в первой позиции стопки, кодируется кодовым словом 0 и стопка не изменяется.

·        Символ  находится в последней позиции стопки, кодируется кодовым словом 111 и перемещается на первую позицию в стопке, при этом символы , , смещаются на одну позицию вниз.

·        Следующий символ  уже находится в первой позиции стопки, кодируется кодовым словом  0 и стопка не изменяется.

·        Символ  находится во второй позиции стопки, кодируется кодовым словом 10 и перемещается на первую позицию в стопке, при этом символ  смещается на одну позицию вниз.

 

Кодовое слово

Начальная «стопка»

Преобразования  «стопки»

 

1

0

а1

а3

а3

а4

А4

а3

2

10

а2

а1

а1

а3

А3

а4

3

110

а3

а2

а2

а1

А1

а1

4

111

а4

а4

а4

а2

А2

а2

 

Рисунок 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

 

 

 

 

наверх

 


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