Вы когда-нибудь задавали себе вопрос, какой алгоритм используется для поиска слова после нажатия Ctrl + F и ввода чего-либо? Ну, я думаю, вы знаете ответ из заголовка, но в этой статье вы узнаете, как именно это делается.
Как мы увидели при поиске строк Морриса-Пратта, нам не нужно сравнивать текст и образец по буквам. Некоторые сравнения можно пропустить, чтобы повысить производительность поиска строк. Действительно, поиск по грубой силе и алгоритм Рабина-Карпа довольно медленны только потому, что они сравнивают рисунок и текст посимвольно.
С другой стороны, алгоритм Морриса-Пратта является очень хорошим улучшением поиска строк грубой силы, но остается вопрос: существует ли какой-либо алгоритм, более быстрый, чем Моррис-Пратт, — есть ли способ пропустить больше сравнений и перейти картина быстрее?
Понятно, что если нам нужно выяснить, содержится ли в тексте один символ, нам нужно как минимум «n» шагов, где n — длина текста. Как только мы должны выяснить, содержится ли шаблон с длиной «m» в тексте с длиной «n», случай становится немного более сложным.
Однако, ответ на то , что есть это такой алгоритм , который быстрее и больше подходит , чем Морриса-Пратта. Это поиск строки Бойера-Мура.
обзор
Бойер-Мур — это алгоритм, который повышает производительность поиска по шаблону в тексте, учитывая некоторые наблюдения. Он был определен в 1977 году Робертом С. Бойером и Дж. Стротером Муром и состоит из некоторых специфических особенностей.
Прежде всего, этот алгоритм начинает сравнение шаблона с самой левой части текста и перемещается вправо, как показано на рисунке ниже.
В отличие от других алгоритмов поиска строк, Бойер-Мур сравнивает шаблон с возможным совпадением справа налево, как показано ниже.
Основной идеей Бойера-Мура, чтобы улучшить производительность, являются некоторые наблюдения за паттерном. В терминологии этого алгоритма они называются хорошими суффиксами и сдвигами плохих символов. Давайте посмотрим на следующих примерах, что они стоят.
Сдвиги Good-суффикса
Так же, как алгоритм Морриса-Пратта, мы начинаем сравнивать шаблон с некоторой частью текста, где будет происходить возможное совпадение. В Бойер-Мур, как я уже сказал, это делается из самой правой буквы шаблона. После совпадения некоторых символов мы обнаруживаем несоответствие.
Итак, как мы можем переместить шаблон вправо, чтобы пропустить необычные сравнения. Чтобы ответить на этот вопрос, нам нужно изучить шаблон. Допустим, есть часть шаблона, которая повторяется внутри самого шаблона, как показано на рисунке ниже.
В этом случае мы должны переместить шаблон, поэтому повторяющаяся часть должна теперь выровняться с первым появлением в шаблоне.
Разновидностью этого случая является случай, когда часть из шаблона A перекрывается с другой частью, которая состоит из тех же символов.
Еще раз, сдвиг должен выровнять вторую часть с ее первым появлением.
Наконец, только часть A, скажем, «B», может произойти в самом начале паттерна, как показано на схеме ниже.
Теперь мы должны выровнять левый конец шаблона с самым правым вхождением «B».
Плохие изменения характера
Помимо сдвигов с хорошим суффиксом, алгоритм Бойера-Мура использует так называемые «сдвиги плохих символов». В случае несоответствия мы можем пропустить сравнения в случае, если символ в тексте не появляется в шаблоне. Чтобы было понятнее, давайте рассмотрим следующие примеры.
На рисунке выше мы видим, что несовпадающий символ «B» в тексте появляется только в начале рисунка. Таким образом, мы можем просто сместить шаблон вправо и выровнять оба символа B, пропуская сравнения. Еще лучший случай описывается следующей диаграммой, где несовпадающая буква вообще не содержится в шаблоне. Тогда мы можем сдвинуть вперед всю модель.
Максимум сдвигов Good-суффикса и Bad-Character
Бойеру-Муру нужны сдвиги как с хорошим суффиксом, так и с плохим характером, чтобы повысить эффективность поиска После несоответствия учитывается максимум обоих для перемещения шаблона вправо.
сложность
Понятно, что Бойер-Мур быстрее, чем Моррис-Пратт, но на самом деле его сложность в худшем случае составляет O (n + m). Дело в том, что в поиске на естественном языке Бойер-Мур справляется довольно хорошо.
Реализация
Наконец, давайте посмотрим реализацию в PHP , которая может быть легко «переписана» на любой другой язык программирования. Единственное, что нам нужно, это структуры для смены плохих персонажей и смены суффиксов.
<?php
/**
* Pattern we're searching for
*
* @var string
*/
$pattern = 'gloria';
/**
* The text we're searching in
*
* @var string
*/
$text = 'Sic transit gloria mundi, non transit gloria Gundi!';
/**
* Calculates the suffixes for a given pattern
*
* @param string $pattern
* @param array $suffixes
*/
function suffixes($pattern, &$suffixes)
{
$m = strlen($pattern);
$suffixes[$m - 1] = $m;
$g = $m - 1;
for ($i = $m - 2; $i >= 0; --$i) {
if ($i > $g && $suffixes[$i + $m - 1 - $f] < $i - $g) {
$suffixes[$i] = $suffixes[$i + $m - 1 - $f];
} else {
if ($i < $g) {
$g = $i;
}
$f = $i;
while ($g >= 0 && $pattern[$g] == $pattern[$g + $m - 1 - $f]) {
$g--;
}
$suffixes[$i] = $f - $g;
}
}
}
/**
* Fills in the array of bad characters.
*
* @param string $pattern
* @param array $badChars
*/
function badCharacters($pattern, &$badChars)
{
$m = strlen($pattern);
for ($i = 0; $i < $m - 1; ++$i) {
$badChars[$pattern{$i}] = $m - $i - 1;
}
}
/**
* Fills in the array of good suffixes
*
* @param string $pattern
* @param array $goodSuffixes
*/
function goodSuffixes($pattern, &$goodSuffixes)
{
$m = strlen($pattern);
$suff = array();
suffixes($pattern, $suff);
for ($i = 0; $i < $m; $i++) {
$goodSuffixes[$i] = $m;
}
for ($i = $m - 1; $i >= 0; $i--) {
if ($suff[$i] == $i + 1) {
for ($j = 0; $j < $m - $i - 1; $j++) {
if ($goodSuffixes[$j] == $m) {
$goodSuffixes[$j] = $m - $i - 1;
}
}
}
}
for ($i = 0; $i < $m - 2; $i++) {
$goodSuffixes[$m - 1 - $suff[$i]] = $m - $i - 1;
}
}
/**
* Performs a search of the pattern into a given text
*
* @param string $pattern
* @param string $text
*/
function boyer_moore($pattern, $text)
{
$n = strlen($text);
$m = strlen($pattern);
$goodSuffixes = array();
$badCharacters = array();
goodSuffixes($pattern, &$goodSuffixes);
badCharacters($pattern, &$badCharacters);
$j = 0;
while ($j < $n - $m) {
for ($i = $m - 1; $i >= 0 && $pattern[$i] == $text[$i + $j]; $i--);
if ($i < 0) {
// note that if the substring occurs more
// than once into the text, the algorithm will
// print out each position of the substring
echo $j;
$j += $goodSuffixes[0];
} else {
$j += max($goodSuffixes[$i], $badCharacters[$text[$i + $j]] - $m + $i + 1);
}
}
}
// search using Boyer-Moore
// will return 12 and 38
boyer_moore($pattern, $text);
заявка
Бойер-Мур — один из наиболее часто используемых алгоритмов поиска строк. Интуитивно понятно, где это может быть полезно, но еще раз скажу лишь, что этот алгоритм считается наиболее часто используемым на практике для операций поиска и замены в текстовых редакторах.