Алгоритм Апостола – Джанкарло

В информатике алгоритм Апостолико-Джанкарло представляет собой вариант алгоритма поиска строк Бойера-Мура , основным применением которого является поиск вхождений шаблона. $P$ в тексте $T$. Как и в случае с другими поисками строк на основе сравнения, это делается путем выравнивания $P$ до определенного показателя $T$ и проверка наличия совпадения по этому индексу. $P$ затем смещается относительно $T$ по правилам алгоритма Бойера–Мура, и процесс повторяется до конца $T$ было достигнуто. Применение правил сдвига Бойера-Мура часто приводит к полному пропуску больших фрагментов текста.

Что касается операции сдвига, Апостолико-Джанкарло по функциональности в точности эквивалентен Бойеру-Муру. Полезность Апостолико-Джанкарло заключается в ускорении операции проверки совпадений по любому индексу. С помощью Бойера-Мура обнаружение появления $P$ в $T$ требует, чтобы все $n$ персонажи $P$ быть явно сопоставлены. Для некоторых шаблонов и текстов это очень неэффективно — простым примером является ситуация, когда и шаблон, и текст состоят из одного и того же повторяющегося символа, и в этом случае выполняется метод Бойера-Мура. $O(nm)$, где $m$ длина в символах $T$. Апостолико-Джанкарло ускоряет этот процесс, записывая количество символов, совпадающих при выравнивании $T$ в таблице, которая объединяется с данными, собранными в ходе предварительной обработки $P$ чтобы избежать избыточной проверки равенства для последовательностей символов, которые, как известно, совпадают. Его можно рассматривать как обобщение правила Галила .

Ссылки

• Апостолико, Альберто; Джанкарло, Рафаэле (1986). «Возвращение к стратегиям поиска строк Бойера-Мура-Галиля» . SIAM Journal по вычислительной технике . 15 : 98–105. дои : 10.1137/0215007 .
• Крошмор, Максим; Лекрок, Тьерри (1997). «Жесткие ограничения сложности алгоритма Апостолико-Джанкарло» (PDF) . Письма об обработке информации . 63 (4): 195–203. дои : 10.1016/S0020-0190(97)00107-5 .
• Крочемор, М.; Риттер, В. (1994). Текстовые алгоритмы . Издательство Оксфордского университета .
• Гасфилд, Д. (1997). Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология . Издательство Кембриджского университета . ISBN  0-521-58519-8 .
• Лекрок, Т. (1992). Поиск слов (кандидатская диссертация). Университет Орлеана .
• Лекрок, Тьерри (1995). «Результаты экспериментов по алгоритмам сопоставления строк». Программное обеспечение: практика и опыт . 25 (7): 727–765. дои : 10.1002/спе.4380250703 . S2CID   15253073 .