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

8. СЛОВАРНЫЕ КОДЫ КЛАССА LZ

 

8.2 Кодирование с использованием скользящего окна

Рассмотрим основные этапы кодирования сообщения , которое порождается некоторым источником информации с алфавитом A алгоритмом LZ с использованием скользящего окна.

Пусть используется окно длины W, т.е. при кодировании символа  исходной последовательности учитываются W предыдущих символов:

 


Сначала осуществляется поиск в окне символа . Если символ не найден, то в качестве кода передается  0  как признак того, что этого символа нет в окне и двоичное представление .

Если символ  найден, то осуществляется поиск в окне слова , начинающегося с этого символа. Если слово  есть в окне, то производится поиск слова , затем    и так далее, пока не будет найдено слово, состоящее из наибольшего количества входных символов в порядке их поступления. В этом случае в качестве кода передается 1 и пара чисел (i, j), указывающая положение найденного слова в окне (i – номер позиции окна, с которой начинается это слово, j – длина слова, позиции в окне нумеруются справа налево). Затем окно сдвигается на j символов вправо по тексту и кодирование продолжается.  Для кодирования чисел (i, j) могут быть использованы коды целых чисел.

 

Пример 8.2.1.  Пусть алфавит источника ,  длина окна W=6. Необходимо закодировать исходное сообщение bababaabacabac. (см. рис. 13)

После кодирования первых шести букв окно будет иметь вид bababa.

 

 

Рисунок 13 Кодирование последовательности bababaabacabac

наверх

 


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