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

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