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

Question

Я хотел бы использовать обратный трекинг для поиска всех подстрок в длинной строке с учетом совпадений переменной длины, то есть совпадений, учитывающих максимальное заданное количество несовпадений, вставок и удалений. Я не смог найти ни одного полезного примера. Самым близким, что я нашел, является эта статья здесь , но она ужасно сложна. Кто-нибудь? * * 1003

Приветствия

Martin

Answer 1

Алгоритм

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

// 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 "с не более чем 1 каждым видом изменений, и оба эти способа заканчиваются в позиции 9:

Haystack: xxabcydef-
Needle:     abc-defg

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

Haystack: xxabcyde-f
Needle:     abc-defg

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

Dominance Relation

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

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

Haystack: abbbbc
Needle:   a-b-bc

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

Haystack: abbbbc
Needle:   ab--bc

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

Haystack: abbbbc
Needle:   abb--c

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

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

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

Answer 2

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

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

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

Answer 3

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

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