4511
правок
Усиление степени сжатия текста: различия между версиями
Перейти к навигации
Перейти к поиску
м
Усиление степени сжатия текста (посмотреть исходный код)
Версия от 20:53, 20 января 2017
, 20 января 2017→Алгоритм усиления степени сжатия
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 82: | Строка 82: | ||
Пусть A – алгоритм сжатия, такой, что для любой строки x размер ее выходного значения ограничен <math>|x| H_0(x) + \eta |x| + \mu \;</math> бит, где <math>\eta \;</math> и <math>\mu \;</math> – константы. Определим функцию стоимости | Пусть A – алгоритм сжатия, такой, что для любой строки x размер ее выходного значения ограничен <math>|x| H_0(x) + \eta |x| + \mu \;</math> бит, где <math>\eta \;</math> и <math>\mu \;</math> – константы. Определим функцию стоимости <math>C_A(x) = |x| H_0 (x) + \eta |x| + \mu \;</math>. В работе [3] Ферраджина и коллеги используют жадный алгоритм с линейным временем выполнения, вычисляющий оптимальное листовое покрытие <math>\mathcal{L}_{min} \;</math> относительно <math>C_A \;</math>. Авторы работы [3] также показали, что для любого <math>k \ge 0 \;</math> существует листовое покрытие <math>\mathcal{L}_k \;</math> стоимостью CA(Lk) = jsj Hk(s) + rj\s\ + O(|^7|fc). Эти два важнейших наблюдения показывают, что при использовании A для сжатия каждой подстроки в разбиении, порожденном оптимальным листовым покрытием Lmin, общий размер выходного значения ограничени в терминах jsj Hk(s) для любого k > 0. На деле | ||
CA(s(u}) =CA(Lmin) < CA(Lk) in u2Lmin О(\Е\к) = jsjHk(s)+ | CA(s(u}) =CA(Lmin) < CA(Lk) in u2Lmin О(\Е\к) = jsjHk(s)+ | ||