4488
правок
Приближенное сравнение регулярных выражений: различия между версиями
Перейти к навигации
Перейти к поиску
Приближенное сравнение регулярных выражений (посмотреть исходный код)
Версия от 22:51, 3 октября 2020
, 3 октября 2020→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Сравнение регулярных выражений, допускающее ошибки или ра…») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть даны текстовая строка T = | Пусть даны ''текстовая строка'' <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. | ||