Штарьков Ю.М. Универсальное кодирование. Теория и алгоритм

М.: Физматлит, 2013. — 380 с. — ISBN: 978-5-9221-1517-9.В книге рассматриваются проблемы теории информации и кодирования — области математики, имеющей эффективное приложение в задачах сжатия дискретных данных. При этом используются распределения вероятностей сжимаемых данных. На практике эти сведения не бывают полными. Поэтому были предложены и изучены методы и алгоритмы универсального кодирования при разных постановках задач, найдены оптимальные коды.
В последней главе приведены численные результаты для набора разных текстов, позволяющие сравнить эффективность разных алгоритмов и их версий.
Книга предназначена для студентов, аспирантов и научных сотрудников, работающих в области теории информации, универсального кодирования, их практического применения и смежных областях.Предисловие
ВведениеКодирование сообщений с известной статистикой
Кодирование и неравенство Крафта
Вероятностное посимвольное кодирование
Оптимальный и близкие к оптимальному коды
Оптимальные коды Хафмена. Коды Шеннона–Фано. Коды Гилберта–Мура.
Источники сообщений и блочные коды
Эргодические и стационарные источники
Источники без памяти
Марковские источники
Общий случай. Контекстные марковские источники. Контекстные источники.
Однородные марковские цепи
Неблочное кодирование
Общие соотношения. Переменное по входу кодирование L. Переменное по входу и выходу кодирование ?V.
Методы и алгоритмы кодирования
Составные коды. Равномерная нумерация блоков. Арифметическое кодирование. Бинаризация.
Синхронизуемое кодирование
Проблема переполнения буфера
Заключение к главеКритерий максимальной средней избыточности
Постановка задачи
Метод комбинаторного кодирования
Источники без памяти. Источники с вычислимыми состояниями. Составные коды и достаточные статистики. Стационарные источники с известным алфавитом.
Метод взвешивания
Общее описание метода. Источники без памяти с конечным алфавитом. Источники с вычислимыми состояниями. Счетный алфавит: пуассоновские источники.
Нижние границы максимальной средней избыточности
Нижняя граница взвешивания. Нижняя граница для подмножества источников. О выборе взвешивающего распределения.
Переменное по входу кодирование
Использование выборки
Постановки задач. Адаптивное кодирование источников без памяти. Адаптивное кодирование пуассоновских источников. Об адаптивном кодировании источников с памятью. Скользящее окно и виртуальный буфер.
Алгоритм «Стопка книг»
Заключение к главе
Приложение ПКритерий максимальной индивидуальной избыточности
Индивидуальная избыточность и МВ-коды
МВ-коды для источников без памяти
МВ-коды для подмножеств источников без памяти
Источники без памяти со счетным алфавитом
Невозрастающие вероятности символов. Пуассоновские источники.
Функции цели и локальная оптимизация
Взвешенные коды для источников без памяти
Индивидуальная избыточность: ? ,. Индивидуальная избыточность: ? < ,. Кодирование после бинаризации.
Взвешивание для источников с вычислимыми состояниями
Общий подход. Использование однократности некоторых переходов.
Множество однородных марковских цепей
Взвешенное кодирование. Избыточность МВ-кодов. Сложность реализации. Обсуждение результатов.
МВ-метод для фрагментов переменной длины
Функции ограничений и множества фрагментов.
Источники без памяти: общие оценки. Равномерное ограничение избыточности. Убывающая функция длины фрагмента.
МВ-метод и критерий относительной избыточности
Общие соотношения. МВ-метод: длины кодовых слов или фрагментов. Подмножества двоичных источников без памяти.
Избыточность адаптивного кодирования
МВ-коды и переполнение буфера
Матричное кодирование
Универсальное кодирование и прогнозирование
Заключение к главе
Приложение ПМинимальные длины описания сообщений
Основные определения и соотношения
Некоторые конструкции МДО-кодов
Источники без памяти: блочный алфавитный код
Последовательные алфавитные коды
Двойное взвешивание. Взвешивание после бинаризации. Локальная оптимизация. Источники с вычислимыми состояниями.
Счетные семейства моделей
Ограничение числа используемых моделей. Семейство простых марковских источников. Более общие счетные семейства. Адаптивное кодирование.
Алгоритмы Лемпела–Зива
Алгоритм LZ-. Алгоритм LZ-.
Краткое обсуждение.
Колмогоровская (алгоритмическая) сложность
Основные понятия. Функции колмогоровской сложности. Колмогоровская сложность и МДО-коды.
МДО-коды и проверка статистических гипотез
Заключение к главеСемейство контекстных марковских моделей
Контекстные модели
Текущее оценивание модели
Алгоритм «Контекст» (R-)
Алгоритм WLZ-
Алгоритм WRF-
Текущее МДО-оценивание
Версии текущего МДО-оценивания
МДО: минимизация текущей скорости кодирования.
МДО: Нечеткое оценивание модели.
Контекстно-древовидное взвешивание (CTW)
Описание КМ-моделей. Взвешивание.
Избыточность и сложность CTW. Бинаризация и CTW.
Уменьшение избыточности CTW
Алфавитный CTW. О взвешивающих вероятностях.
Обобщения CTW
Разные группировки контекстов. Описание первых d символов блока.
Заключение к главеАлгоритмы сжатия
Версии и архиваторы алгоритмов Лемпела–Зива
Общие свойства алгоритма PPM
Версии PPM
Условная вероятность спуска. Обновление и масштабирование частот. Контексты неограниченной длины. Экспериментальные результаты.
Обобщения PPM
Обобщенные частоты символов. Оценка вероятности спуска. Эффективность и сложность реализации.
Объединение алгоритмов
Алгоритмы CTW и PPM. Взвешенное переключение алгоритмов. Алгоритм «змейка».
Версия «змейки».
Преобразование Барроуза–Уиллера (BWT)
Описание BWT. Некоторые свойства и кодирование BWT.
Сжатие двумерных числовых данных
Описание коэффициентов двумерного разложения.
Сжатие рентгеновских томограмм: предсказание.
Вейвлетпреобразование рентгеновских томограмм.
Заключение к главеЗаключение
Список литературы