Том 6, серия 1, номер 4, 1999 г., Стр. 49-91

УДК 519.72
В. Н. Потапов
Обзор методов неискажающего кодирования дискретных источников

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

Потапов В. Н. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 15 сентября 1999 г.