Back

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




                                     

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

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

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

                                     

1. Позадина

Алгоритам за подударање ниски тражи почетни индекс m у ниски S и не тестира их поново; то јест, KMP поставља i на 998. KMP одржава податке у направљеној таблици и стање две променљиве. Када KMP открије да је дошло до неслатања, таблица одређује колико ће KMP повећати m и где ће наставити тестирање i.

                                     

2. KMP алгоритам

Урађен пример алгоритма за третрагу

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

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

У сваком кораку поредимо S. Максимални број зауставања i се граничи са i, односно, за сваки неуспех, можемо само да се зауставимо онолико колико смо напредовали до неуспеха. Онда је јасно да је временска сложеност 2n.

                                     

3. Таблица "делимичног поклапања" такође позната као "функција неуспеха"

Циљ таблице је да се омогући алторитму да не пореди ниједан карактер из S више од једном. Кључни закључак о природи линеарне претраге која омогућава да се то деси је да се провери мали сегмент главног низа према једном почетном сегменту обрасца, знамо тачно на којим местима ново потенцијално поређење може да настави до тренутне позиције и може да почне пре тренутне позиције. Другим речима, ми "прво-тражимо" сам узорак и састављамо листу свих могућих враћања позиција које заобилазе максимум безнадежних карактера сведок се не жртвују ниједна потенцијална погађања током тога.

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



                                     

4. Ефикасност KMP алгоритма

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

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

                                     

5. Варијанте

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

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

                                     

6. Спољашње везе

  • Кнут-Морис-Прат алгоритам Опис C кода од Кристијана Караса и Тиејери Лекрока
  • Апликација за претраживање ниски
  • Објашњење корак по корак KMP-a од Chu-Cheng Hsieh.
  • Објашњење алгоритма од нуле од FH Flensburg.
  • NPTELHRD YouTube видео предавање
  • Објашњење алгоритма и пример C++ кода од David Eppstein
  • Објашњење и имплементација на другим језицима
                                     
  • у том случају он испољава најгору временску сложеност О mn Кнут - Морис - Прат алгоритам смањује ову сложеност на О n користећи рачунање унапред да би
  • razvoj LR k raščlanjivanja, Knut - Moris - Prat algoritam za sravnjivanje niza karaktera itd. Malo je poznato da je Knut predložio naziv Bekus - Naurova
  • odredenih hemijskih struktura bez njihovog ponavljanja. Lindonova reč Knut - Moris - Prat algoritam Kellogg S. Booth Colbourn, Charles J. 1980 Linear Time Automorphism
  • се претражује. Кнут - Морис - Прат алгоритам Апостолико - Ђијанкарлов алгоритам Ахо - Коразик алгоритам подударности ниски Рабин - Карп алгоритам Суфиксно стабло
  • алгоритми који се баве овим проблемима су наивни алгоритам Рабин - Карп, коначни аутомат, Кнут - Морис - Прат Бојер - Мур - Хорспул, итд. Овде ћемо пажњу посветити

Users also searched:

...