Алгоритм Ахо — Корасік — алгоритм пошуку рядків, створений Альфредом Ахо і . Алгоритм реалізує пошук множини підрядків із словника в цьому рядку. Час роботи пропорційно O (M + N + K), де N — довжина рядка-зразка, M — сумарна довжина рядків словника, а K — довжина відповіді, тобто сумарна довжина входжень слів із словника в рядок-зразок. Тому сумарний час роботи може бути квадратичним (наприклад, якщо в рядку «ааааааа», ми шукаємо слова «а», «аа», «ааа», …).
Принцип роботи
Алгоритм складається з двох частин. Перша частина будує за списком підрядків, які треба знайти скінченний автомат, а друга частина передає цьому автоматові рядок, в якому виконується пошук. Автомат отримує по черзі всі символи рядка та переходить за відповідними ребрами.
Поведінку автомата описують три функції:
- функція переходів, яка для кожного стану і деяких вхідних символів вказує стан, в який треба перейти, описується префіксним деревом;
- функція невдач, яка описує, в який стан потрібно перейти, якщо для вхідного символа в автоматі не знайшлося результату в функції переходів;
- функція виводу, яка пов'язує певні стани автомата з результатом, який він повертає.
Цей розділ потребує доповнення. (вересень 2017) |
Література
- Опис алгоритму його авторами:
- Aho, Alfred V.; Corasick, Margaret J. (June 1975). Efficient string matching: An aid to bibliographic search. Communications of the ACM. 18 (6): 333—340. doi:10.1145/360825.360855.
Див. також
Посилання
- Реалізація алгоритму на C# [ 15 січня 2012 у Wayback Machine.]
- Реалізація алгоритму на Erlsnd
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm Aho Korasik algoritm poshuku ryadkiv stvorenij Alfredom Aho i Algoritm realizuye poshuk mnozhini pidryadkiv iz slovnika v comu ryadku Chas roboti proporcijno O M N K de N dovzhina ryadka zrazka M sumarna dovzhina ryadkiv slovnika a K dovzhina vidpovidi tobto sumarna dovzhina vhodzhen sliv iz slovnika v ryadok zrazok Tomu sumarnij chas roboti mozhe buti kvadratichnim napriklad yaksho v ryadku aaaaaaa mi shukayemo slova a aa aaa Princip robotiAlgoritm skladayetsya z dvoh chastin Persha chastina buduye za spiskom pidryadkiv yaki treba znajti skinchennij avtomat a druga chastina peredaye comu avtomatovi ryadok v yakomu vikonuyetsya poshuk Avtomat otrimuye po cherzi vsi simvoli ryadka ta perehodit za vidpovidnimi rebrami Povedinku avtomata opisuyut tri funkciyi funkciya perehodiv yaka dlya kozhnogo stanu i deyakih vhidnih simvoliv vkazuye stan v yakij treba perejti opisuyetsya prefiksnim derevom funkciya nevdach yaka opisuye v yakij stan potribno perejti yaksho dlya vhidnogo simvola v avtomati ne znajshlosya rezultatu v funkciyi perehodiv funkciya vivodu yaka pov yazuye pevni stani avtomata z rezultatom yakij vin povertaye Cej rozdil potrebuye dopovnennya veresen 2017 LiteraturaOpis algoritmu jogo avtorami Aho Alfred V Corasick Margaret J June 1975 Efficient string matching An aid to bibliographic search Communications of the ACM 18 6 333 340 doi 10 1145 360825 360855 Div takozhAlgoritm Komenc ValterPosilannyaRealizaciya algoritmu na C 15 sichnya 2012 u Wayback Machine Realizaciya algoritmu na Erlsnd