КМП алгоритмі: Ішкі мәтін орнын табудың O(n) уақытындағы алгоритмі

Кіріспе

Үлкен O(n) уақытында берілген сөйлемдегі кіші мәтін орнын табу алгоритмі. Компьютер ғылымында, Кнут-Моррис-Пратт алгоритмі (немесе KMP алгоритмі) – бұл "сөз" W-тің негізгі "мәтіндік тізбек" S ішінде кездесетін жерлерін іздейтін алгоритм. Алгоритмнің ерекшелігі, сәйкессіздік туғанда, сөздің өзі келесі сәйкестіктің қайдан басталатынын анықтау үшін жеткілікті ақпаратты камтиды, соның арқасында бұрын сәйкес келген символдарды қайта қарау қажеттігінен құтылуға болады. Алгоритмді Джеймс Х. Моррис жасады, ал Дональд Кнут "бірнеше аптадан кейін" автоматтар теориясы арқылы дербес түрде тапты. 1970 жылы Моррис пен Воган Пратт техникалық есеп жариялады. Үшеуі де 1977 жылы алгоритмді бірлесіп жариялады. Ал 1969 жылы Матиясевич екі өлшемді Тьюринг машинасымен кодталған ұқсас алгоритмді тапты, ол бинарлық алфавиттегі тізбек үлгісін анықтау мәселесін зерттеген кезде. Бұл – тізбектерді сәйкестендірудің алғашқы сызықтық уақытты алгоритмі.

Өмірбаян

Сызықтарды салыстыру алгоритмі іздеу сөзіне сәйкес келетін S[] тізбегіндегі бастапқы индекс m табуды көздейді. Ең қарапайым алгоритм, "күшпен іздеу" немесе "наивті" алгоритмі деп аталатын, әр m индексінде сөздің сәйкестігін іздеу болып табылады, яғни ізделіп жатқан тізбектегі S[m] таңбасына сәйкес келетін орын. Әрбір m позициясында алгоритм ізделіп жатқан сөздің бірінші таңбасының теңдігін тексереді, яғни S[m] =? W[0]. Егер сәйкестік табылса, алгоритм ізделіп жатқан сөздің басқа таңбаларын сөз позициясы индексінің кезекті мәндерін тексеру арқылы тексереді. Алгоритм ізделіп жатқан сөзден W[i] таңбасын алып, S[m+i] =? W[i] теңдігін тексереді. Егер W сөзіндегі барлық кезекті таңбалар m позициясында сәйкес келсе, онда іздеу тізбегіндегі сол позицияда сәйкестік табылды. Егер индекс m тізбектің соңына жетсе және сәйкестік табылмайтын болса, онда іздеу "сәтсіз аяқталды" деп есептеледі. Әдетте, сынақ тексеруі сынақ сәйкестігін жылдам қабылдамайды. Егер тізбектер біркелкі түрде кездейсоқ әріптерден тұрса, онда таңбалардың сәйкес келу ықтималдығы 26-дан 1-ге тең. Көп жағдайда сынақ тексеруі алғашқы әріпте сәйкессіздікті анықтайды. Алғашқы екі әріптің сәйкес келу ықтималдығы 26 әріптің ішінде 1/(26^2) құрайды. Егер таңбалар кездейсоқ болса, онда ұзындығы n болатын S[] тізбегін іздеудің күрделілігі n салыстыруға немесе O(n) тең болады. Күтілетін нәтиже өте жақсы. Егер S[] 1 миллион таңбадан, ал W[] 1000 таңбадан тұрса, онда тізбекті іздеу шамамен 1,04 миллион таңбаны салыстырудан кейін аяқталуы керек. Бірақ бұл күтілетін нәтиже кепілдік берілмейді. Егер тізбектер кездейсоқ болмаса, онда m сынағын тексеру көптеген таңбаларды салыстыруды қажет етуі мүмкін. Ең нашар жағдайда, екі тізбектің соңғы әріптен басқа барлық әріптері сәйкес келеді. Мысалы, S[] тізбегінің барлық 1 миллион таңбасы A-дан тұрады, ал W[] сөзі 999 A таңбасынан және соңғы B таңбасынан тұрады. Бұл жағдайда қарапайым тізбекті салыстыру алгоритмі әрбір сынақ позициясында 1000 таңбаны тексереді, содан кейін сәйкестік жоқ деп танып, сынақ позициясын алға жылжытады. Осылайша, қарапайым жолды іздеу мысалы шамамен 1000 таңбаны салыстыруға және 1 миллион позицияға көбейтіп, 1 миллиард таңбаны салыстыруды қажет етеді. Егер W[] тізбегінің ұзындығы k болса, онда ең нашар жағдайда өнімділік O(k⋅n) тең болады. KMP алгоритмі тікелей алгоритмге қарағанда ең нашар жағдайда жақсы жұмыс істейді. KMP алгоритмі кестелерді алдын ала есептеуге аз уақыт жұмсайды (W[] тізбегінің мөлшеріне пропорционалды, O(k)), содан кейін ол осы кестелерді O(n) уақытында тізбені тиімді іздеу үшін пайдаланады. Айырмашылық KMP алгоритмі алдыңғы сәйкестік туралы ақпаратты пайдаланады, ал тікелей алгоритм жоқ. Жоғарыдағы мысалда, KMP алгоритмі сынақ сәйкестігінің 1000-шы таңбасында (i = 999) сәтсіз екенін анықтағанда, өйткені S[m+999] ≠ W[999], ол m-ді 1-ге арттырады, бірақ жаңа позициядағы алғашқы 998 таңбаның сәйкес келетінін біледі. KMP алгоритмі 999 A таңбасын сәйкес келтірді, бірақ 1000-шы таңбада (999 орын) сәйкессіздікті анықтады. Сынақ сәйкестігінің m позициясын бірге жылжыту алғашқы A таңбасын жояды, сондықтан KMP W[] тізбегімен сәйкес келетін 998 A таңбасы бар екенін біледі және оларды қайтадан сынамайды; яғни, KMP i-ді 998-ге қояды. KMP алгоритмі алдын ала есептелген кестеде және екі күйлік айнымалыда өзінің білімін сақтайды. KMP сәйкессіздікті анықтаған кезде кесте KMP-нің қаншалықты жылжуын (m айнымалысы) және сынақты қай жерден қайта бастауын (i айнымалысы) анықтайды.

A string matching algorithm wants to find the starting index m in string S[] that matches the search word W[]. The most straightforward algorithm, known as the "brute force" or "naive" algorithm, is to look for a word match at each index m, i. e. the position in the string being searched that corresponds to the character S[m]. At each position m the algorithm first checks for equality of the first character in the word being searched, i. e. S[m] =? W[0]. If a match is found, the algorithm tests the other characters in the word being searched by checking successive values of the word position index, i. The algorithm retrieves the character W[i] in the word being searched and checks for equality of the expression S[m+i] =? W[i]. If all successive characters match in W at position m, then a match is found at that position in the search string. If the index m reaches the end of the string then there is no match, in which case the search is said to "fail". Usually, the trial check will quickly reject the trial match. If the strings are uniformly distributed random letters, then the chance that characters match is 1 in 26. In most cases, the trial check will reject the match at the initial letter. The chance that the first two letters will match is 1 in 26 (1 in 26^2 chances of a match over 26 possible letters). So if the characters are random, then the expected complexity of searching string S[] of length n is on the order of n comparisons or O(n). The expected performance is very good. If S[] is 1 million characters and W[] is 1000 characters, then the string search should complete after about 1.04 million character comparisons. That expected performance is not guaranteed. If the strings are not random, then checking a trial m may take many character comparisons. The worst case is if the two strings match in all but the last letter. Imagine that the string S[] consists of 1 million characters that are all A, and that the word W[] is 999 A characters terminating in a final B character. The simple string matching algorithm will now examine 1000 characters at each trial position before rejecting the match and advancing the trial position. The simple string search example would now take about 1000 character comparisons times 1 million positions for 1 billion character comparisons. If the length of W[] is k, then the worst case performance is O(k⋅n). The KMP algorithm has a better worst case performance than the straightforward algorithm. KMP spends a little time precomputing a table (on the order of the size of W[], O(k)), and then it uses that table to do an efficient search of the string in O(n). The difference is that KMP makes use of previous match information that the straightforward algorithm does not. In the example above, when KMP sees a trial match fail on the 1000th character (i = 999) because S[m+999] ≠ W[999], it will increment m by 1, but it will know that the first 998 characters at the new position already match. KMP matched 999 A characters before discovering a mismatch at the 1000th character (position 999). Advancing the trial match position m by one throws away the first A, so KMP knows there are 998 A characters that match W[] and does not retest them; that is, KMP sets i to 998. KMP maintains its knowledge in the precomputed table and two state variables. When KMP discovers a mismatch, the table determines how much KMP will increase (variable m) and where it will resume testing (variable i).

"Бөлек сәйкестік" кестесі (сонымен қатар "жетіспеушілік функциясы" деп те аталады)

Кесте мақсаты – алгоритмге S-тің кез келген символын бір реттен артық сәйкестікке жібермеуді қамтамасыз ету. Бұған мүмкіндік беретін сызықты іздеудің ерекшелігі – негізгі тізбектің белгілі бір бөлігін үлгінің бастапқы бөлігімен салыстырып қарағанда, қазіргі позицияға дейін жалғаса алатын жаңа мүмкін сәйкестіктің қай жерден басталатынын нақты білеміз. Яғни, біз үлгіні алдын ала іздеп, барлық мүмкін қайтару позицияларының тізімін жасаймыз, осы арқылы үмітсіз символдардың максималды санын өткіріп жіберіп, ешқандай мүмкін сәйкестікті жоғалтпаймыз. W-дағы әрбір позиция үшін W-ның сол позицияға дейін (оны қоспағанда) болатын ең ұзын бастапқы сегментінің ұзындығын анықтағымыз келеді, W[0]-дан басталатын толық сегменттен басқа, ол сәйкес келмеді; осылайша келесі сәйкестікті табу үшін қанша қадам артқа шегіну керектігін білеміз. Сондықтан, T[i] – W-ның ең ұзын дұрыс бастапқы сегментінің ұзындығы, ол W[i-1] символында аяқталатын кіші тізбектің бөлігі болып табылады. Біз бос тізбектің ұзындығы 0 екенін қабылдаймыз. Үлгінің басындағы сәйкессіздік ерекше жағдай болғандықтан (артқа шегіну мүмкіндігі жоқ), біз T[0] = 1 деп белгілейміз, бұл туралы төменде талқыланады.

Кесте құру алгоритмінің тиімділігі

Кестенің алгоритмінің уақыт (және кеңістіктік) күрделілігі , мұндағы W ұзындығы.

Сыртқы цикл: pos 1-ге теңестіріледі, цикл шарты pos < k, және pos циклдың әрбір итерациясында 1-ге артады. Осылайша, цикл итерацияны қажет етеді. Ішкі цикл: cnd 0-ге теңестіріледі және сыртқы циклдың әрбір итерациясында ең көп дегенде 1-ге артады. T[cnd] әрқашан cnd-ден кіші болғандықтан, cnd әрбір ішкі циклдың итерациясында кем дегенде 1-ге кемітіледі; ішкі циклдың шарты cnd ≥ 0. Бұл ішкі цикл сыртқы цикл орындаған итерациялар санынан көп емес итерация орындай алады дегенді білдіреді – ішкі циклде cnd-нің 1-ге кемітілуі сыртқы циклда 1-ге артумен сәйкес болуы керек. Сыртқы цикл итерацияны қажет ететіндіктен, ішкі цикл жалпы алғанда итерациядан аспайды. Сыртқы және ішкі циклдер біріктіріліп, ең көп итерацияны орындайды. Бұл Big O нотациясын пайдаланып, уақыт күрделілігіне сәйкес келеді.

KMP алгоритмінің тиімділігі

Алгоритмнің екі бөлігі тиісінше O(k) және O(n) күрделіліктеріне ие болғандықтан, алгоритмнің жалпы күрделілігі O(n + k) болып табылады. Бұл күрделіліктер W немесе S-те қанша қайталанатын үлгі болса да өзгермейді.

Нұсқалар

KMP-нің нақты уақыт режимінде жұмыс істейтін нұсқасын әрбір әріп үшін жеке қателік функциясы кестесін қолдану арқылы іске асыруға болады. Мәтіндегі әріп бойынша сәйкессіздік туындаса, сәйкессіздік орын алған үлгідегі индекс үшін сол әріпке арналған қателік функциясы кестесі қарастырылады. Бұл, үлгінің префиксімен сәйкес келетін ең ұзын қосымшаның ұзындығын қайтарады, сонымен қатар префикстен кейінгі әріптің де сәйкес келуі керек. Осы шектеудің арқасында мәтіндегі әріпті келесі кезеңде қайтадан тексерудің қажеті болмайды, сондықтан мәтіннің әрбір индексін өңдеу кезінде тек тұрақты сандағы операциялар орындалады. Бұл нақты уақыт есептеу талабын қанағаттандырады. Бут алгоритмі лексикографиялық тұрғыдан ең минималды тізбек айналымын табу үшін KMP-нің алдын ала өңдеу функциясының өңделген нұсқасын пайдаланады. Қателік функциясы тізбек айналған сайын кезең-кезеңмен есептеледі.