Обзор методов неискажающего кодирования дискретных источников

Рассмотрены основные задачи и конструкции теории неискажающего кодирования дискретных источников: побуквенное, адаптивное и универсальное кодирования, принцип кратчайшего описания, построение дерева контекстов и преобразование Барроуза–Уилера. Описаны наиболее известные методы сжатия данных: блочное, равномерное по выходу и арифметическое кодирования, схема кодирования Лемпела–Зива и методы интервального кодирования. Для перечисленных методов приведены оценки избыточности, времени кодирования и декодирования, а также объема памяти, используемой при реализации методов. Даны схемы доказательства для некоторых наиболее важных утверждений. Кроме того, рассмотрены задачи рандомизации сообщений и кодирования с синхронизацией, а также способы кодирования текстов на естественных языках и источников с низкой энтропией. Ил. 3, библиогр. 123.