Алгоритм Ахо — Корасік

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Алгоритм Ахо — Корасік — алгоритм пошуку рядків, створений Альфредом Ахо і Маргарет Корасік. Алгоритм реалізує пошук множини підрядків із словника в цьому рядку. Час роботи пропорційно O (M + N + K), де N — довжина рядка-зразка, M — сумарна довжина рядків словника, а K — довжина відповіді, тобто сумарна довжина входжень слів із словника в рядок-зразок. Тому сумарний час роботи може бути квадратичним (наприклад, якщо в рядку «ааааааа», ми шукаємо слова «а», «аа», «ааа», …).

Принцип роботи

[ред. | ред. код]

Алгоритм складається з двох частин. Перша частина будує за списком підрядків, які треба знайти скінченний автомат, а друга частина передає цьому автоматові рядок, в якому виконується пошук. Автомат отримує по черзі всі символи рядка та переходить за відповідними ребрами.

Поведінку автомата описують три функції:

  • функція переходів, яка для кожного стану і деяких вхідних символів вказує стан, в який треба перейти, описується префіксним деревом;
  • функція невдач, яка описує, в який стан потрібно перейти, якщо для вхідного символа в автоматі не знайшлося результату в функції переходів;
  • функція виводу, яка пов'язує певні стани автомата з результатом, який він повертає.

Література

[ред. | ред. код]
  • Опис алгоритму його авторами:
    • 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.

Див. також

[ред. | ред. код]

Посилання

[ред. | ред. код]