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

Пусть даны ''текстовая строка'' <math>T = t_1 t_2 ... t_n</math> и ''регулярное выражение'' R длины m, обозначающее язык <math>\mathcal{L}(R)</math>, над алфавитом <math>\Sigma</math> размера <math>\sigma</math>, а также ''функция расстояния'' между строками d и ''порог'' k. Задача ''приближенного сравнения регулярных выражений'' (approximate regular expression matching, AREM) заключается в нахождении всех текстовых позиций, завершающих так называемое приблизительное вхождение R в T; иначе говоря, в вычислении множества <math>\{ j, \exist i, 1 \le i \le j, \exist P \in \mathcal{L}(R), d(P, t_i ... t_j) \le k \}</math>. T, R и k уже заданы, при этом алгоритм может быть настроен для конкретного d.

Данная статья посвящена так называемому ''взвешенному расстоянию редактирования'', представляющему собой минимальную сумму весов последовательности операций, преобразующих одну строку в другую. В число этих операций входят вставка, удаление и замена символов. Веса представляют собой положительные вещественные значения, ассоциированные с каждой операцией и каждым символом. Вес операции удаления символа <math>c</math> обозначим за <math>w(c \to \epsilon)</math>, вес операции вставки <math>c</math> – за <math>w(\epsilon \to c)</math>, вес операции замены <math>c</math> на <math>c' \neq c</math> – за <math>w(c \to c')</math>. Предполагается, что <math>w(c \to c') = 0</math> для всех <math>c \in \Sigma \cup \epsilon</math> и что выполняется неравенство треугольника, то есть <math>w(x \to y) + w(y \to z) \ge w(x \to z)</math> для любых <math>x, y, z \in \Sigma \cup \{ \epsilon \}</math>. Поскольку расстояние может быть асимметричным, то постулируется, что d(A, B) – это стоимость преобразования A в B. Для простоты и практичности в этой записи предполагается m = o(n).