4430
правок
Усиление степени сжатия текста: различия между версиями
Материал из WEGA
Усиление степени сжатия текста (посмотреть исходный код)
Версия от 21:05, 20 января 2017
, 20 января 2017→Алгоритм усиления степени сжатия
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 97: | Строка 97: | ||
Теорема 1 ([Ферраджина и др., 2005). Пусть A – алгоритм сжатия, который сжимает любую строку x до размера не более | '''Теорема 1 ([Ферраджина и др., 2005). Пусть A – алгоритм сжатия, который сжимает любую строку x до размера не более <math>|x| H_0(x) + \eta |x| + \mu \;</math> бит. Механизм усиления степени сжатия, примененный к A, дает выходное значение, размер которого ограничен <math>|s| H_k(s) + log |s| + \eta |s| + O(|\Sigma|^k) \;</math> бит одновременно для всех <math>k \ge 0 \;</math>. Учитывая A, механизм усиления привносит в процесс сжатия дополнительные накладные расходы на память в размере O(|s| log |s|) бит, но не вносит дополнительных затрат времени.''' | ||
Аналогичный результат имеет место и для модифицированной энтропии <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. | |||
Аналогичный результат имеет место и для модифицированной энтропии (однако доказать его намного сложнее): пусть дан алгоритм сжатия A, который сжимает любую строку x до не более чем | |||
== Применение == | == Применение == | ||
