Теория информации |
Конспект лекций |
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