Приближенное сравнение регулярных выражений: различия между версиями

Для целочисленных весов можно получить лучший результат за счет использования 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>, для которых есть только a альтернативных вариантов.

Теперь возьмем все поддеревья 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>, используя таблицы «четырех русских» для получения текущих значений счетчиков каждого подграфа <math>G_{i + 1}</math>.

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

* [[Сравнение регулярных выражений]] – более простой случай, в котором ищется точное совпадение со строками в L(R).

* [[Последовательное приближенное сравнение строк]] – упрощение данной задачи; в этом случае связь между графом G и матрицей C должна быть очевидной.