Приблизительное сопоставление строк с использованием поиска с возвратом

Алгоритм

Функция ff() ниже использует рекурсию (т.е. возврат) для решения вашей проблемы. Основная идея состоит в том, что в начале любого вызова f() мы пытаемся сопоставить суффикс t исходной строки "иглы" с суффиксом s строки "стог сена", допуская при этом только определенное количество каждого типа операция редактирования.

// ss is the start of the haystack, used only for reporting the match endpoints.
void f(char* ss, char* s, char* t, int mm, int ins, int del) {
    while (*s && *s == *t) ++s, ++t;    // OK to always match longest segment
    if (!*t) printf("%d\n", s - ss);    // Matched; print endpoint of match
    if (mm && *s && *t) f(ss, s + 1, t + 1, mm - 1, ins, del);
    if (ins && *s) f(ss, s + 1, t, mm, ins - 1, del);
    if (del && *t) f(ss, s, t + 1, mm, ins, del - 1);
}

// Find all occurrences of t starting at any position in s, with at most
// mm mismatches, ins insertions and del deletions.
void ff(char* s, char* t, int mm, int ins, int del) {
    for (char* ss = s; *s; ++s) {
//      printf("Starting from offset %d...\n", s - ss);
        f(ss, s, t, mm, ins, del);
    }
}

Пример вызова:

ff("xxabcydef", "abcdefg", 1, 1, 1);

Это выводит:

9
9

потому что есть два способа найти "abcdefg" в "xxabcydef" с не более чем одним изменением каждого типа, и оба эти способа заканчиваются на позиции 9:

Haystack: xxabcydef-
Needle:     abc-defg

который имеет 1 вставку (из y) и 1 удаление (из g) и

Haystack: xxabcyde-f
Needle:     abc-defg

который имеет 1 вставку (из y), 1 удаление (из f) и 1 замену g на f.

Отношения доминирования

Может быть неочевидно, почему на самом деле безопасно использовать цикл while в строке 3 для жадного сопоставления как можно большего количества символов в начале двух строк. На самом деле, это может уменьшить количество раз, когда определенная конечная позиция будет указана как совпадающая, но это никогда не приведет к тому, что конечная позиция будет полностью забыта — и, поскольку мы обычно заинтересованы в просто независимо от того, есть ли совпадение, заканчивающееся в данной позиции стога сена, и без этого while цикла алгоритм всегда занимал бы время, экспоненциальное по размеру иглы, это кажется беспроигрышным.

Он гарантированно работает из-за отношения доминирования. Чтобы убедиться в этом, предположим обратное — что это на самом деле небезопасно (т. е. пропускает некоторые совпадения). Тогда будет какое-то совпадение, в котором начальный сегмент одинаковых символов из обеих строк не выровнен друг с другом, например:

Haystack: abbbbc
Needle:   a-b-bc

Однако любое такое совпадение может быть преобразовано в другое совпадение, имеющее такое же количество операций каждого типа и заканчивающееся в той же позиции, путем смещения самого левого символа, следующего за пробелом, слева от пробела:

Haystack: abbbbc
Needle:   ab--bc

Если вы сделаете это несколько раз, пока не станет невозможно шунтировать символы без замены, вы получите совпадение, в котором наибольший начальный сегмент одинаковых символов из обеих строк выровнен относительно друг друга:

Haystack: abbbbc
Needle:   abb--c

Мой алгоритм найдет все такие совпадения, поэтому он не упустит ни одной позиции совпадения.

Экспоненциальное время

Как и любая программа поиска с возвратом, эта функция будет демонстрировать экспоненциальное замедление при определенных входных данных. Конечно, может быть и так, что на входах, которые вам приходится использовать, этого не происходит, и отрабатывает быстрее, чем конкретные реализации алгоритмов ДП.

Я бы начал с алгоритма расстояния Левенштейна, который является стандартным подходом при проверке сходства строк через несоответствие, вставка и удаление.

Поскольку алгоритм использует динамическое программирование снизу вверх, вы, вероятно, сможете найти все подстроки без для выполнения алгоритма для каждой потенциальной подстроки.

Самый лучший из известных мне алгоритмов для этого — A Fast Bit- Векторный алгоритм для приблизительного сопоставления строк на основе динамического программирования Джина Майерса. Учитывая текст для поиска длины n, строку шаблона для поиска длиной m и максимальное количество несоответствий/вставок/удалений k, этот алгоритм требует времени O(mn/w), где w — размер слова вашего компьютера (32 или 64). Если вы хорошо разбираетесь в алгоритмах работы со строками, на самом деле невероятно, что существует алгоритм, который требует времени, не зависящего от k — ​​долгое время это казалось недостижимой целью.

Я не знаю о существующей реализации вышеуказанного алгоритма. Если вам нужен инструмент, agrep может быть именно тем, что вам нужно. Он использует более ранний алгоритм, который требует времени O(mnk/w), но он достаточно быстр для низких k, т. е. в милях впереди поиска с возвратом в худшем случае.

agrep основан на алгоритме Shift-Or (или "Bitap"), который является очень умным алгоритм динамического программирования, который может представить свое состояние в виде битов целого числа и заставить двоичное сложение выполнять большую часть работы по обновлению состояния, что ускоряет алгоритм в 32 или 64 раза. над более типичной реализацией. :) Алгоритм Майерса также использует эту идею, чтобы получить коэффициент скорости 1/w.