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

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

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

Рекомендации

• Апостолико А., Джанкарло Р., 1986, Пересмотренные стратегии поиска строк Бойера – Мура – ​​Галила, SIAM Журнал по вычислениям 15(1):98–105. Дои:10.1137/0215007.
• Крочмор, М., Лекрок, Т., 1997, Тесные границы сложности алгоритма Апостолико – Джанкарло, Информационные письма 63 (4): 195–203. Дои:10.1016 / S0020-0190 (97) 00107-5.
• Крочмор, М., Риттер, В., 1994, Текстовые алгоритмы, Oxford University Press.
• Гусфилд, Д., 1997, Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология, Издательство Кембриджского университета. ISBN 0-521-58519-8.
• Лекрок, Т., 1992, Recherches de mot, докторская диссертация, Орлеанский университет, Франция.
• Лекрок Т., 1995, Экспериментальные результаты по алгоритмам сопоставления строк, Программное обеспечение - Практика и опыт 25 (7): 727–765. Дои:10.1002 / spe.4380250703.