КМП - Збіг Підрядків: Ніколи Не Відступаємо

Чому нездоровий пошук марнує роботу

Найбільш очевидний спосіб знайти закономірність довжиною m всередині тексту довжиною n — спробувати кожне стартове положення, порівнюючи символ за символом до тих пір, поки вся закономірність не збігнеться або не станеться розбіжності. У типових текстах це швидко, але при ворожому чи надзвичайно повторюваному вході це дуже погано: пошук "AAAAB" всередині довгого пробілу "A" збігається майже в кожному стартовому положенні перед тим, як не відповідає на п'ятому символі, що дає O(n·m) порівнянь у найгіршому випадку.

Розуміння: закономірність вже розповідала вам щось

Алгоритм Кнутса-Морріса-Пратта 1977 року помічає, що коли відбувається невідповідність після збігу певних символів, ці зіставлені символи є фрагментом закономірності – ви точно знаєте, які це за символами, оскільки вони зійшлися. Якщо частина цього фрагменту також є префіксом закономірності, то можна продовжити порівняння починаючи з середини закономірності замість того, щоб починати з її першого символу, і – що особливо важливо – без необхідності переміщувати курсор тексту назад.

Побудова функції невдалості

Це попередньо обчислюється один раз, виключно на основі шаблону, до того, як буде здійснено будь-який перебір тексту. failure[i] – це довжина найдовшого власного префіксу шаблону, який також є власним суфіксом pattern[0..i]:

buildFailure(pattern): failure = масив довжиною m, failure[0] = 0 k = 0 // довжина поточного збігаючого префікса for i = 1 to m - 1: while k > 0 and pattern[i] != pattern[k]: k = failure[k - 1] // повертаємося до коротшого префікса if pattern[i] == pattern[k]: k += 1 failure[i] = k return failure Це попереднє оброблення само по собі коштує O(m), використовуючи той самий трюк "ніколи не рухатися назад" на шаблоні, порівнюваному з самим собою.

buildFailure(pattern):
  failure = array of length m, failure[0] = 0
  k = 0                          // length of current matching prefix
  for i = 1 to m - 1:
    while k > 0 and pattern[i] != pattern[k]:
      k = failure[k - 1]         // fall back to a shorter prefix
    if pattern[i] == pattern[k]:
      k += 1
    failure[i] = k
  return failure

Пошук

З готовою функцією відмов (failure function) пошук тексту потребує лише одного прямого проходу по тексту — індекс тексту ніколи не зменшується, лише індекс шаблону перестрибує назад, використовуючи попередньо обчислену таблицю:

search(text, pattern, failure): j = 0 // індекс у шаблоні for i = 0 to n - 1: // індекс у тексті, ніколи не зменшується while j > 0 and text[i] != pattern[j]: j = failure[j - 1] // перестрибуємо шаблон назад, а не текст if text[i] == pattern[j]: j += 1 if j == m: report match ending at i j = failure[j - 1] // продовжуємо пошук перекриваючихся збігів Because the text index i only ever increases, each text character is examined a bounded number of times overall (an amortised argument on the pattern index gives O(n) total work for the scan), so the whole algorithm — preprocessing plus search — runs in O(n + m), with no dependence on how repetitive either string is.

search(text, pattern, failure):
  j = 0                                   // index into pattern
  for i = 0 to n - 1:                     // index into text, never decreases
    while j > 0 and text[i] != pattern[j]:
      j = failure[j - 1]                  // jump the pattern backward, not the text
    if text[i] == pattern[j]:
      j += 1
    if j == m:
      report match ending at i
      j = failure[j - 1]                  // continue looking for overlapping matches

Використання

Пошукові інструменти на основі алгоритму КМП або подібних за своєю суттю переважно використовуються для пошуку безпосередніх підрядків у простих текстових даних. Це обумовлено тим, що найгірший сценарій алгоритму КМП гарантовано лінійний, на відміну від звичайного скану, який може бути прийнятним в середньому, але патологічним при повторюваних вхідних даних — саме такого типу вхідних даних можуть генерувати супротивник або геном (довгі послідовності повторних основ). Інструменти біоінформатики використовують його для пошуку коротких мотивів у довгих послідовностях ДНК та білків. Ідея про функцію невдачі алгоритму КМП також безпосередньо узагальнюється в алгоритм Ахо-Корсака, який будує єдиний автомат для одночасного пошуку багатьох шаблонів в одному проході по тексту.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте KMP String Matching і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.