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

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

'''Теорема 3 (Фарах и Торуп [6]). Пусть имеются сжатая алгоритмом LZ77 строка Z текста T и шаблон P. Существует рандомизированный алгоритм, определяющий, встречается ли P в T, за время <math>O(|Z| log^2 (|T|/|Z|) + |P|)</math>.'''

'''Теорема 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>.'''

'''Теорема 5 (Кида и др. [9]). Задача CPM для систем коллажей может быть решена за время <math>O((|\mathcal{D}| + |\mathcal{S}|) \cdot height(\mathcal{D})+|P|^2+occ)</math> с использованием <math>O(|\mathcal{D}| + |P|^2)</math> памяти, где occ – количество вхождений шаблона. Для систем коллажей без усечений коэффициент <math>height(\mathcal{D})</math> опускается.'''

Алгоритм [9] состоит из двух этапов. На первом этапе производится предварительная обработка D и P, а на втором – обработка переменных S. На втором этапе имитируется перемещение автомата KMP, работающего на несжатом тексте, с помощью двух функций Jump и Output. Обе эти функции принимают на вход состояние q и переменную X. Первая используется для замены только одного перехода состояния на последовательные переходы состояния автомата KMP для строки <math>\bar{X}</math> для каждой переменной X из S; вторая – для сообщения обо всех вхождениях шаблона, найденных во время переходов состояния. Пусть <math>\delta</math> – функция перехода состояний KMP-автомата. Тогда <math>Jump(q, X) = \delta(q, \bar{X})</math>, а Output(q,X) – множество длин |w| непустых префиксов w из <math>\bar{X}</math>, таких, что <math>\delta(q, w)</math> является конечным состоянием. Наивная реализация этих двух функций в виде двумерного массива требует памяти <math>\Omega(|\mathcal{D}| \cdot |P|)</math>. Структуры данных из [9] используют только <math>\Omega(|\mathcal{D}| + |P|^2)</math> памяти, строятся за время <math>\Omega(|\mathcal{D}| \cdot height(\mathcal{D}) + |P|^2)</math> и позволяют вычислить Jump(q,X) за O(1) времени и перенумеровать множество Output(q, X) за время <math>O(height(\mathcal{D}) + \ell)</math>, где <math>\ell = |Output(q, X)|</math>. Для систем коллажей без усечений коэффициент <math>height(\mathcal{D})</math> опускается.