Алгоритм Кнута – Морриса – Пратта - Knuth–Morris–Pratt algorithm
Класс | Строковый поиск |
---|---|
Структура данных | Нить |
Наихудшая производительность | предварительная обработка + сопоставление |
Сложность пространства в наихудшем случае |
В информатике , то Кнута-Морриса-Пратта строка-поиска алгоритма (или 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 2 (1 из 676). Таким образом, если символы случайны, то ожидаемая сложность поиска в строке 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 ( п ).
Разница в том, что 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
).
Алгоритм KMP
Пример алгоритма поиска
Чтобы проиллюстрировать детали алгоритма, рассмотрим (относительно искусственный) запуск алгоритма, где W
= "ABCDABD" и S
= "ABC ABCDAB ABCDABCDABDE". В любой момент времени алгоритм находится в состоянии, определяемом двумя целыми числами:
-
m
, обозначающий позицию, вS
которой начинается предполагаемый матчW
, -
i
, обозначающий индекс текущего рассматриваемого символа вW
.
На каждом шаге алгоритм сравнивает S[m+i]
с W[i]
и приращения , i
если они равны. Это изображено в начале пробега, как
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
Алгоритм сравнивает последовательные символы или W
с «параллельными» символами S
, переходя от одного к другому, увеличивая их, i
если они совпадают. Однако на четвертом шаге S[3] = ' '
не совпадает W[3] = 'D'
. Вместо того, чтобы снова начинать поиск с S[1]
, мы отмечаем, что 'A'
между позициями 1 и 2 в S
; следовательно, предварительно проверив все эти символы (и зная, что они совпадают с соответствующими символами в W
), нет никаких шансов найти начало совпадения. Следовательно, алгоритм устанавливает m = 3
и i = 0
.
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
Это совпадение не выполняется для начального символа, поэтому алгоритм устанавливает m = 4
иi = 0
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
Здесь i
увеличивается почти полное совпадение "ABCDAB"
до i = 6
несовпадения W[6]
и S[10]
. Однако непосредственно перед концом текущего частичного совпадения была та подстрока, "AB"
которая могла быть началом нового совпадения, поэтому алгоритм должен это учитывать. Поскольку эти символы совпадают с двумя символами, предшествующими текущей позиции, повторная проверка этих символов не требуется; алгоритм устанавливает m = 8
(начало начального префикса) и i = 2
(сигнализируя о совпадении первых двух символов) и продолжает сопоставление. Таким образом, алгоритм не только пропускает ранее сопоставленные символы S
( "AB"
), но также и ранее сопоставленные символы W
(префикса "AB"
).
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
Этот поиск в новой позиции немедленно завершается ошибкой, потому что W[2]
(а 'C'
) не соответствует S[10]
(а ' '
). Как и в первом испытании, несоответствие приводит к тому, что алгоритм возвращается к началу W
и начинает поиск с позиции несовпадающего символа S
:, m = 10
reset i = 0
.
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
Совпадение at m=10
немедленно завершается ошибкой, поэтому алгоритм затем пытается m = 11
и i = 0
.
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
И снова алгоритм совпадает "ABCDAB"
, но следующий символ 'C'
,, не совпадает с последним символом 'D'
слова W
. Рассуждая, как и раньше, алгоритм устанавливает m = 15
, чтобы начать с двухсимвольной строки, "AB"
ведущей к текущей позиции, установить i = 2
и продолжить сопоставление с текущей позиции.
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
На этот раз совпадение завершено, и первый символ совпадения - это S[15]
.
Описание псевдокода для алгоритма поиска.
Приведенный выше пример содержит все элементы алгоритма. На данный момент мы предполагаем существование таблицы «частичного совпадения» T
, описанной ниже , которая указывает, где нам нужно искать начало нового совпадения при обнаружении несоответствия. Записи T
построены таким образом, что если у нас есть совпадение, начинающееся с S[m]
этого, не удается при сравнении S[m + i]
с W[i]
, то следующее возможное совпадение начинается с индекса m + i - T[i]
в S
(то есть, T[i]
это количество «обратного отслеживания», которое нам нужно выполнить после несоответствия). Это имеет два следствия: во-первых, T[0] = -1
это означает, что если W[0]
это несоответствие, мы не можем вернуться назад и должны просто проверить следующий символ; и, во-вторых, хотя следующее возможное совпадение начнется с индекса m + i - T[i]
, как в приведенном выше примере, нам не нужно фактически проверять какие-либо T[i]
символы после этого, так что мы продолжаем поиск с W[T[i]]
. Ниже приведен пример реализации псевдокода алгоритма поиска KMP.
algorithm kmp_search: input: an array of characters, S (the text to be searched) an array of characters, W (the word sought) output: an array of integers, P (positions in S at which W is found) an integer, nP (number of positions) define variables: an integer, j ← 0 (the position of the current character in S) an integer, k ← 0 (the position of the current character in W) an array of integers, T (the table, computed elsewhere) let nP ← 0 while j < length(S) do if W[k] = S[j] then let j ← j + 1 let k ← k + 1 if k = length(W) then (occurrence found, if only first occurrence is needed, m ← j - k may be returned here) let P[nP] ← j - k, nP ← nP + 1 let k ← T[k] (T[length(W)] can't be -1) else let k ← T[k] if k < 0 then let j ← j + 1 let k ← k + 1
Эффективность алгоритма поиска
Если предположить , что предварительное существование таблицы T
, поиск часть алгоритма Кнута-Морриса-Пратта имеет сложность O ( п ) , где п представляет длину S
и вывода является большой-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
at 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"
первой. Мы увидим, что он следует той же схеме, что и основной поиск, и эффективен по тем же причинам. Ставим T[0] = -1
. Для того, чтобы найти T[1]
, мы должны обнаружить надлежащий суффикс из "A"
которых также является префикс шаблона W
. Но правильных суффиксов у нет "A"
, поэтому мы устанавливаем T[1] = 0
. Чтобы найти T[2]
, мы видим, что подстрока W[0]
- W[1]
( "AB"
) имеет правильный суффикс "B"
. Однако «B» не является префиксом шаблона 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, м + 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
.
Поэтому составляем следующую таблицу:
i
|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
W[i]
|
А | B | C | D | А | B | D | |
T[i]
|
-1 | 0 | 0 | 0 | -1 | 0 | 2 | 0 |
Другой пример:
i
|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
W[i]
|
А | B | А | C | А | B | А | B | C | |
T[i]
|
-1 | 0 | -1 | 1 | -1 | 0 | -1 | 3 | 2 | 0 |
Другой пример (немного измененный по сравнению с предыдущим примером):
i
|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
W[i]
|
А | B | А | C | А | B | А | B | А | |
T[i]
|
-1 | 0 | -1 | 1 | -1 | 0 | -1 | 3 | -1 | 3 |
Еще один более сложный пример:
i
|
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 год | 22 | 23 | 24 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
W[i]
|
п | А | р | Т | я | C | я | п | А | Т | E | я | N | п | А | р | А | C | ЧАС | U | Т | E | |||
T[i]
|
-1 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 3 | 0 | 0 | 0 | 0 | 0 | 0 |
Описание псевдокода для алгоритма построения таблиц.
Приведенный выше пример иллюстрирует общую технику сборки стола с минимумом суеты. Принцип заключается в общем поиске: большая часть работы уже была сделана для того, чтобы добраться до текущей позиции, поэтому очень мало нужно делать, чтобы выйти из нее. Единственная небольшая сложность заключается в том, что логика, которая верна в конце строки, ошибочно дает неправильные подстроки в начале. Это требует некоторого кода инициализации.
algorithm kmp_table: input: an array of characters, W (the word to be analyzed) output: an array of integers, T (the table to be filled) define variables: an integer, pos ← 1 (the current position we are computing in T) an integer, cnd ← 0 (the zero-based index in W of the next character of the current candidate substring) let T[0] ← -1 while pos < length(W) do if W[pos] = W[cnd] then let T[pos] ← T[cnd] else let T[pos] ← cnd while cnd ≥ 0 and W[pos] ≠ W[cnd] do let cnd ← T[cnd] let pos ← pos + 1, cnd ← cnd + 1 let T[pos] ← cnd (only needed when all word occurrences are searched)
Эффективность алгоритма построения таблиц
Временная (и пространственная) сложность табличного алгоритма равна , где - длина .
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 , чтобы найти лексикографический минимальное вращение строки . Функция разрушения постепенно вычисляется по мере вращения струны.
Примечания
использованная литература
- Кормен, Томас ; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001). «Раздел 32.4: Алгоритм Кнута-Морриса-Пратта». Введение в алгоритмы (второе изд.). MIT Press и McGraw-Hill. стр. 923 -931. ISBN 0-262-03293-7. Zbl 1047.68161 .
- Крошмор, Максим; Риттер, Войцех (2003). Жемчужины стрингологии. Текстовые алгоритмы . Ривер Эдж, Нью-Джерси: World Scientific. С. 20–25. ISBN 981-02-4897-0. Zbl 1078.68151 .
- Шпанковский, Войцех (2001). Анализ среднего случая алгоритмов на последовательностях . Серия Wiley-Interscience по дискретной математике и оптимизации. С предисловием Филиппа Флажоле. Чичестер: Вайли. С. 15–17, 136–141. ISBN 0-471-24063-X. Zbl 0968.68205 .
внешние ссылки
- Анимация апплета поиска строки
- Объяснение алгоритма и образец кода С ++ по Дэвиду Eppstein
- Описание алгоритма Кнута-Морриса-Пратта и код C Кристиана Чарраса и Тьерри Лекрока
- Разъяснение алгоритма с нуля Фленсбургом.
- Чу-Ченг Се (Chu-Cheng Hsieh), разоблачающие этапы запуска KMP .
- Видео лекции НПТЕЛГРД на YouTube
- Видео лекции LogicFirst на YouTube
- Доказательство правильности
- Преобразование между различными формами алгоритма
- Алгоритм Кнута-Морриса-Пратта, написанный на C #
- Алгоритм поиска строк Кнута-Морриса-Пратта (часть I) + мои домашние алгоритмы, формально проверенные с использованием CBMC , алгоритм поиска строк Кнута-Морриса-Пратта (часть II): версия DFA , алгоритм поиска строк Кнута-Морриса-Пратта (часть III): версия без DFA