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

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

Теорема 2 (Амир и др,. [ ]). CPM-версия задачи LZW для первого вхождения может быть решена за время O(jPj2 + jc(T)j) и с аналогичными требованиями к памяти.

Расширение [ ] до задачи сравнения с несколькими шаблонами (сравнение со словарем) было предложено Кидой и коллегами в работе [10], вместе с первыми экспериментальными результатами в этой области.

Теорема 3 (Фарах и Торуп [ ]). Пусть имеются сжатая алгоритмом LZ77 строка Z текста T и шаблон P. Существует рандомизированный алгоритм, определяющий, встречается ли P в T, за время O(jZjlog2(jTj/jZj) + jPj).

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

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

Результаты исследований Амира и коллег [ ] были обобщены в работе Киды и др. [9] в виде единой структуры систем коллажей.

Теорема 5 (Кида и др. [ ]). Задача CPM для систем коллажей может быть решена за время 0((\T>\ + \S\)- height (T))+\P\2+occ) с использованием O(jDj + jPj2) памяти, где occ – количество вхождений шаблона. Для систем коллажей без усечений коэффициент height(D) опускается.