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

Наиболее универсальное решение этой задачи [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> на ноль.