Алгоритм Комментца-Вальтера
В информатике алгоритм Комментц-Вальтера — это алгоритм поиска строк, изобретенный Беате Комментц-Вальтер . [1] Как и алгоритм сопоставления строк Ахо-Корасика , он может искать несколько шаблонов одновременно. Он сочетает в себе идеи Ахо-Корасика с быстрым сопоставлением алгоритма поиска строк Бойера-Мура . Для текста длины n и максимальной длины шаблона m время его выполнения в худшем случае равно O ( mn ), хотя средний случай часто намного лучше. [2]
GNU grep однажды реализовал алгоритм сопоставления строк, очень похожий на Commentz-Walter. [3]
История
[ редактировать ]Статья об алгоритме была впервые опубликована Беате Комментц-Вальтер в 1979 году в Саарском университете и напечатана «Р. Шернером». [1] В документе подробно описаны два разных алгоритма, которые, по ее утверждению, сочетают в себе идею алгоритмов Ахо-Корасика и Бойера-Мура , которые она назвала алгоритмами B и B1. Однако в статье основное внимание уделяется алгоритму B.
Как работает алгоритм
[ редактировать ]
Алгоритм Комментца-Вальтера объединяет два известных алгоритма, чтобы попытаться лучше решить проблему сопоставления нескольких шаблонов. Этими двумя алгоритмами являются Boyer-Moore , который обеспечивает сопоставление одиночных шаблонов с использованием фильтрации, и Aho-Corasick . Для этого алгоритм реализует суффиксный автомат для поиска шаблонов внутри входной строки, а также использует обратные шаблоны, в отличие от Aho-Corasick . [4]
Commentz-Walter должен пройти две фазы: фазу предварительных вычислений и фазу сопоставления. На первом этапе алгоритм Комментца-Вальтера использует обратный шаблон для построения дерева шаблонов, это считается этапом предварительного вычисления. Второй этап, известный как этап сопоставления, учитывает два других алгоритма. Используя Бойера-Мура технику сдвига Ахо-Корасика , алгоритм Комментца-Вальтера может начать сопоставление. и технику конечных автоматов [4]
Алгоритм Commentz-Walter будет сканировать входную строку в обратном направлении, проверяя на несоответствие. Если и когда алгоритм обнаружит несоответствие, он уже будет знать некоторые символы, которые совпадают, а затем будет использовать эту информацию в качестве индекса. Используя индекс, алгоритм проверяет заранее вычисленную таблицу, чтобы найти расстояние, на которое она должна сдвинуться, после этого алгоритм еще раз начинает новую попытку сопоставления.
Временная сложность
[ редактировать ]Сравнение алгоритма Ахо-Корасика с алгоритмом Комментца-Вальтера дает результаты с учетом идеи временной сложности. Ахо-Корасик считается линейным O ( m+n+k ), где k — количество совпадений. Комментц-Вальтера можно считать квадратичным O ( mn ). Причина этого заключается в том, что Commentz-Walter был разработан путем добавления сдвигов в алгоритме поиска строк Бойера-Мура к алгоритму Ахо-Корасика , тем самым переместив его сложность с линейной на квадратичную.
Согласно исследованию, проведенному в «Журнале Национального научного фонда Шри-Ланки» 46, алгоритм Commentz-Walter в целом работает быстрее, чем алгоритм сопоставления строк Ахо-Корасика . Это, по данным журнала, существует только при использовании длинных паттернов. Тем не менее, в журнале утверждается, что критического анализа этого утверждения нет и нет общего согласия относительно эффективности алгоритма. [5]
Как видно из визуализации времени работы алгоритма, сделанной в исследовании «Международного журнала передовых компьютерных наук и информационных технологий», производительность алгоритма увеличивалась линейно по мере увеличения самого короткого шаблона в наборе шаблонов. [4]
Альтернативный алгоритм
[ редактировать ]В оригинальной статье Комментца-Вальтера также был создан альтернативный алгоритм. Этот алгоритм, известный как B1, работает аналогично основному алгоритму Комментца-Вальтера, с той лишь разницей, что дерево шаблонов используется на этапе сканирования.
В документе также утверждается, что этот алгоритм работает лучше за счет увеличения времени и пространства как на этапе предварительной обработки, так и на этапе поиска. Однако этот алгоритм официально не тестировался в других исследованиях, поэтому его реальная производительность неизвестна. [1]
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б с Комментц-Вальтер, Беате (1979). Алгоритм сопоставления строк, быстрый в среднем (PDF) . Международный коллоквиум по автоматам, языкам и программированию . ЛНКС . Том. 71. Грац, Австрия: Шпрингер. стр. 118–132. дои : 10.1007/3-540-09510-1_10 . ISBN 3-540-09510-1 . Архивировано из оригинала (PDF) 10 октября 2017 г.
- ^ Уотсон, Брюс Уильям (15 сентября 1995 г.). Таксономии и инструментарий алгоритмов регулярного языка . Эйндховенский технологический университет . дои : 10.6100/IR444299 . ISBN 90-386-0396-7 .
- ^ «grep: удалить код Commentz-Walter» . GNU grep . 18 января 2017 г. Проверено 15 мая 2022 г.
- ^ Jump up to: Перейти обратно: а б с Акинул Ислам Джони (2014). «Анализ алгоритмов сопоставления нескольких строк с образцом» (PDF) . Международный журнал передовых компьютерных наук и информационных технологий (IJACSIT) . 3 (4): 344–353. ISSN 2296-1739 .
- ^ Девасурендра, Южная Дакота; Виданагаматчи, С.М. (2018). «Анализ средней временной сложности алгоритма Комментца-Вальтера» . Журнал Национального научного фонда Шри-Ланки . 46 (4): 547–557. дои : 10.4038/jnsfsr.v46i4.8630 .