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

Ключевые слова и синонимы

Сравнение строк в сжатом тексте; поиск по сжатой строке

Постановка задачи

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

Системы коллажей

Системы коллажей – это полезные CPM-ориентированные абстракции форматов сжатия, предложенные Кидой и коллегами [9]. Алгоритмы, разработанные для систем коллажей, можно применить для множества различных форматов сжатия. В той же статье был представлен общий алгоритм Кнута-Морриса-Пратта [1] для систем коллажей. Использование общего алгоритма Бойера-Мура [2] для систем коллажей было предложено почти той же группой авторов [18].

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

[math]\displaystyle{ a }[/math] для [math]\displaystyle{ a \in \Sigma \cup \{ \epsilon \} }[/math] (примитивное присваивание)

[math]\displaystyle{ X_i X_j }[/math] для i,j < k (конкатенация)

[math]\displaystyle{ ^{[j]}X_i }[/math] для i < k и целого положительного числа j (усечение префикса длины j)

[math]\displaystyle{ X_i^{[j]} }[/math] для i < k и целого положительного числа j (усечение суффикса длины j)

[math]\displaystyle{ (X_i)^j }[/math] для i < k и положительного целого числа ј (j-кратное повторение)

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

Рисунок 1. Иерархия систем коллажей

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

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

Основные результаты

Разработать оптимальное решение для кодирования длин серий несложно. Для двумерного кодирования длин серий, используемого при передаче факсимильных изображений, оптимальное решение было предложено Амиром, Бенсоном и Фарахом [3].

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

Те же авторы предложили в [2] почти оптимальное решение для LZW-сжатия.

Теорема 2 (Амир и др,. [2]). CPM-версия задачи LZW для первого вхождения может быть решена за время [math]\displaystyle{ O(|P|^2 + |\mathbf{c}(T)|) }[/math] и с аналогичными требованиями к памяти.

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

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

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

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

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

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

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

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

Теорема 6 (Амир и др,. [4]). Существует CPM-алгоритм типа inplace для двумерной схемы кодирования длин серий, который работает за время [math]\displaystyle{ O(|\mathbf{c} (T)| + |P| \; log \; \sigma) }[/math], используя [math]\displaystyle{ O(\mathbf{c}(P)) }[/math] дополнительной памяти, где [math]\displaystyle{ \sigma }[/math] – минимальное значение из |P| и размера алфавита.

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

Теорема 7 (Миядзаки и др. [13]). Задача FCPM для прямолинейных программ решается за время [math]\displaystyle{ O(|\mathbf{c}(T)|^2 \cdot |\mathbf{c}(P)|^2) }[/math] с использованием [math]\displaystyle{ O(|\mathbf{c}(T)| \cdot |\mathbf{c}(P)|) }[/math] памяти.

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

Теорема 8 (Карккайнен и др. [8]). При использовании модели расстояния Левенштейна задача ACPM может быть решена за время [math]\displaystyle{ O(k \cdot |P| \cdot |\mathbf{c}(T)| + occ) }[/math] для LZ78/LZW и за время [math]\displaystyle{ O(|P| \cdot (k^2 \cdot |\mathcal{D}| + k \cdot |\mathcal{S}|) + occ) }[/math] для обычных систем коллажей, где k – заданный порог ошибок.

Теорема 9 (Макинен и др. [11]). При использовании модели взвешенного расстояния редактирования задача ACPM для кодирования длин серий может быть решена за время [math]\displaystyle{ O(|P| \cdot |\mathbf{c}(P)| \cdot |\mathbf{c}(T)) }[/math].

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

Теорема 10 (Наварро [14]). Задача RCPM решается за время [math]\displaystyle{ O(2^{|P|} + |P| \cdot |\mathbf{c}(T)| + occ \cdot |P| \cdot log |P|) }[/math], где occ – количество вхождений P в T.

Применение

Техники CPM позволяют осуществлять поиск непосредственно в базах данных сжатого текста. Одним из перспективных приложений является поиск в базах данных сжатого текста на портативных устройствах, у которых память, хранилище и мощность процессора ограничены.

Экспериментальные результаты

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

Еще одна непростая цель заключается в выполнении задачи CPM быстрее простого поиска по исходным файлам в несжатом формате. Эта цель была достигнута Манбером [12] (с его собственной схемой сжатия) и Шибатой и др. [17] (с BPE). Коэффициенты сокращения времени поиска у них почти совпадают с коэффициентами сжатия. К сожалению, коэффициенты сжатия не очень высоки. Де Мура и др. [5] достигли цели, используя байтовый код Хаффмана для слов. Коэффициент сжатия относительно высок, но поиск возможен только по целым словам и фразам.

См. также

• Многомерное сравнения с шаблоном для сжатого текста представляет собой более сложную версию CPM, в которой текст и шаблон являются многомерными строками в сжатом формате.
• Последовательное точное сравнение строк, последовательное приближенное сравнение строк, сравнение регулярных выражений, соответственно, относятся к упрощенным версиям алгоритмов CPM, ACPM и RCPM, в которых текст и шаблон задаются в виде несжатых строк.

Литература

1. Amir, A., Benson, G.: Efficient two-dimensional compressed matching. In: Proc. Data Compression Conference '92 (DCC'92), pp. 279 (1992)

2. Amir, A., Benson, G., Farach, M.: Let sleeping files lie: Pattern matching in Z-compressed files. J. Comput. Syst. Sci. 52(2), 299-307(1996)

3. Amir, A., Benson, G., Farach, M.: Optimal two-dimensional compressed matching. J. Algorithms 24(2), 354-379 (1997)

4. Amir, A., Landau, G.M., Sokol, D.: Inplace run-length 2d compressed search.Theor. Comput. Sci. 290(3), 1361 -1383 (2003)

5. de Moura, E., Navarro, G., Ziviani, N., Baeza-Yates, R.: Fast and flexible word searching on compressed text. ACM Trans. Inf. Syst. 18(2), 113-139(2000)

6. Farach, M., Thorup, M.: String-matching in Lempel-Ziv compressed strings. Algorithmica 20(4), 388-404 (1998)

7. Ga˛sieniec, L., Karpinski, M., Plandowski, W., Rytter, W.: Efficient algorithms for Lempel-Ziv encoding. In: Proc. 5th Scandinavian Workshop on Algorithm Theory (SWAT'96). LNCS, vol. 1097, pp. 392-403 (1996)

8. Karkkainen, J., Navarro, G., Ukkonen, E.: Approximate string matching on Ziv-Lempel compressed text. J. Discret. Algorithms 1 (3-4), 313-338 (2003)

9. Kida, T., Matsumoto, T., Shibata, Y., Takeda, M., Shinohara, A., Arikawa, S.: Collage systems: a unifying framework for compressed pattern matching. Theor. Comput. Sci. 298(1), 253-272 (2003)

10. Kida, T., Takeda, M., Shinohara, A., Miyazaki, M., Arikawa, S.: Multiple pattern matching in LZW compressed text. J. Discret. Algorithms 1 (1), 133-158 (2000)

11. Makinen, V., Navarro, G., Ukkonen, E.: Approximate matching of run-length compressed strings. Algorithmica 35(4), 347-369 (2003)

12. Manber, U.: A text compression scheme that allows fast searching directly in the compressed file. ACM Trans. Inf. Syst. 15(2), 124-136(1997)

13. Miyazaki, M., Shinohara, A., Takeda, M.: An improved pattern matching algorithm for strings in terms of straight-line programs. J.Discret. Algorithms 1(1), 187-204 (2000)

14. Navarro, G.: Regular expression searching on compressed text. J. Discret. Algorithms 1 (5-6), 423-443 (2003)

15. Navarro, G., Tarhio, J.: LZgrep: A Boyer-Moore string matching tool for Ziv-Lempel compressed text. Softw. Pract. Exp. 35(12), 1107-1130(2005)

16. Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci. 302(1-3), 211-222 (2003)

17. Shibata, Y., Kida, T., Fukamachi, S., Takeda, M., Shinohara, A., Shinohara, T., Arikawa, S.: Speeding up pattern matching by text compression. In: Proc. 4th Italian Conference on Algorithms and Complexity (CIAC'00). LNCS, vol. 1767, pp. 306-315. Springer, Heidelberg (2000)

18. Shibata, Y., Matsumoto, T., Takeda, M., Shinohara, A., Arikawa, S.: A Boyer-Moore type algorithm for compressed pattern matching. In: Proc. 11th Annual Symposium on Combinatorial Pattern Matching (CPM'00). LNCS, vol. 1848, pp. 181-194. Springer, Heidelberg (2000)