Алгоритм Бойера-Мура

Материал из Википедии — свободной энциклопедии

Алгоритм Бойера-Мура поиска строки считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером (англ. Robert S. Boyer) и Джеем Муром (англ. J Strother Moore) в 1977 году. Преимущество этого алгоритма в том, что не нужно сравнивать шаблон (строка, которую хотим найти) с каждой буквой исходного текста, так как некоторые из них можно пропустить. Чем длиннее шаблон, тем быстрее работает алгоритм.

[править] Описание алгоритма

Первым делом строится таблица смещений для искомого шаблона. Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если последний символ шаблона и соответствующий ему при наложении символ строки не совпадают, то образец сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение. Если же символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит мы нашли подстроку и поиск окончен. Если же какой-то (не последний) символ шаблона не совпадает с соответствующим символом строки, мы сдвигаем шаблон на один символ вправо и снова начинаем проверку с последнего символа. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого образца, либо не будет достигнут конец строки.

[править] Построение таблицы

В таблице хранится величина сдвига для каждого символа в шаблоне. Величина сдвига определяется из тех соображений, что он должен быть максимально возможным, но таким, чтобы не пропустить вхождение искомого шаблона.

Таблица содержит список всех символов в шаблоне. В соответствие каждому символу ставится его порядковый номер, считая с конца строки. Если символ встречается несколько раз, то используется самое правое вхождение.

[править] Пример

Для шаблона «abbad» таблица имеет следующий вид.

[править] Пример работы алгоритма

Искомый шаблон — «abbad» (таблица для этого шаблона построена выше).

abeccacbabbabbad
abbad

Начало поиска. Последний символ образца не совпадает с наложенным символом строки. Сдвигаем образец вправо на 5 позиций:

abeccacbadbabbad
     abbad

Три символа образца совпали, а четвертый — нет. Сдвигаем образец вправо на одну позицию:

abeccacbadbabbad
      abbad

Последний символ снова не совпадает с символом строки. В соответствии с таблицей смещений сдвигаем образец на 2 позиции:

abeccacbadbabbad
        abbad

Еще раз сдвигаем образец на 2 позиции:

abeccacbadbabbad
          abbad

Теперь, в соответствии с таблицей, сдвигаем образец на одну позицию, и получаем искомое вхождение образца:

abeccacbadbabbad
           abbad

[править] Пример

Простой пример реализации алгоритма Бойера-Мура на языке Паскаль.

Процедура получает ссылки на три переменные: haystack и needle строкового типа и result целого типа, причём первые две для процедуры являются константами и не могут быть изменены. В переменной haystack должна содержаться строка, в которой будет осуществлён поиск, а перемнная needle должна содержать подстроку, которую надо найти. В результате выполнения процедуры переменная result будет содержать номер позиции, начиная с которого подстрока needle входит в строку haystack, или 0, если вхождения нет.

procedure boyer_moore(const haystack: string; const needle: string; var result: byte);
var
        i, j, k      : byte;
        needle_len   : byte;
        haystack_len : byte;
        needle_table : array[char] of byte;
begin
 
needle_len := length(needle);
haystack_len := length(haystack);
 
if needle_len < haystack_len then
begin
        for i := 0 to 255 do
                needle_table[chr(i)] := needle_len;
        for i := 1 to needle_len-1 do
                needle_table[needle[i]] := needle_len-i;
 
        i := needle_len;
        j := i;
        while (j > 0) and (i < haystack_len) do
        begin
                j := needle_len; k := i;
                while (j > 0) and (haystack[k] = needle[j]) do
                begin
                        dec(k);
                        dec(j);
                end;
                i := i + needle_table[haystack[i]];
        end;
 
        if k + 1 > haystack_len - needle_len then
                result := 0
        else
                result := k + 1;
 
end    
else
        result := 0;
end;

[править] Литература

• Никлаус Вирт Алгоритмы и структуры данных. — М.: Невский Диалект, 2006. С. 352. ISBN 5-7940-0065-1