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

В Информатика, то Кнут – Моррис – Пратт алгоритм поиска строки (или же Алгоритм KMP) ищет вхождения слова "слово" W внутри основной «текстовой строки» S используя наблюдение, что при возникновении несоответствия само слово содержит достаточно информации, чтобы определить, где может начаться следующее совпадение, таким образом минуя повторную проверку ранее согласованных символов.

В алгоритм был задуман Джеймс Х. Моррис и независимо обнаружен Дональд Кнут "несколько недель спустя" от теория автоматов.^[1][2]Моррис и Воан Пратт опубликовал технический отчет в 1970 году.^[3]Эти трое также совместно опубликовали алгоритм в 1977 году.^[1] Самостоятельно в 1969 г. Матиясевич^[4][5] обнаружил аналогичный алгоритм, закодированный двумерной машиной Тьюринга, при изучении проблемы распознавания строк и шаблонов в двоичном алфавите. Это был первый алгоритм линейного времени для сопоставления строк.^[6]

Фон

Алгоритм сопоставления строк хочет найти начальный индекс м в строке S [] что соответствует поисковому слову W [].

Самый простой алгоритм, известный как "Грубая сила "или" Наивный "алгоритм заключается в поиске совпадения слов по каждому индексу м, т.е. позиция в поисковой строке, соответствующая символу S [м]. На каждой позиции м алгоритм сначала проверяет равенство первого символа в искомом слове, т.е. S [м] =? Вт [0]. Если совпадение найдено, алгоритм проверяет другие символы в искомом слове, проверяя последовательные значения индекса позиции слова, я. Алгоритм извлекает символ W [i] в искомом слове и проверяет равенство выражения S [m + i] =? W [i]. Если все последовательные символы совпадают в W на позиции м, то совпадение будет найдено в этой позиции в строке поиска. Если индекс м достигает конца строки, тогда совпадения нет, и в этом случае поиск считается "неудачным".

Обычно пробная проверка быстро отклоняет пробное соответствие. Если строки представляют собой равномерно распределенные случайные буквы, то вероятность совпадения символов составляет 1 из 26. В большинстве случаев пробная проверка отклоняет совпадение по начальной букве. Вероятность совпадения первых двух букв - 1 из 26.² (1 из 676). Итак, если символы случайны, то ожидаемая сложность поиска в строке S [] длины п находится в порядке п сравнения или О(п). Ожидаемая производительность очень хорошая. Если S [] составляет 1 миллион символов и W [] составляет 1000 символов, то поиск строки должен завершиться после примерно 1,04 миллиона сравнений символов.

Ожидаемая производительность не гарантируется. Если строки не случайны, то проверка пробной м может потребоваться много сравнений символов. Худший случай - если две строки совпадают во всех буквах, кроме последней. Представьте себе, что строка S [] состоит из 1 миллиона символов, которые все А, и это слово W [] 999 А персонажи, заканчивающиеся финалом B персонаж. Простой алгоритм сопоставления строк теперь будет проверять 1000 символов в каждой пробной позиции перед тем, как отклонить соответствие и продвинуть пробную позицию. В примере простого строкового поиска теперь потребуется примерно 1000 сравнений символов, умноженных на 1 миллион позиций, для сравнения 1 миллиарда символов. Если длина W [] является k, то производительность в худшем случае О(k⋅п).

Алгоритм KMP имеет лучшую производительность в худшем случае, чем простой алгоритм. KMP тратит немного времени на предварительное вычисление таблицы (порядка размера W [], О(k)), а затем он использует эту таблицу для эффективного поиска строки в О(п).

Разница в том, что KMP использует информацию о предыдущем совпадении, чего не делает простой алгоритм. В приведенном выше примере, когда KMP обнаруживает, что пробное совпадение не выполнено на 1000-м символе (я = 999), потому что S [m + 999] ≠ W [999], он будет увеличиваться м на 1, но он будет знать, что первые 998 символов в новой позиции уже совпадают. KMP соответствует 999 А символов до обнаружения несоответствия на 1000-м символе (позиция 999). Продвижение позиции пробного матча м по одному выбрасывает первый А, поэтому KMP знает, что 998 А символы, которые соответствуют W [] и не проверяет их повторно; то есть KMP устанавливает я до 998. KMP сохраняет свои знания в предварительно вычисленной таблице и двух переменных состояния. Когда KMP обнаруживает несоответствие, таблица определяет, насколько увеличится KMP (переменная м) и где будет возобновлено тестирование (переменная я).

Алгоритм KMP

Пример алгоритма поиска

Чтобы проиллюстрировать детали алгоритма, рассмотрим (относительно искусственный) запуск алгоритма, где W = "ABCDABD" и S = «ABC ABCDAB ABCDABCDABDE». В любой момент времени алгоритм находится в состоянии, определяемом двумя целыми числами:

• м, обозначающий позицию внутри S где предполагаемый матч для W начинается,
• я, обозначающий индекс текущего рассматриваемого символа в W.

На каждом шаге алгоритм сравнивает S [m + i] с W [i] и приращения я если они равны. Это изображено в начале пробега, как

             1 2 мес .: 01234567890123456789012S: ABCABCDAB ABCDABCDABDEW: ABCDABDя: 0123456

Алгоритм сравнивает последовательные символы W "параллельным" персонажам S, переходя от одного к другому, увеличивая я если они совпадают. Однако на четвертом шаге S [3] = "" не совпадает W [3] = 'D'. Вместо того, чтобы снова искать S [1]отметим, что нет 'А' находится между позициями 1 и 2 в S; следовательно, предварительно проверив все эти символы (и зная, что они соответствуют соответствующим символам в W), нет шансов найти начало матча. Следовательно, алгоритм устанавливает м = 3 и я = 0.

             1 2 м: 01234567890123456789012S: ABCABCDAB ABCDABCDABDEW: АBCDABDя: 0123456

Это совпадение не выполняется для начального символа, поэтому алгоритм устанавливает м = 4 и я = 0

             1 2 м: 01234567890123456789012S: ABC ABCDABABCDABCDABDEW: ABCDABDя: 0123456

Здесь, я увеличивается через почти полное совпадение "ABCDAB" до того как я = 6 дающий несоответствие W [6] и S [10]. Однако незадолго до конца текущего частичного совпадения была эта подстрока "AB" это может быть началом нового совпадения, поэтому алгоритм должен это учитывать. Поскольку эти символы соответствуют двум символам до текущей позиции, эти символы не нужно проверять снова; алгоритм устанавливает м = 8 (начало начального префикса) и я = 2 (сигнализируя о совпадении первых двух символов) и продолжает сопоставление. Таким образом, алгоритм не только пропускает ранее согласованные символы S (в "AB"), но также и ранее сопоставленные символы W (префикс "AB").

             1 2 м: 01234567890123456789012S: ABC ABCDABABCDABCDABDEW: ABCDABDя: 0123456

Этот поиск в новой позиции немедленно завершается ошибкой, потому что W [2] (а 'C') не совпадает S [10] (а ' '). Как и в первом испытании, несоответствие заставляет алгоритм возвращаться к началу W и начинает поиск с несовпадающей позиции символа S: м = 10, перезагрузить я = 0.

             1 2 м: 01234567890123456789012S: ABC ABCDABABCDABCDABDEW: АBCDABDя: 0123456

Матч на м = 10 немедленно дает сбой, поэтому алгоритм затем пытается м = 11 и я = 0.

             1 2 м: 01234567890123456789012S: ABC ABCDAB ABCDABCДАБДЕW: ABCDABDя: 0123456

И снова алгоритм соответствует "ABCDAB", но следующий символ, 'C', не соответствует последнему символу 'D' слова W. Рассуждая по-прежнему, алгоритм устанавливает м = 15, чтобы начать с двухсимвольной строки "AB" ведущий к текущей позиции, установить я = 2, и продолжить сопоставление с текущей позиции.

             1 2 м: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDEW: ABCDABDя: 0123456

На этот раз совпадение завершено, и первый символ совпадения - S [15].

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

Приведенный выше пример содержит все элементы алгоритма. На данный момент мы предполагаем наличие таблицы «частичного соответствия». Т, описал ниже, который указывает, где нам нужно искать начало нового совпадения в случае, если текущее совпадение заканчивается несоответствием. Записи Т построены так, что если у нас есть совпадение, начинающееся с S [м] что не удается при сравнении S [m + i] к W [i], то следующее возможное совпадение начнется с индекса m + i - T [i] в S (то есть, Т [я] это количество "откатов", которое нам нужно сделать после несоответствия). Это имеет два значения: во-первых, Т [0] = -1, что означает, что если Вт [0] это несоответствие, мы не можем вернуться назад и должны просто проверить следующий символ; и во-вторых, хотя следующее возможное совпадение будет начинать по индексу m + i - T [i], как в примере выше, нам не нужно проверять Т [я] символов после этого, чтобы продолжить поиск с W [T [i]]. Ниже приведен образец псевдокод реализация алгоритма поиска КМП.

алгоритм 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 позволять к ← к + 1 если k = длина (Вт) тогда                (вхождение найдено, если требуется только первое вхождение, здесь может быть возвращено m ← j - k) позволять P [nP] ← j - k, nP ← nP + 1 позволять k ← T [k] (T [длина (W)] не может быть -1) еще            позволять k ← T [k] если к <0 тогда                позволять j ← j + 1 позволять к ← к + 1

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

Предполагая предыдущее существование таблицы Т, поисковая часть алгоритма Кнута – Морриса – Пратта имеет сложность О(п), куда п это длина S и О является нотация big-O. За исключением фиксированных накладных расходов, возникающих при входе в функцию и выходе из нее, все вычисления выполняются в пока петля. Ограничить количество итераций этого цикла; заметьте, что Т построен так, что если матч, начавшийся в S [м] не удается при сравнении S [m + i] к W [i], то следующее возможное совпадение должно начаться в S [m + (i - T [i])]. В частности, следующее возможное совпадение должно произойти с индексом выше, чем м, так что Т [я] <я.

Этот факт означает, что цикл может выполняться не более 2п раз, так как на каждой итерации выполняется одна из двух ветвей цикла. Первая ветвь неизменно увеличивается я и не меняется м, так что индекс м + я изучаемого в настоящее время характера S увеличена. Вторая ветка добавляет я - Т [я] к м, и, как мы видели, это всегда положительное число. Таким образом, расположение м начала текущего потенциального матча увеличивается. При этом уходит вторая ветка. м + я без изменений, для м получает я - Т [я] добавил к нему, и сразу после Т [я] присваивается как новое значение я, следовательно new_m + new_i = old_m + old_i - T [old_i] + T [old_i] = old_m + old_i. Теперь цикл заканчивается, если м + я = п; следовательно, каждая ветвь цикла может быть достигнута не более чем п раз, поскольку они соответственно увеличиваются либо м + я или же м, и м ≤ м + я: если м = птогда непременно м + я ≥ п, так что, поскольку он увеличивается не более чем на единицу, мы должны были иметь м + я = п в какой-то момент в прошлом, и поэтому в любом случае мы бы закончили.

Таким образом, цикл выполняет не более 2п раз, показывая, что временная сложность алгоритма поиска составляет О(п).

Вот еще один способ подумать о времени выполнения: допустим, мы начинаем согласовывать W и S на позиции я и п. Если W существует как подстрока S в p, тогда W [0..m] = S [p..p + m]В случае успеха, то есть слово и текст совпадают в позициях (W [i] = S [p + i]), увеличиваем я на 1.При неудаче, то есть слово и текст не совпадают в позициях (W [i] ≠ S [p + i]), текстовый указатель остается неподвижным, в то время как указатель слова откатывается на определенную величину (я = Т [я], куда Т это таблица переходов), и мы пытаемся сопоставить W [T [i]] с S [p + i].Максимальное количество откатов я ограничен я, то есть для любого сбоя мы можем откатиться только на столько, сколько мы продвинулись до отказа. Тогда ясно, что время выполнения равно 2п.

Таблица «частичного соответствия» (также известная как «функция отказа»)

Цель таблицы - позволить алгоритму не совпадать ни с одним символом S больше чем единожды. Ключевое наблюдение о природе линейного поиска, которое позволяет этому случиться, заключается в том, что проверка некоторого сегмента основной строки на соответствие начальный сегмент шаблона, мы точно знаем, в каких местах новое потенциальное совпадение, которое могло бы продолжиться до текущей позиции, могло начаться до текущей позиции. Другими словами, мы «предварительно ищем» сам шаблон и составляем список всех возможных резервных позиций, которые обходят максимум безнадежных символов, не жертвуя при этом никакими потенциальными совпадениями.

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

Рабочий пример алгоритма построения таблицы

Рассмотрим пример W = "ABCDABD" первый. Мы увидим, что он следует той же схеме, что и основной поиск, и эффективен по тем же причинам. Мы установили Т [0] = -1. Найти Т [1], мы должны открыть правильный суффикс из "А" который также является префиксом шаблона W. Но нет правильных суффиксов "А", поэтому мы устанавливаем Т [1] = 0. Найти Т [2], мы видим, что подстрока Вт [0] - W [1] ("AB") имеет собственный суффикс "B". Однако "B" не является префиксом шаблона. W. Поэтому положим Т [2] = 0.

Продолжая Т [3], мы сначала проверяем правильный суффикс длины 1, и, как и в предыдущем случае, это не удается. Следует ли нам также проверять более длинные суффиксы? Нет, теперь мы отмечаем, что есть ярлык для проверки все суффиксы: допустим, мы открыли правильный суффикс который является правильный префикс (Правильный префикс строки не равен самой строке) и оканчивается на W [2] длиной 2 (максимально возможная); то его первый символ также является правильным префиксом W, отсюда и собственно префикс, заканчивающийся на W [1], которое, как мы уже определили, не произошло как Т [2] = 0 и нет Т [2] = 1. Следовательно, на каждом этапе сокращенное правило состоит в том, что нужно рассматривать проверку суффиксов заданного размера m + 1, только если действительный суффикс размера m был найден на предыдущем этапе (т. Е. Т [х] = м) и не стоит беспокоиться о проверке m + 2, m + 3 и т. д.

Следовательно, нам даже не нужно беспокоиться о подстроках, имеющих длину 2, и, как и в предыдущем случае, не работает единственная строка с длиной 1, поэтому Т [3] = 0.

Переходим к следующему W [4], 'А'. Та же логика показывает, что самая длинная подстрока, которую нам нужно рассмотреть, имеет длину 1, и, как и в предыдущем случае, она не работает, поскольку «D» не является префиксом W. Но вместо установки Т [4] = 0, мы можем добиться большего, отметив, что W [4] = W [0], а также поиск Т [4] следует соответствующее S персонаж, S [м + 4], было несоответствие, и поэтому S [m + 4] ≠ 'A'. Таким образом, нет смысла возобновлять поиск с S [м + 4]; мы должны начинать на 1 позицию впереди. Это означает, что мы можем изменить шаблон W по длине совпадения плюс один символ, поэтому Т [4] = -1.

Рассматривая теперь следующего персонажа, W [5], который 'B': хотя при осмотре самая длинная подстрока кажется 'А', мы все еще устанавливаем Т [5] = 0. Рассуждения аналогичны тому, почему Т [4] = -1. W [5] сам расширяет совпадение префикса, начатое с W [4], и можно считать, что соответствующий символ в S, S [m + 5] ≠ 'B'. Итак, возвращение до W [5] бессмысленно, но S [м + 5] может быть 'А', следовательно Т [5] = 0.

Наконец, мы видим, что следующий символ в текущем сегменте, начинающийся с W [4] = 'А' было бы 'B', и действительно это тоже W [5]. Более того, тот же аргумент, что и выше, показывает, что нам не нужно смотреть перед W [4] найти сегмент для W [6], так что это все, и берем Т [6] = 2.

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

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

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

Другой более сложный пример:

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

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

алгоритм kmp_table:    Вход: массив символов, W (слово для анализа) выход: массив целых чисел, T (таблица для заполнения) определить переменные: целое число, pos ← 1 (текущая позиция, которую мы вычисляем в T) целое число, cnd ← 0 (отсчитываемый от нуля индекс в W следующего символа текущей подстроки кандидата) позволять Т [0] ← -1 пока pos <длина (Вт) делать        если W [pos] = W [cnd] тогда            позволять T [pos] ← T [cnd] еще            позволять T [pos] ← cnd позволять cnd ← T [cnd] (для увеличения производительности) пока cnd ≥ 0 и W [pos] ≠ W [cnd] делать                позволять cnd ← T [cnd] позволять pos ← pos + 1, cnd ← cnd + 1 позволять T [pos] ← cnd (требуется только при поиске всех вхождений слов)

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

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

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

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

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

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