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

  •  
      Этот алгоритм делает то, что на первый взгляд кажется невозможным: в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец. Как так может быть? Идея проста. Пусть, например, мы ищем образец "abcd". Посмотрим на четвертую букву слова: если, к примеру, это буква "e", то нет никакой необходимости читать первые три буквы. (В самом деле, в образце буквы "e" нет, поэтому он может начаться не раньше пятой буквы.)

      Мы приведем самый простой вариант этого алгоритма, который не гарантирует быстрой работы во всех случаях. Пусть x[1]..x[n] - образец, который надо искать. Для каждого символа s найдем самое правое его вхождение в слово X, то есть наибольшее k, при котором x[k]=s. Эти сведения будем хранить в массиве pos[s]; если символ s вовсе не встречается, то нам будет удобно положить pos[s] = 0 (мы увидим дальше, почему).

      10.5.1. Как заполнить массив pos?

      Решение.
      положить все pos[s] равными 0
      for i:=1 to n do begin
      pos[x[i]]:=i;
      end;

      В процессе поиска мы будем хранить в переменной last номер буквы в слове, против которой стоит последняя буква образца. Вначале last = n (длина образца), затем постепенно увеличивается.
      last:=n;
      {все предыдущие положения образца уже проверены}
      while last <= m do begin {слово не кончилось}
      | if x[m] <> y[last] then begin {последние буквы разные}
      | | last := last + (n - pos[y[last]]);
      | | {n - pos[y[last]] - это минимальный сдвиг образца,
      | | при котором напротив y[last] встанет такая же
      | | буква в образце. Если такой буквы нет вообще,
      | | то сдвигаем на всю длину образца}
      | end else begin
      | | если нынешнее положение подходит, т.е. если
      | | x[1]..x[n] = y[last-n+1]..y[last],
      | | то сообщить о совпадении;
      | | last := last+1;
      | end;
      end;

      Знатоки рекомендуют проверку совпадения проводить справа налево, т.е. начиная с последней буквы образца (в которой совпадение заведомо есть). Можно также немного сэкономить, произведя вычитание заранее и храня не pos[s], а n-pos[s], т.е. число букв в образце справа от последнего вхождения буквы s.

      Возможны разные модификации этого алгоритма. Например, можно строку last:=last+1 заменить на last:=last+(т-u), где u - координата второго справа вхождения буквы x[n] в образец.

      10.5.2. Как проще всего учесть это в программе?

      Решение. При построении таблицы pos написать
      for i:=1 to n-1 do...

      (далее как раньше), а в основной программе вместо last:=last+1 написать
      last:= last+n-pos[y[last]];

      Приведенный нами упрощённый вариант алгоритма Бойера - Мура в некоторых случаях требует существенно больше n действий (число действий порядка mn), проигрывая алгоритму Кнута - Морриса - Пратта.

      10.5.3. Привести пример ситуации, в которой образец не входит в слово, но алгоритму требуется порядка mn действий, чтобы это установить.

      Решение. Пусть образец имеет вид baaa..aa, а само слово состоит только из букв a. Тогда на каждом шаге несоответствие выясняется лишь в последний момент.

      Настоящий (не упрощённый) алгоритм Бойера - Мура гарантирует, что число действий не превосходит C*(m+n) в худшем случае. Он использует идеи, близкие к идеям алгоритма Кнута - Морриса - Пратта. Представим себе, что мы сравнивали образец со входным словом, идя справа налево. При этом некоторый кусок Z (являющийся концом образца) совпал, а затем обнаружилось различие: перед Z в образце стоит не то, что во входном слове. Что можно сказать в этот момент о входном слове? В нем обнаружен фрагмент, равный Z, а перед ним стоит не та буква, что в образце. Эта информация может позволить сдвинуть образец на несколько позиций вправо без риска пропустить его вхождение. Эти сдвиги следует вычислить заранее для каждого конца Z нашего образца. Как говорят знатоки, всё это (вычисление таблицы сдвигов и её использование) можно уложить в C*(m+n) действий.

Другие записи

10.06.2016. 10.6. Алгоритм Рабина
Этот алгоритм основан на простой идее. Представим себе, что в слове длины m мы ищем образем длины n. Вырежем окошечко размера n и будем двигать его по входному слову. Нас интересует, не совпадает ли…
10.06.2016. 10.7. Более сложные образцы и автоматы
  Мы можем искать не конкретно слово, а подслова заданного вида. Например, можно искать слова вида a?b, где вместо ? может стоять любая буква (иными словами, нас интересует буква b на расстоянии…