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