RUS  ENG
Полная версия
ЖУРНАЛЫ // Проблемы передачи информации // Архив

Пробл. передачи информ., 1996, том 32, выпуск 1, страницы 35–40 (Mi ppi299)

Неравенства и алгоритмы универсального сжатия данных

Д. Зив


Аннотация: Описываются неасимптотические равномерные границы эффективности алгоритмов сжатия данных в случае, когда длина $N$ доступной для кодера обучающей выборки (“предыстории”) недостаточно велика для получения максимального сжатия, а именно, энтропии источника. Конечной целью является рассмотрение двух характеристик: энтропии $\ell$-го порядка $H(X_1^\ell)$ и связанной с ней условной энтропии $H(X_1^{\ell-k}|X_{-k+1}^0)$. Установленные границы основаны на классическом теоретико-информационном использовании свойства выпуклости. Тем не менее, показывается, что рассуждения о выпуклости, которые годятся для одних случаев, полностью бесполезны для других. Кроме того, эти классические рассуждения, если их правильно использовать, ведут к построению эффективных алгоритмов сжатия данных в каждом из рассмотренных случаев.
В работе рассматриваются только однозначно декодируемые коды с фиксированной длиной на входе и переменной длиной на выходе.

УДК: 621.391.1:519.28


 Англоязычная версия: Problems of Information Transmission, 1996, 32:1, 28–32

Реферативные базы данных:


© МИАН, 2024