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

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

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

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

Сначала строится таблица смещений для искомого шаблона. Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона.

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

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

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

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

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

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

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

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

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

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

abeccacbadbabbad
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 > haystack_len - needle_len then
                result := 0
        else
                result := k + 1;
 
end    
else
        result := 0;
end;

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

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