Ејхо—Корасикин алгоритам
У рачунарству, Ејхо—Корасикин алгоритам за подударност ниски је алгоритам за претрагу ниски који су измислили Алфред Вејно Ејхо и Маргарет Џ. Корасик. То је алгоритам по принципу претраге речника који налази елементе коначног скупа ниски („речника“) у оквиру унетог текста. Врши симултано подударање шаблона. Теорија сложености израчунавања алгоритма је линеарна у дужини шаблона, плус дужини претраженог текста, плус броја подударности на излазу. Узмимо у обзир да, пошто су све подударности нађене, може бити квадратни број подударања ако је подударан сваки подстринг.

Алгоритам гради машину коначног стања која подсећа на дрво, са додатним везама између различитих унутрашњих чворова. Ове додатне унутрашње везе допуштају брзе прелазе између неуспелих поклапања шаблона(претрага за мачка у дрвету које не садржи мачка али садржи мачевалац не би успела на чвору са префиксом мач) и осталих грана које деле заједнички префикс. Ово омогућава аутоматизацију преласка између подударних шаблона без потребе за бектрекингом.

Када је речник шаблона познат унапред, конструкција аутомата може бити извршена офлајн и компајлирани аутомат сачуван за каснију употребу. У овом случају, његово време извршавања је линеарно у дужини улаза плус број подударних улаза.

Ејхо—Корасикин алгоритам за подударност стрингова засновао је базу оригиналне листе Јуникс програма.

Граф испод је Ејхо—Корасикина структура података, направљена из наведеног речника, са сваким редом у табели који представља чвор у стаблу, са путањом колона која указује на јединствен низ карактера из корена ка чвору.

Структура података има по један чвор за сваки префикс сваког стринга у речнику. Ако је (bca) у речнику онда ће постојати чворови за (bca), (bc), (b) и (). Постоји црна усмерена грана детета из сваког чвора до чвора чије име се добија надовезивањем једног карактера. Самим тим постоји црна грана од (bc) до (bca). Постоји плава усмерена суфикс грана од сваког чвора до чвора који је најдужи могући стриктни суфикс тог чвора у графу. На пример, за чвор (caa) стриктни суфикси су (aa), (a) и (). Најдужи од њих који постоји у графу је (a), тако да постоји плава грана од (caa) до (a). Постоји зелена грана речничког суфикса од сваког чвора до следећег чвора у речнику до ког се може доћи пратећи плаве гране. На пример, постоји зелена грана од (bca) до (a) због тога што је (a) први чвор у речнику (тзв. бели чвор) до кога се долази пратећи плаве гране до (ca), а онда до (a).

На сваком кораку, тренутни чвор се продужава тражећи своје дете, а ако оно не постоји, налазећи његово дете суфикс, а ако то не успе налазећи дете суфикс његовог суфикса итд. завршавајући на крају у корену ако ништа није виђено пре тога.

Када алгоритам дође до чвора, избацује све речничке улазе који се завршавају на тренутној позицији карактера у унетом тексту. Ово се ради штампањем сваког чвора до кога се дошло пратећи суфикс везе речника почевши од тог чвора, и настављајући све док се не дође до чвора који нема речничку суфикс везу. Као додатак, и тај чвор се штампа ако представља улаз у речник.

Извршење на улазном стрингу abccab повлачи следеће кораке:

Референце

Спољашње везе 
 Set Matching and Aho–Corasick Algorithm, lecture slides by Pekka Kilpeläinen
 Aho–Corasick entry in NIST's Dictionary of Algorithms and Data Structures
 Aho–Corasick string matching in C#, a CodeProject tutorial by Tomáš Petříček
 Aho-Corasick string matching in PHP, optimized for terms-filtering
 Aho-Corasick C implementation
 Aho-Corasick Python wrapper
 Aho-Corasick Java implementation
 Animated Aho-Corasick, an animated implementation of Aho-Corasick for learning purposes

Алгоритми на нискама
У рачунарству , Ејхо—Корасикин алгоритам за подударност ниски је алгоритам за претрагу ниски који су измислили Алфред Вејно Ејхо и Маргарет Џ. Корасик . То је алгоритам по принципу претраге речника који налази елементе коначног скупа ниски ( „ речника “ ) у оквиру унетог текста . Врши симултано подударање шаблона . Теорија сложености израчунавања алгоритма је линеарна у дужини шаблона , плус дужини претраженог текста , плус броја подударности на излазу . Узмимо у обзир да , пошто су све подударности нађене , може бити квадратни број подударања ако је подударан сваки подстринг . Алгоритам гради машину коначног стања која подсећа на дрво , са додатним везама између различитих унутрашњих чворова . Ове додатне унутрашње везе допуштају брзе прелазе између неуспелих поклапања шаблона( претрага за мачка у дрвету које не садржи мачка али садржи мачевалац не би успела на чвору са префиксом мач ) и осталих грана које деле заједнички префикс . Ово омогућава аутоматизацију преласка између подударних шаблона без потребе за бектрекингом . Када је речник шаблона познат унапред , конструкција аутомата може бити извршена офлајн и компајлирани аутомат сачуван за каснију употребу . У овом случају , његово време извршавања је линеарно у дужини улаза плус број подударних улаза . Ејхо—Корасикин алгоритам за подударност стрингова засновао је базу оригиналне листе Јуникс програма . Граф испод је Ејхо—Корасикина структура података , направљена из наведеног речника , са сваким редом у табели који представља чвор у стаблу , са путањом колона која указује на јединствен низ карактера из корена ка чвору . Структура података има по један чвор за сваки префикс сваког стринга у речнику . Ако је ( bca ) у речнику онда ће постојати чворови за ( bca ) , ( bc ) , ( b ) и ( ) . Постоји црна усмерена грана детета из сваког чвора до чвора чије име се добија надовезивањем једног карактера . Самим тим постоји црна грана од ( bc ) до ( bca ) . Постоји плава усмерена суфикс грана од сваког чвора до чвора који је најдужи могући стриктни суфикс тог чвора у графу . На пример , за чвор ( caa ) стриктни суфикси су ( aa ) , ( a ) и ( ) . Најдужи од њих који постоји у графу је ( a ) , тако да постоји плава грана од ( caa ) до ( a ) . Постоји зелена грана речничког суфикса од сваког чвора до следећег чвора у речнику до ког се може доћи пратећи плаве гране . На пример , постоји зелена грана од ( bca ) до ( a ) због тога што је ( a ) први чвор у речнику ( тзв. бели чвор ) до кога се долази пратећи плаве гране до ( ca ) , а онда до ( a ) . На сваком кораку , тренутни чвор се продужава тражећи своје дете , а ако оно не постоји , налазећи његово дете суфикс , а ако то не успе налазећи дете суфикс његовог суфикса итд. завршавајући на крају у корену ако ништа није виђено пре тога . Када алгоритам дође до чвора , избацује све речничке улазе који се завршавају на тренутној позицији карактера у унетом тексту . Ово се ради штампањем сваког чвора до кога се дошло пратећи суфикс везе речника почевши од тог чвора , и настављајући све док се не дође до чвора који нема речничку суфикс везу . Као додатак , и тај чвор се штампа ако представља улаз у речник . Извршење на улазном стрингу abccab повлачи следеће кораке : Референце Спољашње везе Set Matching and Aho–Corasick Algorithm , lecture slides by Pekka Kilpeläinen Aho–Corasick entry in NIST's Dictionary of Algorithms and Data Structures Aho–Corasick string matching in C # , a CodeProject tutorial by Tomáš Petříček Aho-Corasick string matching in PHP , optimized for terms-filtering Aho-Corasick C implementation Aho-Corasick Python wrapper Aho-Corasick Java implementation Animated Aho-Corasick , an animated implementation of Aho-Corasick for learning purposes Алгоритми на нискама