Аноним

Сравнение с шаблоном для сжатого текста: различия между версиями

Материал из WEGA
м
Строка 38: Строка 38:




Теорема 1 (Амир и др,. [ ]). Существует оптимальное решение задачи CPM для двумерной схемы кодирования длин серий.
'''Теорема 1 (Амир и др,. [3]). Существует оптимальное решение задачи CPM для двумерной схемы кодирования длин серий.'''




Строка 44: Строка 44:




Теорема 2 (Амир и др,. [ ]). CPM-версия задачи LZW для первого вхождения может быть решена за время O(jPj2 + jc(T)j) и с аналогичными требованиями к памяти.
'''Теорема 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(jZjlog2(jTj/jZj) + jPj).
'''Теорема 3 (Фарах и Торуп [6]). Пусть имеются сжатая алгоритмом LZ77 строка Z текста T и шаблон P. Существует рандомизированный алгоритм, определяющий, встречается ли P в T, за время <math>O(|Z| log^2 (|T|/|Z|) + |P|)</math>.'''




Факторизация Лемпеля-Зива – это версия алгоритма сжатия LZ77 без автореференции. Между факторизациями Лемпеля-Зива и системами коллажей имеется следующее отношение.
Факторизация Лемпеля-Зива – это версия алгоритма сжатия LZ77 без ''автореференции''. Между факторизациями Лемпеля-Зива и системами коллажей имеется следующее отношение.




Теорема 4 ([Гатсинец и др. [ ], Риттер [ ]). Факторизация по Лемпеля-Зива Z по T может быть преобразована в систему коллажей размера O(\Z\ -log|Z|), порождающую T за время O(\Z\ - log jZj), и в обычную систему коллажей размера O(\Z\ -log jTj), порождающую T за время O(\Z\ -log jTj).
'''Теорема 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) опускается.




4551

правка