Усиление степени сжатия текста: различия между версиями

Аналогичный результат имеет место и для модифицированной энтропии <math>H^*_k \;</math> (однако доказать его намного сложнее): пусть дан алгоритм сжатия A, который сжимает любую строку x до не более чем <math>\lambda |x| \; H^*_0 (x) + \mu</math> бит. Механизм усиления степени сжатия дает выходное значение, размер которого ограничен <math>\lambda |s| \; H^*_k(s) + log |s| + O(|\Sigma|^k)</math> бит одновременно для всех <math>k \ge 0 \;</math>. В работе [3] авторы также показали, что ни один алгоритм сжатия, удовлетворяющий некоторым мягким предположениям относительно его внутренних принципов работы, не способен получить схожую границу, не включающую одновременно мультипликативный коэффициент <math>\lambda \;</math> и аддитивный логарифмический терм. Кроме того, в [3] была предложена конкретизация усилителя, которая сжимает любую строку s до не более чем <math>2,5 |s| \; H^*_k(s) +log |s| + O(|\Sigma|^k)</math> бит. Эта граница аналитически превосходит границы, доказанные для лучших существующих алгоритмов сжатия, включая алгоритмы Лемпеля-Зива и [[алгоритм Барроуза-Уилера|Барроуза-Уилера]] и алгоритм PPM.