1313
правок
Приближенное сравнение регулярных выражений: различия между версиями
Материал из WEGA
Приближенное сравнение регулярных выражений (посмотреть исходный код)
Версия от 04:34, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показано 17 промежуточных версий 1 участника) | |||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть даны ''текстовая строка'' <math>T = t_1 t_2 ... t_n</math> и ''регулярное выражение'' R длины m, обозначающее язык <math>\mathcal{L}(R)</math>, над алфавитом <math>\Sigma</math> размера <math>\sigma</math>, а также ''функция расстояния'' между строками d и ''порог'' k. Задача ''приближенного сравнения регулярных выражений'' (approximate regular expression matching, AREM) заключается в нахождении всех текстовых позиций, завершающих так называемое приблизительное вхождение R в T; иначе говоря, в вычислении множества <math>\{ 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>T = t_1 t_2 ... t_n</math> и ''регулярное выражение'' R длины m, обозначающее язык <math>\mathcal{L}(R)</math>, над алфавитом <math>\Sigma</math> размера <math>\sigma</math>, а также ''функция расстояния'' между строками d и ''порог'' k. Задача ''приближенного сравнения регулярных выражений'' (approximate regular expression matching, AREM) заключается в нахождении всех текстовых позиций, завершающих так называемое ''приблизительное вхождение'' R в T; иначе говоря, в вычислении множества <math>\{ 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. | ||
Данная статья посвящена так называемому взвешенному расстоянию редактирования, представляющему собой минимальную сумму весов последовательности операций, преобразующих одну строку в другую. В число этих операций входят вставка, удаление и замена символов. Веса представляют собой положительные вещественные значения, ассоциированные с каждой операцией и каждым символом. Вес операции удаления символа c обозначим за w(c | Данная статья посвящена так называемому ''взвешенному расстоянию редактирования'', представляющему собой минимальную сумму весов последовательности операций, преобразующих одну строку в другую. В число этих операций входят вставка, удаление и замена символов. Веса представляют собой положительные вещественные значения, ассоциированные с каждой операцией и каждым символом. Вес операции удаления символа <math>c</math> обозначим за <math>w(c \to \epsilon)</math>, вес операции вставки <math>c</math> – за <math>w(\epsilon \to c)</math>, вес операции замены <math>c</math> на <math>c' \neq c</math> – за <math>w(c \to c')</math>. Предполагается, что <math>w(c \to c) = 0</math> для всех <math>c \in \Sigma \cup \epsilon</math> и что выполняется неравенство треугольника, то есть <math>w(x \to y) + w(y \to z) \ge w(x \to z)</math> для любых <math>x, y, z \in \Sigma \cup \{ \epsilon \}</math>. Поскольку расстояние может быть асимметричным, то постулируется, что d(A, B) – это стоимость преобразования A в B. Для простоты и практичности в данной статье предполагается m = o(n). | ||
== Основные результаты == | == Основные результаты == | ||
Наиболее универсальное решение этой задачи [ ] строится на графовой модели процесса вычисления расстояния. Предположим, что регулярное выражение R преобразуется методом Томпсона [ ] в недетерминированный конечный автомат (НКА) с O(m) состояний и переходов. Рассмотрим этот автомат в виде ориентированного графа G(V, E), ребра которого помечены элементами множества | Наиболее универсальное решение этой задачи [3] строится на графовой модели процесса вычисления расстояния. Предположим, что регулярное выражение R преобразуется методом Томпсона [8] в недетерминированный конечный автомат (НКА) с O(m) состояний и переходов. Рассмотрим этот автомат в виде ориентированного графа G(V, E), ребра которого помечены элементами множества <math>\Sigma \cup \{ \epsilon \}</math>. Для решения задачи AREM строится ориентированный и взвешенный граф <math>\mathcal{G}</math>. <math>\mathcal{G}</math> формируется путем создания n + 1 копий <math>G, G_0, G_1, ..., G_n</math> и последующего присвоения им весов таким образом, чтобы свести расчет расстояния к задаче нахождения кратчайших путей в графе <math>\mathcal{G}</math>. | ||
Более формально: граф G составляют вершины | Более формально: граф <math>\mathcal{G}</math> составляют вершины <math>\{v_i, v \in V, 0 \le i \le n \}</math>, такие, что <math>v_i</math> является копией вершины <math>v \in V</math> в графе <math>G_i</math>. Для каждого ребра <math>u \xrightarrow{c} v</math> в E, <math>c \in \Sigma \cup \{ \epsilon \}</math>, к графу <math>\mathcal{G}</math> добавляются следующие ребра: | ||
<math>u_i \to v_i</math> с весом <math>w(c \to \epsilon), 0 \le i \le n,</math> | |||
<math>u_i \to u_{i + 1}</math> с весом <math>w(\epsilon \to t_{i + 1}), 0 \le i < n,</math> | |||
<math>u_i \to v_{i + 1}</math> с весом <math>w(c \to t_{i + 1}), 0 \le i < n.</math> | |||
Для простоты предположим, что G имеет начальное состояние s и уникальное конечное состояние f (это всегда можно организовать). По определению, самый короткий путь в <math>\mathcal{G}</math> из <math>s_0</math> в <math>f_n</math> дает наименьшее расстояние между T и строкой в <math>\mathcal{L}(R)</math>. Чтобы адаптировать граф к задаче AREM, веса ребер между <math>s_i</math> и <math>s_{i + 1}</math> полагаем нулевыми. | |||
Таким образом, задача AREM сводится к вычислению кратчайших путей. Нетрудно заметить, что <math>\mathcal{G}</math> можно топологически отсортировать так, чтобы все пути к вершинам в <math>G_i</math> вычислялись раньше всех путей к вершинам в <math>G_{i + 1}</math>. Таким способом можно легко решить задачу нахождения кратчайших путей, для чего потребуется время O(mn log m) и память O(m). На самом деле, если ограничить задачу этим конкретным случаем ''сетевых выражений'', которые являются регулярными выражениями без замыкания Клини, то G не имеет циклов, а вычисление кратчайших путей может быть выполнено за время O(mn) и за еще более короткое время в среднем [2]. | |||
Наиболее деликатная часть процесса достижения времени O(mn) для регулярных выражений общего вида [3] заключается в том, чтобы доказать, что с учетом типов циклов, возникающих в НКА регулярных выражений, можно правильно вычислить расстояния внутри каждого <math>G_i</math>, выполнив три действия: (а) вычислить расстояния в топологическом порядке <math>G_i</math> без учета ''обратных ребер'', введенных замыканием Клини; (б) обновить стоимости путей за счет однократного использования обратных ребер; (в) обновить стоимости путей еще раз в топологическом порядке, вновь игнорируя обратные ребра. | |||
'''Теорема 1 (Майерс и Миллер, 1989 [3]). Существует решение с временем выполнения O(mn) в наихудшем случае для задачи AREM с использованием взвешенного расстояния редактирования.''' | |||
Для целочисленных весов можно получить лучший результат за счет использования RAM-модели с единичной стоимостью при помощи «метода четырех русских». Идея заключается в следующем. Возьмем небольшое подвыражение R, порождающее НКА, который будет преобразовываться в небольшой подграф каждого графа <math>G_i</math>. В момент распространения стоимостей путей по этому автомату с каждой вершиной будет связан счетчик, (говорящий о текущем кратчайшем пути из <math>s_0</math>). Этот счетчик может быть сведен к числу в диапазоне [0, k + 1], где k + 1 обозначает «больше, чем k». Если небольшой НКА имеет r состояний, то для полного описания счетчиков соответствующего подграфа <math>G_i</math> требуется <math>r \lceil log_2 \; (k + 2) \rceil</math> бит. Более того, зная начальный набор значений для счетчиков, можно предварительно вычислить будущее распространение, которое будет происходить в пределах одного подграфа <math>G_i</math>, в таблице, имеющей <math>2^{r \lceil log_2 \; (k + 2) \rceil}</math> записей – по одной на каждую возможную конфигурацию счетчиков. Чтобы стоимость построения и хранения этих таблиц была ограничена o(n), достаточно обеспечить выполнение соотношения <math>r < \alpha \; log_{k + 2} \; n</math> для некоторого <math>\alpha < 1</math>. При помощи этих таблиц распространение внутри подграфа можно осуществить за константное время. Аналогично, распространение стоимостей по одному и тому же подграфу в <math>G_{i + 1}</math> также может быть предварительно вычислено в таблицах, поскольку оно зависит только от текущих счетчиков в <math>G_i</math> и от символа текста <math>t_{i + 1}</math>, для которых существует только <math>\sigma</math> альтернативных вариантов. | |||
Теорема 2 (Ву и коллеги, 1995 [ ]). Для случая целочисленных весов существует решение с временем выполнения O(n + mn/ | |||
Теперь возьмем все поддеревья R, максимальный размер которых не превышает r, и предварительно обработаем их при помощи вышеприведенной техники. Преобразуем каждое такое поддерево в лист в R, помеченный специальным символом <math>a_A</math>, ассоциированным с соответствующим небольшим НКА A. Если в R нет последовательных замыканий Клини, которые можно упростить как R** = R*, то размер R после этого преобразования составит O(m/r). Обозначим преобразованное регулярное выражение за R'. В сущности, к R' применяется техника теоремы 1, которая говорит о том, как обращаться с особыми листьями, соответствующими небольшим НКА. Эти листья при помощи построения Томпсона преобразуются в две вершины, соединенных ребром с меткой <math>a_A</math>. Когда процесс распространения стоимости пути достигает вершины-источника ребра с меткой <math>a_A</math> со стоимостью c, необходимо обновить счетчик начального состояния НКА A до c (или k + 1, если c > k). Затем с помощью таблицы «метода четырех русских» можно выполнить все операции распространения стоимости в пределах A за константное время и, наконец, получить в счетчике конечного состояния A новое значение для целевой вершины ребра, помеченного <math>a_A</math>, в НКА верхнего уровня. Таким образом, все ребра (обычные и особые) НКА верхнего уровня могут быть пройдены за константное время, поэтому с помощью теоремы 1 значения стоимости в <math>G_i</math> можно получить за время O(mn/r). После этого стоимости переносятся в <math>G_{i + 1}</math>, используя таблицы «четырех русских» для получения текущих значений счетчиков каждого подграфа A в графе <math>G_{i + 1}</math>. | |||
'''Теорема 2 (Ву и коллеги, 1995 [10]). Для случая целочисленных весов существует решение с временем выполнения <math>O(n + mn/log_{k + 2} \; n)</math> в наихудшем случае для задачи AREM с использованием взвешенного расстояния редактирования.''' | |||
== Применение == | == Применение == | ||
Эта задача применяется в вычислительной биологии для нахождения определенных типов мотивов в ДНК и последовательностях белка. Подробнее об этом см. обсуждение в работе [ ]. В частности, ограниченными регулярными выражениями являются шаблоны PROSITE, достаточно широко применяющиеся при поиске | Эта задача применяется в вычислительной биологии для нахождения определенных типов мотивов в ДНК и последовательностях белка. Подробнее об этом см. обсуждение в работе [1]. В частности, ограниченными регулярными выражениями являются шаблоны PROSITE, достаточно широко применяющиеся при поиске в последовательностях белка. На практике шаблоны PROSITE можно искать при помощи более быстрых алгоритмов [7]. То же происходит и с другими классами сложных шаблонов [6] и сетевых выражений [2]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Сложность задачи AREM в наихудшем случае не вполне понятна. Разумеется, ее можно описать значением | Сложность задачи AREM в наихудшем случае не вполне понятна. Разумеется, ее можно описать значением <math>\Omega(n)</math>, которое было достигнуто для m log(k + 2) = O(log n); но неизвестно, насколько его можно улучшить. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
О некоторых недавних экспериментах сообщается в работе [ ]. Для малых значений m и k, и предполагая, что все веса равны 1 (за исключением w(c | О некоторых недавних экспериментах сообщается в работе [5]. Для малых значений m и k, и предполагая, что все веса равны 1 (за исключением <math>w(c \to c) = 0)</math>, битово-параллельные алгоритмы со сложностью в наихудшем случае <math>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) сопоставляет последовательности приблизительных сетевых выражений с произвольными весами и заданной величиной гэпа между каждым сетевым выражением и последующим. | Эффективное решение задачи 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). | * [[Сравнение регулярных выражений]] – более простой случай, в котором ищется точное совпадение со строками в <math>\mathcal{L}(R)</math>. | ||
* [[Последовательное приближенное сравнение строк]] – упрощение данной задачи; в этом случае связь между графом G и матрицей C должна быть очевидной. | * [[Последовательное приближенное сравнение строк]] – упрощение данной задачи; в этом случае связь между графом <math>\mathcal{G}</math> и матрицей C должна быть очевидной. | ||
== Литература == | == Литература == | ||
| Строка 72: | Строка 77: | ||
10. Wu, S., Manber, U., Myers, E.W.: A subquadratic algorithm for approximate regular expression matching. J. Algorithms 19(3), 346-360(1995) | 10. Wu, S., Manber, U., Myers, E.W.: A subquadratic algorithm for approximate regular expression matching. J. Algorithms 19(3), 346-360(1995) | ||
[[Категория: Совместное определение связанных терминов]] | |||
