Приближенное сравнение регулярных выражений

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

Сравнение регулярных выражений, допускающее ошибки или разногласия

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

Пусть даны текстовая строка [math]\displaystyle{ T = t_1 t_2 ... t_n }[/math] и регулярное выражение R длины m, обозначающее язык [math]\displaystyle{ \mathcal{L}(R) }[/math], над алфавитом [math]\displaystyle{ \Sigma }[/math] размера [math]\displaystyle{ \sigma }[/math], а также функция расстояния между строками d и порог k. Задача приближенного сравнения регулярных выражений (approximate regular expression matching, AREM) заключается в нахождении всех текстовых позиций, завершающих так называемое приблизительное вхождение R в T; иначе говоря, в вычислении множества [math]\displaystyle{ \{ j, \exist i, 1 \le i \le j, \exist P \in \mathcal{L}(R), d(P, t_i ... t_j) \le k \} }[/math]. T, R и k уже заданы, при этом алгоритм может быть настроен для конкретного d.

Данная статья посвящена так называемому взвешенному расстоянию редактирования, представляющему собой минимальную сумму весов последовательности операций, преобразующих одну строку в другую. В число этих операций входят вставка, удаление и замена символов. Веса представляют собой положительные вещественные значения, ассоциированные с каждой операцией и каждым символом. Вес операции удаления символа [math]\displaystyle{ c }[/math] обозначим за [math]\displaystyle{ w(c \to \epsilon) }[/math], вес операции вставки [math]\displaystyle{ c }[/math] – за [math]\displaystyle{ w(\epsilon \to c) }[/math], вес операции замены [math]\displaystyle{ c }[/math] на [math]\displaystyle{ c' \neq c }[/math] – за [math]\displaystyle{ w(c \to c') }[/math]. Предполагается, что [math]\displaystyle{ w(c \to c) = 0 }[/math] для всех [math]\displaystyle{ c \in \Sigma \cup \epsilon }[/math] и что выполняется неравенство треугольника, то есть [math]\displaystyle{ w(x \to y) + w(y \to z) \ge w(x \to z) }[/math] для любых [math]\displaystyle{ x, y, z \in \Sigma \cup \{ \epsilon \} }[/math]. Поскольку расстояние может быть асимметричным, то постулируется, что d(A, B) – это стоимость преобразования A в B. Для простоты и практичности в данной статье предполагается m = o(n).

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

Наиболее универсальное решение этой задачи [3] строится на графовой модели процесса вычисления расстояния. Предположим, что регулярное выражение R преобразуется методом Томпсона [8] в недетерминированный конечный автомат (НКА) с O(m) состояний и переходов. Рассмотрим этот автомат в виде ориентированного графа G(V, E), ребра которого помечены элементами множества [math]\displaystyle{ \Sigma \cup \{ \epsilon \} }[/math]. Для решения задачи AREM строится ориентированный и взвешенный граф [math]\displaystyle{ \mathcal{G} }[/math]. [math]\displaystyle{ \mathcal{G} }[/math] формируется путем создания n + 1 копий [math]\displaystyle{ G, G_0, G_1, ..., G_n }[/math] и последующего присвоения им весов таким образом, чтобы свести расчет расстояния к задаче нахождения кратчайших путей в графе [math]\displaystyle{ \mathcal{G} }[/math].

Более формально: граф [math]\displaystyle{ \mathcal{G} }[/math] составляют вершины [math]\displaystyle{ \{v_i, v \in V, 0 \le i \le n \} }[/math], такие, что [math]\displaystyle{ v_i }[/math] является копией вершины [math]\displaystyle{ v \in V }[/math] в графе [math]\displaystyle{ G_i }[/math]. Для каждого ребра [math]\displaystyle{ u \xrightarrow{c} v }[/math] в E, [math]\displaystyle{ c \in \Sigma \cup \{ \epsilon \} }[/math], к графу [math]\displaystyle{ \mathcal{G} }[/math] добавляются следующие ребра:

[math]\displaystyle{ u_i \to v_i }[/math] с весом [math]\displaystyle{ w(c \to \epsilon), 0 \le i \le n, }[/math]

[math]\displaystyle{ u_i \to u_{i + 1} }[/math] с весом [math]\displaystyle{ w(\epsilon \to t_{i + 1}), 0 \le i \lt n, }[/math]

[math]\displaystyle{ u_i \to v_{i + 1} }[/math] с весом [math]\displaystyle{ w(c \to t_{i + 1}), 0 \le i \lt n. }[/math]

Для простоты предположим, что G имеет начальное состояние s и уникальное конечное состояние f (это всегда можно организовать). По определению, самый короткий путь в [math]\displaystyle{ \mathcal{G} }[/math] из [math]\displaystyle{ s_0 }[/math] в [math]\displaystyle{ f_n }[/math] дает наименьшее расстояние между T и строкой в [math]\displaystyle{ \mathcal{L}(R) }[/math]. Чтобы адаптировать граф к задаче AREM, веса ребер между [math]\displaystyle{ s_i }[/math] и [math]\displaystyle{ s_{i + 1} }[/math] полагаем нулевыми.

Таким образом, задача AREM сводится к вычислению кратчайших путей. Нетрудно заметить, что [math]\displaystyle{ \mathcal{G} }[/math] можно топологически отсортировать так, чтобы все пути к вершинам в [math]\displaystyle{ G_i }[/math] вычислялись раньше всех путей к вершинам в [math]\displaystyle{ G_{i + 1} }[/math]. Таким способом можно легко решить задачу нахождения кратчайших путей, для чего потребуется время O(mn log m) и память O(m). На самом деле, если ограничить задачу этим конкретным случаем сетевых выражений, которые являются регулярными выражениями без замыкания Клини, то G не имеет циклов, а вычисление кратчайших путей может быть выполнено за время O(mn) и за еще более короткое время в среднем [2].

Наиболее деликатная часть процесса достижения времени O(mn) для регулярных выражений общего вида [3] заключается в том, чтобы доказать, что с учетом типов циклов, возникающих в НКА регулярных выражений, можно правильно вычислить расстояния внутри каждого [math]\displaystyle{ G_i }[/math], выполнив три действия: (а) вычислить расстояния в топологическом порядке [math]\displaystyle{ G_i }[/math] без учета обратных ребер, введенных замыканием Клини; (б) обновить стоимости путей за счет однократного использования обратных ребер; (в) обновить стоимости путей еще раз в топологическом порядке, вновь игнорируя обратные ребра.

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

Для целочисленных весов можно получить лучший результат за счет использования RAM-модели с единичной стоимостью при помощи «метода четырех русских». Идея заключается в следующем. Возьмем небольшое подвыражение R, порождающее НКА, который будет преобразовываться в небольшой подграф каждого графа [math]\displaystyle{ G_i }[/math]. В момент распространения стоимостей путей по этому автомату с каждой вершиной будет связан счетчик, (говорящий о текущем кратчайшем пути из [math]\displaystyle{ s_0 }[/math]). Этот счетчик может быть сведен к числу в диапазоне [0, k + 1], где k + 1 обозначает «больше, чем k». Если небольшой НКА имеет r состояний, то для полного описания счетчиков соответствующего подграфа [math]\displaystyle{ G_i }[/math] требуется [math]\displaystyle{ r \lceil log_2 \; (k + 2) \rceil }[/math] бит. Более того, зная начальный набор значений для счетчиков, можно предварительно вычислить будущее распространение, которое будет происходить в пределах одного подграфа [math]\displaystyle{ G_i }[/math], в таблице, имеющей [math]\displaystyle{ 2^{r \lceil log_2 \; (k + 2) \rceil} }[/math] записей – по одной на каждую возможную конфигурацию счетчиков. Чтобы стоимость построения и хранения этих таблиц была ограничена o(n), достаточно обеспечить выполнение соотношения [math]\displaystyle{ r \lt \alpha \; log_{k + 2} \; n }[/math] для некоторого [math]\displaystyle{ \alpha \lt 1 }[/math]. При помощи этих таблиц распространение внутри подграфа можно осуществить за константное время. Аналогично, распространение стоимостей по одному и тому же подграфу в [math]\displaystyle{ G_{i + 1} }[/math] также может быть предварительно вычислено в таблицах, поскольку оно зависит только от текущих счетчиков в [math]\displaystyle{ G_i }[/math] и от символа текста [math]\displaystyle{ t_{i + 1} }[/math], для которых существует только [math]\displaystyle{ \sigma }[/math] альтернативных вариантов.

Теперь возьмем все поддеревья R, максимальный размер которых не превышает r, и предварительно обработаем их при помощи вышеприведенной техники. Преобразуем каждое такое поддерево в лист в R, помеченный специальным символом [math]\displaystyle{ a_A }[/math], ассоциированным с соответствующим небольшим НКА A. Если в R нет последовательных замыканий Клини, которые можно упростить как R** = R*, то размер R после этого преобразования составит O(m/r). Обозначим преобразованное регулярное выражение за R'. В сущности, к R' применяется техника теоремы 1, которая говорит о том, как обращаться с особыми листьями, соответствующими небольшим НКА. Эти листья при помощи построения Томпсона преобразуются в две вершины, соединенных с ребром с меткой [math]\displaystyle{ a_A }[/math]. Когда процесс распространения стоимости пути достигает вершины-источника ребра с меткой [math]\displaystyle{ a_A }[/math] со стоимостью c, необходимо обновить счетчик начального состояния НКА A до c (или k + 1, если c > k). Затем с помощью таблицы «метода четырех русских» можно выполнить все операции распространения стоимости в пределах A за константное время и, наконец, получить в счетчике конечного состояния A новое значение для целевой вершины ребра, помеченного [math]\displaystyle{ a_A }[/math], в НКА верхнего уровня. Таким образом, все ребра (обычные и особые) НКА верхнего уровня могут быть пройдены за константное время, поэтому с помощью теоремы 1 стоимости в [math]\displaystyle{ G_i }[/math] можно получить за время O(mn/r). После этого стоимости переносятся в [math]\displaystyle{ G_{i + 1} }[/math], используя таблицы «четырех русских» для получения текущих значений счетчиков каждого подграфа [math]\displaystyle{ G_{i + 1} }[/math].

Теорема 2 (Ву и коллеги, 1995 [10]). Для случая целочисленных весов существует решение с временем выполнения [math]\displaystyle{ O(n + mn/log_{k + 2} \; n) }[/math] в наихудшем случае для задачи AREM с использованием взвешенного расстояния редактирования.

Применение

Эта задача применяется в вычислительной биологии для нахождения определенных типов мотивов в ДНК и последовательностях белка. Подробнее об этом см. обсуждение в работе [1]. В частности, ограниченными регулярными выражениями являются шаблоны PROSITE, достаточно широко применяющиеся при поиске последовательностей белка. На практике шаблоны PROSITE можно искать при помощи более быстрых алгоритмов [7]. То же происходит и с другими классами сложных шаблонов [6] и сетевыми выражениями [2].

Открытые вопросы

Сложность задачи AREM в наихудшем случае не вполне понятна. Разумеется, ее можно описать значением [math]\displaystyle{ \Omega(n) }[/math], которое было достигнуто для m log(k + 2) = O(log n); но неизвестно, насколько его можно улучшить.

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

О некоторых недавних экспериментах сообщается в работе [5]. Для малых значений m и k, и предполагая, что все веса равны 1 (за исключением [math]\displaystyle{ w(c \to c) = 0) }[/math], битово-параллельные алгоритмы со сложностью в наихудшем случае [math]\displaystyle{ O(kn(m /log \; n)^2) }[/math] [4 , 9] являются самыми быстрыми (второй из них способен пропускать некоторые символы текста в зависимости от R). Для произвольных целочисленных весов наилучшим выбором является более сложный битово-параллельный алгоритм [5] либо алгоритм на основе метода «четырех русских» [10] для больших значений m и k. Первоначальный алгоритм [3] работает медленнее, однако только он поддерживает произвольные веса.

Ссылка на код

Эффективное решение задачи AREM (для случая упрощенного выбора веса) обеспечивают такие хорошо известные пакеты, как agrep (http://webglimpse.net/download.html, поддиректория верхнего уровня agrep/) и nrgrep (http://www.dcc.uchile.cl/~gnavarro/software). Для биологических приложений пакет anrep [2] (http://www.cs.arizona.edu/people/gene/CODE/anrep.tar.Z) сопоставляет последовательности приблизительных сетевых выражений с произвольными весами и заданной величиной гэпа между каждым сетевым выражением и последующим.

См. также

• Сравнение регулярных выражений – более простой случай, в котором ищется точное совпадение со строками в L(R).
• Последовательное приближенное сравнение строк – упрощение данной задачи; в этом случае связь между графом G и матрицей C должна быть очевидной.

Литература

1. Gusfield, D.: Algorithms on strings, trees and sequences. Cambridge University Press, Cambridge (1997)

2. Myers, E.W.: Approximate matching of network expressions with spacers. J.Comput.Biol. 3(1), 33-51 (1996)

3. Myers, E.W., Miller, W.: Approximate matching of regular expressions. Bullet. Math. Biol. 51, 7-37 (1989)

4. Navarro, G.: Nr-grep: a fast and flexible pattern matching tool. Softw. Pr. Exp. 31,1265-1312 (2001)

5. Navarro, G.: Approximate regular expression searching with arbitrary integer weights. Nord. J. Comput. 11 (4), 356-373 (2004)

6. Navarro, G., Raffinot, M.: Flexible Pattern Matching in Strings - Practical on-line search algorithms for texts and biological sequences. Cambridge University Press, Cambridge (2002)

7. Navarro, G., Raffinot, M.: Fast and simple character classes and bounded gaps pattern matching, with applications to protein searching. J. Comput. Biol. 10(6), 903-923 (2003)

8. Thompson, K.: Regular expression search algorithm. Commun. ACM 11(6),419-422 (1968)

9. Wu, S., Manber, U.: Fast text searching allowing errors. Commun. ACM 35(10), 83-91 (1992)

10. Wu, S., Manber, U., Myers, E.W.: A subquadratic algorithm for approximate regular expression matching. J. Algorithms 19(3), 346-360(1995)