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

Алгоритм Бойера — Мура — Хорспула поиска строки — упрощённый вариант алгоритма Бойера — Мура. АБМХ работает лучше алгоритма Бойера — Мура на случайных текстах. К тому же, требующая многих предварительных вычислений эвристика совпавшего суффикса опускается.

Впрочем, оценка (в худшем случае на непериодических шаблонах) у АБМХ составляет |needle|·|haystack| (вместо 3|haystack| у Бойера-Мура).

Описание алгоритма

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

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

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

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

Построение таблицы

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

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

Пример

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

a	b	d
1	2	5

Примечания

Позиция последнего символа шаблона в алгоритме не рассматривается, то есть значение смещения для символа 'd' будет равно длине шаблона — 5.

В таблице соответствия символ — смещение, для всех символов, не вошедших в шаблон, величина смещения устанавливается равной длине шаблона — 5.

Пример работы алгоритма

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

abeccacbadbabbad
abbad

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

abeccacbadbabbad
     abbad

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

abeccacbadbabbad
      abbad

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

abeccacbadbabbad
        abbad

И снова последний символ строки b не совпадает с символом шаблона.Сдвигаем на 2 позиции:

abeccacbadbabbad
          abbad

Последний символ исходной строки «a» снова не совпадает с символом шаблона. В соответствии с таблицей смещений сдвигаем образец на 1 позицию и получаем искомое вхождение образца:

abeccacbadbabbad
           abbad

Пример

Паскаль

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

procedure boyer_moore(const haystack: string; const needle: string; var result: integer);
var
        i, j, k      : integer;
        needle_len   : integer;
        haystack_len : integer;
        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;

C

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

int BoyerMooreHorspool(char *haystack, char *needle)
{
        int i,j,k, needle_len = 0,haystack_len = 0;
        int needle_table[256];
 
        for (char *p = needle; *p; *p++)
                ++needle_len;
        for (char *p = haystack; *p; *p++)
                ++haystack_len;
 
        if (needle_len <= haystack_len)
        {
                for (i = 0; i < 256; i++)
                        needle_table[i] = needle_len;
 
                for (i = 1; i < needle_len; i++)
                        needle_table[needle[i-1]] = needle_len-i;
 
                i = needle_len;
                j = i;
 
                while (j > 0 && i <= haystack_len)
                {
                        j = needle_len;
                        k = i;
                        while (j > 0 && haystack[k-1] == needle[j-1])
                        {
                                --k;
                                --j;
                        }
                        i+=needle_table[haystack[i-1]];
                }
 
                if (k > haystack_len - needle_len)
                        return -1;
                else return k;
        }
        else return -1;
}

Java

public boolean HorspoolMatch(String text, String pattern) {
 
    int scan, last, k = 0;
    int textLen = text.length();
    int patternLen = pattern.length();
    int n = 256;
    int[] patternTable = new int[n];
 
    if (patternLen < textLen) {
 
        for (scan = 0; scan < n; scan++) {
            patternTable[scan] = patternLen;
        }
 
        for (scan = 0; scan < patternLen - 1; scan++) {
            patternTable[pattern.charAt(scan)] = patternLen - scan - 1;
        }
 
 
        scan = 0;
 
        while (scan < textLen - patternLen) {
            last = patternLen - 1;
 
            while ((last >= 0) && (text.charAt(last + scan) == pattern.charAt(last))) {
                last--;
            }
 
            if (last == -1) {
                return true;
            }
            scan += patternTable[text.charAt(scan + last)];
        }
    }
    return false;
}

Литература

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

Ссылки

• Пример реализации алгоритма Хорспула