Алгоритм Кнута – Морриса – Пратта - Knuth–Morris–Pratt algorithm

Алгоритм Кнута – Морриса – Пратта

Класс	Строковый поиск
Структура данных	Нить
Наихудшая производительность	${\ Displaystyle \ Theta (м)}$предварительная обработка + сопоставление${\ Displaystyle \ Theta (п)}$
Сложность пространства в наихудшем случае	${\ Displaystyle \ Theta (м)}$

В информатике , то Кнута-Морриса-Пратта строка-поиска алгоритма (или 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 из 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 = 10reset 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существует как подстрока Sat 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.

Поэтому составляем следующую таблицу:

Другой пример:

Другой пример (немного измененный по сравнению с предыдущим примером):

Еще один более сложный пример:

Описание псевдокода для алгоритма построения таблиц.

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

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)

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

Временная (и пространственная) сложность табличного алгоритма равна , где - длина . ${\ Displaystyle О (к)}$${\ displaystyle k}$W

• Внешний цикл: posинициализируется значением 1, условие цикла равно pos < k, и posувеличивается на 1 на каждой итерации цикла. Таким образом, цикл будет повторяться.${\ displaystyle k-1}$

• Внутренний цикл: cndинициализируется 0и увеличивается максимум на 1 в каждой итерации внешнего цикла. T[cnd]всегда меньше cnd, поэтому cndуменьшается как минимум на 1 в каждой итерации внутреннего цикла; условие внутреннего цикла cnd ≥ 0. Это означает, что внутренний цикл может выполняться не больше, чем столько раз, сколько выполнялся внешний цикл - каждое уменьшение cndна 1 во внутреннем цикле должно иметь соответствующее увеличение на 1 во внешнем цикле. Поскольку внешний цикл требует итераций, внутренний цикл может занимать в сумме не более итераций.${\ displaystyle k-1}$${\ displaystyle k-1}$

В совокупности внешний и внутренний циклы занимают максимум итераций. Это соответствует временной сложности с использованием нотации Big O . ${\ displaystyle 2k-2}$${\ Displaystyle О (к)}$

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

Поскольку две части алгоритма имеют сложность соответственно O(k)и O(n), сложность всего алгоритма составляет O(n + k).

Эти сложности одинаковы, независимо от того, сколько повторяющихся паттернов содержится в Wили S.

Варианты

В режиме реального время версия KMP может быть реализована с помощью отдельной функции сбоя таблицы для каждого символа в алфавите. Если несоответствие происходит на символе в тексте, таблица функций отказа для символа сверяется с индексом в шаблоне, в котором произошло несоответствие. Это вернет длину самой длинной подстроки, заканчивающейся совпадением префикса шаблона, с добавленным условием, что символ после префикса . С этим ограничением символ в тексте не нужно снова проверять на следующем этапе, и поэтому между обработкой каждого индекса текста выполняется только постоянное количество операций. Это удовлетворяет ограничению вычислений в реальном времени. ${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle x}$${\ displaystyle x}$

В алгоритме Бута использует модифицированную версию функции предварительной обработки 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