Учеб. метод. пособие. — Н. Новгород: Изд-во ННГУ, 2007. — 80 с.
В учебно-методических материалах освещаются вопросы экономного
кодирования информации. Для различных классов языков сообщений
излагаются теоретические результаты, характеризующие возможности
сжатия информации при учете ее вероятностных и структурных свойств.
Приводится краткий обзор методов кодирования, применяемых в
приложениях.
Для преподавателей, научных работников, аспирантов и студентов, специализирующихся в области дискретной математики и теории кодирования, или интересующихся проблемами теории кодирования. Содержание
Алфавитное кодирование
Основные определения
Проблема распознавания взаимной однозначности алфавитного кодирования
Алгоритм построения префиксного кода по набору длин элементарных кодов
Алгоритмы экономного алфавитного кодирования
Возможности сжатия при алфавитном кодировании, учитывающем синтаксис языка сообщений
Кодирование вероятностных источников с конечным числом состояний
Вопросы кодирования стохастических языков. Соотношение между стоимостью оптимального кодирования и энтропией стохастического языка
Основные определения, относящиеся к кодированию стохастических языков
Соотношение между стоимостью оптимального кодирования и энтропией для произвольного стохастического языка
Вопросы кодирования контекстно-свободных языков
Основные определения и понятия, связанные с КС-языками и стохастическими КС-языками
Связь стоимости оптимального кодирования стохастического КС-языка с энтропией и матрицей первых моментов
Метод укрупнения правил КС-грамматики
Неразрешимость проблем, связанных с кодированием стохастических КС-языков
Кодирование стохастических КС-языков в докритическом случае
Кодирование стохастических КС-языков в критическом случае
Краткий обзор методов экономного кодирования, используемых в приложениях
Арифметическое кодирование
Алгоритмы Зива-Лемпеля
Преобразование Барроуза-Уилера
Для преподавателей, научных работников, аспирантов и студентов, специализирующихся в области дискретной математики и теории кодирования, или интересующихся проблемами теории кодирования. Содержание
Алфавитное кодирование
Основные определения
Проблема распознавания взаимной однозначности алфавитного кодирования
Алгоритм построения префиксного кода по набору длин элементарных кодов
Алгоритмы экономного алфавитного кодирования
Возможности сжатия при алфавитном кодировании, учитывающем синтаксис языка сообщений
Кодирование вероятностных источников с конечным числом состояний
Вопросы кодирования стохастических языков. Соотношение между стоимостью оптимального кодирования и энтропией стохастического языка
Основные определения, относящиеся к кодированию стохастических языков
Соотношение между стоимостью оптимального кодирования и энтропией для произвольного стохастического языка
Вопросы кодирования контекстно-свободных языков
Основные определения и понятия, связанные с КС-языками и стохастическими КС-языками
Связь стоимости оптимального кодирования стохастического КС-языка с энтропией и матрицей первых моментов
Метод укрупнения правил КС-грамматики
Неразрешимость проблем, связанных с кодированием стохастических КС-языков
Кодирование стохастических КС-языков в докритическом случае
Кодирование стохастических КС-языков в критическом случае
Краткий обзор методов экономного кодирования, используемых в приложениях
Арифметическое кодирование
Алгоритмы Зива-Лемпеля
Преобразование Барроуза-Уилера