Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Жолдарды іздеу алгоритмі
String searching algorithm
Компьютер ғылымында Ахо-Корасик алгоритмі — Альфред В. Ахо және Маргарет Дж. Корасик 1975 жылы ойлап тапқан жолдарды іздеу алгоритмі. Бұл кіріс мәтіні ішінде шекті жолдар жиынтығының ("сөздік") элементтерін табуға арналған сөздікке сәйкестік алгоритмінің бір түрі. Ол барлық жолдарды бір уақытта сәйкестендіреді. Алгоритмнің күрделілігі жолдардың ұзындығы, ізделіп жатқан мәтіннің ұзындығы және табылған сәйкестіктер санына пропорционалды. Барлық сәйкестіктер табылатындықтан, егер әрбір ішкі жол сәйкес келсе, сәйкестіктердің саны квадраттық болуы мүмкін (мысалы, сөздік = , , , және кіріс жолы ). Формальды түрде алгоритм әртүрлі ішкі түйіндер арасындағы қосымша сілтемелермен триге ұқсас шекті күй машинасы құрастырады. Бұл қосымша ішкі сілтемелер сәтсіз жол сәйкестіктері арасында жылдам өтуге мүмкіндік береді (мысалы, триде жоқ, бірақ бар және осылайша префиксі бар түйінде сәтсіздікке ұшыраса, ортақ жұрнақпен бөлісетін басқа тармақтарға өтуге болады. Алдыңғы жағдайда, үшін ең жақсы көлденең өту болуы мүмкін). Бұл автоматқа кері қайтару қажеттілігінсіз жол сәйкестіктері арасында өтуге мүмкіндік береді. Егер жол сөздігі алдын ала белгілі болса (мысалы, компьютерлік вирустар базасы), автоматты құру желіден тыс орындалуы мүмкін және құрастырылған автомат кейін пайдалану үшін сақталады. Бұл жағдайда, оның жұмыс уақыты кіріс ұзындығына және сәйкес келетін жазбалар санына пропорционалды. Ахо-Корасик жол сәйкестік алгоритмі бастапқы Unix командасының негізін құрады fgrep.
In computer science, the Aho—Corasick algorithm is a string searching algorithm invented by Alfred V. Aho and Margaret J. Corasick in 1975. It is a kind of dictionary matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all strings simultaneously. The complexity of the algorithm is linear in the length of the strings plus the length of the searched text plus the number of output matches. Note that because all matches are found, there can be a quadratic number of matches if every substring matches (e. g. dictionary = , , , and input string is ). Informally, the algorithm constructs a finite state machine that resembles a trie with additional links between the various internal nodes. These extra internal links allow fast transitions between failed string matches (e. g. a search for in a trie that does not contain , but contains , and thus would fail at the node prefixed by ), to other branches of the trie that share a common suffix (e. g., in the previous case, a branch for might be the best lateral transition). This allows the automaton to transition between string matches without the need for backtracking. When the string dictionary is known in advance (e. g. a computer virus database), the construction of the automaton can be performed once off line and the compiled automaton stored for later use. In this case, its run time is linear in the length of the input plus the number of matched entries. The Aho—Corasick string matching algorithm formed the basis of the original Unix command fgrep.
Динамикалық іздеу тізімі
Бастапқы Aho-Corasick алгоритмі іздеу жолдарының жиынтығы өзгермейтін деп есептейді. Алгоритм қолданылып жатқанда жаңа іздеу жолдары қосылатын жағдайларда оны тікелей қолдануға болмайды. Мысалы, интерактивті индекстеу бағдарламасында пайдаланушы мәтінді қарап, көріп отырғанда жаңа сөздерді немесе тіркестерді бөліп көрсетеді. Бертран Мейер алгоритмнің ұлғаятын нұсқасын ұсынды, онда іздеу жолдары жиынтығы іздеу барысында кеңейтілуі мүмкін, ал бастапқы алгоритмнің күрделілігі сақталады.
The original Aho—Corasick algorithm assumes that the set of search strings is fixed. It does not directly apply to applications in which new search strings are added during application of the algorithm. An example is an interactive indexing program, in which the user goes through the text and highlights new words or phrases to index as they see them. Bertrand Meyer introduced an incremental version of the algorithm in which the search string set can be incrementally extended during the search, retaining the algorithmic complexity of the original.