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

Алгоритм [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] используют только O(jDj + jPj2) памяти, строятся за время O(\T)\ ■ height(D) + jPj2) и позволяют вычислить Jump(q,X) за O(1) времени и перенумеровать множество Output(q, X) за время O(height(D) + I), где I = jOutput(q; X)j. Для систем коллажей без усечений коэффициент height(D) опускается.

Другой критерий алгоритмов CPM основывается на объеме дополнительной памяти [ ]. Алгоритм CPM является алгоритмом типа inplace, если объем дополнительной памяти пропорционален размеру входных данных P.