4511
правок
Приближенное сравнение регулярных выражений: различия между версиями
Материал из WEGA
Приближенное сравнение регулярных выражений (посмотреть исходный код)
Версия от 23:00, 3 октября 2020
, 3 октября 2020→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
== Основные результаты == | == Основные результаты == | ||
Наиболее универсальное решение этой задачи [ ] строится на графовой модели процесса вычисления расстояния. Предположим, что регулярное выражение R преобразуется методом Томпсона [ ] в недетерминированный конечный автомат (НКА) с O(m) состояний и переходов. Рассмотрим этот автомат в виде ориентированного графа G(V, E), ребра которого помечены элементами множества | Наиболее универсальное решение этой задачи [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> и последующего присвоения им весов таким образом, чтобы свести расчет расcтояния к задаче нахождения кратчайших путей в графе <math>\mathcal{G}</math>. | ||
