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

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

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

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

Пусть даны текстовая строка T = t1t 2. .tn и регулярное выражение R длины m обозначающее язык L(R), над алфавитом S размера a, а также функция расстояния между строками d и порог k. Задача приближенного сравнения регулярных выражений (approximate regular expression matching, AREM) заключается в нахождении всех текстовых позиций, завершающих так называемое приблизительное вхождение R в T; иначе говоря, в вычислении множества fj; 9 i; 1 < i < j; d(P; t i : tj) < kg. T, R и k уже заданы, при этом алгоритм может быть настроен для конкретного d.

Данная статья посвящена так называемому взвешенному расстоянию редактирования, представляющему собой минимальную сумму весов последовательности операций, преобразующих одну строку в другую. В число этих операций входят вставка, удаление и замена символов. Веса представляют собой положительные вещественные значения, ассоциированные с каждой операцией и каждым символом. Вес операции удаления символа c обозначим за w(c ! e), вес операции вставки c – за w( -> c), вес операции замены c на c / с0 – за w(c !c 0). Предполагается, что w(c ! c) = 0 для всех c 2 £ [ e и что выполняется неравенство треугольника, то есть w(x ! y) + w(y ! z) > w(x ! z) для любых x; y; z 2 S U {e}. Поскольку расстояние может быть асимметричным, то постулируется, что d(A, B) – это стоимость преобразования A в B. Для простоты и практичности в этой записи предполагается m = o(n).

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

Наиболее универсальное решение этой задачи [ ] строится на графовой модели процесса вычисления расстояния. Предположим, что регулярное выражение R преобразуется методом Томпсона [ ] в недетерминированный конечный автомат (НКА) с O(m) состояний и переходов. Рассмотрим этот автомат в виде ориентированного графа G(V, E), ребра которого помечены элементами множества E U {e}. Ориентированный и взвешенный граф G построен для решения задачи AREM. G формируется путем создания n + 1 копий G; G0; G1 ; Gn и последующего присвоения им весов таким образом, чтобы свести расчет растояния к задаче нахождения кратчайших путей в графе G.

Более формально: граф G составляют вершины f v i ; v 2 V; 0 < i < ng, такие, что vi является копией вершины v 2 V в графе Gi. Для каждого ребра u ! c v in E, c 2 £ U {e}, следующие ребра добавлятся к графу G: ui ! vi ; с весом w(c !>• ) ; 0 < i < n ; ui !u i+1 ; с весом w(e !t i+1) ; 0 < i < n ; ui ! vi+1 ; с весом w(c !t i+1) ; 0 < i < n :

Для простоты предположим, что G имеет начальное состояние s и уникальное конечное состояние f (это всегда можно организовать). По определению, самый короткий путь в G из s0 в fn дает наименьшее расстояние между T и строкой в L(R). Чтобы адаптировать граф к задаче AREM, меняем веса ребер между si и si+1 на ноль.

Таким образом, задача AREM сводится к вычислению кратчайших путей. Нетрудно заметить, что G можно топологически отсортировать так, чтобы все пути к вершинам в 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)