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

Материал из WEGA
Перейти к навигации Перейти к поиску

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

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

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

Пусть имеются [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. Иерархия систем коллажей


Система коллажей 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] достигли цели, используя байтовый код Хаффмана для слов. Коэффициент сжатия относительно высок, но поиск возможен только по целым словам и фразам.

См. также

Литература

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)

Источник — http://pco.iis.nsk.su/wega/index.php?title=Сравнение_с_шаблоном_для_сжатого_текста&oldid=14668