4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 38: | Строка 38: | ||
Теорема 1 (Амир и др,. [ ]). Существует оптимальное решение задачи CPM для двумерной схемы кодирования длин серий. | '''Теорема 1 (Амир и др,. [3]). Существует оптимальное решение задачи CPM для двумерной схемы кодирования длин серий.''' | ||
Строка 44: | Строка 44: | ||
Теорема 2 (Амир и др,. [ ]). CPM-версия задачи LZW для первого вхождения может быть решена за время O( | '''Теорема 2 (Амир и др,. [2]). CPM-версия задачи LZW для первого вхождения может быть решена за время <math>O(|P|^2 + |\mathbf{c}(T)|)</math> и с аналогичными требованиями к памяти.''' | ||
Расширение [ ] до задачи сравнения с несколькими шаблонами (сравнение со словарем) было предложено Кидой и коллегами в работе [10], вместе с первыми экспериментальными результатами в этой области. | Расширение [2] до задачи сравнения с несколькими шаблонами (сравнение со словарем) было предложено Кидой и коллегами в работе [10], вместе с первыми экспериментальными результатами в этой области. | ||
Для схемы сжатия LZ77 Фарах и Торуп [6] представили следующий результат. | Для схемы сжатия LZ77 Фарах и Торуп [6] представили следующий результат. | ||
Теорема 3 (Фарах и Торуп [ ]). Пусть имеются сжатая алгоритмом LZ77 строка Z текста T и шаблон P. Существует рандомизированный алгоритм, определяющий, встречается ли P в T, за время O( | '''Теорема 3 (Фарах и Торуп [6]). Пусть имеются сжатая алгоритмом LZ77 строка Z текста T и шаблон P. Существует рандомизированный алгоритм, определяющий, встречается ли P в T, за время <math>O(|Z| log^2 (|T|/|Z|) + |P|)</math>.''' | ||
Факторизация Лемпеля-Зива – это версия алгоритма сжатия LZ77 без автореференции. Между факторизациями Лемпеля-Зива и системами коллажей имеется следующее отношение. | Факторизация Лемпеля-Зива – это версия алгоритма сжатия LZ77 без ''автореференции''. Между факторизациями Лемпеля-Зива и системами коллажей имеется следующее отношение. | ||
Теорема 4 ([ | '''Теорема 4 ([Гасинец и др. [7], Риттер [16]). Факторизация по Лемпеля-Зива Z по T может быть преобразована в систему коллажей размера <math>O(|Z| \cdot log|Z|)</math>, порождающую T за время <math>O(|Z| \cdot log |Z|)</math>, и в обычную систему коллажей размера <math>O(|Z| \cdot log |T|)</math>, порождающую T за время <math>O(|Z| \cdot log |T|)</math>.''' | ||
Результаты исследований Амира и коллег [ ] были обобщены в работе Киды и др. [9] в виде единой структуры систем коллажей. | Результаты исследований Амира и коллег [2] были обобщены в работе Киды и др. [9] в виде единой структуры систем коллажей. | ||
Теорема 5 (Кида и др. [ ]). Задача CPM для систем коллажей может быть решена за время 0((\T>\ + \S\)- height (T))+\P\2+occ) с использованием O(jDj + jPj2) памяти, где occ – количество вхождений шаблона. Для систем коллажей без усечений коэффициент height(D) опускается. | Теорема 5 (Кида и др. [9]). Задача CPM для систем коллажей может быть решена за время 0((\T>\ + \S\)- height (T))+\P\2+occ) с использованием O(jDj + jPj2) памяти, где occ – количество вхождений шаблона. Для систем коллажей без усечений коэффициент height(D) опускается. | ||
правка