Русская Википедия:Алгоритм Кнута — Морриса — Пратта

Материал из Онлайн справочника
Версия от 11:48, 19 июля 2023; EducationBot (обсуждение | вклад) (Новая страница: «{{Русская Википедия/Панель перехода}} '''Алгоритм Кнута — Морриса — Пратта''' (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных, то есть р...»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигацииПерейти к поиску

Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать асимптотически более эффективный алгоритм невозможно.

Алгоритм был разработан Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом[1]. Результаты своей работы они опубликовали совместно в 1977 году[2].

Постановка задачи

Даны образец (строка) <math>\displaystyle S</math> и строка <math>\displaystyle T</math>. Требуется определить индекс, начиная с которого образец <math>\displaystyle S</math> содержится в строке <math>\displaystyle T</math>. Если <math>\displaystyle S</math> не содержится в <math>\displaystyle T</math> — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число). При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.

Идея

Алгоритм Ахо — Корасик также позволяет искать одну строку за линейное время. Но слабое место этого алгоритма — конечный автомат, который в явном виде строится за O(|needle|·|Σ|) операций и требует столько же памяти.

Если искать всего одну строку, каждое состояние будет иметь только один «прямой» переход. Побочные же переходы будем вычислять динамически, никак их не кэшируя.

если haystack[i] = needle[state]
  то state = state + 1
  иначе state = побочный_переход(state, haystack[i])

Легко заметить, что суффиксные ссылки алгоритма Ахо — Корасик представляют собой префикс-функцию искомого шаблона.

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

Рассмотрим сравнение строк на позиции <math>\displaystyle i</math>, где образец <math>\displaystyle S[ 0, m - 1 ]</math> сопоставляется с частью текста <math>\displaystyle \displaystyle T[ i, i + m - 1 ]</math>. Предположим, что первое несовпадение произошло между <math>\displaystyle \displaystyle T[ i + j ]</math> и <math>\displaystyle S[ j ]</math>, где <math>\displaystyle 1 < j < m</math>. Тогда <math>\displaystyle T[ i, i + j - 1 ] = S[ 0, j - 1 ] = P</math> и <math>\displaystyle a = T[ i + j ] \ne S[ j ] = b</math>.

При сдвиге вполне можно ожидать, что префикс (начальные символы) образца <math>\displaystyle S</math> сойдется с каким-нибудь суффиксом (конечные символы) текста <math>\displaystyle P</math>. Длина наиболее длинного префикса, являющегося одновременно суффиксом, есть значение префикс-функции от строки <math>\displaystyle S</math> для индекса <math>\displaystyle j</math>.

Это приводит нас к следующему алгоритму: пусть <math>\displaystyle \rm{\pi}[ j ]</math> — значение префикс-функции от строки <math>\displaystyle S[ 0, m - 1 ]</math> для индекса <math>\displaystyle j</math>. Тогда после сдвига мы можем возобновить сравнения с места <math>\displaystyle T[ i + j ]</math> и <math>\displaystyle S[ \rm{\pi}[ j ] ]</math> без потери возможного местонахождения образца. Можно показать, что таблица <math>\displaystyle \rm{\pi}</math> может быть вычислена (амортизационно) за <math>\displaystyle \Theta( m )</math> сравнений перед началом поиска. А поскольку строка <math>\displaystyle T</math> будет пройдена ровно один раз, суммарное время работы алгоритма будет равно <math>\displaystyle \Theta(m + n)</math>, где <math>n</math> — длина текста <math>\displaystyle T</math>.

Псевдокод для алгоритма

function KMP(S, T) 
  k ← 0
  A ← ø   // A - пустое множество
  π ← Prefix_Function(S)    // считается префикс-функция от образца S
  for i = 1 to |T| do    // |T| - длина строки T
    while k > 0 and T[i] ≠ S[k + 1] do
      k ←  π[k]
    end while
    if T[i] = S[k + 1] then
      k ← k + 1
    end if
    if k = |S| then
      A ← A ⋃ {i - |S| + 1} // это если мы в начале считали префикс-функцию
      A ← A ⋃ {i}           // это если мы в начале считали z-функцию
      k ← π[k]
    end if
  end for
  return A  
end function

Функция возвращает <math>\displaystyle A</math> — множество номеров элементов строки <math>\displaystyle T</math>, которыми оканчиваются найденные вхождения <math>\displaystyle S</math> в <math>\displaystyle T</math>.

См. также

Примечания

Шаблон:Примечания

Ссылки

Шаблон:Wikibooks

Шаблон:Перевести Шаблон:RqШаблон:СтрокиШаблон:Дональд Кнут