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

Пусть имеются <math>\mathbf{c}</math> – заданный алгоритм сжатия, <math>\mathbf{c}</math>(A) – результат сжатия строки A; даны строка шаблонов P и сжатый текст <math>\mathbf{c}</math>(T). Задача ''сравнения с шаблоном для сжатого текста'' (compressed pattern matching, CPM) заключается в поиске всех вхождений P в T без распаковки T. Целью является выполнение задачи за меньшее время по сравнению с распаковкой и последующим простым поиском, который требует O(|P| + |T|) времени (предполагая, что для распаковки достаточно O(|T|) времени). Алгоритм CPM называется оптимальным, если он выполняется за время O(|P| + |<math>\mathbf{c}</math>(T)|). CPM была впервые определена в работе Амира и Бенсона [1]; было выполнено множество исследований различных форматов сжатия.

Системы коллажей – это полезные CPM-ориентированные абстракции форматов сжатия, предложенные Кидой и коллегами [9]. Алгоритмы, разработанные для систем коллажей, можно применить для множества различных форматов сжатия. В той же статье был представлен общий алгоритм Кнута-Морриса-Пратта [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%BD%D1%83%D1%82%D0%B0_%E2%80%94_%D0%9C%D0%BE%D1%80%D1%80%D0%B8%D1%81%D0%B0_%E2%80%94_%D0%9F%D1%80%D0%B0%D1%82%D1%82%D0%B0|(KMP)] для систем коллажей. Использование общего алгоритма Бойера-Мура [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9C%D1%83%D1%80%D0%B0|(BM)] для систем коллажей было предложено почти той же группой авторов [18].

''Система коллажей'' представляет собой пару <math>\langle \mathcal{D}, \mathcal{S} \rangle</math>, определенную следующим образом. <math>\mathcal{D}</math> - это последовательность присваиваний <math>X_1 = expr_1, X_2 = expr_2, ..., X_n = expr_n</math>, где для каждого k = 1,..., n элемент <math>X_k</math> является переменной, а <math>expr_k</math> – любой из форм:

<math>X_i X_j</math> для i,j < k (конкатенация)

Под ''усечением префикса (или суффикса) длины j'' мы понимаем операцию над строками, которая берет строку w и возвращает строку, полученную из w путем удаления ее префикса (или суффикса) длины j. Переменные <math>X_k</math> представляют строки <math>\bar{X_k}</math>, полученные путем оценки их выражений. ''Размером'' <math>\mathcal{D}</math> является количество n присваиваний, обозначаемое <math>|\mathcal{D}|</math>. обозначим за <math>height(\mathcal{D})</math> максимальную зависимость в <math>\mathcal{D}</math>. <math>\mathcal{S}</math> – это последовательность <math>X_{i_1} ... X_{j_\ell}</math> переменных, определенных в <math>\mathcal{D}</math>. ''Длина'' <math>\mathcal{S}</math> представляет собой количество <math>\ell</math> переменных в <math>\mathcal{S}</math> и обозначается <math>|\mathcal{S}|</math>. Таким образом, можно считать, что <math>|\mathbf{c}(T)| = |\mathcal{D}| + |\mathcal{S}|</math>.

Система коллажей <math>\langle \mathcal{D}, \mathcal{S} \rangle</math> представляет собой строку, полученную путем конкатенации строк <math>\bar{X_{i_1}}, ..., \bar{X_{j_\ell}}</math>, представленных переменными <math>X_{i_1}, ..., X_{j_\ell}</math> из <math>\mathcal{S}</math>. Следует отметить, что любая система коллажей может быть преобразована в систему с <math>|\mathcal{S}| = 1</math> путем добавления серии присваиваний с операциями конкатенации в <math>\mathcal{D}</math>. Это может означать, что <math>\mathcal{S}</math> не нужна. Однако разнообразные схемы сжатия могут быть естественным образом отражены путем разделения <math>\mathcal{D}</math> (определение ''фраз'') и <math>\mathcal{S}</math> (результатом чего является факторизация текста T на фразы). Способы выражения сжатых текстов для существующих схем сжатия можно найти в [9].

Система коллажей называется ''свободной от усечений'', если <math>\mathcal{D}</math> не содержит операций усечения, и ''регулярной'', если <math>\mathcal{D}</math> не содержит ни повторений, ни операций усечения. Регулярная система коллажей является ''простой'', если <math>| \bar{Y} | = 1</math> или <math>| \bar{Z} | = 1</math> для каждого присваивания X = YZ. На рис. 1 представлена иерархия систем коллажей. Системы коллажей для RE-PAIR, SEQUITUR, Byte-Pair-Encoding (BPE) и схемы сжатия на основе грамматического преобразования являются регулярными. В семействе Лемпеля-Зива системы коллажей для LZ78/LZW просты, а системы для LZ77/LZSS не являются усеченными.

Расширение [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> опускается.'''

Существует множество вариантов задачи CPM. Далее некоторые из них будут вкратце рассмотрены. Алгоритм сравнения с шаблоном для полностью сжатого текста (Fully-compressed pattern matching, FCPM) – это сложный вариант, когда и T, и P даны в сжатом формате. Прямолинейная программа представляет собой регулярную систему коллажей с jSj = 1.

Теорема 7 (Миядзаки и др. [ ]). Задача FCPM для прямолинейных программ решается за время O(jc(T)j2 - |c(P)|2) с использованием O(jc(T) - \c{P)\) памяти.

Приближенное сравнение с шаблоном для сжатого текста (Approximate compressed pattern matching, ACPM) относится к случаю, когда допускаются ошибки.

Теорема 8 (Карккайнен и др. [ ]). При использовании модели расстояния Левенштейна задача ACPM может быть решена за время O(k ■ \P\ ■ c(T)j + occ) для LZ78/LZW и за время O(\P\ ■ (k2 ■ jDj + k-\S\) + occ) для обычных систем коллажей, где k – заданный порог ошибок.

Теорема 9 (Макинен и др. [ ]). При использовании модели взвешенного расстояния редактирования задача ACPM для кодирования длин серий может быть решена за время O(\P\ ■ \c(P)\ - c(T)j).

Сравнение регулярных выражений с шаблоном для сжатого текста (Regular expression compressed pattern matching, RCPM) имеет место в случае, когда P может быть регулярным выражением.

Теорема 10 (Наварро [ ]). Задача RCPM решается за время O(2jPj + |P| - c(T)j + occ ■ \P\ ■ log jPj), где occ – количество вхождений P в T.

Одной из важных целей задачи CPM является получение результата за более короткое время по сравнению с распаковкой и последующим простым поиском. Кида и др. [ ] экспериментально показали, что их алгоритмы достигают этой цели. Наварро и Тархио [15] представили алгоритмы типа BM (Бойера-Мура) для схем сжатия LZ78/LZW и показали, что они работают в два раза быстрее, чем декомпрессия с последующим поиском с использованием лучших алгоритмов. (Код доступен по адресу www.dcc.uchile.cl/gnavarro/software).