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

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

Для целочисленных весов можно получить лучший результат за счет использования RAM-модели с единичной стоимостью при помощи «метода четырех русских». Идея заключается в следующем. Возьмем небольшое подвыражение R, порождающее НКА, который будет преобразовываться в небольшой подграф каждого графа <math>G_i</math>. В момент распространения стоимостей путей по этому автомату с каждой вершиной будет связан счетчик, (говорящий о текущем кратчайшем пути из s0). Этот счетчик может быть сведен к числу в диапазоне [0, k + 1], где k + 1 обозначает «больше, чем k». Если небольшой НКА имеет r состояний, то для полного описания счетчиков соответствующего подграфа <math>G_i</math> требуется r dlog2 (k + 2)e бит. Более того, учитывая начальный набор значений для счетчиков, можно предварительно вычислить будущее распространение, которое будет происходить в пределах одного подграфа <math>G_i</math>, в таблице, имеющей 2rdl°g2(k+2)e записей – по одной на каждую возможную конфигурацию счетчиков. Чтобы стоимость построения и хранения этих таблиц была ограничена o(n), достаточно обеспечить выполнение соотношения r < a logk+2 n для некоторого a < 1. При помощи этих таблиц распространение внутри подграфа можно осуществить за константное время. Аналогично, распространение затрат по одному и тому же подграфу в <math>G_{i + 1}</math> также может быть предварительно вычислено в таблицах, поскольку оно зависит только от текущих счетчиков в <math>G_i</math> и от символа текста <math>t_{i + 1}</math>, для которых есть только 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 стоимости в <math>G_i</math> можно получить за время O(mn/r). После этого стоимости переносятся в <math>G_{i + 1}</math>, используя таблицы «четырех русских» для получения текущих значений счетчиков каждого подграфа <math>G_{i + 1}</math>.