5.6. Кодирование с предсказанием

Только что было показано, что использовать структуру переходных вероятностей в исходных сообщениях для уменьшения длины закодированных сообщений; код Хаффмена учитывает частоты отдельных входных символов, а марковский процесс позволяет учесть также зависимости между символами. В исходных сообщениях существует много других структур, позволяющих уменьшить длину закодированных сообщений, однако их слишком много для того, чтобы шровести подробное исследование в этой книге. Поэтому рассмотрим общий случай, когда предполагается, что имеется либо программа, либо какое-либо устройство, посредством которых можно выявить структуру сообщения и использовать ее для предсказания следующего символа. Предположим для простоты, что источник является двоичным. С помощью программы произведем кодирование входной последовательности двоичных сообщений в последовательность двоичных символов, содержащую сравнительно длинные отрезки символов 0, разделенные относительно более редкими символами 1. На втором этапе кодирования, на котором возникает сжатие, посылается последовательность чисел, в которой каждое число указывает длину соответствующей серии нулей. Приемник может восстановить первоначальное сообщение, используя практически такое же оборудование, как при кодировании.