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

Наиболее универсальное решение этой задачи [ ] строится на графовой модели процесса вычисления расстояния. Предположим, что регулярное выражение R преобразуется методом Томпсона [ ] в недетерминированный конечный автомат (НКА) с O(m) состояний и переходов. Рассмотрим этот автомат в виде ориентированного графа G(V, E), ребра которого помечены элементами множества E U {e}. Ориентированный и взвешенный граф G построен для решения задачи AREM. G формируется путем создания n + 1 копий G; G0; G1 ; Gn и последующего присвоения им весов таким образом, чтобы свести расчет растояния к задаче нахождения кратчайших путей в графе G.