- Артикул:00-01117892
- Автор: Р. Е. Кричевский
- ISBN: 5-256-00325-9
- Тираж: 8400 экз.
- Обложка: Мягкая обложка
- Издательство: Радио и связь (все книги издательства)
- Город: Москва
- Страниц: 168
- Формат: 60х90/16
- Год: 1989
- Вес: 211 г
Развернуть ▼
Книга посвящена изложению теории кодирования источника - раздела теории информации, изучающего методы компактного представления данных. В книгу включены классические результаты, никакие предварительные знания для чтения не требуются. Особое внимание уделяется достижениям последнего времени, которые еще не нашли монографического освещения. Среди них - теория универсального кодирования, теоретико-информационная трактовка проблемы поиска в словарях, приложения к корректирующим кодам. Книга носит теоретический характер, но приводятся примеры, относящиеся к факсимильному кодированию, телефонной и спутниковой связи, построению определителей растений и животных. Нас интересует прежде всего взаимосвязь между степенью сжатия и его сложностью.
Разработаны алгоритмы универсального кодирования, не требующие точного знания характеристик источника для осуществления хорошего сжатия.
Рассмотрение проблемы поиска с точки зрения теории кодирования источника позволило установить минимальные размеры поисковых программ. Разработаны простые способы построения поисковых программ с использованием теории полей Галуа.
Для научных работников - специалистов в области теории связи и информатики.
Содержание
Предисловие
Введение
Глава 1. Источники сообщений и их энтропия
§ 1.1. Конечные комбинаторные источники
§ 1.2. Компакты и их е-энтропия
§ 1.3. Вероятностные источники
§ 1.4. Стационарные источники
Глава 2. Стоимость кодирования
§ 2.1. Деревья и префиксные коды
§ 2.2. Неравенство Крафта. Код Левенштейна
§ 2.3. Кодирование конечных комбинаторных источников
§ 2.4. Колмогоровская сложность
§ 2.5. Кодирование конечных вероятностных источников
§ 2.6. Равновероятные буквы. Пороговые функции
§ 2.7. Блочное кодирование стационарных источников
§ 2.8. Неблочное кодирование
§ 3.1. Кодирование классов вероятностных источников
§ 3.2. Универсальное кодирование источников Бернулли
§ 3.3. Адантивное кодирование
§ 3.4. Монотонные источники
§ 3.5. Кодирование классов комбинаторных источников
§ 3.6. Универсальное кодирование стационарных последовательностей
Глава 4. Методы поиска информации
§ 4.1. Лексикографический поиск
§ 4.2. Побуквенный поиск
§ 4.3. Нумерационный поиск
§ 4.4. Хеширование. Индекс склеивания
Глава 5. Универсальные множества сжимающих отображений
§ 5.1. Распределение кластеров
§ 5.2. Вероятности больших уклонений
§ 5.3. Универсальные множества нумераторов
§ 5.4. Универсальные хеш-множества
§ 5.5. Универсальные множества на основе кодов
§ 5.6. Универсальные множества на основе полей Галуа
Глава 6. Сложность кодирования комбинаторных источников
§ 6.1. Кодирование комбинаторного источника с большой избыточностью
§ 6.2. Каналы с произвольным аддитивным шумом
§ 6.3. Кодирование комбинаторного источника с малой избыточностью
§ 6.4. Сложность хеширования
§ 6.5. Эффективное построение нумераторов
§ 6.6. Эффективное построение хеш-функций
§ 6.7. Основные выводы
Глава 7. Сложность кодирования вероятностных источников
§ 7.1. Произвольные конечные вероятностные источники
§ 7.2. Сложность кодирования марковских и бернуллиевских источников
§ 7.3. Равномерный по выходу универсальный код
§ 7.4. Сжатие с помощью стоики книг
§ 7.5. Автоматное сжатие
Приложение. Построение универсальных нумераторов
Основные обозначения
Список литературы