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

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

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

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

Најједноставнији алгоритам је тражити подударање карактер на узастопним вредностиа индекса m, положај у ниски који се тражи, нпр. S[m]. Ако индекс м дође до краја ниске онда нема подударања, а за претрагу се каже да није "успела“. На свакој позицији м алгоритам прво проверава једнакост првог карактера у траженој речи, нпр. S[m] =? W. Ако дође до подударања, алгоритам тестира остале карактере у траженој речи тако што проверава узастопне вредности од позиције индекса у речи, 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, то ће повећати m за 1, али ће знати да првих 998 карактера на овој позицији већ одговара. KMP је проверио 999 A карактера пре него што је открио неслатање на хиљадитом карактеру (на позицији 999). Померање позиције пробног поређења m за 1 одбацује прво слово A, тако да KMP зна да има 998 A карактера који се подударају са W[]и не тестира их поново; то јест, KMP поставља i на 998. KMP одржава податке у направљеној таблици и стање две променљиве. Када KMP открије да је дошло до неслатања, таблица одређује колико ће KMP повећати m и где ће наставити тестирање (i).

KMP алгоритам

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

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 је размак и W = 'D', је неподударање. Уместо да почиње поново претрагу на S, напомињемо да се 'A' појављује између позиција 0 и 3 у S осим на 0; дакле, када је претходно провериосве те карактере, знамо да нема шансе да се нађе подударање ако их проверимо поново. Стога прелазимо на следећи карактер, постављајући m = 4 и i = 0. (м ће прво постати 3 пошто m + i - T[i] = 0 + 3 - 0 = 3 и онда постаје 4 пошто T = -1) 1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456

Брзо добијамо скоро потпуно подударање "ABCDAB" када, на W (S), поново имамо раскорак. Међутим, непосредно пре краја тренутног парцијалног поређења, прошли смо "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 = -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.

Опис псеудокода алгоритма за претрагу

Пример изнад садржи све елементе алгоритма. За сада, претпоставимо да постоји таблица "делимичног поређења" T, описана испод, која показује где треба да погледамо за почетак новог подударања у случају да се садашњи заврши неуспехом. Ставке из T су направљене тако да ако почињемо на S[m] који не успе током поређења S[m + i] до W[i], онда ће следеће могуће поређење почети од m + i - T[i] у S (то јест, T[i] је величина "бектрекинга" који треба да урадимо после неслагања). Ово има две импликације: прву, T = -1, која показује да ако W је неусклађеност, не можемо да бектрекујемо и морамо једноставно да поредимо следећи карактер; и друга, иако ће слдеће могуће подударање почети код индекса 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 који управи није прошао поређење; ово је колико далеко морамо да се враимо у тражењу следећег поклапања. Стога T[i] је управо дужина најдужег могућег одговарајућег почетног сегмента W који је такође сегмент подниза који се завршава код W[i - 1]. Користимо конвенцијз да празна ниска има дужину 0. Пошто је неслагање на самом почетку узорак посебан случај (не постоји могућност бектрекинга), постављамо T = -1, као што је већ изнад.

Урађен пример алгоритма за прављење таблице Разматрамо пример, W = "ABCDABD" прво. Видећемо да следи исти образац као главна претрага, и ефикасан је из сличних разлога. Постављамо T = -1. Да би нашли T, морамо да откријемо одговарајући суфккс од "A" који је исто и префикс од W. Али нема одговарајућих суфикса од "A", тако да постављамо T = 0. На исти начин, T = 0.