Алгоритм поиска подстроки Бойера-Мура и его модификации
Boyer–Moore string-search algorithm
Алгоритм поиска строк Бойера-Мура: эффективный метод для быстрого поиска подстрок в тексте. История, принцип работы и оптимизация для высокой производительности.
String searching algorithm
the Boyer–Moore theorem prover
В информатике алгоритм поиска строк Бойера-Мура — это эффективный алгоритм поиска строк, являющийся стандартным эталоном для практической литературы по поиску строк. Он был разработан Робертом С. Бойером и Дж. Стротером Муром в 1977 году. Оригинальная статья содержала статические таблицы для вычисления сдвигов образца без объяснения того, как их создавать. Алгоритм для создания таблиц был опубликован в последующей работе; эта статья содержала ошибки, которые позже были исправлены Войцехом Риттером в 1980 году. Алгоритм предварительно обрабатывает строку, которую необходимо найти (образец), но не строку, в которой производится поиск (текст). Таким образом, он хорошо подходит для приложений, в которых образец значительно короче текста или сохраняется при множественных поисках. Алгоритм Бойера-Мура использует информацию, полученную на этапе предварительной обработки, чтобы пропускать части текста, что приводит к меньшему постоянному множителю, чем у многих других алгоритмов поиска строк. В целом, алгоритм работает быстрее по мере увеличения длины образца. Ключевые особенности алгоритма — сопоставление по концу образца, а не по началу, и пропуск по тексту с шагом в несколько символов, а не поиск каждого символа в тексте.
In computer science, the Boyer–Moore string search algorithm is an efficient string searching algorithm that is the standard benchmark for practical string search literature. It was developed by Robert S. Boyer and J Strother Moore in 1977. The original paper contained static tables for computing the pattern shifts without an explanation of how to produce them. The algorithm for producing the tables was published in a follow on paper; this paper contained errors which were later corrected by Wojciech Rytter in 1980. The algorithm preprocesses the string being searched for (the pattern), but not the string being searched in (the text). It is thus well suited for applications in which the pattern is much shorter than the text or where it persists across multiple searches. The Boyer–Moore algorithm uses information gathered during the preprocess step to skip sections of the text, resulting in a lower constant factor than many other string search algorithms. In general, the algorithm runs faster as the pattern length increases. The key features of the algorithm are to match on the tail of the pattern rather than the head, and to skip along the text in jumps of multiple characters rather than searching every single character in the text.
Выступление
Алгоритм Бойера-Мура, представленный в оригинальной статье, имеет время выполнения в худшем случае O(n+m) только если образец не встречается в тексте. Это было впервые доказано Кнутом, Моррисом и Праттом в 1977 году, с верхней границей в 5n сравнений в худшем случае. Ричард Коул в 1991 году предоставил доказательство с верхней границей в 3n сравнений в худшем случае. Когда образец встречается в тексте, время выполнения исходного алгоритма в худшем случае составляет O(nm). Это легко увидеть, когда и образец, и текст состоят исключительно из одного и того же повторяющегося символа. Однако, включение правила Галиля обеспечивает линейное время выполнения во всех случаях.
The Boyer–Moore algorithm as presented in the original paper has worst case running time of O(n+m) only if the pattern does not appear in the text. This was first proved by Knuth, Morris, and Pratt in 1977, with an upper bound of 5n comparisons in the worst case. Richard Cole gave a proof with an upper bound of 3n comparisons in the worst case in 1991. When the pattern does occur in the text, running time of the original algorithm is O(nm) in the worst case. This is easy to see when both pattern and text consist solely of the same repeated character. However, inclusion of the Galil rule results in linear runtime across all cases.
Варианты
Алгоритм Бойера-Мура-Горспола является упрощением алгоритма Бойера-Мура, использующим только правило плохого символа. Алгоритм Апостолико-Джанкарло ускоряет процесс проверки наличия соответствия при заданном выравнивании, избегая явного сравнения символов. Он использует информацию, полученную при предварительной обработке шаблона, в сочетании с длиной совпадения суффикса, фиксируемой при каждой попытке сопоставления. Хранение длин совпадения суффикса требует дополнительную таблицу, размер которой равен размеру искомого текста. Алгоритм Райты повышает эффективность алгоритма Бойера-Мура-Горспола. Способ поиска конкретной подстроки в заданной строке отличается от алгоритма Бойера-Мура-Горспола.
The Boyer–Moore–Horspool algorithm is a simplification of the Boyer–Moore algorithm using only the bad character rule. The Apostolico–Giancarlo algorithm speeds up the process of checking whether a match has occurred at the given alignment by skipping explicit character comparisons. This uses information gleaned during the pre processing of the pattern in conjunction with suffix match lengths recorded at each match attempt. Storing suffix match lengths requires an additional table equal in size to the text being searched. The Raita algorithm improves the performance of Boyer–Moore–Horspool algorithm. The searching pattern of particular sub string in a given string is different from Boyer–Moore–Horspool algorithm.