Алгоритм Кнута-Морриса-Пратта: поиск подстроки за O(n)

Введение

Алгоритм поиска местоположения подстроки в заданном предложении за время O(n).

В информатике алгоритм Кнута — Морриса — Пратта (или алгоритм KMP) — это алгоритм поиска подстроки, который ищет вхождения "слова" W в основной "текстовой строке" S, используя наблюдение о том, что при возникновении несовпадения само слово содержит достаточно информации для определения места, с которого может начаться следующее совпадение, тем самым избегая повторной проверки ранее сопоставленных символов. Алгоритм был разработан Джеймсом Моррисом и независимо открыт Дональдом Кнутом "через несколько недель" на основе теории автоматов. Моррис и Воган Пратт опубликовали технический отчет в 1970 году. В 1977 году они также совместно опубликовали этот алгоритм. Независимо от этого, в 1969 году Матиясевич обнаружил аналогичный алгоритм, реализованный в виде двумерной машины Тьюринга, при изучении задачи распознавания соответствия образцов строк над двоичным алфавитом. Это был первый алгоритм линейного времени для поиска подстроки.

Предыстория

Алгоритм сопоставления строк стремится найти начальный индекс m в строке S[], соответствующий поисковому слову W[]. Наиболее простой алгоритм, известный как "метод грубой силы" или "наивный" алгоритм, заключается в поиске совпадения слова в каждом индексе m, то есть в позиции строки, соответствующей символу S[m]. В каждой позиции m алгоритм сначала проверяет равенство первого символа в искомом слове, то есть S[m] =? W[0]. Если найдено совпадение, алгоритм проверяет остальные символы в искомом слове, последовательно проверяя значения индекса позиции слова i. Алгоритм извлекает символ W[i] из искомого слова и проверяет равенство выражения S[m+i] =? W[i]. Если все последующие символы совпадают в W в позиции m, то совпадение найдено в этой позиции в искомой строке. Если индекс m достигает конца строки, то совпадения нет, и поиск считается "неудачным". Обычно пробная проверка быстро отклоняет пробное совпадение. Если строки состоят из равномерно распределенных случайных букв, то вероятность совпадения символов составляет 1 к 26. В большинстве случаев пробная проверка отклоняет совпадение по первой букве. Вероятность совпадения первых двух букв составляет 1 к 26 (1 к 26^2 – вероятность совпадения из 26 возможных букв). Следовательно, если символы случайны, то ожидаемая сложность поиска строки S[] длиной n составляет порядка n сравнений или O(n). Ожидаемая производительность очень хороша. Если S[] содержит 1 миллион символов, а W[] – 1000 символов, то поиск строки должен завершиться примерно после 1,04 миллиона сравнений символов. Однако такая ожидаемая производительность не гарантирована. Если строки не случайны, то проверка пробного m может потребовать большого количества сравнений символов. Наихудший случай – когда две строки совпадают во всех символах, кроме последнего. Представьте, что строка S[] состоит из 1 миллиона символов, все из которых равны A, а слово W[] состоит из 999 символов A, заканчивающихся символом B. Простой алгоритм сопоставления строк теперь будет проверять 1000 символов в каждой пробной позиции, прежде чем отклонить совпадение и перейти к следующей пробной позиции. В этом примере простой поиск строки займет около 1000 сравнений символов, умноженных на 1 миллион позиций, то есть 1 миллиард сравнений символов. Если длина W[] равна k, то наихудшая производительность составляет O(k⋅n). Алгоритм KMP имеет лучшую производительность в наихудшем случае, чем простой алгоритм. KMP тратит некоторое время на предварительное вычисление таблицы (порядка размера W[], O(k)), а затем использует эту таблицу для эффективного поиска строки за O(n). Отличие состоит в том, что KMP использует информацию о предыдущих совпадениях, которой нет у простого алгоритма. В приведенном выше примере, когда KMP обнаруживает неудачу пробного совпадения на 1000-м символе (i = 999), потому что S[m+999] ≠ W[999], он увеличит m на 1, но будет знать, что первые 998 символов в новой позиции уже совпадают. KMP сопоставил 999 символов A, прежде чем обнаружить несоответствие на 1000-м символе (позиция 999). Перемещение пробной позиции m на один символ вперед отбрасывает первый символ A, поэтому KMP знает, что есть 998 символов A, которые совпадают с W[], и не будет проверять их повторно; то есть KMP установит i равным 998. KMP сохраняет свои знания в предварительно вычисленной таблице и двух переменных состояния. Когда KMP обнаруживает несоответствие, таблица определяет, насколько увеличится KMP (переменная m) и с какой позиции будет продолжена проверка (переменная i).

A string matching algorithm wants to find the starting index m in string S[] that matches the search word W[]. The most straightforward algorithm, known as the "brute force" or "naive" algorithm, is to look for a word match at each index m, i. e. the position in the string being searched that corresponds to the character S[m]. At each position m the algorithm first checks for equality of the first character in the word being searched, i. e. S[m] =? W[0]. If a match is found, the algorithm tests the other characters in the word being searched by checking successive values of the word position index, i. The algorithm retrieves the character W[i] in the word being searched and checks for equality of the expression S[m+i] =? W[i]. If all successive characters match in W at position m, then a match is found at that position in the search string. If the index m reaches the end of the string then there is no match, in which case the search is said to "fail". Usually, the trial check will quickly reject the trial match. If the strings are uniformly distributed random letters, then the chance that characters match is 1 in 26. In most cases, the trial check will reject the match at the initial letter. The chance that the first two letters will match is 1 in 26 (1 in 26^2 chances of a match over 26 possible letters). So if the characters are random, then the expected complexity of searching string S[] of length n is on the order of n comparisons or O(n). The expected performance is very good. If S[] is 1 million characters and W[] is 1000 characters, then the string search should complete after about 1.04 million character comparisons. That expected performance is not guaranteed. If the strings are not random, then checking a trial m may take many character comparisons. The worst case is if the two strings match in all but the last letter. Imagine that the string S[] consists of 1 million characters that are all A, and that the word W[] is 999 A characters terminating in a final B character. The simple string matching algorithm will now examine 1000 characters at each trial position before rejecting the match and advancing the trial position. The simple string search example would now take about 1000 character comparisons times 1 million positions for 1 billion character comparisons. If the length of W[] is k, then the worst case performance is O(k⋅n). The KMP algorithm has a better worst case performance than the straightforward algorithm. KMP spends a little time precomputing a table (on the order of the size of W[], O(k)), and then it uses that table to do an efficient search of the string in O(n). The difference is that KMP makes use of previous match information that the straightforward algorithm does not. In the example above, when KMP sees a trial match fail on the 1000th character (i = 999) because S[m+999] ≠ W[999], it will increment m by 1, but it will know that the first 998 characters at the new position already match. KMP matched 999 A characters before discovering a mismatch at the 1000th character (position 999). Advancing the trial match position m by one throws away the first A, so KMP knows there are 998 A characters that match W[] and does not retest them; that is, KMP sets i to 998. KMP maintains its knowledge in the precomputed table and two state variables. When KMP discovers a mismatch, the table determines how much KMP will increase (variable m) and where it will resume testing (variable i).

Таблица "частичное совпадение" (также известная как "функция отказа")

Цель таблицы — позволить алгоритму не сопоставлять ни один символ строки S более одного раза. Ключевое наблюдение о природе линейного поиска, позволяющее это реализовать, заключается в том, что после проверки некоторого сегмента основной строки по отношению к начальному сегменту образца, мы точно знаем, в каких местах может начаться новое потенциальное совпадение, которое может быть продолжено до текущей позиции. Иными словами, мы "предварительно просматриваем" сам образец и составляем список всех возможных позиций отката, которые позволяют пропустить максимум бесполезных символов, не упуская при этом ни одного потенциального совпадения. Нам необходимо иметь возможность, для каждой позиции в W, определить длину самого длинного возможного начального сегмента W, предшествующего (но не включающего) эту позицию, отличного от полного сегмента, начинающегося с W[0], который только что не смог сопоставиться; это определяет, насколько далеко необходимо вернуться при поиске следующего совпадения. Следовательно, T[i] представляет собой точную длину самого длинного собственного начального сегмента W, который также является сегментом подстроки, заканчивающейся в W[i-1]. Мы принимаем соглашение, что пустая строка имеет длину 0. Поскольку несовпадение в самом начале образца является особым случаем (возможности отката нет), мы устанавливаем T[0] = 1, как будет описано ниже.

Эффективность алгоритма составления таблицы

Временная (и пространственная) сложность табличного алгоритма равна , где – длина W.

Внешний цикл: переменная pos инициализируется значением 1, условие цикла – pos < k, и pos увеличивается на 1 в каждой итерации цикла. Таким образом, цикл выполнит итераций. Внутренний цикл: переменная cnd инициализируется значением 0 и увеличивается максимум на 1 в каждой итерации внешнего цикла. T[cnd] всегда меньше cnd, поэтому cnd уменьшается как минимум на 1 в каждой итерации внутреннего цикла; условие завершения внутреннего цикла – cnd ≥ 0. Это означает, что общее количество выполнений внутреннего цикла не может превысить количество выполнений внешнего цикла – каждое уменьшение cnd на 1 во внутреннем цикле должно соответствовать увеличению на 1 во внешнем цикле. Поскольку внешний цикл выполняется итераций, внутренний цикл может выполнить не более итераций в общей сложности. Таким образом, внешние и внутренние циклы вместе выполняют не более итераций. Это соответствует временной сложности в нотации Big O.

Эффективность алгоритма KMP

Поскольку две части алгоритма имеют сложности O(k) и O(n) соответственно, сложность всего алгоритма составляет O(n + k). Эти сложности остаются неизменными, вне зависимости от количества повторяющихся шаблонов в W или S.

Варианты

Версия алгоритма KMP в реальном времени может быть реализована с использованием отдельной таблицы отказов для каждого символа алфавита. Если при сравнении символов в тексте происходит несовпадение, то для символа, вызвавшего несовпадение, используется таблица отказов, чтобы определить индекс в образце, в котором произошло несовпадение. Это возвращает длину самой длинной подстроки, заканчивающейся в этом индексе и совпадающей с префиксом образца, с дополнительным условием, что символ, следующий за префиксом, не совпадает. Благодаря этому ограничению, символ в тексте не нужно повторно проверять на следующем этапе, и поэтому между обработкой каждого индекса текста выполняется лишь постоянное количество операций. Это удовлетворяет требованию вычислений в реальном времени. Алгоритм Бута использует модифицированную версию функции предварительной обработки KMP для нахождения лексикографически минимальной циклической перестановки строки. Таблица отказов вычисляется последовательно по мере циклического сдвига строки.