Соответствие строковому шаблону с одним или нулевым несоответствием
Учитывая строку и образец, который нужно сопоставить, насколько эффективно могут быть найдены совпадения, имеющие ноль или одно несоответствие.
e.g)
S = abbbaaabbbabab
P = abab
Matches are abbb(index 0),aaab(index 4),abbb(index 6),abab(index 10)
Я пытался изменить алгоритм KMP, но я не уверен в подходе.
Пожалуйста, дайте мне идею, чтобы продолжить проблему.
Благодарю.
4 ответа
Хорошо, я нашел это! Я нашел лучший алгоритм!
Это может показаться немного смелым, но пока алгоритм, который я собираюсь предложить, имеет оба времени выполнения O(m + n) и потребление памяти O(m + n) и сами входные данные имеют те же свойства, что алгоритм может быть оптимизирован только в константе.
Используемые алгоритмы
Я собираюсь использовать смешение между алгоритмами KMP и Rabin Karp для моего решения. Рабин Карп использует скользящие хэши для сравнения подстрок исходных строк. Это требует линейного по времени предварительного вычисления, которое использует линейную дополнительную память, но с тех пор сравнение подстрок двух строк является постоянным O(1) (это амортизируется, если вы правильно обрабатываете столкновения).
Что мое решение не будет делать
Мое решение не найдет все вхождения в первой строке, которые соответствуют второй строке, но не более 1 разницы. Однако алгоритм может быть модифицирован таким образом, чтобы для каждого начального индекса в первой строке при наличии такого совпадения был найден хотя бы один из них (это оставлено читателю).
наблюдения
Позволять m длина второй строки и n - длина первой строки. Я собираюсь разделить задачу на две части: если я стремлюсь найти соответствие не более чем с одним отличием, я хочу найти подстроки первой строки: PREF будет подстрока до единой разницы и SUFF подстрока после разницы. я хочу len(PREF) + len(SUFF) + 1 = m, где PREF или же SUFF будет искусственно укорочен при необходимости (когда строки совпадают без разницы).
Я собираюсь основывать свое решение на одном очень важном наблюдении: предположим, что есть подстрока первой строки, начинающаяся с индекса i с длиной m это соответствует второй строке с не более чем одной разницей. Тогда если мы возьмем PREF как можно дольше будет еще решение для SUFF, Это очевидно: я просто довожу разницу до конца.
Алгоритм
А теперь следует сам алгоритм. Начните с обычного KMP. Каждый раз, когда расширение префикса терпит неудачу и ссылки сбоя должны следовать, сначала проверьте, пропустит ли следующая буква, оставшийся суффикс будет соответствовать оставшейся части второй строки. Если это так, то найдено искомое совпадение с не более чем одной разницей в символах. Если нет - мы продолжаем обычную KMP, делая проверку Рабина Карпа каждый раз, когда нужно перейти по ссылке сбоя.
Позвольте мне уточнить далее проверку Рабина Карпа на примере. Предположим, мы находимся на определенном этапе КМП, и мы обнаружили, что first.substring[i, i + k - 1] соответствует первому k буквы второй строки. Предположим также, что письмо first[i + k] отличается от second[k], Затем вы проверяете, first.substring[i + k + 1, i + m - 1] точно соответствует second.substring[k + 1, m - 1] используя Рабина Карпа. Это как раз тот случай, когда вы расширили индекс формы начального префикса i насколько это возможно, и вы пытаетесь сейчас, есть ли совпадение не более чем с одним отличием.
Рабин Карп будет использоваться только при переходе по ссылке сбоя, которая перемещает начальный индекс префикса как минимум с одного, что означает, что самое большее O(n) Используются звонки Рабина Карпа, каждый со сложностью O(1) для общей линейной сложности.
Это называется приближенной проблемой сопоставления строк. В вашем конкретном случае вы хотите максимальное расстояние редактирования 1.
Алгоритм bitap - довольно быстрый способ его решения.
Чтобы найти все подсовпадения, включая одно несоответствие, вам нужны 2 z-функции (одна для исходного P, а другая для обратного P). После этого массива buld из самых длинных префиксов суб-соответствий для исходной и обращенной строки S. Позже вам нужно обратить вспять второй массив. И в конце все просто: пробежитесь по первому массиву и проверьте, равна ли длина самого длинного префикса длине P. Если это так, то это совпадение без ошибок. Если он короче, проверьте второй массив в позиции (i + длина (P) - 1). Если сумма двух значений равна длине (P) - 1, то это субматч с одной ошибкой.
Сложность O(len(P) + len(S))
Всесторонний обзор различных алгоритмов и того, как они сравниваются друг с другом, дан Гонсало Наварро в его Руководстве по приближенному сопоставлению строк. На страницах 80, 81 и 82 показаны результаты сложности, включая наихудший и средний случаи, а также требования к пространству для различных алгоритмов.
(В используемых здесь обозначениях n относится к длине искомого текста, m к длине шаблона, σ к размеру алфавита и k к максимальному расстоянию редактирования, которое в вашем случае равно 1).