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

Теперь возьмем все поддеревья 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>.

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