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

У рачунарству, Кнут-Морис-Прат алгоритам за претрагу низова (или KMP алгоритам) тражи појаве "речи" W у главној "речи" S тако што прати када дође до неслатања, сама реч садржи довољно информације да одреди где може доћи до следећег слатања, тако заобилазећи преиспитивање рамије услкађених карактера.

Алгоритам је замишљен 1974. од стране Кнута и Прата, и независно од њих Мориса. Сва тројица су га заједно објавили 1977. године.

Алгоритам за подударање ниски тражи почетни индекс m у ниски S[] која одговара речи за претрагу W[].

Најједноставнији алгоритам је тражити подударање карактер на уза��топним вредностиа индекса m, положај у ниски који се тражи, нпр. S[m]. Ако индекс м дође до краја ниске онда нема подударања, а за претрагу се каже да није "успела“. На свакој позицији м алгоритам прво проверава једнакост првог карактера у траженој речи, нпр. S[m] =? W[1]. Ако дође до подударања, алгоритам тестира остале карактере у траженој речи тако што проверава узастопне вредности од позиције индекса у речи, i. Алгоритам враћа карактер W[i] у траженој речи и проверава једнакост израза S[m+i] =? W[i]. Ако се сви узастопни карактери подударају у W на позицији m онда је пронађено подударање на тој позицији у претрази ниске.

Обично, прва проба брзо одбацује прво подударање. Ако су ниске равномерно распоређена насумична слова, онда је шанса да се карактери подударају 1 у 26. У већини случајева, прва провера ће одбити подударање у почетном слову. Шанса да се прва два слова подударају је 1 у 26^2 (1 у 676). Тако да ако су карактери насумични, онда је очекивана сложеност тражене ниске S[] дужине k је у реду од k поређења или O(k). Очекиване перформансе су веома добре. Ако је S[] 1 милијарда карактера а W[] је 1000 карактера, онда би претрага ниске требало да се заврши после 1 милијарде поређења карактера (за шта треба отприлике пар секунди).

Te очекиване перформансе нису загарантоване. Ако ниске нису насумичне, онда провера пробе m може захтевати много поређења карактера. Најгори случај је ако се две ниске подударају на свим карактерима осим на задњем. Замислите да се ниска S[] састоји од милијарду карактера који су сви A, и да је реч W[] 999 A карактера прекидајући се са завршним B карактером. Једноставни алгоритам поређења ће сада испитати 1000 карактера на свакој позицији провере пре него што одбије подударање и помера пробну позицију. Једноставни пример претраге ниске би сада поредио око 1000 карактера пута милијарду позиција за трилион поређења карактера (за шта можда треба око сат времена). Ако је дужина W[] n, онда је најгори случај O(k⋅n).

KMP алгоритам нема страховит најгори учинак као у случају директног алгоритма. KMP проведе мало времена правећи таблицу (на основу величине W[], O(n)), и онда користи ту таблицу да уради ефикасну претрагу ниске у O(k). KMP би претражио претходни пример за пар десетина секунди.

Разлика је у томе што KMP користи информације претходних подударања што директни алгоритам не ради. У примеру изнад, када KMP види да пробно поређење на 1000. карактеру није успело (i=999) због S[m+999]≠W[999], то ће повећати m за 1, али ће знати да првих 998 карактера на овој позицији већ одговара. KMP је проверио 999 A карактера пре него што је открио неслатање на хиљадитом карактеру (на позицији 999). Померање позиције пробног поређења m за 1 одбацује прво слово A, тако да KMP зна да има 998 A карактера који се подударају са W[]и не тестира их поново; то јест, KMP поставља i на 998. KMP одржава податке у направљеној таблици и стање две променљиве. Када KMP открије да је дошло до неслатања, таблица одређује колико ће KMP повећати m и где ће наставити тестирање (i).

Да би показали детаље алторитма, урадићемо (релативно вештачки) пролаз алгоритма. У сваком моменту, алгоритам је у стању одређеном од стране два интиџера:

• m који означава позицију у S што је почетак потенцијалног подударања за W
• i је индекс у W који означава карактер који се тренутно разматра.

У сваком кораку поредимо S[m+i] са W[i] и напредујемо ако су једнаки. То је приказано, на почетку рада, као

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

Настављамо упоређујући узастопне карактере из W са "паралелним" карактерима из S, крећући се од једног до другог ако се подударају. Међутим, у четвртом кораку, добијамо да је S[3] је размак и W[3] = 'D', је неподударање. Уместо да почиње поново претрагу на S[1], напомињемо да се 'A' појављује између позиција 0 и 3 у S осим на 0; дакле, када је претходно провериосве те карактере, знамо да нема шансе да се нађе подударање ако их проверимо поново. Стога прелазимо на следећи карактер, постављајући m = 4 и i = 0. (м ће прво постати 3 пошто m + i - T[i] = 0 + 3 - 0 = 3 и онда постаје 4 пошто T[0] = -1)

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456

Брзо добијамо скоро потпуно подударање "ABCDAB" када, на W[6] (S[10]), поново имамо раскорак. Међутим, непосредно пре краја тренутног парцијалног поређења, прошли смо "AB" што може бити почетак новог подударања, тако да морамо узети ово у обзир. Како већ знамо да се ови карактери подударају са два карактера пре тренутне позиције, не морамо их опет проверавати; само ресетујемо m = 8, i = 2 и наставимо поређење тренутног карактера. Дакле, не само да изоставимо претходно упарене карактере из S, али и претходно поређене карактере из W.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456

Ова претрага одмах не успе, међутим, док узорак још увек не садржи размак, током првог прегледа, враћамо се на почетак W и почињемо претрагу на следећем карактеру из S: m = 11, ресетујемо i = 0. (м прво постаје 10 због m + i - T[i] = 8 + 2 - 0 = 10 и онда постаје 11 због T[0] = -1)

             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]]. Следи пример Псеудокод имплементације КМP алгоритма.

algorithm kmp_search:
    input:
        an array of characters, S (the text to be searched)
        an array of characters, W (the word sought)
    output:
        an integer (the zero-based position in S at which W is found)

    define variables:
        an integer, m ← 0 (the beginning of the current match in S)
        an integer, i ← 0 (the position of the current character in W)
        an array of integers, T (the table, computed elsewhere)

    while m+i is less than the length of S, do:
        if W[i] = S[m + i],
            if i equals the (length of W)-1,
                return m
            let i ← i + 1
        otherwise,
            let m ← m + i - T[i],
            if T[i] is greater than -1,
                let i ← T[i]
            else
                let i ← 0
            
    (if we reach here, we have searched all of S unsuccessfully)
    return the length of S

Под претпоставком да претходно постоји таблица T, део претраге КМP алгоритма има комплексност O(n), где је n дужина S и O је Велико О. Осим фиксне главе настале при уласку и изласку из функције, сви прорачуни се изводе у while петљи. Да би везали број итерација у овој петљи; посматрамо да T је конструисан тако да ако дође до слагања које почиње код S[m] не успе поредећи S[m + i] са W[i], онда следеће могуће поклапање мора почети на S[m + (i - T[i])]. Конкретно следеће могуће поклапање се мора догодити на већем индексу од m, тако да T[i] < i.

Ова чињеница указује на то да се петља извршава највише 2n пута. Јер, у свакој итерацији, извршава једну од две гране у петљи. Први огранак се неминовно повећава i и не мења се m, тако да индекс m + i тренутно разматраног карактера из S се повећава. Други grana додаје i - T[i] до m, и како смо видели, ово је увек позитиван број. Тако локација m од почетка текућег потенцијалног подударања се повећава. Сада, петља се завршава ако је m + i = n; Зато се свакој грани петље може се приступити највише k пута, јер се редом повећавају или m + i или m, и m ≤ m + i: ако је m = n, онда је сигурно m + i ≥ n, тако да, пошто се повећава за јединичме инкременте највише, мора да смо имали m + i = n у неком моменту у прошлости, и зато у сваком случају би били готови.

Тако да се петља извршава највише 2n пута, показујући да је временска сложеност алгоритма O(n).

Ово је још један начин да се размишља о извршавању: Рецимо да почнемо да поредимо W и S на позицијама i и p, ако W постоји као подниска S код p, онда W[0 до m] == S[p до p+m]. Након успеха, то јест, реч и текст упарени на позицијама(W[i] == S[p+i]), повећавамо i за 1 (i++). Након неуспеха, то јест, реч и текст се не подударају на позицијама (W[i] != S[p+i]), показивач на текст се још увек задржава, док се показивач на реч враћа уназад за одрећен број (i = T[i], где је T скок у таблици) и покушавамо да упаримо W[T[i]] са S[p+i]. Максимални број зауставања i се граничи са i, односно, за сваки неуспех, можемо само да се зауставимо онолико колико смо напредовали до неуспеха. Онда је јасно да је временска сложеност 2n.

Циљ таблице је да се омогући алторитму да не пореди ниједан карактер из 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] = 0.

Настављајући до T[3], видимо да постоји пречица до провере свих суфикса: рецимо да смо открили одговарајући суфикс којим је одговарајући префикс и завршава се на W[2] дужине 2 (маскимумом); онда је први знак одговарајући префикс W, стога одговарајући префикс, и завршава се на W[1], којим смо већ утврдили да не могу да се јаве у случају T[2]. Отуда у свакој фази, правило пречице је да треба да се провере суфикси дате величине m+1 само ако је валидни суфикс величине m пронађен у претходној фази (нпр T[x]=m).

Стога није нам ни потребно да се бавимо подниском да има дужину 2, како и у претходном случају један једини дужине 1 не успе, па је T[3] = 0.

Пролазимо до додатног W[4], 'A'. Иста логика показује да најдужа подниска коју разматрамо има дужину 1, и мада у овом случају 'A' radi , присетимо се да тражимо сегменте који се завршавају пре тренутног карактера; стога T[4] = 0 as well.

Собзиром на следећи карактер, W[5], који је 'B', употребљавамо следећу логику: ако бисмо пронашли подузорак који почиње пре следећег карактера W[4], али се ипак наставља до следећег W[5], онда би сам имао одговарајући почетни сегмент који се завршава код W[4] али почиње пре њега, што је контрадикторно чињеници да смо већ пронашли 'A' сама је најраније појављивање одговарајућег сегмента који се завршава код W[4]. Стога не морамо да гледамо пре W[4] да би нашли терминалну нису за W[5]. Из тога следи T[5] = 1.

На крају, видимо да ће следећи карактер у текућем сегменту са почетком у 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)
        an array of integers, T (the table to be filled)
    output:
        nothing (but during operation, it populates the table)

    define variables:
        an integer, pos ← 2 (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)

    (the first few values are fixed but different from what the algorithm
might suggest)
    let T[0] ← -1, T[1] ← 0

    while pos is less than the length of W, do:
        (first case: the substring continues)
        if W[pos - 1] = W[cnd], 

          let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1

        (second case: it doesn't, but we can fall back)
        otherwise, if cnd > 0, let cnd ← T[cnd]

        (third case: we have run out of candidates.  Note cnd = 0)
        otherwise, let T[pos] ← 0, pos ← pos + 1

Сложеност алгоритма таблице је O(n), где је n дужина W. Као изузетак неких иницијализација сав посао се обавља у while петљи, то је довољно да се покаже да се ова петља извршава у O(n) времену, које ће вршити истовремено испитивање количине pos и pos - cnd. У првој грани, pos - cnd се чува, како оба pos и cnd се повећавају истовремено, али наравно, pos се повећава. У другој грани, cnd се мења са T[cnd], што смо видели изнад је увек стриктно мања од cnd, чиме се повећава pos - cnd. У трећој грани, pos се повећава и cnd није, тако да обе pos и pos - cnd се повећавају. Како јеpos ≥ pos - cnd, то значи да у свакој фази или pos или доња граница за pos се повећавају; Зато што се алгоритам завршава једном pos = n, мора да се прекине после највише 2n итерација петље, пошто pos - cnd почиње код 1. Стога сложеност алгоритма табеле је O(n).

Пошто два дека алгоритма имају, редом, O(k) и O(n) сложеност, сложеност целог алторитма је O(n + k).

Ове сложености су исте, без обзира колико се понављају обрасци су у W и S.

Верзија рачунања у реалном времену KMP-а се може имплементирати користећи одвојене таблице за неуспех за сваки карактер у алфабету. Ако до неслагања дође код карактера ${\displaystyle x}$ у тексту, таблица за неуспех за карактере ${\displaystyle x}$ консултује се за индекс ${\displaystyle i}$ у обрасцу на којем је дошло до неслагања. Ово ће вратити дужину најдуже ниске завршавајући се код ${\displaystyle i}$ спајањем префикса у обрасцу, са додатним условом да је карактер након префикса ${\displaystyle x}$. Са овим ограничењем, карактер ${\displaystyle x}$ у тексту не мора се поново проверити у следећој фази, и тако само константан број операција се врши између обраде сваког индекса текста. То задовољава ограничење рачунања у реалном времену.

Бут алгоритам користи модификовану верзију KMP функције претпроцесирања да нађе лексикографску минималну ротацију ниске. Функција неуспеха се постепено рачуна како се ниска ротира.

• Бојер-Мур алгоритам за претрагу ниски
• Робин-Карп алгоритам за претрагу ниски
• Ахо-Корасик алгоритам за поређење ниски

• Knuth, Donald; Morris, James H., jr; Pratt, Vaughan (1977). „Fast pattern matching in strings”. SIAM Journal on Computing. 6 (2): 323—350. Zbl 0372.68005. doi:10.1137/0206024. Архивирано из оригинала 04. 01. 2010. г. Приступљено 30. 05. 2013. 
• Cormen, Thomas; Lesiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). „Section 32.4: The Knuth-Morris-Pratt algorithm”. Introduction to Algorithms (Second изд.). MIT Press and McGraw-Hill. стр. 923-931. ISBN 978-0-262-03293-3. Zbl 1047.68161. 
• Crochemore, Maxime; Rytter, Wojciech (2003). Jewels of stringology. Text algorithms. River Edge, NJ: World Scientific. стр. 20—25. ISBN 978-981-02-4897-0. Zbl 1078.68151. 
• Szpankowski, Wojciech (2001). Average case analysis of algorithms on sequences. Wiley-Interscience Series in Discrete Mathematics and Optimization. With a foreword by Philippe Flajolet. Chichester: Wiley. стр. 15—17,136—141. ISBN 978-0-471-24063-1. Zbl 0968.68205. 

Викикњиге имају више информација о String searching/Knuth-Morris-Pratt pattern matcher

• Апликација за претраживање ниски
• Објашњење алгоритма и пример C++ кода од David Eppstein
• Објашњење и имплементација на другим језицима Архивирано на сајту Wayback Machine (16. јун 2016)
• Кнут-Морис-Прат алгоритам Опис C кода од Кристијана Караса и Тиејери Лекрока
• Објашњење алгоритма од нуле Архивирано на сајту Wayback Machine (21. јануар 2020) од FH Flensburg.
• Објашњење корак по корак KMP-a од Chu-Cheng Hsieh.
• [1] NPTELHRD YouTube видео предавање