4511
правок
Приближенное сравнение регулярных выражений: различия между версиями
Материал из WEGA
Приближенное сравнение регулярных выражений (посмотреть исходный код)
Версия от 22:57, 3 октября 2020
, 3 октября 2020→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Данная статья посвящена так называемому взвешенному расстоянию редактирования, представляющему собой минимальную сумму весов последовательности операций, преобразующих одну строку в другую. В число этих операций входят вставка, удаление и замена символов. Веса представляют собой положительные вещественные значения, ассоциированные с каждой операцией и каждым символом. Вес операции удаления символа c обозначим за w(c | Данная статья посвящена так называемому ''взвешенному расстоянию редактирования'', представляющему собой минимальную сумму весов последовательности операций, преобразующих одну строку в другую. В число этих операций входят вставка, удаление и замена символов. Веса представляют собой положительные вещественные значения, ассоциированные с каждой операцией и каждым символом. Вес операции удаления символа <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). | ||
== Основные результаты == | == Основные результаты == | ||
