Алгоритм Бойера-Мура — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Достоинства)
м (rollbackEdits.php mass rollback)
 
(не показано 67 промежуточных версий 9 участников)
Строка 1: Строка 1:
Алгоритм Бойера-Мура, разработанный двумя учеными Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения справа налево в отличии от многих других алгоритмов.
+
'''Алгоритм Бойера-Мура''', разработанный двумя учеными {{---}} Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения в шаблоне справа налево в отличие от многих других алгоритмов.
  
 
Алгоритм Бойера-Мура считается наиболее эффективным алгоритмом поиска шаблонов в стандартных приложениях и командах, таких как Ctrl+F в браузерах и текстовых редакторах.
 
Алгоритм Бойера-Мура считается наиболее эффективным алгоритмом поиска шаблонов в стандартных приложениях и командах, таких как Ctrl+F в браузерах и текстовых редакторах.
  
==Асимптотики==
+
==Алгоритм==
* Фаза предварительных вычислений требует <tex>O(m + \sigma)</tex> времени и памяти
+
Алгоритм сравнивает символы шаблона <tex>x</tex> справа налево, начиная с самого правого, один за другим с символами исходной строки <tex>y</tex>. Если символы совпадают, производится сравнение предпоследнего символа шаблона и так до конца. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен. В случае несовпадения какого-либо символа (или полного совпадения всего шаблона) он использует две предварительно вычисляемых эвристических функций, чтобы сдвинуть позицию для начала сравнения вправо.
* В худшем случае поиск требует <tex>O(m \cdot n)</tex> сравнений.
+
 
* В лучшем случае требует <tex>O(n / m)</tex> сравнений.
+
Таким образом для сдвига позиции начала сравнения алгоритм Бойера-Мура выбирает между двумя функциями, называемыми эвристиками хорошего суффикса и плохого символа (иногда они называются эвристиками совпавшего суффикса и стоп-символа). Так как функции эвристические, то выбор между ними простой {{---}} ищется такое итоговое значение, чтобы мы не проверяли максимальное число позиций и при этом нашли все подстроки равные шаблону.
 +
 
 +
Алфавит обозначим буквой <tex>\Sigma</tex>.
 +
 
 +
Пусть <tex>|y|=n</tex>, <tex>|x|=m</tex> и <tex>|\Sigma|=\sigma</tex>.
 +
 
 +
Предположим, что в процессе сравнения возникает несовпадение между символом <tex>x[i]=a</tex> шаблона и символом <tex>y[i+j]=b</tex> исходного текста при проверке в позиции <tex>j</tex>. Тогда <tex>x[i+1 \dots m-1]=y[i+j+1 \dots j+m-1]=u</tex> и <tex>x[i] \neq y[i+j]</tex>, и <tex>m - i - 1</tex> символов шаблона уже совпало.
  
В 1991 году Р.Коул доказал следующую теорему:
+
===Правило сдвига хорошего суффикса===
{{Теорема
+
Если при сравнении текста и шаблона совпало один или больше символов, шаблон сдвигается в зависимости от того, какой суффикс совпал.
|author=Richard Cole
 
|statement=В худшем случае требуется <tex>O(3 \cdot n)</tex> сравнений в случае шаблона с периодом равным длине самого шаблона.
 
|proof=Доказательство [http://www.cs.nyu.edu/cs/faculty/cole/papers/CHPZ95.ps]
 
}}
 
  
==Алгоритм==
+
Если существуют такие подстроки равные <tex>u</tex>, что они полностью входят в <tex>x</tex> и идут справа от символов, отличных от <tex>x[i]</tex>, то сдвиг происходит к самой правой из них, отличной от <tex> u </tex>. Понятно, что таким образом мы не пропустим никакую строку, так как сдвиг просходит на следующую слева подстроку <tex> u </tex> от суффикса. После выравнивания шаблона по этой подстроке сравнение шаблона опять начнется с его последнего символа. На новом шаге алгоритма можно строку <tex> u </tex>, по которой был произведён cдвиг, не сравнивать с текстом {{---}} возможность для модификации и дальнейшего ускорения алгоритма.
Алгоритм сравнивает символы ''шаблона'' (<tex>y</tex>) справа налево, начиная с самого правого, один за другим с символами ''исходной строки'' (<tex>x</tex>). В случае несовпадения какого-либо символа (или полного совпадения всего шаблона) он использует две предварительно вычисляемых функций, чтобы сдвинуть позицию для начала сравнения вправо.
 
  
Пусть <tex>|y|=n</tex> и <tex>|x|=m</tex>.
+
[[Файл:boyer-moore-algorithm-1.png|450px|thumb|center|'''Сдвиг хорошего суффикса''', вся подстрока <tex>u</tex> полностью встречается справа от символа <tex>c</tex>, отличного от символа <tex>a</tex>.]]
  
Предположим, что в процессе сравнения возникает несовпадение между символом <tex>x[i]=a</tex> шаблона и символом <tex>y[i+j]=b</tex> исходного текста при проверке в позиции <tex>j</tex>. Тогда <tex>x[i+1 .. m-1]=y[i+j+1 .. j+m-1]=u</tex> и <tex>x[i] \neq y[i+j]</tex>, т.е. <tex>m - i - 1</tex> символов паттерна уже совпало.
+
Если не существует таких подстрок, то смещение состоит в выравнивании самого длинного суффикса <tex>v</tex> подстроки <tex>y[i+j+1 \dots j+m-1]</tex> с соответствующим префиксом <tex>x</tex>. Из-за того, что мы не смогли найти такую подстроку, то, очевидно, что ни один суффикс шаблона <tex>x</tex> уже не будет лежать в подстроке <tex>y[i+j+1 \dots j+m-1]</tex>, поэтому единственный вариант, что в эту подстроку попадет префикс.
  
Операция '''сдвига хорошего суффикса''' состоит в выравнивании подстроки <tex>u</tex> с её самым правым вхождением в <tex>x</tex>, идущим справа от символа, отличного от <tex>x[i]</tex>.
+
[[Файл:boyer-moore-algorithm-2.png|450px|thumb|center|'''Сдвиг хорошего суффикса''', только суффикс подстроки <tex>u</tex> повторно встречается в <tex>x</tex>.]]
  
[[Файл:boyer-moore-algorithm-1.gif|450px|thumb|center|'''Сдвиг хорошего суффикса''', вся подстрока <tex>u</tex> полностью встречается справа от символа <tex>c</tex>, отличного от символа <tex>a</tex>.]]
+
===Правило сдвига плохого символа===
 +
В таблице плохих символов указывается последняя позиция в шаблоне (исключая последнюю букву) каждого из символов алфавита. Для всех символов, не вошедших в шаблон, пишем <tex>m</tex>. Предположим, что у нас не совпал символ <tex>c</tex> из текста на очередном шаге с символом из шаблона. Очевидно, что в таком случае мы можем сдвинуть шаблон до первого вхождения этого символа <tex>c</tex> в шаблоне, потому что совпадений других символов точно не может быть. Если в шаблоне такого символа нет, то можно сдвинуть весь шаблон полностью.
  
Если не существует такого сегмента, то смещение состоит в выравнивании самого длинного суффикса <tex>v</tex> подстроки <tex>y[i+j+1 .. j+m-1]</tex> с соответствующим префиксом <tex>x</tex>.
+
Если символ исходного текста <tex>y[i + j]</tex> встречается в шаблоне <tex>x</tex>, то происходит его выравнивание с его самым правым появлением в подстроке <tex>x[0 \dots m-2]</tex>.
  
[[Файл:boyer-moore-algorithm-2.gif|450px|thumb|center|'''Сдвиг хорошего суффикса''', только суффикс подстроки <tex>u</tex> повторно встречается в <tex>x</tex>.]]
+
[[Файл:boyer-moore-algorithm-3.png|450px|thumb|center|'''Сдвиг плохого символа''', символ <tex>a</tex> входит в <tex>x</tex>.]]
  
Операция '''сдвига плохого символа''' состоит в выравнивании символа исходного текста <tex>у[i + j]</tex> с его самым правым появлением в <tex>x[0 .. m-2]</tex>.
+
Если <tex>y[i+j]</tex> не встречается в шаблоне <tex>x</tex>, то ни одно вхождение <tex>x</tex> в <tex>y</tex> не может включать в себя <tex>y[i+j]</tex>, и левый конец окна сравнения совмещен с символом непосредственно идущим после <tex>y[i+j]</tex>, то есть символ <tex>y[i+j+1]</tex>.
  
[[Файл:boyer-moore-algorithm-3.gif|450px|thumb|center|'''Сдвиг плохого символа''', символ <tex>a</tex> входит в <tex>x</tex>.]]
+
[[Файл:boyer-moore-algorithm-4.png|450px|thumb|center|'''Сдвиг плохого символа''', символ <tex>b</tex> не входит в <tex>x</tex>.]]
  
Если <tex>y[i+j]</tex> не встречается в шаблоне x, то ни одно вхождение x в y не может включать в себя <tex>y[i+j]</tex>, и левый конец окна сравнения совмещен с символом непосредственно идущим после <tex>y[i+j]</tex>, т.е. <tex>y[i+j+1]</tex>.
+
Обратите внимание, что сдвиг плохого символа может быть отрицательным, поэтому исходя из ранее приведенных свойств этих функций берется значение равное максимуму между сдвигом хорошего суффикса и сдвигом плохого символа.
  
[[Файл:boyer-moore-algorithm-4.gif|450px|thumb|center|'''Сдвиг плохого символа''', символ <tex>b</tex> не входит в <tex>x</tex>.]]
+
===Формальное определение===
  
Обратите внимание, что сдвиг плохого символа может быть отрицательным, таким образом для сдвига окна сравнения алгоритм Бойера-Мура использует значение, равное максимуму между сдвигом хорошего суффикса и сдвига плохого символа. Более формально две функции сдвигов определяются следующим образом:
+
Теперь определим две функции сдвигов более формально следующим образом:
  
 
Пусть значения функции сдвига хорошего суффикса хранятся в массиве <tex>bmGs</tex> размером <tex>m+1</tex>.
 
Пусть значения функции сдвига хорошего суффикса хранятся в массиве <tex>bmGs</tex> размером <tex>m+1</tex>.
  
 
Определим два условия:
 
Определим два условия:
* <tex>Cs(i, s)</tex>: для каждого <tex>k</tex> такого, что <tex>i < k < m</tex> выполняется <tex>s \geqslant k</tex> или <tex>x[k-s]=x[k]</tex>
+
* <tex>\mathrm{Cs}(i, s)</tex>: для каждого <tex>k</tex> такого, что <tex>i < k < m</tex> выполняется <tex>s \geqslant k</tex> или <tex>x[k-s]=x[k]</tex>
* <tex>Co(i, s)</tex>: если <tex>s < i</tex>, то выполняется <tex>x[i-s] \neq x[i]</tex>
+
* <tex>\mathrm{Co}(i, s)</tex>: если <tex>s < i</tex>, то выполняется <tex>x[i-s] \neq x[i]</tex>
 +
 
 +
Тогда для всех <tex>i</tex> таких, что <tex>0 \leqslant i < m</tex> выполняется <tex>bmGs[i+1]=\min\{s > 0 : \mathrm{Cs}(i, s)\ \wedge\ \mathrm{Co}(i, s)\}</tex>.
  
Тогда для всех <tex>i</tex> таких, что <tex>0 \leqslant i < m</tex> выполняется <tex>bmGs[i+1]=\min\{s > 0 : Cs(i, s)\ and\ Co(i, s)\}</tex>. А значение <tex>bmGs[0]</tex> определим, как длину периода шаблона <tex>x</tex>.
+
А значение <tex>bmGs[0]</tex> определим, как длину периода шаблона <tex>x</tex>.
  
Для вычисления bmGs будем использовать массив <tex>suff</tex>, определенный так:
+
Для вычисления <tex> bmGs </tex> будем использовать функцию <tex>\mathrm{suffixLength}</tex>, определенную так:
для всех <tex>i</tex> таких, что <tex>1 \leqslant i < m</tex> выполняется <tex>suff[i]=\max\{k : x[i-k+1 .. i]=x[m-k .. m-1]\}</tex>
+
для всех <tex>i</tex> таких, что <tex>1 \leqslant i < m</tex> выполняется <tex>\mathrm{suffixLength}(i)=\max\{k : x[i-k+1 \dots i]=x[m-k \dots m-1]\}</tex>
  
 
Сдвиги плохих символов будем хранить в массиве <tex>bmBc</tex> размером <tex>\sigma</tex>.
 
Сдвиги плохих символов будем хранить в массиве <tex>bmBc</tex> размером <tex>\sigma</tex>.
 
Для каждого символа <tex>c</tex> из <tex>\Sigma</tex>: <tex>bmBc[c] = \begin{cases}
 
Для каждого символа <tex>c</tex> из <tex>\Sigma</tex>: <tex>bmBc[c] = \begin{cases}
   \min\{i : 1 \leqslant i < m-1\ and\ x[m-1-i]=c\},  & \mbox{if }  c \in x\\
+
   \min\{i : 1 \leqslant i < m-1\ \wedge\ x[m-1-i]=c\},  & \mbox{if }  c \in x\\
 
   m, & \mbox{otherwise}
 
   m, & \mbox{otherwise}
 
\end{cases}</tex>
 
\end{cases}</tex>
  
Массивы <tex>bmBc</tex> и <tex>bmGs</tex> вычисляются за <tex>O(m+\sigma)</tex> времени до основной фазы поиска и требуют, очевидно, <tex>O(m+\sigma)</tex> памяти.
+
Массивы <tex>bmBc</tex> и <tex>bmGs</tex> вычисляются за <tex>O(m^2+\sigma)</tex> времени до основной фазы поиска и требуют, очевидно, <tex>O(m+\sigma)</tex> памяти.
 +
 
 +
==Псевдокод==
 +
Константой <tex>|\Sigma|=\sigma</tex> обозначим размер нашего алфавита.
  
==Псевдо-код==
+
Функция для вычисления таблицы сдвигов плохих символов. Она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона). Вычисляется прямо по определению за <tex>O(m+\sigma)</tex>.
Константой <tex>|\Sigma|=\sigma=ASIZE</tex> обозначим размер нашего алфавита.
+
  '''int'''[] preBmBc('''char'''[m] x):
 +
      '''int''' table<tex>[</tex> <tex>|\Sigma|</tex> <tex>]</tex>
 +
      <font color=green>// Заполняем значением по умолчанию, равным длине шаблона</font>
 +
      '''for''' i = 0 .. <tex>|\Sigma|</tex> - 1
 +
        table[i] = m
 +
      <font color=green>// Вычисление функции по определению</font>
 +
      '''for''' i = 0 .. m - 2
 +
        table[x[i]] = m - 1 - i
 +
      '''return''' table
  
Функция для вычисления таблицы сдвигов плохих символов. Она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона). Вычисляется прямо по определению за <tex>O(m+\sigma)</tex>
+
Функция, проверяющая, что подстрока <tex>x[p \dots m - 1]</tex> является префиксом шаблона <tex>x</tex>. Требует <tex>O(m - p)</tex> времени.
   int[] '''preBmBc'''(string x, int m):
+
   '''boolean''' isPrefix('''char'''[m] x, '''int''' p):
       int bmBc[ASIZE];
+
       '''int''' j = 0
      <font color=green>// Значение по умолчанию = m</font>
+
       '''for''' i = p .. m - 1
       for i = 0 .. ASIZE-1
+
         '''if''' x[i] != x[j]
         bmBc[i] = m;
+
            '''return''' false
      for i = 0 .. m - 2
+
         ++j
         bmBc[x[i]] = m - i - 1;
+
       '''return''' true
       return bmBc;
+
 
+
Функция, возвращающая для позиции <tex>p</tex> длину максимальной подстроки, которая является суффиксом шаблона <tex>x</tex>. Требует <tex>O(m - p)</tex> времени. //здесь неправильно, нет смысла сравнивать элементы ШАБЛОНА С САМИМ СОБОЙ
Функция для вычисления таблицы суффиксов. Она находит для каждой позиции в шаблоне <tex>x</tex> максимальную длину суффикса <tex>x</tex>, который повторяется в строке и заканчивается в данной позиции. Например, для строки "'''abcabcabc'''" таблица будет '''0,0,3,0,0,6,0,0,9''', а для строки "'''abcabcc'''" - '''0,0,1,0,0,1,7'''. Также, очевидно, что значение функции для последнего элемента будет равно длине всей строки.
+
  '''int''' suffixLength('''char'''[m] x, '''int''' p):
  int[] '''suffixes'''(string x, int m):
+
      '''int''' len = 0
      int f;
+
      '''int''' i = p
      int suff[m];
+
       '''int''' j = m - 1
      suff[m - 1] = m;
+
       '''while''' i <tex>\geqslant</tex> 0 '''and''' x[i] == x[j]
       int g = m - 1;
+
            ++len
       for i = m - 2 .. 0
+
            --i
        if (i > g and suff[i + m - 1 - f] < i - g)
+
             --j
            suff[i] = suff[i + m - 1 - f];
+
       '''return''' len
        else
 
            if (i < g)
 
              g = i;
 
            f = i;
 
            while (g >= 0 and x[g] == x[g + m - 1 - f])
 
              --g;
 
             suff[i] = f - g;
 
       return suff;
 
  
Функция для вычисления сдвигов хороших суффиксов
+
Функция для вычисления сдвигов хороших суффиксов. Требует <tex>O(m)</tex> времени, несмотря на циклы в вызываемых функциях, из-за того, что каждый внутренний цикл в худшем случае будет выполняться на каждой позиции <tex>i</tex> не больше, чем <tex>i</tex> раз. Получается натуральный ряд, сумма <tex>m</tex> первых членов которого <tex dpi="150">\frac{m \cdot (m - 1)}{2}</tex>. Следовательно, получается оценка по времени <tex>O(m^2)</tex>.
   void '''preBmGs'''(string x, int m):
+
   '''int'''[] preBmGs('''char'''[m] x):
       int i, j, suff[XSIZE];
+
       '''int''' table[m]
       int bmGs[]
+
       '''int''' lastPrefixPosition = m
      suff = suffixes(x, m);
+
       '''for''' i = m - 1 .. 0
+
         <font color=green>// Если подстрока x[i+1..m-1] является префиксом, то запомним её начало</font>
       for (i = 0; i < m; ++i)
+
         '''if''' isPrefix(x, i + 1)
         bmGs[i] = m;
+
            lastPrefixPosition = i + 1
      j = 0;
+
        table[m - 1 - i] = lastPrefixPosition - i + m - 1
      for i = m - 1 .. 0
+
      <font color=green>// Вычисление функции по определению</font>
         if (suff[i] == i + 1)
+
       '''for''' i = 0 .. m - 2
            while (j < m - 1 - i)
+
         '''int''' slen = suffixLength(x, i)
              if (bmGs[j] == m)
+
        table[slen] = m - 1 - i + slen
                  bmGs[j] = m - 1 - i;
+
      '''return''' table
              ++j
 
       for i = 0 .. m - 2
 
         bmGs[m - 1 - suff[i]] = m - 1 - i;
 
 
   
 
   
 
Основная функция алгоритма Бойера-Мура
 
Основная функция алгоритма Бойера-Мура
   void '''BM'''(string x, int m, string y, int n):
+
   '''function''' BM('''char'''[n] y, '''char'''[m] x): '''vector <int>'''
       int bmGs[m];
+
       '''vector <int>''' answer <font color=green>// вектор, содержащий все вхождения подстроки в строку</font>
       int bmBc[ASIZE];
+
      '''if''' m == 0
+
        answer.pushBack(-1) <font color=green>// Искомая подстрока является пустой</font>
       <font color=green>//Предварительные вычисления</font>
+
        '''return''' answer
       bmGs = preBmGs(x, m);
+
        
       bmBc = preBmBc(x, m);
+
       <font color=green>// Предварительные вычисления</font>
   
+
       '''int'''<tex>[</tex> <tex>|\Sigma|</tex> <tex>]</tex> bmBc = preBmBc(x)
       <font color=green>//Поиск подстроки</font>
+
       '''int'''[m] bmGs = preBmGs(x)
       int j = 0;
+
     
      while (j <= n - m)
+
       <font color=green>// Поиск подстроки</font>
         int i = m - 1;
+
       '''for''' i = m - 1 .. n - 1
         while (i >= 0 and x[i] == y[i + j])
+
         '''int''' j = m - 1
 +
         '''while''' x[j] == y[i]
 +
            '''if''' j == 0
 +
              answer.pushBack(i) <font color=green>// Найдена подстрока в позиции i</font>
 
             --i
 
             --i
         if (i < 0)
+
            --j
            OUTPUT(j); <font color=green>// Найдена подстрока в позиции j</font>
+
         i += max(bmGs[m - 1 - j], bmBc[y[i]])
            j += bmGs[0]; <font color=green>//Очевидно, что можем сделать сдвиг на период, т.к. там явно не будет совпадений.</font>
+
      '''if''' (answer == <tex> \varnothing </tex>)
        else
+
        answer.pushBack(-1) <font color=green>// Искомая подстрока не найдена</font>
            j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
+
      '''return''' answer
 +
 
 +
==Пример==
 +
Пусть нам дана строка <tex>y = GCATCGCAGAGAGTATACAGTACG</tex> и образец <tex>x=GCAGAGAG</tex>.
 +
 
 +
Построим массивы <tex>bmBc</tex> и <tex>bmGs</tex> :
 +
 
 +
[[Файл:RaitaPre.png|250px]]
 +
 
 +
[[Файл:Crochemore.png|300px]]
 +
 
 +
Рассмотрим шаги алгоритма:
 +
 
 +
{| class = "wikitable"
 +
! Изображение !! <tex>(j, bmGs[y[j]])</tex> !! Описание
 +
|-align="center"
 +
|[[Файл:BMexample1.png|550px]]
 +
|<tex>(7, 1)</tex>
 +
|Сравниванием последние символы, они неравны, поэтому сдвигаемся на <tex> bmGs[y[j]]</tex>, где <tex>y[j]</tex> {{---}} это не совпавший символ. В данном случае <tex>y[j]=7</tex>, а <tex> bmGs[7]= 1</tex>.
 +
|-align="center"
 +
|[[Файл:BMexample2.png|550px]]
 +
|<tex>(8, 4)</tex>
 +
|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на <tex> bmGs[5]= 4</tex>.
 +
|-align="center"
 +
|[[Файл:BMexample3.png|550px]]
 +
|<tex>(12, 7)</tex>
 +
|Последние символы совпали, сравниваем далее. Строчка найдена. Продолжаем работу и сдвигаемся на <tex> bmGs[0]= 7</tex>.
 +
|-align="center"
 +
|[[Файл:BMexample4.png|550px]]
 +
|<tex>(19, 4)</tex>
 +
|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на <tex> bmGs[5]= 4</tex>.
 +
|-align="center"
 +
|[[Файл:BMexample5.png|550px]]
 +
|<tex>(23, 7)</tex>
 +
|Последние символы совпали, предпоследние различны. Алгоритм закончил работу.
 +
|-align="center"
 +
|}
 +
 
 +
В итоге, чтобы найти одно вхождение образца длиной <tex>m = 8</tex> в образце длиной <tex>n = 24</tex>, нам понадобилось <tex>17</tex> сравнений символов.
 +
 
 +
==Асимптотики==
 +
* Фаза предварительных вычислений требует <tex>O(m^2 + \sigma)</tex> времени и памяти.
 +
* В худшем случае поиск требует <tex>O(m \cdot n)</tex> сравнений.
 +
* В лучшем случае требует <tex > \Omega \left( \dfrac{n}{m} \right)</tex> сравнений.
 +
 
 +
'''Пример:'''
 +
Исходный текст <tex>bb \dots bb</tex> и шаблон <tex>abab \dots abab</tex>. Из-за того, что все символы <tex>b</tex> из текста повторяются в шаблоне <tex>\dfrac{m}{2}</tex> раз, эвристика хорошего суффикса будет пытаться сопоставить шаблон в каждой позиции (суммарно, <tex>n</tex> раз), а эвристика плохого символа в каждой позиции будет двигать строку <tex>\dfrac{m}{2}</tex> раз. Итого, <tex>O(n \cdot m)</tex>.
 +
 
 +
где <tex>n</tex> {{---}} длина исходного текста, <tex>m</tex> {{---}} длина шаблона, <tex>\sigma</tex> {{---}} размер алфавита.
 +
 
 +
==Варианты==
 +
===Алгоритм Бойера — Мура — Хорспула===
 +
Этот алгоритм работает лучше Бойера-Мура на случайных текстах — для него оценка в среднем лучше.
 +
Алгоритм использует только сдвиги плохих символов, при этом за такой символ берётся символ из исходного текста, который соответствует последнему символу шаблона, независимо от того, где случилось несовпадение.
 +
Поскольку реальные поисковые образцы редко имеют равномерное распределение, алгоритм Бойера-Мура-Хорспула может дать как выигрыш, так и проигрыш по сравнению с стандартной реализацией.
 +
===Алгоритм Чжу — Такаоки===
 +
На коротких алфавитах сдвиги плохих символов не помогают уже на коротких суффиксах. Простейший способ улучшить работу алгоритма в таких условиях — вместо одного плохого символа строить таблицу для пары символов: несовпавшего и идущего перед ним. Такой алгоритм получил собственное имя: алгоритм Чжу — Такаоки.
 +
На предварительную обработку расходуется <tex>O(m+\sigma^2)</tex> времени.
  
 
==Сравнение с другими алгоритмами==
 
==Сравнение с другими алгоритмами==
 
===Достоинства===
 
===Достоинства===
 
* Алгоритм Бойера-Мура на хороших данных очень быстр, а вероятность появления плохих данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск.
 
* Алгоритм Бойера-Мура на хороших данных очень быстр, а вероятность появления плохих данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск.
* На больших алфавитах (относительно длины шаблона) алгоритм чрезвычайно быстрый и требует намного меньше памяти относительно [[Алгоритм Ахо-Корасик|алгоритма Ахо-Корасик]].
+
* На больших алфавитах (относительно длины шаблона) алгоритм чрезвычайно быстрый и требует намного меньше памяти, чем [[Алгоритм Ахо-Корасик|алгоритм Ахо-Корасик]].
* Алгоритм проще большинства алгоритмов поиска (при некоторых реализациях объем кода сравним с [[Наивный_алгоритм_поиска_подстроки_в_строке|наивным поиском]])
+
* Позволяет добавить множество модификаций, таких как поиск подстроки, включающей ''любой символ (?)'' (но для реализации ''множества символов (*)'' не подходит, так как длина шаблона должна быть известна заранее).
* Позволяет добавить множество модификаций, таких как поиск подстроки, включающей ''любой символ (?)'' (но для реализации ''множества символов (*)'' не походит, т.к. длина шаблона должна быть известна заранее).
 
  
 
===Недостатки===
 
===Недостатки===
 
* Алгоритмы семейства Бойера-Мура не расширяются до приблизительного поиска, поиска любой строки из нескольких.
 
* Алгоритмы семейства Бойера-Мура не расширяются до приблизительного поиска, поиска любой строки из нескольких.
* Сравнение не является "чёрным ящиком", поэтому при реализации наиболее быстрого поиска приходится либо рассчитывать на удачную работу оптимизатора, либо вручную оптимизировать поиск.
 
 
* На больших алфавитах (например, Юникод) может занимать много памяти. В таких случаях либо обходятся хэш-таблицами, либо дробят алфавит, рассматривая, например, 4-байтовый символ как пару двухбайтовых.
 
* На больших алфавитах (например, Юникод) может занимать много памяти. В таких случаях либо обходятся хэш-таблицами, либо дробят алфавит, рассматривая, например, 4-байтовый символ как пару двухбайтовых.
* На искусственно подобранных неудачных текстах (например, needle=«колоколоколоколоколокол») скорость алгоритма Бойера-Мура серьёзно снижается.
+
* На искусственно подобранных неудачных текстах скорость алгоритма Бойера-Мура серьёзно снижается.
  
==Ссылки==
+
==Источники информации==
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9C%D1%83%D1%80%D0%B0 Википедия:Алгоритм Бойера-Мура]
+
* [[wikipedia:ru:Алгоритм_Бойера_—_Мура|Википедия {{---}} Алгоритм Бойера-Мура]]
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9C%D1%83%D1%80%D0%B0_%E2%80%94_%D0%A5%D0%BE%D1%80%D1%81%D0%BF%D1%83%D0%BB%D0%B0 Википедия:Алгоритм Бойера-Мура-Хорспула]
+
* [[wikipedia:ru:Алгоритм_Бойера_—_Мура_—_Хорспула|Википедия {{---}} Алгоритм Бойера-Мура-Хорспула]]
* [http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm Wikipedia:Boyer–Moore string search algorithm]
+
* [[wikipedia:Boyer–Moore_string_search_algorithm|Wikipedia {{---}} Boyer–Moore string search algorithm]]
 
* [http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140 Boyer-Moore algorithm]
 
* [http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140 Boyer-Moore algorithm]
 +
* [http://algolist.manual.ru/search/esearch/bm.php Алгоритм Боуера-Мура]
  
 
[[Категория: Дискретная математика и алгоритмы]]  
 
[[Категория: Дискретная математика и алгоритмы]]  
 
[[Категория: Поиск подстроки в строке]]
 
[[Категория: Поиск подстроки в строке]]
 +
[[Категория: Точный поиск]]

Текущая версия на 19:21, 4 сентября 2022

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

Алгоритм Бойера-Мура считается наиболее эффективным алгоритмом поиска шаблонов в стандартных приложениях и командах, таких как Ctrl+F в браузерах и текстовых редакторах.

Алгоритм

Алгоритм сравнивает символы шаблона [math]x[/math] справа налево, начиная с самого правого, один за другим с символами исходной строки [math]y[/math]. Если символы совпадают, производится сравнение предпоследнего символа шаблона и так до конца. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен. В случае несовпадения какого-либо символа (или полного совпадения всего шаблона) он использует две предварительно вычисляемых эвристических функций, чтобы сдвинуть позицию для начала сравнения вправо.

Таким образом для сдвига позиции начала сравнения алгоритм Бойера-Мура выбирает между двумя функциями, называемыми эвристиками хорошего суффикса и плохого символа (иногда они называются эвристиками совпавшего суффикса и стоп-символа). Так как функции эвристические, то выбор между ними простой — ищется такое итоговое значение, чтобы мы не проверяли максимальное число позиций и при этом нашли все подстроки равные шаблону.

Алфавит обозначим буквой [math]\Sigma[/math].

Пусть [math]|y|=n[/math], [math]|x|=m[/math] и [math]|\Sigma|=\sigma[/math].

Предположим, что в процессе сравнения возникает несовпадение между символом [math]x[i]=a[/math] шаблона и символом [math]y[i+j]=b[/math] исходного текста при проверке в позиции [math]j[/math]. Тогда [math]x[i+1 \dots m-1]=y[i+j+1 \dots j+m-1]=u[/math] и [math]x[i] \neq y[i+j][/math], и [math]m - i - 1[/math] символов шаблона уже совпало.

Правило сдвига хорошего суффикса

Если при сравнении текста и шаблона совпало один или больше символов, шаблон сдвигается в зависимости от того, какой суффикс совпал.

Если существуют такие подстроки равные [math]u[/math], что они полностью входят в [math]x[/math] и идут справа от символов, отличных от [math]x[i][/math], то сдвиг происходит к самой правой из них, отличной от [math] u [/math]. Понятно, что таким образом мы не пропустим никакую строку, так как сдвиг просходит на следующую слева подстроку [math] u [/math] от суффикса. После выравнивания шаблона по этой подстроке сравнение шаблона опять начнется с его последнего символа. На новом шаге алгоритма можно строку [math] u [/math], по которой был произведён cдвиг, не сравнивать с текстом — возможность для модификации и дальнейшего ускорения алгоритма.

Сдвиг хорошего суффикса, вся подстрока [math]u[/math] полностью встречается справа от символа [math]c[/math], отличного от символа [math]a[/math].

Если не существует таких подстрок, то смещение состоит в выравнивании самого длинного суффикса [math]v[/math] подстроки [math]y[i+j+1 \dots j+m-1][/math] с соответствующим префиксом [math]x[/math]. Из-за того, что мы не смогли найти такую подстроку, то, очевидно, что ни один суффикс шаблона [math]x[/math] уже не будет лежать в подстроке [math]y[i+j+1 \dots j+m-1][/math], поэтому единственный вариант, что в эту подстроку попадет префикс.

Сдвиг хорошего суффикса, только суффикс подстроки [math]u[/math] повторно встречается в [math]x[/math].

Правило сдвига плохого символа

В таблице плохих символов указывается последняя позиция в шаблоне (исключая последнюю букву) каждого из символов алфавита. Для всех символов, не вошедших в шаблон, пишем [math]m[/math]. Предположим, что у нас не совпал символ [math]c[/math] из текста на очередном шаге с символом из шаблона. Очевидно, что в таком случае мы можем сдвинуть шаблон до первого вхождения этого символа [math]c[/math] в шаблоне, потому что совпадений других символов точно не может быть. Если в шаблоне такого символа нет, то можно сдвинуть весь шаблон полностью.

Если символ исходного текста [math]y[i + j][/math] встречается в шаблоне [math]x[/math], то происходит его выравнивание с его самым правым появлением в подстроке [math]x[0 \dots m-2][/math].

Сдвиг плохого символа, символ [math]a[/math] входит в [math]x[/math].

Если [math]y[i+j][/math] не встречается в шаблоне [math]x[/math], то ни одно вхождение [math]x[/math] в [math]y[/math] не может включать в себя [math]y[i+j][/math], и левый конец окна сравнения совмещен с символом непосредственно идущим после [math]y[i+j][/math], то есть символ [math]y[i+j+1][/math].

Сдвиг плохого символа, символ [math]b[/math] не входит в [math]x[/math].

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

Формальное определение

Теперь определим две функции сдвигов более формально следующим образом:

Пусть значения функции сдвига хорошего суффикса хранятся в массиве [math]bmGs[/math] размером [math]m+1[/math].

Определим два условия:

  • [math]\mathrm{Cs}(i, s)[/math]: для каждого [math]k[/math] такого, что [math]i \lt k \lt m[/math] выполняется [math]s \geqslant k[/math] или [math]x[k-s]=x[k][/math]
  • [math]\mathrm{Co}(i, s)[/math]: если [math]s \lt i[/math], то выполняется [math]x[i-s] \neq x[i][/math]

Тогда для всех [math]i[/math] таких, что [math]0 \leqslant i \lt m[/math] выполняется [math]bmGs[i+1]=\min\{s \gt 0 : \mathrm{Cs}(i, s)\ \wedge\ \mathrm{Co}(i, s)\}[/math].

А значение [math]bmGs[0][/math] определим, как длину периода шаблона [math]x[/math].

Для вычисления [math] bmGs [/math] будем использовать функцию [math]\mathrm{suffixLength}[/math], определенную так: для всех [math]i[/math] таких, что [math]1 \leqslant i \lt m[/math] выполняется [math]\mathrm{suffixLength}(i)=\max\{k : x[i-k+1 \dots i]=x[m-k \dots m-1]\}[/math]

Сдвиги плохих символов будем хранить в массиве [math]bmBc[/math] размером [math]\sigma[/math]. Для каждого символа [math]c[/math] из [math]\Sigma[/math]: [math]bmBc[c] = \begin{cases} \min\{i : 1 \leqslant i \lt m-1\ \wedge\ x[m-1-i]=c\}, & \mbox{if } c \in x\\ m, & \mbox{otherwise} \end{cases}[/math]

Массивы [math]bmBc[/math] и [math]bmGs[/math] вычисляются за [math]O(m^2+\sigma)[/math] времени до основной фазы поиска и требуют, очевидно, [math]O(m+\sigma)[/math] памяти.

Псевдокод

Константой [math]|\Sigma|=\sigma[/math] обозначим размер нашего алфавита.

Функция для вычисления таблицы сдвигов плохих символов. Она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона). Вычисляется прямо по определению за [math]O(m+\sigma)[/math].

  int[] preBmBc(char[m] x):
     int table[math][[/math] [math]|\Sigma|[/math] [math]][/math]
     // Заполняем значением по умолчанию, равным длине шаблона
     for i = 0 .. [math]|\Sigma|[/math] - 1
        table[i] = m
     // Вычисление функции по определению
     for i = 0 .. m - 2
        table[x[i]] = m - 1 - i
     return table

Функция, проверяющая, что подстрока [math]x[p \dots m - 1][/math] является префиксом шаблона [math]x[/math]. Требует [math]O(m - p)[/math] времени.

  boolean isPrefix(char[m] x, int p):
     int j = 0
     for i = p .. m - 1
        if x[i] != x[j]
           return false
        ++j
     return true

Функция, возвращающая для позиции [math]p[/math] длину максимальной подстроки, которая является суффиксом шаблона [math]x[/math]. Требует [math]O(m - p)[/math] времени. //здесь неправильно, нет смысла сравнивать элементы ШАБЛОНА С САМИМ СОБОЙ

  int suffixLength(char[m] x, int p):
     int len = 0
     int i = p
     int j = m - 1
     while i [math]\geqslant[/math] 0 and x[i] == x[j]
           ++len 
           --i
           --j
     return len

Функция для вычисления сдвигов хороших суффиксов. Требует [math]O(m)[/math] времени, несмотря на циклы в вызываемых функциях, из-за того, что каждый внутренний цикл в худшем случае будет выполняться на каждой позиции [math]i[/math] не больше, чем [math]i[/math] раз. Получается натуральный ряд, сумма [math]m[/math] первых членов которого [math]\frac{m \cdot (m - 1)}{2}[/math]. Следовательно, получается оценка по времени [math]O(m^2)[/math].

  int[] preBmGs(char[m] x):
     int table[m]
     int lastPrefixPosition = m
     for i = m - 1 .. 0
        // Если подстрока x[i+1..m-1] является префиксом, то запомним её начало
        if isPrefix(x, i + 1)
           lastPrefixPosition = i + 1
        table[m - 1 - i] = lastPrefixPosition - i + m - 1
     // Вычисление функции по определению
     for i = 0 .. m - 2
        int slen = suffixLength(x, i)
        table[slen] = m - 1 - i + slen
     return table

Основная функция алгоритма Бойера-Мура

  function BM(char[n] y, char[m] x): vector <int>
     vector <int> answer // вектор, содержащий все вхождения подстроки в строку
     if m == 0
        answer.pushBack(-1) // Искомая подстрока является пустой
        return answer 
     
     // Предварительные вычисления
     int[math][[/math] [math]|\Sigma|[/math] [math]][/math] bmBc = preBmBc(x)
     int[m] bmGs = preBmGs(x)
     
     // Поиск подстроки
     for i = m - 1 .. n - 1
        int j = m - 1
        while x[j] == y[i]
           if j == 0
              answer.pushBack(i) // Найдена подстрока в позиции i
           --i
           --j
        i += max(bmGs[m - 1 - j], bmBc[y[i]])
     if (answer == [math] \varnothing [/math])
        answer.pushBack(-1) // Искомая подстрока не найдена
     return answer

Пример

Пусть нам дана строка [math]y = GCATCGCAGAGAGTATACAGTACG[/math] и образец [math]x=GCAGAGAG[/math].

Построим массивы [math]bmBc[/math] и [math]bmGs[/math] :

RaitaPre.png

Crochemore.png

Рассмотрим шаги алгоритма:

Изображение [math](j, bmGs[y[j]])[/math] Описание
BMexample1.png [math](7, 1)[/math] Сравниванием последние символы, они неравны, поэтому сдвигаемся на [math] bmGs[y[j]][/math], где [math]y[j][/math] — это не совпавший символ. В данном случае [math]y[j]=7[/math], а [math] bmGs[7]= 1[/math].
BMexample2.png [math](8, 4)[/math] Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на [math] bmGs[5]= 4[/math].
BMexample3.png [math](12, 7)[/math] Последние символы совпали, сравниваем далее. Строчка найдена. Продолжаем работу и сдвигаемся на [math] bmGs[0]= 7[/math].
BMexample4.png [math](19, 4)[/math] Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на [math] bmGs[5]= 4[/math].
BMexample5.png [math](23, 7)[/math] Последние символы совпали, предпоследние различны. Алгоритм закончил работу.

В итоге, чтобы найти одно вхождение образца длиной [math]m = 8[/math] в образце длиной [math]n = 24[/math], нам понадобилось [math]17[/math] сравнений символов.

Асимптотики

  • Фаза предварительных вычислений требует [math]O(m^2 + \sigma)[/math] времени и памяти.
  • В худшем случае поиск требует [math]O(m \cdot n)[/math] сравнений.
  • В лучшем случае требует [math] \Omega \left( \dfrac{n}{m} \right)[/math] сравнений.

Пример: Исходный текст [math]bb \dots bb[/math] и шаблон [math]abab \dots abab[/math]. Из-за того, что все символы [math]b[/math] из текста повторяются в шаблоне [math]\dfrac{m}{2}[/math] раз, эвристика хорошего суффикса будет пытаться сопоставить шаблон в каждой позиции (суммарно, [math]n[/math] раз), а эвристика плохого символа в каждой позиции будет двигать строку [math]\dfrac{m}{2}[/math] раз. Итого, [math]O(n \cdot m)[/math].

где [math]n[/math] — длина исходного текста, [math]m[/math] — длина шаблона, [math]\sigma[/math] — размер алфавита.

Варианты

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

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

Алгоритм Чжу — Такаоки

На коротких алфавитах сдвиги плохих символов не помогают уже на коротких суффиксах. Простейший способ улучшить работу алгоритма в таких условиях — вместо одного плохого символа строить таблицу для пары символов: несовпавшего и идущего перед ним. Такой алгоритм получил собственное имя: алгоритм Чжу — Такаоки. На предварительную обработку расходуется [math]O(m+\sigma^2)[/math] времени.

Сравнение с другими алгоритмами

Достоинства

  • Алгоритм Бойера-Мура на хороших данных очень быстр, а вероятность появления плохих данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск.
  • На больших алфавитах (относительно длины шаблона) алгоритм чрезвычайно быстрый и требует намного меньше памяти, чем алгоритм Ахо-Корасик.
  • Позволяет добавить множество модификаций, таких как поиск подстроки, включающей любой символ (?) (но для реализации множества символов (*) не подходит, так как длина шаблона должна быть известна заранее).

Недостатки

  • Алгоритмы семейства Бойера-Мура не расширяются до приблизительного поиска, поиска любой строки из нескольких.
  • На больших алфавитах (например, Юникод) может занимать много памяти. В таких случаях либо обходятся хэш-таблицами, либо дробят алфавит, рассматривая, например, 4-байтовый символ как пару двухбайтовых.
  • На искусственно подобранных неудачных текстах скорость алгоритма Бойера-Мура серьёзно снижается.

Источники информации