В информатике алгоритм Кнута–Морриса–Пратта (или алгоритм КМП ) — это алгоритм поиска строк , который ищет вхождения «слова» Wв основную «текстовую строку», Sиспользуя наблюдение, что при возникновении несовпадения само слово содержит достаточно информации, чтобы определить, где может начаться следующее совпадение, тем самым обходя повторную проверку ранее сопоставленных символов.
Алгоритм был задуман Джеймсом Х. Моррисом и независимо открыт Дональдом Кнутом «несколько недель спустя» из теории автоматов . [1] [2] Моррис и Воан Пратт опубликовали технический отчет в 1970 году. [3] Эти трое также опубликовали алгоритм совместно в 1977 году. [1] Независимо, в 1969 году, Матиясевич [4] [5] открыл похожий алгоритм, закодированный двумерной машиной Тьюринга, изучая проблему распознавания сопоставления строк с образцом в двоичном алфавите. Это был первый алгоритм линейного времени для сопоставления строк. [6]
Алгоритм сопоставления строк хочет найти начальный индекс 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 сравнений или Θ ( 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 символов AW[] , которые совпадают , и не проверяет их повторно; то есть KMP устанавливает iзначение 998. KMP сохраняет свои знания в предварительно вычисленной таблице и двух переменных состояния. Когда KMP обнаруживает несовпадение, таблица определяет, насколько увеличится KMP (переменная m) и где он возобновит тестирование (переменная i).
Чтобы проиллюстрировать детали алгоритма, рассмотрим (относительно искусственный) запуск алгоритма, где W= "ABCDABD" и S= "ABC ABCDAB ABCDABDABDE". В любой момент времени алгоритм находится в состоянии, определяемом двумя целыми числами:
m, обозначая позицию, в Sкоторой начинается предполагаемый матч W,i, обозначающий индекс текущего рассматриваемого символа в W.На каждом шаге алгоритм сравнивает S[m+i]и W[i]увеличивает, iесли они равны. Это изображено в начале выполнения, как
1 2 м: 01234567890123456789012С: АБВ АБВCDAB АБВГДАБДЕ Ш: АБВГ Д АБД я: 012 3 456
Алгоритм сравнивает последовательные символы Wс «параллельными» символами S, переходя от одного к другому путем увеличения, iесли они совпадают. Однако на четвертом шаге S[3] = ' 'не совпадает W[3] = 'D'. Вместо того, чтобы снова начать поиск в S[1], мы замечаем, что 'A'между позициями 1 и 2 в не встречается ничего S; следовательно, проверив все эти символы ранее (и зная, что они совпали с соответствующими символами в W), нет никаких шансов найти начало соответствия. Поэтому алгоритм устанавливает m = 3и i = 0.
1 2 м: 01234567890123456789012С: АБВ АБВCDAB АБВГДАБДЕ Ш: А BCDABD я: 0 123456
Это совпадение не выполняется на начальном символе, поэтому алгоритм устанавливает m = 4иi = 0
1 2 м: 01234567890123456789012С: АБВ АБВCDAB АБВCDABDE Ш: АБВCDAB Д я: 012345 6
Здесь, iувеличивается до почти полного совпадения , "ABCDAB"пока i = 6не даст несовпадение в W[6]и S[10]. Однако, непосредственно перед концом текущего частичного совпадения была та подстрока "AB", которая могла быть началом нового совпадения, поэтому алгоритм должен это учитывать. Поскольку эти символы соответствуют двум символам до текущей позиции, эти символы не нужно проверять снова; алгоритм устанавливает m = 8(начало начального префикса) и i = 2(сигнализируя о совпадении первых двух символов) и продолжает сопоставление. Таким образом, алгоритм не только пропускает ранее сопоставленные символы S( "AB"), но также и ранее сопоставленные символы W(префикс "AB").
1 2 м: 01234567890123456789012С : АБВ АБВГД АБВГДАБДЕ Ш: АБВГД Д : 01 2 3456
Этот поиск в новой позиции немедленно терпит неудачу, поскольку W[2](a 'C') не соответствует S[10](a ' '). Как и в первом испытании, несоответствие заставляет алгоритм вернуться к началу Wи начать поиск в несовпадающей позиции символа S: m = 10, сброс i = 0.
1 2 м: 01234567890123456789012С: АБВ АБВCDAB АБВГДАБДЕ Ш: А BCDABD я: 0 123456
Сопоставление по m=10сразу же терпит неудачу, поэтому алгоритм далее пробует m = 11и i = 0.
1 2 м: 01234567890123456789012С: АБВ АБВСДАБ АБВСДАБ С ДАБДЕ Ш: АБВСДАБ Д я: 012345 6
И снова алгоритм сопоставляет "ABCDAB", но следующий символ, 'C', не совпадает с последним символом 'D'слова W. Рассуждая так же, как и раньше, алгоритм устанавливает m = 15, чтобы начать с двухсимвольной строки, "AB"ведущей к текущей позиции, устанавливает i = 2, и продолжает сопоставление с текущей позиции.
1 2 м: 01234567890123456789012С: ABC ABCDAB ABCD ABCDABD E W: ABCDABD i: 0123456
На этот раз совпадение завершено, и первым символом совпадения является S[15].
Приведенный выше пример содержит все элементы алгоритма. На данный момент мы предполагаем существование таблицы "частичных совпадений" T, описанной ниже, которая указывает, где нам нужно искать начало нового совпадения при обнаружении несовпадения. Записи из Tпостроены так, что если у нас есть совпадение, начинающееся с S[m], которое не срабатывает при сравнении S[m + i]с W[i], то следующее возможное совпадение начнется с индекса m + i - T[i]in S(то есть, T[i]это количество "возвратов", которое нам нужно сделать после несовпадения). Это имеет два следствия: во-первых, T[0] = -1, что указывает на то, что если W[0]является несовпадением, мы не можем вернуться назад и должны просто проверить следующий символ; и во-вторых, хотя следующее возможное совпадение начнется с индекса m + i - T[i], как в примере выше, нам фактически не нужно проверять какие-либо символы T[i]после него, так что мы продолжим поиск с W[T[i]]. Ниже приведен пример реализации псевдокода алгоритма поиска KMP.
алгоритм kmp_search : ввод : массив символов, S (текст для поиска) массив символов, W (искомое слово) выход : массив целых чисел P (позиции в S, в которых находится W) целое число, nP (количество позиций) определение переменных : целое число, j ← 0 (позиция текущего символа в S) целое число, k ← 0 (позиция текущего символа в W) массив целых чисел, T (таблица, вычисленная в другом месте) пусть nP ← 0 пока j < длина(S) делать если W[k] = S[j] тогда пусть j ← j + 1 пусть k ← k + 1 если k = длина(W) тогда (вхождение найдено, если необходимо только первое вхождение, здесь можно вернуть m ← j - k) пусть P[nP] ← j - k, nP ← nP + 1 пусть k ← T[k] (T[length(W)] не может быть -1) иначе пусть k ← T[k] если k < 0, то пусть j ← j + 1 пусть k ← k + 1
Предполагая предварительное существование таблицы T, поисковая часть алгоритма Кнута–Морриса–Пратта имеет сложность O ( n ) , где n — длина S, а O — обозначение big-O . За исключением фиксированных накладных расходов, возникающих при входе и выходе из функции, все вычисления выполняются в whileцикле. Чтобы ограничить количество итераций этого цикла, заметьте, что Tпостроено так, что если сопоставление, начавшееся в , терпит S[m]неудачу при сравнении S[m + i]с W[i], то следующее возможное сопоставление должно начинаться в S[m + (i - T[i])]. В частности, следующее возможное сопоставление должно иметь место при более высоком индексе, чем m, так что T[i] < i.
Этот факт подразумевает, что цикл может выполняться не более 2 n раз, так как на каждой итерации он выполняет одну из двух ветвей в цикле. Первая ветвь неизменно увеличивается iи не изменяется m, так что индекс m + iтекущего рассматриваемого символа Sувеличивается. Вторая ветвь добавляется i - T[i]к m, и, как мы видели, это всегда положительное число. Таким образом, местоположение mначала текущего потенциального соответствия увеличивается. В то же время вторая ветвь остается m + iнеизменной, так как mдобавляется i - T[i]к ней, и сразу после этого T[i]назначается в качестве нового значения i, следовательно new_m + new_i = old_m + old_i - T[old_i] + T[old_i] = old_m + old_i. Теперь цикл заканчивается, если m + i= n ; следовательно, каждая ветвь цикла может быть достигнута не более n раз, так как они соответственно увеличивают либо m + iили m, и m ≤ m + i: если m= n , то, безусловно, m + i≥ n , так что, поскольку он увеличивается не более чем на единицу, мы должны были иметь m + i= n в какой-то момент в прошлом, и поэтому в любом случае мы бы закончили.
Таким образом, цикл выполняется не более 2 n раз, что показывает, что временная сложность алгоритма поиска составляет O ( n ).
Вот еще один способ представить себе время выполнения: Допустим, мы начинаем сопоставлять Wи Sв позиции iи p. Если Wсуществует как подстрока Sв p, то W[0..m] = S[p..p+m]. В случае успеха, то есть слова и текста, совпадающих в позициях ( W[i] = S[p+i]), мы увеличиваем iна 1. В случае неудачи, то есть слова и текста, не совпадающих в позициях ( W[i] ≠ S[p+i]), указатель текста остается неподвижным, в то время как указатель слова откатывается на определенную величину ( i = T[i], где T— таблица переходов), и мы пытаемся сопоставить W[T[i]]с S[p+i]. Максимальное количество откатов iограничено i, то есть при любой неудаче мы можем откатиться только на столько, на сколько мы продвинулись до неудачи. Тогда ясно, что время выполнения равно 2 n .
Цель таблицы — позволить алгоритму не сопоставлять ни один символ Sболее одного раза. Ключевое наблюдение о природе линейного поиска, которое позволяет это сделать, заключается в том, что, проверив некоторый сегмент основной строки по начальному сегменту шаблона, мы точно знаем, в каких местах новое потенциальное совпадение, которое может продолжаться до текущей позиции, может начинаться до текущей позиции. Другими словами, мы «предварительно ищем» сам шаблон и составляем список всех возможных резервных позиций, которые обходят максимум безнадежных символов, не жертвуя при этом никакими потенциальными совпадениями.
Мы хотим иметь возможность искать для каждой позиции в Wдлину максимально возможного начального сегмента, Wведущего к (но не включая) этой позиции, за исключением полного сегмента, начинающегося с W[0]которого, который просто не совпал; это то, насколько далеко нам нужно вернуться назад, чтобы найти следующее совпадение. Следовательно, T[i]это в точности длина максимально возможного правильного начального сегмента, Wкоторый также является сегментом подстроки, заканчивающейся на W[i - 1]. Мы используем соглашение, что пустая строка имеет длину 0. Поскольку несовпадение в самом начале шаблона является особым случаем (нет возможности вернуться назад), мы устанавливаем T[0] = -1, как обсуждается ниже.
Рассмотрим пример W = "ABCDABD"first. Мы увидим, что он следует почти той же схеме, что и основной поиск, и эффективен по тем же причинам. Мы устанавливаем T[0] = -1. Чтобы найти T[1], мы должны обнаружить правильный суффикс , который "A"также является префиксом pattern W. Но правильных суффиксов для "A", поэтому мы устанавливаем T[1] = 0. Чтобы найти T[2], мы видим, что подстрока W[0]- W[1]( "AB") имеет правильный суффикс "B". Однако "B" не является префиксом pattern W. Поэтому мы устанавливаем T[2] = 0.
Продолжая T[3], мы сначала проверяем правильный суффикс длины 1, и, как и в предыдущем случае, он терпит неудачу. Должны ли мы также проверять более длинные суффиксы? Нет, теперь мы замечаем, что есть сокращенный способ проверки всех суффиксов: предположим, что мы обнаружили правильный суффикс , который является правильным префиксом (правильный префикс строки не равен самой строке) и заканчивается на W[2]с длиной 2 (максимально возможной); тогда его первый символ также является правильным префиксом W, следовательно, сам правильный префикс, и он заканчивается на W[1], что, как мы уже определили, не встречалось как T[2] = 0и не T[2] = 1. Следовательно, на каждом этапе правило сокращенного способа заключается в том, что нужно рассматривать проверку суффиксов заданного размера m+1 только в том случае, если на предыдущем этапе был найден допустимый суффикс размера m (т. е. T[x] = m), и не следует беспокоиться о проверке m+2, m+3 и т. д.
Поэтому нам даже не нужно беспокоиться о подстроках, имеющих длину 2, и, как и в предыдущем случае, единственная подстрока длиной 1 терпит неудачу, поэтому T[3] = 0.
Переходим к последующему W[4], 'A'. Та же логика показывает, что самая длинная подстрока, которую нам нужно рассмотреть, имеет длину 1, и, как и в предыдущем случае, она терпит неудачу, поскольку "D" не является префиксом W. Но вместо установки T[4] = 0, мы можем сделать лучше, отметив, что W[4] = W[0], а также что поиск по T[4]подразумевает, что соответствующий Sсимвол , S[m+4]был несовпадением и, следовательно S[m+4] ≠ 'A', . Таким образом, нет смысла перезапускать поиск в S[m+4]; мы должны начать с 1 позиции впереди. Это означает, что мы можем сместить шаблон Wна длину совпадения плюс один символ, поэтому T[4] = -1.
Теперь рассмотрим следующий символ, W[5], который есть 'B': хотя при осмотре самая длинная подстрока выглядит как 'A', мы все равно устанавливаем T[5] = 0. Рассуждения аналогичны тому, почему T[4] = -1. W[5]сам по себе расширяет префиксное соответствие, начатое с W[4], и мы можем предположить, что соответствующий символ в S, S[m+5] ≠ 'B'. Таким образом, возврат до W[5]бессмыслен, но S[m+5]может быть 'A', следовательно T[5] = 0.
Наконец, мы видим, что следующим символом в текущем сегменте, начинающемся с, W[4] = 'A'будет 'B', и действительно, это также W[5]. Более того, тот же аргумент, что и выше, показывает, что нам не нужно искать ранее, W[4]чтобы найти сегмент для W[6], так что это он, и мы берем T[6] = 2.
Поэтому составляем следующую таблицу:
Другой пример:
Еще один пример (немного измененный по сравнению с предыдущим примером):
Еще один более сложный пример:
Пример выше иллюстрирует общую технику сборки таблицы с минимумом суеты. Принцип тот же, что и у общего поиска: большая часть работы уже сделана для достижения текущей позиции, поэтому для выхода из нее нужно сделать совсем немного. Единственное небольшое осложнение заключается в том, что логика, которая верна в конце строки, ошибочно выдает неверные подстроки в начале. Это требует некоторого кода инициализации.
алгоритм kmp_table : ввод : массив символов, W (слово для анализа) выход : массив целых чисел T (таблица, которую нужно заполнить) определение переменных : целое число, pos ← 1 (текущая позиция, которую мы вычисляем в T) целое число, cnd ← 0 (отсчитываемый от нуля индекс в W следующего символа текущей подстроки-кандидата) пусть Т[0] ← -1 пока pos < length(W) do если W[pos] = W[cnd] тогда пусть T[pos] ← T[cnd] иначе пусть T[pos] ← cnd пока cnd ≥ 0 и W[pos] ≠ W[cnd] do пусть cnd ← T[cnd] пусть pos ← pos + 1, cnd ← cnd + 1 let T[pos] ← cnd (необходимо только при поиске всех вхождений слова)
Временная (и пространственная) сложность табличного алгоритма равна , где — длина .W
posинициализируется значением 1, условие цикла равно pos < k, и posувеличивается на 1 в каждой итерации цикла. Таким образом, цикл будет выполнять итерации.
cndинициализируется 0и увеличивается не более чем на 1 в каждой итерации внешнего цикла. T[cnd]всегда меньше cnd, поэтому cndуменьшается не менее чем на 1 в каждой итерации внутреннего цикла; условие внутреннего цикла — cnd ≥ 0. Это означает, что внутренний цикл может выполняться не более того количества раз в общей сложности, сколько выполнился внешний цикл — каждое уменьшение cndна 1 во внутреннем цикле должно иметь соответствующее увеличение на 1 во внешнем цикле. Поскольку внешний цикл требует итераций, внутренний цикл может выполняться не более итераций в общей сложности.В совокупности внешний и внутренний циклы занимают максимум итераций. Это соответствует временной сложности с использованием нотации Big O.
Поскольку две части алгоритма имеют, соответственно, сложность O(k)и O(n), сложность всего алгоритма составляет O(n + k).
Эти сложности одинаковы, независимо от того, сколько повторяющихся шаблонов содержится в Wили S.
Реал -тайм версия KMP может быть реализована с использованием отдельной таблицы функций отказов для каждого символа в алфавите. Если несоответствие происходит в символе в тексте, таблица функций отказов для символа обращается к индексу в шаблоне, в котором произошло несоответствие. Это вернет длину самой длинной подстроки, заканчивающейся при соответствии префиксу шаблона, с дополнительным условием, что символ после префикса - . С этим ограничением символ в тексте не нужно проверять снова на следующей фазе, и поэтому между обработкой каждого индекса текста выполняется только постоянное количество операций [ необходима цитата ] . Это удовлетворяет ограничению вычислений в реальном времени.
Алгоритм Бута использует модифицированную версию функции предварительной обработки KMP для поиска лексикографически минимального поворота строки . Функция отказа постепенно вычисляется по мере поворота строки.
В 2012 году я узнал, что Юрий Матиясевич предвидел алгоритмы линейного сопоставления с образцом и предварительной обработки образов, описанные в этой статье, в частном случае двоичного алфавита еще в 1969 году. Он представил их как конструкции для машины Тьюринга с двумерной рабочей памятью.
