Википедија

Knut-Moris-Prat algoritam

U računarstvu, Knut-Moris-Prat algoritam za pretragu nizova (ili KMP algoritam) traži pojave "reči" W u glavnoj "reči" S tako što prati kada dođe do neslatanja, sama reč sadrži dovoljno informacije da odredi gde može doći do sledećeg slatanja, tako zaobilazeći preispitivanje ramije uslkađenih karaktera.

Algoritam je zamišljen 1974. od strane Knuta i Prata, i nezavisno od njih Morisa. Sva trojica su ga zajedno objavili 1977. godine.

Pozadina uredi

Algoritam za podudaranje niski traži početni indeks m u niski S[] koja odgovara reči za pretragu W[].

Najjednostavniji algoritam je tražiti podudaranje karakter na uzastopnim vrednostia indeksa m, položaj u niski koji se traži, npr. S[m]. Ako indeks m dođe do kraja niske onda nema podudaranja, a za pretragu se kaže da nije "uspela“. Na svakoj poziciji m algoritam prvo proverava jednakost prvog karaktera u traženoj reči, npr. S[m] =? W[1]. Ako dođe do podudaranja, algoritam testira ostale karaktere u traženoj reči tako što proverava uzastopne vrednosti od pozicije indeksa u reči, i. Algoritam vraća karakter W[i] u traženoj reči i proverava jednakost izraza S[m+i] =? W[i]. Ako se svi uzastopni karakteri podudaraju u W na poziciji m onda je pronađeno podudaranje na toj poziciji u pretrazi niske.

Obično, prva proba brzo odbacuje prvo podudaranje. Ako su niske ravnomerno raspoređena nasumična slova, onda je šansa da se karakteri podudaraju 1 u 26. U većini slučajeva, prva provera će odbiti podudaranje u početnom slovu. Šansa da se prva dva slova podudaraju je 1 u 26^2 (1 u 676). Tako da ako su karakteri nasumični, onda je očekivana složenost tražene niske S[] dužine k je u redu od k poređenja ili O(k). Očekivane performanse su veoma dobre. Ako je S[] 1 milijarda karaktera a W[] je 1000 karaktera, onda bi pretraga niske trebalo da se završi posle 1 milijarde poređenja karaktera (za šta treba otprilike par sekundi).

Te očekivane performanse nisu zagarantovane. Ako niske nisu nasumične, onda provera probe m može zahtevati mnogo poređenja karaktera. Najgori slučaj je ako se dve niske podudaraju na svim karakterima osim na zadnjem. Zamislite da se niska S[] sastoji od milijardu karaktera koji su svi A, i da je reč W[] 999 A karaktera prekidajući se sa završnim B karakterom. Jednostavni algoritam poređenja će sada ispitati 1000 karaktera na svakoj poziciji provere pre nego što odbije podudaranje i pomera probnu poziciju. Jednostavni primer pretrage niske bi sada poredio oko 1000 karaktera puta milijardu pozicija za trilion poređenja karaktera (za šta možda treba oko sat vremena). Ako je dužina W[] n, onda je najgori slučaj O(k⋅n).

KMP algoritam nema strahovit najgori učinak kao u slučaju direktnog algoritma. KMP provede malo vremena praveći tablicu (na osnovu veličine W[], O(n)), i onda koristi tu tablicu da uradi efikasnu pretragu niske u O(k). KMP bi pretražio prethodni primer za par desetina sekundi.

Razlika je u tome što KMP koristi informacije prethodnih podudaranja što direktni algoritam ne radi. U primeru iznad, kada KMP vidi da probno poređenje na 1000. karakteru nije uspelo (i=999) zbog S[m+999]≠W[999], to će povećati m za 1, ali će znati da prvih 998 karaktera na ovoj poziciji već odgovara. KMP je proverio 999 A karaktera pre nego što je otkrio neslatanje na hiljaditom karakteru (na poziciji 999). Pomeranje pozicije probnog poređenja m za 1 odbacuje prvo slovo A, tako da KMP zna da ima 998 A karaktera koji se podudaraju sa W[]i ne testira ih ponovo; to jest, KMP postavlja i na 998. KMP održava podatke u napravljenoj tablici i stanje dve promenljive. Kada KMP otkrije da je došlo do neslatanja, tablica određuje koliko će KMP povećati m i gde će nastaviti testiranje (i).

KMP algoritam uredi

Urađen primer algoritma za tretragu uredi

Da bi pokazali detalje altoritma, uradićemo (relativno veštački) prolaz algoritma. U svakom momentu, algoritam je u stanju određenom od strane dva intidžera:

  • m koji označava poziciju u S što je početak potencijalnog podudaranja za W
  • i je indeks u W koji označava karakter koji se trenutno razmatra.

U svakom koraku poredimo S[m+i] sa W[i] i napredujemo ako su jednaki. To je prikazano, na početku rada, kao 

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

Nastavljamo upoređujući uzastopne karaktere iz W sa "paralelnim" karakterima iz S, krećući se od jednog do drugog ako se podudaraju. Međutim, u četvrtom koraku, dobijamo da je S[3] je razmak i W[3] = 'D', je nepodudaranje. Umesto da počinje ponovo pretragu na S[1], napominjemo da se 'A' pojavljuje između pozicija 0 i 3 u S osim na 0; dakle, kada je prethodno proveriosve te karaktere, znamo da nema šanse da se nađe podudaranje ako ih proverimo ponovo. Stoga prelazimo na sledeći karakter, postavljajući m = 4 i i = 0. (m će prvo postati 3 pošto m + i - T[i] = 0 + 3 - 0 = 3 i onda postaje 4 pošto T[0] = -1) 

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

Brzo dobijamo skoro potpuno podudaranje "ABCDAB" kada, na W[6] (S[10]), ponovo imamo raskorak. Međutim, neposredno pre kraja trenutnog parcijalnog poređenja, prošli smo "AB" što može biti početak novog podudaranja, tako da moramo uzeti ovo u obzir. Kako već znamo da se ovi karakteri podudaraju sa dva karaktera pre trenutne pozicije, ne moramo ih opet proveravati; samo resetujemo m = 8, i = 2 i nastavimo poređenje trenutnog karaktera. Dakle, ne samo da izostavimo prethodno uparene karaktere iz S, ali i prethodno poređene karaktere iz W. 

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

Ova pretraga odmah ne uspe, međutim, dok uzorak još uvek ne sadrži razmak, tokom prvog pregleda, vraćamo se na početak W i počinjemo pretragu na sledećem karakteru iz S: m = 11, resetujemo i = 0. (m prvo postaje 10 zbog m + i - T[i] = 8 + 2 - 0 = 10 i onda postaje 11 zbog T[0] = -1) 

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

Ponovo, odmah dolazi do podudaranja "ABCDAB" ali sledeći karakter, 'C', se ne podudara sa poslednjim karakterom 'D' reči W. Obrazloženje kao i pre, postabljamo m = 15, da počne sa dvokarakternom niskom "AB" vodeći do trenutne pozicije, postavlja se i = 2, i nastavlja poređenje od trenutne pozicije. 

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

Ovog puta smo uspeli da završimo poređenje, čiji su prvi karakteri S[15].

Opis pseudokoda algoritma za pretragu uredi

Primer iznad sadrži sve elemente algoritma. Za sada, pretpostavimo da postoji tablica "delimičnog poređenja" T, opisana ispod, koja pokazuje gde treba da pogledamo za početak novog podudaranja u slučaju da se sadašnji završi neuspehom. Stavke iz T su napravljene tako da ako počinjemo na S[m] koji ne uspe tokom poređenja S[m + i] do W[i], onda će sledeće moguće poređenje početi od m + i - T[i] u S (to jest, T[i] je veličina "bektrekinga" koji treba da uradimo posle neslaganja). Ovo ima dve implikacije: prvu, T[0] = -1, koja pokazuje da ako W[0] je neusklađenost, ne možemo da bektrekujemo i moramo jednostavno da poredimo sledeći karakter; i druga, iako će sldeće moguće podudaranje početi kod indeksa m + i - T[i], kao u primeru iznad, ne moramo u stvari da proveravamo T[i] karaktere posle toga, tako da nastavimo pretragu posle W[T[i]]. Sledi primer Pseudokod implementacije KMP algoritma. 

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

Efikasnost algoritma za pretragu uredi

Pod pretpostavkom da prethodno postoji tablica T, deo pretrage KMP algoritma ima kompleksnost O(n), gde je n dužina S i O je Veliko O. Osim fiksne glave nastale pri ulasku i izlasku iz funkcije, svi proračuni se izvode u while petlji. Da bi vezali broj iteracija u ovoj petlji; posmatramo da T je konstruisan tako da ako dođe do slaganja koje počinje kod S[m] ne uspe poredeći S[m + i] sa W[i], onda sledeće moguće poklapanje mora početi na S[m + (i - T[i])]. Konkretno sledeće moguće poklapanje se mora dogoditi na većem indeksu od m, tako da T[i] < i.

Ova činjenica ukazuje na to da se petlja izvršava najviše 2n puta. Jer, u svakoj iteraciji, izvršava jednu od dve grane u petlji. Prvi ogranak se neminovno povećava i i ne menja se m, tako da indeks m + i trenutno razmatranog karaktera iz S se povećava. Drugi grana dodaje i - T[i] do m, i kako smo videli, ovo je uvek pozitivan broj. Tako lokacija m od početka tekućeg potencijalnog podudaranja se povećava. Sada, petlja se završava ako je m + i = n; Zato se svakoj grani petlje može se pristupiti najviše k puta, jer se redom povećavaju ili m + i ili m, i m ≤ m + i: ako je m = n, onda je sigurno m + i ≥ n, tako da, pošto se povećava za jediničme inkremente najviše, mora da smo imali m + i = n u nekom momentu u prošlosti, i zato u svakom slučaju bi bili gotovi.

Tako da se petlja izvršava najviše 2n puta, pokazujući da je vremenska složenost algoritma O(n).

Ovo je još jedan način da se razmišlja o izvršavanju: Recimo da počnemo da poredimo W i S na pozicijama i i p, ako W postoji kao podniska S kod p, onda W[0 do m] == S[p do p+m]. Nakon uspeha, to jest, reč i tekst upareni na pozicijama(W[i] == S[p+i]), povećavamo i za 1 (i++). Nakon neuspeha, to jest, reč i tekst se ne podudaraju na pozicijama (W[i] != S[p+i]), pokazivač na tekst se još uvek zadržava, dok se pokazivač na reč vraća unazad za odrećen broj (i = T[i], gde je T skok u tablici) i pokušavamo da uparimo W[T[i]] sa S[p+i]. Maksimalni broj zaustavanja i se graniči sa i, odnosno, za svaki neuspeh, možemo samo da se zaustavimo onoliko koliko smo napredovali do neuspeha. Onda je jasno da je vremenska složenost 2n.

Tablica "delimičnog poklapanja" (takođe poznata kao "funkcija neuspeha") uredi

Cilj tablice je da se omogući altoritmu da ne poredi nijedan karakter iz S više od jednom. Ključni zaključak o prirodi linearne pretrage koja omogućava da se to desi je da se proveri mali segment glavnog niza prema jednom početnom segmentu obrasca, znamo tačno na kojim mestima novo potencijalno poređenje može da nastavi do trenutne pozicije i može da počne pre trenutne pozicije. Drugim rečima, mi "prvo-tražimo" sam uzorak i sastavljamo listu svih mogućih vraćanja pozicija koje zaobilaze maksimum beznadežnih karaktera svedok se ne žrtvuju nijedna potencijalna pogađanja tokom toga.

Želimo da budemo u stanju da pogledamo, za svaku poziciju u W, dužinu najdužeg mogućeg početnog segmenta iz W vodeći do (ali ne uključujući) tu poziciju, umesto ceo segment počevši od W[0] koji upravi nije prošao poređenje; ovo je koliko daleko moramo da se vraimo u traženju sledećeg poklapanja. Stoga T[i] je upravo dužina najdužeg mogućeg odgovarajućeg početnog segmenta W koji je takođe segment podniza koji se završava kod W[i - 1]. Koristimo konvencijz da prazna niska ima dužinu 0. Pošto je neslaganje na samom početku uzorak poseban slučaj (ne postoji mogućnost bektrekinga), postavljamo T[0] = -1, kao što je već iznad.

Urađen primer algoritma za pravljenje tablice uredi

Razmatramo primer, W = "ABCDABD" prvo. Videćemo da sledi isti obrazac kao glavna pretraga, i efikasan je iz sličnih razloga. Postavljamo T[0] = -1. Da bi našli T[1], moramo da otkrijemo odgovarajući sufkks od "A" koji je isto i prefiks od W. Ali nema odgovarajućih sufiksa od "A", tako da postavljamo T[1] = 0. Na isti način, T[2] = 0.

Nastavljajući do T[3], vidimo da postoji prečica do provere svih sufiksa: recimo da smo otkrili odgovarajući sufiks kojim je odgovarajući prefiks i završava se na W[2] dužine 2 (maskimumom); onda je prvi znak odgovarajući prefiks W, stoga odgovarajući prefiks, i završava se na W[1], kojim smo već utvrdili da ne mogu da se jave u slučaju T[2]. Otuda u svakoj fazi, pravilo prečice je da treba da se provere sufiksi date veličine m+1 samo ako je validni sufiks veličine m pronađen u prethodnoj fazi (npr T[x]=m).

Stoga nije nam ni potrebno da se bavimo podniskom da ima dužinu 2, kako i u prethodnom slučaju jedan jedini dužine 1 ne uspe, pa je T[3] = 0.

Prolazimo do dodatnog W[4], 'A'. Ista logika pokazuje da najduža podniska koju razmatramo ima dužinu 1, i mada u ovom slučaju 'A' radi , prisetimo se da tražimo segmente koji se završavaju pre trenutnog karaktera; stoga T[4] = 0 as well.

Sobzirom na sledeći karakter, W[5], koji je 'B', upotrebljavamo sledeću logiku: ako bismo pronašli poduzorak koji počinje pre sledećeg karaktera W[4], ali se ipak nastavlja do sledećeg W[5], onda bi sam imao odgovarajući početni segment koji se završava kod W[4] ali počinje pre njega, što je kontradiktorno činjenici da smo već pronašli 'A' sama je najranije pojavljivanje odgovarajućeg segmenta koji se završava kod W[4]. Stoga ne moramo da gledamo pre W[4] da bi našli terminalnu nisu za W[5]. Iz toga sledi T[5] = 1.

Na kraju, vidimo da će sledeći karakter u tekućem segmentu sa početkom u W[4] = 'A' biti 'B', i zaista ovo je takođe W[5]. Štaviše, isti argument kao iznad pokazuje da ne moramo da tražimo pre W[4] da bi našli segment za W[6], tako da to je to, i uzimamo T[6] = 2.

Zato smo sastavili sledeću tabelu:

i 0 1 2 3 4 5 6
W[i] A B C D A B D
T[i] -1 0 0 0 0 1 2

Drugi primer zanimljiviji i složeniji:

i 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3
W[i] P A R T I C I P A T E I N P A R A C H U T E
T[i] -1 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 1 2 3 0 0 0 0 0

Opis pseudokoda algoritma za pravljenje tablice uredi

Primer iznad ilustruje opštu tehniku sklapanja tabele sa minimumom napora. Princip je da od ukupne pretrage: veći deo posla je već urađeno u dobijanju trenutne pozicije, dakle veoma malo treba da se uradi da se ostavi. Samo manja komplikacija je da je logika koja je ispravna kasno u nizu pogrešno ne daje odgovarajuće podniske na početku. To zahteva malu inicijalizaciju koda. 

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

Efikasnost algoritma za pravljenje tablice uredi

Složenost algoritma tablice je O(n), gde je n dužina W. Kao izuzetak nekih inicijalizacija sav posao se obavlja u while petlji, to je dovoljno da se pokaže da se ova petlja izvršava u O(n) vremenu, koje će vršiti istovremeno ispitivanje količine pos i pos - cnd. U prvoj grani, pos - cnd se čuva, kako oba pos i cnd se povećavaju istovremeno, ali naravno, pos se povećava. U drugoj grani, cnd se menja sa T[cnd], što smo videli iznad je uvek striktno manja od cnd, čime se povećava pos - cnd. U trećoj grani, pos se povećava i cnd nije, tako da obe pos i pos - cnd se povećavaju. Kako jepos ≥ pos - cnd, to znači da u svakoj fazi ili pos ili donja granica za pos se povećavaju; Zato što se algoritam završava jednom pos = n, mora da se prekine posle najviše 2n iteracija petlje, pošto pos - cnd počinje kod 1. Stoga složenost algoritma tabele je O(n).

Efikasnost KMP algoritma uredi

Pošto dva deka algoritma imaju, redom, O(k) i O(n) složenost, složenost celog altoritma je O(n + k).

Ove složenosti su iste, bez obzira koliko se ponavljaju obrasci su u W i S.

Varijante uredi

Verzija računanja u realnom vremenu KMP-a se može implementirati koristeći odvojene tablice za neuspeh za svaki karakter u alfabetu. Ako do neslaganja dođe kod karaktera   u tekstu, tablica za neuspeh za karaktere   konsultuje se za indeks   u obrascu na kojem je došlo do neslaganja. Ovo će vratiti dužinu najduže niske završavajući se kod   spajanjem prefiksa u obrascu, sa dodatnim uslovom da je karakter nakon prefiksa  . Sa ovim ograničenjem, karakter   u tekstu ne mora se ponovo proveriti u sledećoj fazi, i tako samo konstantan broj operacija se vrši između obrade svakog indeksa teksta. To zadovoljava ograničenje računanja u realnom vremenu.

But algoritam koristi modifikovanu verziju KMP funkcije pretprocesiranja da nađe leksikografsku minimalnu rotaciju niske. Funkcija neuspeha se postepeno računa kako se niska rotira.

Vidi još uredi

Literatura uredi

Spoljašnje veze uredi

 
Vikiknjige imaju više informacija o String searching/Knuth-Morris-Pratt pattern matcher
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Кнут-Морис-Прат_алгоритам&oldid=25411283”