Теория информации |
Конспект лекций |
7. АДАПТИВНЫЕ МЕТОДЫ КОДИРОВАНИЯ
7.3 Код «Стопка книг»
Этот метод был предложен Б. Я. Рябко в 1980
году. Название метод получил по аналогии со стопкой книг, лежащей на столе.
Обычно сверху стопки находятся книги, которые недавно использовались, а внизу
стопки – книги, которые использовались давно, и после каждого обращения к
стопке использованная книга кладется сверху стопки.
До начала кодирования буквы исходного алфавита упорядочены
произвольным образом и каждой позиции в стопке присвоено свое кодовое слово,
причем первой позиции стопки соответствует самое короткое кодовое слово, а
последней позиции - самое длинное кодовое слово. Очередной символ
кодируется кодовым словом, соответствующим номеру его позиции в стопке, и
переставляется на первую позицию в стопке.
Пример 7.3.1. Приведем описание кода на примере алфавита . Статистика источника неизвестна. Пусть необходимо
закодировать сообщение
(см.
рис.11)
·
Символ находится в третьей
позиции начальной стопки, кодируется кодовым словом 110 и перемещается на
первую позицию в стопке, при этом символы
и
смещаются на одну
позицию вниз.
·
Следующий символ уже находится в первой
позиции стопки, кодируется кодовым словом 0 и стопка не изменяется.
·
Символ находится в
последней позиции стопки, кодируется кодовым словом 111 и перемещается на
первую позицию в стопке, при этом символы
,
,
смещаются на одну позицию вниз.
·
Следующий символ уже находится в первой
позиции стопки, кодируется кодовым словом
0 и стопка не изменяется.
·
Символ находится во второй
позиции стопки, кодируется кодовым словом 10 и перемещается на первую позицию в
стопке, при этом символ
смещается на одну
позицию вниз.
№ |
Кодовое слово |
Начальная «стопка» |
Преобразования «стопки» |
||||
1 |
0 |
а1 |
|
|
|
|
а3 |
2 |
10 |
|
|
|
|
А3 |
а4 |
3 |
110 |
а3 |
|
|
|
|
а1 |
|
111 |
|
|
а4 |
|
|
|
Рисунок 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