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

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

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

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

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

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

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

Система коллажей представляет собой пару hD; Si, определенную следующим образом. T) - это последовательность заданий X1 = expr1;X2 = expr2;: : : : ; Xn = exprn; где, для каждого k = 1,...n , X k является переменной, а exprk – любой из форм:

a для a 2 S U "g ; (примитивное присваивание)

XiXj для i;j< k ; (конкатенация)

[j]Xi для i < k и целого положительного числа j ; (усечение префикса длины j)

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

(Xi)j для i < k и положительного целого числа ј: (j-кратное повторение)

Под усечением префикса (или суффикса) длины j мы понимаем операцию над строками, которая берет строку w и возвращает строку, полученную из w путем удаления ее префикса (или суффикса) длины j. Переменные Xk представляют строки Xk, полученные путем оценки их выражений. Размер T) – это количество n присваиваний, обозначаемое jDj. обозначим за height(D) максимальную зависимость в D. S – это последовательность Xi 1 - - Xjt переменных, определенных в D. Длина S представляет собой количество I переменных в S и обозначается jSj. Таким образом, можно считать, что jc(T)j = jDj + jSj.

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

Система коллажей hD; Si представляет собой строку, полученную путем конкатенации строк Xi 1...: ; Xje, представленных переменными Xi 1...: ; Xje из S. Следует отметить, что любая система коллажей может быть преобразована в систему с jSj = 1 путем добавления серии присваиваний с операциями конкатенации в D. Это может означать, что S не нужна. Однако разнообразные схемы сжатия могут быть естественным образом отражены путем разделения D (определение фраз) и S (результатом чего является факторизация текста T на фразы). Способы выражения сжатых текстов для существующих схем сжатия можно найти в [9].

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

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

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

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

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

Теорема 2 (Амир и др,. [ ]). CPM-версия задачи LZW для первого вхождения может быть решена за время O(jPj2 + jc(T)j) и с аналогичными требованиями к памяти.

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

Теорема 3 (Фарах и Торуп [ ]). Пусть имеются сжатая алгоритмом LZ77 строка Z текста T и шаблон P. Существует рандомизированный алгоритм, определяющий, встречается ли P в T, за время O(jZjlog2(jTj/jZj) + jPj).

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

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

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

Теорема 5 (Кида и др. [ ]). Задача CPM для систем коллажей может быть решена за время 0((\T>\ + \S\)- height (T))+\P\2+occ) с использованием O(jDj + jPj2) памяти, где occ – количество вхождений шаблона. Для систем коллажей без усечений коэффициент height(D) опускается.

Алгоритм [ ] состоит из двух этапов. На первом этапе производится предварительная обработка D и P, а на втором – обработка переменных S. На втором этапе имитируется перемещение автомата KMP, работающего на несжатом тексте, с помощью двух функций Jump и Output. Обе эти функции принимают на вход состояние q и переменную X. Первая используется для замены только одного перехода состояния на последовательные переходы состояния автомата KMP для строки X для каждой переменной X из S; вторая – для сообщения обо всех вхождениях шаблона, найденных во время переходов состояния. Пусть S – функция перехода состояний KMP-автомата. Тогда Jump(q;X) = 8{q,X), а Output(q,X) – множество длин jwj непустых префиксов w из X, таких, что S(q, w) является конечным состоянием. Наивная реализация этих двух функций в виде двумерного массива требует памяти J2(|D| - |P|). Структуры данных из [ ] используют только 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.

Теорема 6 (Амир и др,. [ ]). Существует CPM-алгоритм типа inplace для двумерной схемы кодирования длин серий, который работает за время O(jc(T)j + jPj logcr), используя O(c(P)) дополнительной памяти, где a – минимальное значение среди jPj и размера алфавита.

Существует множество вариантов задачи 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 позволяют осуществлять поиск непосредственно в базах данных сжатого текста. Одним из перспективных приложений является поиск в базах данных сжатого текста на портативных устройствах, у которых память, хранилище и мощность процессора ограничены.

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

Одной из важных целей задачи CPM является получение результата за более короткое время по сравнению с распаковкой и последующим простым поиском. Кида и др. [ ] экспериментально показали, что их алгоритмы достигают этой цели. Наварро и Тархио [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)