4551
правка
Приближенное сравнение регулярных выражений: различия между версиями
Перейти к навигации
Перейти к поиску
Приближенное сравнение регулярных выражений (посмотреть исходный код)
Версия от 23:23, 3 октября 2020
, 3 октября 2020→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
Более формально: граф 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> | |||
Таким образом, задача AREM сводится к вычислению кратчайших путей. Нетрудно заметить, что G можно топологически отсортировать так, чтобы все пути к вершинам в Gi вычислялись раньше всех путей к вершинам в Gi+1. Таким способом можно легко решить задачу нахождения кратчайших путей, для чего потребуется время O(mn log m) и память O(m). На самом деле, если ограничить задачу этим конкретным случаем сетевых выражений, которые являются регулярными выражениями без замыкания Клини, то G не имеет циклов, а вычисление кратчайших путей может быть выполнено за время O(mn) и за еще более короткое время в среднем [2]. | |||
Для простоты предположим, что G имеет начальное состояние s и уникальное конечное состояние f (это всегда можно организовать). По определению, самый короткий путь в <math>\mathcal{G}</math> из s0 в fn дает наименьшее расстояние между T и строкой в L(R). Чтобы адаптировать граф к задаче AREM, меняем веса ребер между si и si+1 на ноль. | |||
Таким образом, задача AREM сводится к вычислению кратчайших путей. Нетрудно заметить, что <math>\mathcal{G}</math> можно топологически отсортировать так, чтобы все пути к вершинам в Gi вычислялись раньше всех путей к вершинам в Gi+1. Таким способом можно легко решить задачу нахождения кратчайших путей, для чего потребуется время O(mn log m) и память O(m). На самом деле, если ограничить задачу этим конкретным случаем сетевых выражений, которые являются регулярными выражениями без замыкания Клини, то G не имеет циклов, а вычисление кратчайших путей может быть выполнено за время O(mn) и за еще более короткое время в среднем [2]. | |||