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

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

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

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

Пусть даны текстовая строка [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]. Ориентированный и взвешенный граф [math]\displaystyle{ \mathcal{G} }[/math] построен для решения задачи AREM. [math]\displaystyle{ \mathcal{G} }[/math] формируется путем создания n + 1 копий [math]\displaystyle{ G, G_0, G_1, ..., G_n }[/math] и последующего присвоения им весов таким образом, чтобы свести расчет расcтояния к задаче нахождения кратчайших путей в графе [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] из s0 в fn дает наименьшее расстояние между T и строкой в L(R). Чтобы адаптировать граф к задаче AREM, меняем веса ребер между si и si+1 на ноль.

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

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

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

Для целочисленных весов можно получить лучший результат за счет использования RAM-модели с единичной стоимостью при помощи «метода четырех русских». Идея заключается в следующем. Возьмем небольшое подвыражение R, порождающее НКА, который будет преобразовываться в небольшой подграф каждого графа Gi. В момент распространения стоимостей путей по этому автомату с каждой вершиной будет связан счетчик, (говорящий о текущем кратчайшем пути из s0). Этот счетчик может быть сведен к числу в диапазоне [0, k + 1], где k + 1 обозначает «больше, чем k». Если небольшой НКА имеет r состояний, то для полного описания счетчиков соответствующего подграфа Gi требуется r dlog2 (k + 2)e бит. Более того, учитывая начальный набор значений для счетчиков, можно предварительно вычислить будущее распространение, которое будет происходить в пределах одного подграфа Gi, в таблице, имеющей 2rdl°g2(k+2)e записей – по одной на каждую возможную конфигурацию счетчиков. Чтобы стоимость построения и хранения этих таблиц была ограничена o(n), достаточно обеспечить выполнение соотношения r < a logk+2 n для некоторого a < 1. При помощи этих таблиц распространение внутри подграфа можно осуществить за константное время. Аналогично, распространение затрат по одному и тому же подграфу в Gi+1 также может быть предварительно вычислено в таблицах, поскольку оно зависит только от текущих счетчиков в Gi и от символа текста ti+1, для которых есть только a альтернативных вариантов.

Теперь возьмем все поддеревья R, максимальный размер которых не превышает r, и предварительно обработаем их при помощи вышеприведенной техники. Преобразуем каждое такое поддерево в лист в R, помеченный специальным символом aA, ассоциированным с соответствующим небольшим НКА A. Если в R нет последовательных замыканий Клини, которые можно упростить как R** = R*, то размер R после этого преобразования составит O(m/r). Назовем R0 преобразованным регулярным выражением. В сущности, к R0 применяется техника теоремы 1, которая говорит о том, как обращаться с особыми листьями, соответствующими небольшим НКА. Эти листья при помощи построения Томпсона преобразуются в две вершины, соединенных с ребром с меткой aA. Когда процесс распространения стоимости пути достигает вершины-источника ребра с меткой AA со стоимостью c, необходимо обновить счетчик начального состояния НКА A до c (или k + 1, если c > k). Затем с помощью таблицы «метода четырех русских» можно выполнить все операции распространения стоимости в пределах A за константное время и, наконец, получить в счетчике конечного состояния A новое значение для целевой вершины ребра, помеченного AA, в НКА верхнего уровня. Таким образом, все ребра (обычные и особые) НКА верхнего уровня могут быть пройдены за константное время, поэтому с помощью теоремы 1 стоимости в Gi можно получить за время O(mn/r). После этого стоимости переносятся в Gi+1, используя таблицы «четырех русских» для получения текущих значений счетчиков каждого подграфа Gi+1.

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

Применение

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

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

Сложность задачи AREM в наихудшем случае не вполне понятна. Разумеется, ее можно описать значением Q(n), которое было достигнуто для mlog(k + 2) = O(log n); но неизвестно, насколько его можно улучшить.

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

О некоторых недавних экспериментах сообщается в работе [ ]. Для малых значений m и k, и предполагая, что все веса равны 1 (за исключением w(c ! c) = 0), битово-параллельные алгоритмы с наихудшей сложностью O(kn(m/log n)2) [4 , 9] являются самыми быстрыми (второй из них способен пропускать некоторые символы текста в зависимости от R). Для произвольных целочисленных весов наилучшим выбором является более сложный битово-параллельный алгоритм [ ] либо алгоритм на основе метода «четырех русских» [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)