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

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

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

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

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

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

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

Система коллажей представляет собой пару $⟨\mathcal{D},\mathcal{S}⟩$, определенную следующим образом. $\mathcal{D}$ - это последовательность присваиваний $X_1=exp{r}_1,X_2=exp{r}_2,...,X_n=exp{r}_n$, где для каждого k = 1,..., n элемент $X_k$ является переменной, а $exp{r}_k$ имеет любую из следующих форм:

$a$ для $a\in \mathrm{\Sigma }\cup \{ϵ\}$ (примитивное присваивание)

$X_i{X}_j$ для i, j < k (конкатенация)

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

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

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

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

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

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

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

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

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

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

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

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

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

Для схемы сжатия LZ77 Фарах и Торуп [6] представили следующий результат.

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

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

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

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

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

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

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

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

Существует множество вариантов задачи CPM. Далее некоторые из них будут вкратце рассмотрены.

Алгоритм сравнения с шаблоном для полностью сжатого текста (Fully-compressed pattern matching, FCPM) – это сложный вариант, в котором и T, и P даны в сжатом формате. Прямолинейная программа представляет собой регулярную систему коллажей с $|\mathcal{S}|=1$.

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

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

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

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

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

Теорема 10 (Наварро [14]). Задача RCPM решается за время $O(2^{|P|}+|P|\cdot |\mathbf{c}(T)|+occ\cdot |P|\cdot log|P|)$, где 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)