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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Применение турбо-сдвига в случае |v| < |u|)
м (rollbackEdits.php mass rollback)
 
(не показаны 43 промежуточные версии 5 участников)
Строка 1: Строка 1:
'''Турбо-алгоритм Бойера-Мура''' (англ. ''Turbo Boyer-Moore'')  является улучшением [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]]. Турбо-алгоритм, разработанный группой учёных во главе с М.Крочемором, предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае.
+
'''Турбо-алгоритм Бойера-Мура''' (англ. ''Turbo Boyer-Moore'')  является улучшением [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]]. Турбо-алгоритм, разработанный группой учёных во главе с М.Крочемором, предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае. Помимо эвристики стоп-символа и эвристики совпавшего суффикса, применяется третья эвристика — эвристика турбосдвига.
 
==Алгоритм==
 
==Алгоритм==
Турбо-алгоритм Бойера-Мура не нуждается в дополнительном препроцессинге и требует только постоянную дополнительную память относительно оригинального алгоритма Бойера-Мура. Он состоит в запоминании сегмента текста, который соответствует суффиксу шаблона во время последней попытки (и только тогда, когда сдвиг хорошего суффикса был выполнен).
+
Турбо-алгоритм Бойера-Мура не нуждается в дополнительном препроцессинге и требует только постоянную дополнительную память относительно оригинального алгоритма Бойера-Мура. Он состоит в запоминании сегмента текста, который соответствует суффиксу шаблона, совпавшему во время предыдущего шага алгоритма (и только тогда, когда сдвиг хорошего суффикса был выполнен).
 
Эта методика представляет два преимущества:
 
Эта методика представляет два преимущества:
 
# Можно перепрыгнуть через этот сегмент.
 
# Можно перепрыгнуть через этот сегмент.
Строка 7: Строка 7:
 
Турбо-сдвиг может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.
 
Турбо-сдвиг может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.
  
Пусть <tex>u</tex> — запомненный сегмент, а <tex>v</tex> — cуффикс, совпавший во время текущей попытки, такой что <tex>uzv</tex> — суффикс <tex>x</tex>. Тогда <tex>av</tex> — суффикс <tex>x</tex>, два символа <tex>a</tex> и <tex>b</tex> встречаются на расстоянии <tex>p</tex> в тексте, и суффикс <tex>x</tex> длины <tex>|uzv|</tex> имеет период длины <tex>p</tex>, а значит не может перекрыть оба появления символов <tex>a</tex> и <tex>b</tex> в тексте. Наименьший возможный сдвиг имеет длину <tex>|u| - |v|</tex>  (его мы и называем турбо-сдвигом).[[Файл:Tbm1.png|800px|center]]
+
===Определение турбо-сдвига===
 +
Пусть <tex>u</tex> — запомненный сегмент, а <tex>v</tex> — cуффикс, совпавший во время текущей попытки, такой что <tex>uzv</tex> — суффикс <tex>x</tex>. Тогда <tex>av</tex> — суффикс <tex>x</tex>, два символа <tex>a</tex> и <tex>b</tex> встречаются на расстоянии <tex>p</tex> в тексте, и суффикс <tex>x</tex> длины <tex> \mathrm{size}(uzv)</tex> имеет период длины <tex>p</tex>, а значит не может перекрыть оба появления символов <tex>a</tex> и <tex>b</tex> в тексте. Наименьший возможный сдвиг имеет длину <tex> \mathrm{size}(u) - \mathrm{size}(v)</tex>  (его мы и называем турбо-сдвигом).[[Файл:Tbm1.png|600px|center]]
  
===Применение турбо-сдвига в случае |v| < |u|===
+
Тем не менее, при <tex> \mathrm{size}(u) < \mathrm{size}(v)</tex>, если длина сдвига плохого символа больше, чем длина сдвига хорошего суффикса и длины турбо-сдвига, то длина фактического сдвига должна быть больше или равна <tex> \mathrm{size}(u) + 1</tex>. Действительно, в этом случае два символа <tex>c</tex> и <tex>d</tex> различны, так как мы предположили, что предыдущий сдвиг был сдвигом хороший суффикса. Тогда сдвиг больший, чем турбо-сдвиг, но меньший, чем <tex> \mathrm{size}(u) +1</tex> будет выравнивать <tex>c</tex> и <tex>d</tex> с таким же символом в <tex>v</tex>, в этом случае длина фактического сдвига должна быть по крайней мере равен <tex> \mathrm{size}(u) +1</tex>.
При <tex>|v| < |u|</tex>, если длина сдвига плохого символа больше, чем длина сдвига хорошего суффикса и длины турбо-сдвига, то длина фактического сдвига должна быть больше или равна <tex>|u| + 1</tex>. Действительно, в этом случае два символа <tex>c</tex> и <tex>d</tex> различны, так как мы предположили, что предыдущий сдвиг был сдвигом хороший суффикса. Тогда сдвиг больший, чем турбо-сдвиг, но меньший, чем <tex>|u| +1</tex> будет выравнивать <tex>c</tex> и <tex>d</tex> с таким же символом в <tex>v</tex>, в этом случае длина фактического сдвига должна быть по крайней мере равен <tex>|u| +1</tex>.
+
[[Файл:Tbm2.png|600px|center]]
[[Файл:Tbm2.png|800px|center]]
+
Нельзя совместить символы <tex>c \neq d</tex> с одним и тем же символом в <tex>v</tex>.
Нельзя совместить символы <tex>c \neq d</tex> с одним и тем же символом <tex>v</tex>.
+
 
 +
===Описание алгоритма===
 +
В [[Алгоритм Бойера-Мура|алгоритм Бойера-Мура]] дополнительно добавится запоминание длины <tex> \mathrm{size}(u)</tex> сегмента текста, который соответствует суффиксу шаблона во время последней попытки, который мы не будем лишний раз рассматривать при сравнении суффиксов двух подстрок, а также запоминании размера сдвига <tex>\mathrm{shift}</tex>, который мы совершили. Вычислять его будем следующим образом:
 +
 
 +
Пусть <tex>\mathrm{size}(y) = n</tex>, <tex>\mathrm{size}(x)=m</tex> и <tex>\sigma</tex> {{---}} размер алфавита.
 +
 
 +
* Если текущем шаге у нас подстрока совпала с шаблоном <tex>x</tex>, то <tex>\mathrm{shift} = bmGs[0]</tex> (<tex>bmGs[0]</tex> равен периоду шаблона <tex>x</tex>), <tex> \mathrm{size}(u) = m -  \mathrm{shift}</tex>.
 +
* Иначе возможны два случая:
 +
** Если сдвиг хорошего суффикса не меньше турбо-сдвига и сдвига плохого символа, тогда <tex> \mathrm{shift} = bmGs[j+1]</tex>,  <tex>\mathrm{size}(u) = \min(m - \mathrm{shift}, \mathrm{size}(v))</tex>, где <tex>v</tex> {{---}} текущая подстрока.
 +
** В противном случае,  <tex> \mathrm{size}(u) = 0</tex>, <tex>\mathrm{shift} = \max( \mathrm{turboShift}, \mathrm{bCShift})</tex>, где <tex> \mathrm{turboShift}</tex> {{---}} длина турбо-сдвига, <tex> \mathrm{bCShift}</tex> {{---}} длина сдвига плохого символа. Если турбо-сдвиг меньше сдвига плохого символа, то <tex> \mathrm{shift}</tex> должен быть не больше <tex>\mathrm{size}(u_0) + 1</tex>, где <tex>u_0</tex> {{---}} сегмент текста, рассматриваемый на прошлом шаге.
  
 
==Псевдокод==
 
==Псевдокод==
Стадия препроцессинга совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]].
+
Стадия препроцессинга совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]], функция вычислений сдвигов плохих символов и функция вычисления хороших суффиксов не меняются, меняется только сам алгоритм, в него добавляется обработка турбо-сдвигов.
 
+
<font color=green>//x {{---}} шаблон, y {{---}} текст, m {{---}} длина шаблона, n {{---}} длина текста</font>
В сам алгоритм добавляется обработка турбо-сдвигов.
+
  '''function''' TBM(x: '''char'''[m], y: '''char'''[n]): '''List<int>'''  
  '''function''' TBM('''char'''[] x, '''char'''[] y)
 
    '''int''' n = length(y)
 
    '''int''' m = length(x)
 
 
     '''int''' i = 0
 
     '''int''' i = 0
 
     '''int''' u = 0
 
     '''int''' u = 0
 
     '''int''' shift = m
 
     '''int''' shift = m
 +
    <font color=green>//answer {{---}} массив, в который мы сохраняем индексы, начиная с которых, подстроки текста совпадают с шаблоном</font>
 +
    '''List<int>''' answer
 
   
 
   
 
     '''if''' (m == 0)
 
     '''if''' (m == 0)
Строка 39: Строка 48:
 
                 j -= u
 
                 j -= u
 
         '''if''' (j < 0)  
 
         '''if''' (j < 0)  
             print(i)
+
             answer.add(i)
             shift = bm_gs[0]
+
             shift = bmGs[0]
 
             u = m - shift
 
             u = m - shift
 
         '''else'''  
 
         '''else'''  
 
             '''int''' v = m - 1 - j
 
             '''int''' v = m - 1 - j
             '''int''' turbo_shift = u - v
+
             '''int''' turboShift = u - v
             '''int''' bc_shift = bm_bc[y[i + j]] - m + j + 1
+
             '''int''' bCShift = bmBc[y[i + j]] - m + j + 1
             shift = max(turbo_shift, bc_shift, bm_gs[j + 1])
+
             shift = max(turboShift, bCShift, bmGs[j + 1])
             '''if''' (shift == bm_gs[j + 1])
+
             '''if''' (shift == bmGs[j + 1])
 
                 u = min((m - shift), v)
 
                 u = min((m - shift), v)
 
             '''else'''  
 
             '''else'''  
                 '''if''' (turbo_shift < bc_shift)  
+
                 '''if''' (turboShift < bcShift)  
 
                     shift = min(shift, (u + 1))
 
                     shift = min(shift, (u + 1))
 
                 u = 0
 
                 u = 0
 
         i += shift
 
         i += shift
 +
    '''return''' answer
  
 
==Асимптотика==
 
==Асимптотика==
{{Утверждение|statement= 
+
{{Утверждение|statement= Фаза препроцессинга требует <tex>O(m + \sigma)</tex> времени и памяти, где <tex>\sigma</tex> {{---}} размер алфавита.  
* Фаза препроцессинга требует <tex>O(m + \sigma)</tex> времени и памяти, где <tex>\sigma</tex> {{---}} размер алфавита.  
+
|proof= Стадия препроцессинга совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]]<ref>В этом конспекте приведена реализация за <tex>O(n^2)</tex> и неконстантную память, реализацию за <tex>O(n)</tex> и константную память можно посмотреть вот [http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140 тут] </ref>, поэтому рассмотрим только стадию поиска.}}
* Фаза поиска требует <tex>O(n)</tex> времени.
+
{{Утверждение|statement= Фаза поиска требует <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} длина строки, в которой выполняется поиск.
* В худшем случае поиск требует <tex>O(2n)</tex> сравнений.
+
}}
|proof= Стадия препроцессинга совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]], поэтому рассмотрим только стадию поиска.
+
{{Утверждение|statement= В худшем случае поиск требует <tex>O(2n)</tex> сравнений.
 +
|proof= Так как мы запоминаем последний просмотренный сегмент текста, совпадающий с суффиксом шаблона, это позволяет нам пропускать его при нахождении очередного (нам незачем второй раз просматривать сегмент, про который известно, что он совпадает), что уменьшет число сравнений и хождений по строке. Докажем, что число сравнений после такой оптимизаций будет <tex>O(2n)</tex>.
  
Разобьём поиск на стадии. Каждая стадия делится на две операции: сканирование и сдвиг. На этапе <tex>k</tex> мы назовём <tex>suf_k</tex> длину суффикса шаблона, что совпадает с текстом. Этому предшествует символ, который не совпадает с соответствующим символом в тексте (в случае когда <tex>suf_k</tex> не соответствует длине шаблона). Мы также назовём <tex>shift_k</tex> длину сдвига, сделанного на этапе <tex>k</tex>.
+
Разобьём поиск на шаги, каждый из которых будет состоять из двух операций: сканирования и сдвига. На шаге <tex>k</tex> мы будем называть <tex>suf_k</tex> длину суффикса шаблона, что совпадает с текстом, перед суффиксом шаблона будет символ, который не совпадает с соответствующим символом в тексте (в случае когда <tex>suf_k</tex> не соответствует длине шаблона). Мы также будем называть <tex>shift_k</tex> длину сдвига, сделанного на шаге <tex>k</tex>.
  
Рассмотрим три типа стадий в зависимости от характера сканирования и сдвига. Мы говорим, что сдвиг на стадии <tex>k</tex> короткий, если <tex>2shift_k < suf_k + 1</tex>. Тогда три типа сдвигов будут:  
+
Рассмотрим три типа шагов в зависимости от характера сканирования и сдвига. Мы говорим, что сдвиг на шаге <tex>k</tex> короткий, если <tex>2shift_k < suf_k + 1</tex>. Тогда эти три типа будут:  
# Стадия с последующей стадией с прыжком.
+
# Шаг с последующим шагом с прыжком.
# Стадия с длинным сдвигом, без последующей стадии с прыжком.
+
# Шаг с длинным сдвигом, без последующего шага с прыжком.
# Стадия с коротким сдвигом, без последующей стадии с прыжком.
+
# Шаг с коротким сдвигом, без последующего шага с прыжком.
Идея доказательства состоит в амортизации сравнения со сдвигами. Определим стоимость <tex>cost_k</tex> следующим образом:
+
Идея доказательства состоит в [[Амортизационный_анализ|амортизации]] стоимости сравнения со сдвигами. Определим стоимость шага <tex>cost_k</tex> следующим образом:
* Если стадия <tex>k</tex> имеет тип (1), <tex>cost_k = 1</tex>.
+
* Если шаг <tex>k</tex> имеет тип (1), <tex>cost_k = 1</tex>.
* Если стадия <tex>k</tex> имеет тип (2) или (3), стоимость <tex>cost_k = suf_k + 1</tex>.
+
* Если шаг <tex>k</tex> имеет тип (2) или (3), стоимость <tex>cost_k = suf_k + 1</tex>.
В случае стадии типа (1), стоимость соответствует единственному сравнению несовпадающих символов. Другие сравнения, проведенные в течение той же стадии, являются
 
стоимостью последующих этапов. Общее количество сравнений выполняемых алгоритмом это сумма стоимостей. Мы хотим доказать, что <tex> \sum cost < 2 \sum shifts</tex>. Во второй <tex> \sum </tex> длину последнего сдвига заменим <tex>m</tex>. Даже с этим предположением, мы имеем <tex> \sum shifts < |t|</tex>, и если неравенство выполняется, тo <tex> \sum cost < 2|t|</tex>.
 
  
Для стадии типа (1), <tex>cost_k = 1</tex> очевидным образом меньше, чем <tex>2shift_k</tex>, так как <tex>shift_k > 0</tex>. Для стадии типа (2), <tex>cost_k = suf_k + 1 \leqslant 2 shift_k</tex>, по определению длинных сдвигов. Остается рассмотреть стадии типа (3). Так как в этой ситуации мы имеем <tex>shift_k < suf_k</tex>, единственный вариант, что обычный сдвиг применяется на стадии <tex>k</tex>. Тогда мы запоминаем этот момент. На следующей стадии, <tex>k + 1</tex>, мы что-то запомнили, что приводит к возможному турбо-сдвигу. Ситуация на стадии <tex>k + 1</tex>, основная ситуация, когда турбо-сдвиг возможен. Прежде чем продолжить доказательство, мы сначала рассмотрим два случая и установим неравенства (по стоимости стадии <tex>k</tex>), которые используем позже.
+
Общее количество сравнений, выполняемых алгоритмом {{---}} сумма стоимостей шагов. Мы хотим доказать, что <tex> \sum cost < 2 \sum shifts</tex>. Во второй <tex> \sum </tex> длину последнего сдвига заменим <tex>m</tex>.
* Случай (а): <tex>suf_k + shift_k \leqslant |p|</tex>. По определению турбо-сдвига, мы имеем <tex>suf_k - suf_{k+1} < shift_{k + 1}</tex>. Таким образом, <tex>cost_k = sufk + 1 \leqslant suf_{k+1} + shift_{k+1} + 1 \leqslant shift_k + shift_{k + 1}</tex>.
+
В случае шага типа (1), стоимость соответствует единственному сравнению несовпадающих символов. Другие сравнения, проведенные в течение того же шага, являются
* Случай (б): <tex>suf_k + shift_k > |p|</tex>. По определению турбо-сдвига, мы имеем <tex>suf_{k+1} + shift_k + shift_{k + 1} \geqslant m</tex>. Тогда <tex>cost_k \leqslant m \leqslant 2shift_k - 1 + shift_{k + 1}</tex>.
+
стоимостью последующих шагов.
Можно считать, что на стадии <tex>k + 1</tex> случай (б) имеет место, потому что это дает нам верхнюю границу <tex>cost_k</tex> (это верно, если <tex>shift_k \geqslant 2</tex>, случай <tex>shift_k = 1</tex> можно обрабатывать напрямую). Если стадия <tex>k + 1</tex> типа (1), то <tex>cost_{k + 1} = 1</tex>, а затем <tex>cost_k + cost_{k+1} \leqslant 2shift_k + shift_{k+1}</tex>, что даже лучше, чем ожидалось. Если на стадии <tex>k + 1</tex> мы имеем <tex>suf_{k + 1} \leqslant shift_{k + 1}</tex>, то мы получим то, что ожидалось: <tex>cost_k + cost_{k + 1} \leqslant 2shift_k + 2shift_{k + 1}</tex>.
 
Последняя ситуация для рассмотрения, когда на стадии <tex>k + 1</tex> мы имеем <tex>suf_{k + 1} > shift_{k + 1}</tex>. Это означает, что, как уже упоминалось ранее, обычный сдвиг применяется на стадии <tex>k + 1</tex>.
 
  
Таким образом, приведенный выше анализ также применяется на стадии <tex>k + 1</tex>, и, так как только случай (а) может произойти тогда мы получаем <tex>cost_{k + 1} \leqslant shift_{k + 1} + shift_{k + 2}</tex>. Мы, наконец, получаем <tex>cost_k + cost_{k + 1} \leqslant 2shift_k + 2shift_{k + 1} + shift_{k + 2}</tex>.
+
Рассмотрим каждый тип шага:
Последний аргумент, доказывающий первый шаг индукции: если все стадии <tex>k</tex> до <tex>k + j</tex> таковы, что <tex>suf_k > shift_k,... , suf_{k + j} > shift_{k + j}</tex>, то <tex>cost_k + ... + cost_{k + j} \leqslant 2shift_k + ... + 2shift_{k + j} + shift_{k + j + 1}</tex>.  
+
# <tex>cost_k = 1</tex> очевидным образом меньше, чем <tex>2shift_k</tex>, так как <tex>shift_k > 0</tex>.
 +
# <tex>cost_k = suf_k + 1 \leqslant 2 shift_k</tex>, по определению длинных сдвигов.
 +
# Так как в этой ситуации мы имеем <tex>shift_k < suf_k</tex>, единственный возможный вариант, это когда обычный сдвиг применяется на шаге <tex>k</tex>. Тогда мы должны это запомнить. На следующем шаге, <tex>k + 1</tex>, мы что-то запомнили, что приводит к возможному турбо-сдвигу. Ситуация на шаге <tex>k + 1</tex> {{---}} основная ситуация, когда турбо-сдвиг возможен. Прежде чем продолжить доказательство, мы сначала рассмотрим два случая и установим неравенства (по стоимости шага <tex>k</tex>), которые используем позже.
 +
#* Случай (а): <tex>suf_k + shift_k \leqslant |p|</tex>. По определению турбо-сдвига, мы имеем <tex>suf_k - suf_{k+1} < shift_{k + 1}</tex>. Таким образом, <tex>cost_k = sufk + 1 \leqslant suf_{k+1} + shift_{k+1} + 1 \leqslant shift_k + shift_{k + 1}</tex>.
 +
#* Случай (б): <tex>suf_k + shift_k > |p|</tex>. По определению турбо-сдвига, мы имеем <tex>suf_{k+1} + shift_k + shift_{k + 1} \geqslant m</tex>. Тогда <tex>cost_k \leqslant m \leqslant 2shift_k - 1 + shift_{k + 1}</tex>.
 +
: Можно считать, что на шаге <tex>k + 1</tex> случай (б) имеет место, потому что это дает нам верхнюю границу <tex>cost_k</tex> (это верно, если <tex>shift_k \geqslant 2</tex>, случай <tex>shift_k = 1</tex> можно обрабатывать напрямую). Если шаг <tex>k + 1</tex> типа (1), то <tex>cost_{k + 1} = 1</tex>, а затем <tex>cost_k + cost_{k+1} \leqslant 2shift_k + shift_{k+1}</tex>, что даже лучше, чем ожидалось. Если на шаге <tex>k + 1</tex> мы имеем <tex>suf_{k + 1} \leqslant shift_{k + 1}</tex>, то мы получим то, что ожидалось: <tex>cost_k + cost_{k + 1} \leqslant 2shift_k + 2shift_{k + 1}</tex>. Последняя ситуация для рассмотрения, когда на шаге <tex>k + 1</tex> мы имеем <tex>suf_{k + 1} > shift_{k + 1}</tex>. Это означает, что, как уже упоминалось ранее, обычный сдвиг применяется на шаге <tex>k + 1</tex>. Таким образом, приведенный выше анализ также применяется на шаге <tex>k + 1</tex>, и, так как только случай (а) может произойти, мы получаем <tex>cost_{k + 1} \leqslant shift_{k + 1} + shift_{k + 2}</tex>. Мы, наконец, получаем <tex>cost_k + cost_{k + 1} \leqslant 2shift_k + 2shift_{k + 1} + shift_{k + 2}</tex>.
  
 +
Покажем правильность шагов по индукции: если все шаги <tex>k</tex> до <tex>k + j</tex> таковы, что <tex>suf_k > shift_k,... , suf_{k + j} > shift_{k + j}</tex>, то <tex>cost_k + ... + cost_{k + j} \leqslant 2shift_k + ... + 2shift_{k + j} + shift_{k + j + 1}</tex>. <br />
 
Пусть <tex>k'</tex> первый этап после этапа <tex>k</tex> такой, что <tex>suf_{k'} \leqslant shift_{k'}</tex>. Целое число <tex>k'</tex> существует потому, что иначе получим бесконечную последовательность сдвигов с уменьшающейся длиной. После этого мы получим <tex>cost_k + ... + cost_{k'} \leqslant 2shift_k + ... + 2shift_{k'}</tex>.
 
Пусть <tex>k'</tex> первый этап после этапа <tex>k</tex> такой, что <tex>suf_{k'} \leqslant shift_{k'}</tex>. Целое число <tex>k'</tex> существует потому, что иначе получим бесконечную последовательность сдвигов с уменьшающейся длиной. После этого мы получим <tex>cost_k + ... + cost_{k'} \leqslant 2shift_k + ... + 2shift_{k'}</tex>.
  
Строка 88: Строка 101:
  
 
==Пример работы==
 
==Пример работы==
Пусть нам дана строка <tex>y = GCATCGCAGAGAGTATACAGTACG</tex> и образец <tex>x=GCAGAGAG</tex>
+
Пусть нам дана строка <tex>y = GCATCGCAGAGAGTATACAGTACG</tex> и образец <tex>x=GCAGAGAG</tex>.
  
 
Построим массив <tex>bmBc</tex>:
 
Построим массив <tex>bmBc</tex>:
Строка 101: Строка 114:
 
|[[Файл:Raita1.png|550px]]
 
|[[Файл:Raita1.png|550px]]
 
|<tex>(7, 1)</tex>
 
|<tex>(7, 1)</tex>
|Делаем сравнение последних символов, оно неудачно, сдвигаемся на <tex>bmGs[7] = bmBc[A]-8+8 = 1</tex>.
+
|Сравниваем последние символы, они неравны, поэтому сдвигаемся на <tex>bmGs[7] = bmBc[A]-8+8 = 1</tex>.
 
|-align="center"
 
|-align="center"
 
|[[Файл:Tbme2.PNG|550px]]
 
|[[Файл:Tbme2.PNG|550px]]
Строка 121: Строка 134:
 
|}
 
|}
  
В итоге, чтобы найти одно вхождение образца длиной <tex>m = 8</tex> в образце длиной <tex>n = 24</tex> нам понадобилось <tex>15</tex> сравнений символов
+
В итоге, чтобы найти одно вхождение образца длиной <tex>m = 8</tex> в образце длиной <tex>n = 24</tex> нам понадобилось <tex>15</tex> сравнений символов.
  
 
==См. также==
 
==См. также==
Строка 128: Строка 141:
 
* [[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]
 
* [[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]
 
* [[Алгоритм Апостолико-Крочемора|Алгоритм Апостолико-Крочемора]]
 
* [[Алгоритм Апостолико-Крочемора|Алгоритм Апостолико-Крочемора]]
 +
 +
==Примечания==
 +
 +
<references />
 +
 
==Источники информации==
 
==Источники информации==
 
* [[wikipedia:ru:Алгоритм_Бойера_—_Мура|Википедия {{---}} Алгоритм Бойера-Мура]]
 
* [[wikipedia:ru:Алгоритм_Бойера_—_Мура|Википедия {{---}} Алгоритм Бойера-Мура]]

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

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

Алгоритм

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

  1. Можно перепрыгнуть через этот сегмент.
  2. Она может позволить выполнение «турбо-сдвига».

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

Определение турбо-сдвига

Пусть [math]u[/math] — запомненный сегмент, а [math]v[/math] — cуффикс, совпавший во время текущей попытки, такой что [math]uzv[/math] — суффикс [math]x[/math]. Тогда [math]av[/math] — суффикс [math]x[/math], два символа [math]a[/math] и [math]b[/math] встречаются на расстоянии [math]p[/math] в тексте, и суффикс [math]x[/math] длины [math] \mathrm{size}(uzv)[/math] имеет период длины [math]p[/math], а значит не может перекрыть оба появления символов [math]a[/math] и [math]b[/math] в тексте. Наименьший возможный сдвиг имеет длину [math] \mathrm{size}(u) - \mathrm{size}(v)[/math] (его мы и называем турбо-сдвигом).
Tbm1.png

Тем не менее, при [math] \mathrm{size}(u) \lt \mathrm{size}(v)[/math], если длина сдвига плохого символа больше, чем длина сдвига хорошего суффикса и длины турбо-сдвига, то длина фактического сдвига должна быть больше или равна [math] \mathrm{size}(u) + 1[/math]. Действительно, в этом случае два символа [math]c[/math] и [math]d[/math] различны, так как мы предположили, что предыдущий сдвиг был сдвигом хороший суффикса. Тогда сдвиг больший, чем турбо-сдвиг, но меньший, чем [math] \mathrm{size}(u) +1[/math] будет выравнивать [math]c[/math] и [math]d[/math] с таким же символом в [math]v[/math], в этом случае длина фактического сдвига должна быть по крайней мере равен [math] \mathrm{size}(u) +1[/math].

Tbm2.png

Нельзя совместить символы [math]c \neq d[/math] с одним и тем же символом в [math]v[/math].

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

В алгоритм Бойера-Мура дополнительно добавится запоминание длины [math] \mathrm{size}(u)[/math] сегмента текста, который соответствует суффиксу шаблона во время последней попытки, который мы не будем лишний раз рассматривать при сравнении суффиксов двух подстрок, а также запоминании размера сдвига [math]\mathrm{shift}[/math], который мы совершили. Вычислять его будем следующим образом:

Пусть [math]\mathrm{size}(y) = n[/math], [math]\mathrm{size}(x)=m[/math] и [math]\sigma[/math] — размер алфавита.

  • Если текущем шаге у нас подстрока совпала с шаблоном [math]x[/math], то [math]\mathrm{shift} = bmGs[0][/math] ([math]bmGs[0][/math] равен периоду шаблона [math]x[/math]), [math] \mathrm{size}(u) = m - \mathrm{shift}[/math].
  • Иначе возможны два случая:
    • Если сдвиг хорошего суффикса не меньше турбо-сдвига и сдвига плохого символа, тогда [math] \mathrm{shift} = bmGs[j+1][/math], [math]\mathrm{size}(u) = \min(m - \mathrm{shift}, \mathrm{size}(v))[/math], где [math]v[/math] — текущая подстрока.
    • В противном случае, [math] \mathrm{size}(u) = 0[/math], [math]\mathrm{shift} = \max( \mathrm{turboShift}, \mathrm{bCShift})[/math], где [math] \mathrm{turboShift}[/math] — длина турбо-сдвига, [math] \mathrm{bCShift}[/math] — длина сдвига плохого символа. Если турбо-сдвиг меньше сдвига плохого символа, то [math] \mathrm{shift}[/math] должен быть не больше [math]\mathrm{size}(u_0) + 1[/math], где [math]u_0[/math] — сегмент текста, рассматриваемый на прошлом шаге.

Псевдокод

Стадия препроцессинга совпадает со стадией препроцессинга в алгоритме Бойера-Мура, функция вычислений сдвигов плохих символов и функция вычисления хороших суффиксов не меняются, меняется только сам алгоритм, в него добавляется обработка турбо-сдвигов.

//x — шаблон, y — текст, m — длина шаблона, n — длина текста
function TBM(x: char[m], y: char[n]): List<int>   
   int i = 0
   int u = 0
   int shift = m
   //answer — массив, в который мы сохраняем индексы, начиная с которых, подстроки текста совпадают с шаблоном
   List<int> answer

   if (m == 0)
        return
        
   //Предварительные вычисления
   int bmBc[] = preBmBc(x, m)
   int bmGs[] = preBmGs(x, m)

   while (i <= n - m) 
       int j = m - 1
       while (j >= 0 and x[j] == y[i + j])
           --j
           if (u != 0 and j == m - 1 - shift) 
               j -= u
       if (j < 0) 
           answer.add(i)
           shift = bmGs[0]
           u = m - shift
       else 
           int v = m - 1 - j
           int turboShift = u - v
           int bCShift = bmBc[y[i + j]] - m + j + 1
           shift = max(turboShift, bCShift, bmGs[j + 1])
           if (shift == bmGs[j + 1])
               u = min((m - shift), v)
           else 
               if (turboShift < bcShift) 
                   shift = min(shift, (u + 1))
               u = 0
       i += shift
   return answer

Асимптотика

Утверждение:
Фаза препроцессинга требует [math]O(m + \sigma)[/math] времени и памяти, где [math]\sigma[/math] — размер алфавита.
[math]\triangleright[/math]
Стадия препроцессинга совпадает со стадией препроцессинга в алгоритме Бойера-Мура[1], поэтому рассмотрим только стадию поиска.
[math]\triangleleft[/math]
Утверждение:
Фаза поиска требует [math]O(n)[/math] времени, где [math]n[/math] — длина строки, в которой выполняется поиск.
Утверждение:
В худшем случае поиск требует [math]O(2n)[/math] сравнений.
[math]\triangleright[/math]

Так как мы запоминаем последний просмотренный сегмент текста, совпадающий с суффиксом шаблона, это позволяет нам пропускать его при нахождении очередного (нам незачем второй раз просматривать сегмент, про который известно, что он совпадает), что уменьшет число сравнений и хождений по строке. Докажем, что число сравнений после такой оптимизаций будет [math]O(2n)[/math].

Разобьём поиск на шаги, каждый из которых будет состоять из двух операций: сканирования и сдвига. На шаге [math]k[/math] мы будем называть [math]suf_k[/math] длину суффикса шаблона, что совпадает с текстом, перед суффиксом шаблона будет символ, который не совпадает с соответствующим символом в тексте (в случае когда [math]suf_k[/math] не соответствует длине шаблона). Мы также будем называть [math]shift_k[/math] длину сдвига, сделанного на шаге [math]k[/math].

Рассмотрим три типа шагов в зависимости от характера сканирования и сдвига. Мы говорим, что сдвиг на шаге [math]k[/math] короткий, если [math]2shift_k \lt suf_k + 1[/math]. Тогда эти три типа будут:

  1. Шаг с последующим шагом с прыжком.
  2. Шаг с длинным сдвигом, без последующего шага с прыжком.
  3. Шаг с коротким сдвигом, без последующего шага с прыжком.

Идея доказательства состоит в амортизации стоимости сравнения со сдвигами. Определим стоимость шага [math]cost_k[/math] следующим образом:

  • Если шаг [math]k[/math] имеет тип (1), [math]cost_k = 1[/math].
  • Если шаг [math]k[/math] имеет тип (2) или (3), стоимость [math]cost_k = suf_k + 1[/math].

Общее количество сравнений, выполняемых алгоритмом — сумма стоимостей шагов. Мы хотим доказать, что [math] \sum cost \lt 2 \sum shifts[/math]. Во второй [math] \sum [/math] длину последнего сдвига заменим [math]m[/math]. В случае шага типа (1), стоимость соответствует единственному сравнению несовпадающих символов. Другие сравнения, проведенные в течение того же шага, являются стоимостью последующих шагов.

Рассмотрим каждый тип шага:

  1. [math]cost_k = 1[/math] очевидным образом меньше, чем [math]2shift_k[/math], так как [math]shift_k \gt 0[/math].
  2. [math]cost_k = suf_k + 1 \leqslant 2 shift_k[/math], по определению длинных сдвигов.
  3. Так как в этой ситуации мы имеем [math]shift_k \lt suf_k[/math], единственный возможный вариант, это когда обычный сдвиг применяется на шаге [math]k[/math]. Тогда мы должны это запомнить. На следующем шаге, [math]k + 1[/math], мы что-то запомнили, что приводит к возможному турбо-сдвигу. Ситуация на шаге [math]k + 1[/math] — основная ситуация, когда турбо-сдвиг возможен. Прежде чем продолжить доказательство, мы сначала рассмотрим два случая и установим неравенства (по стоимости шага [math]k[/math]), которые используем позже.
    • Случай (а): [math]suf_k + shift_k \leqslant |p|[/math]. По определению турбо-сдвига, мы имеем [math]suf_k - suf_{k+1} \lt shift_{k + 1}[/math]. Таким образом, [math]cost_k = sufk + 1 \leqslant suf_{k+1} + shift_{k+1} + 1 \leqslant shift_k + shift_{k + 1}[/math].
    • Случай (б): [math]suf_k + shift_k \gt |p|[/math]. По определению турбо-сдвига, мы имеем [math]suf_{k+1} + shift_k + shift_{k + 1} \geqslant m[/math]. Тогда [math]cost_k \leqslant m \leqslant 2shift_k - 1 + shift_{k + 1}[/math].
Можно считать, что на шаге [math]k + 1[/math] случай (б) имеет место, потому что это дает нам верхнюю границу [math]cost_k[/math] (это верно, если [math]shift_k \geqslant 2[/math], случай [math]shift_k = 1[/math] можно обрабатывать напрямую). Если шаг [math]k + 1[/math] типа (1), то [math]cost_{k + 1} = 1[/math], а затем [math]cost_k + cost_{k+1} \leqslant 2shift_k + shift_{k+1}[/math], что даже лучше, чем ожидалось. Если на шаге [math]k + 1[/math] мы имеем [math]suf_{k + 1} \leqslant shift_{k + 1}[/math], то мы получим то, что ожидалось: [math]cost_k + cost_{k + 1} \leqslant 2shift_k + 2shift_{k + 1}[/math]. Последняя ситуация для рассмотрения, когда на шаге [math]k + 1[/math] мы имеем [math]suf_{k + 1} \gt shift_{k + 1}[/math]. Это означает, что, как уже упоминалось ранее, обычный сдвиг применяется на шаге [math]k + 1[/math]. Таким образом, приведенный выше анализ также применяется на шаге [math]k + 1[/math], и, так как только случай (а) может произойти, мы получаем [math]cost_{k + 1} \leqslant shift_{k + 1} + shift_{k + 2}[/math]. Мы, наконец, получаем [math]cost_k + cost_{k + 1} \leqslant 2shift_k + 2shift_{k + 1} + shift_{k + 2}[/math].

Покажем правильность шагов по индукции: если все шаги [math]k[/math] до [math]k + j[/math] таковы, что [math]suf_k \gt shift_k,... , suf_{k + j} \gt shift_{k + j}[/math], то [math]cost_k + ... + cost_{k + j} \leqslant 2shift_k + ... + 2shift_{k + j} + shift_{k + j + 1}[/math].
Пусть [math]k'[/math] первый этап после этапа [math]k[/math] такой, что [math]suf_{k'} \leqslant shift_{k'}[/math]. Целое число [math]k'[/math] существует потому, что иначе получим бесконечную последовательность сдвигов с уменьшающейся длиной. После этого мы получим [math]cost_k + ... + cost_{k'} \leqslant 2shift_k + ... + 2shift_{k'}[/math].

Это показывает нам, что [math] \sum cost_k \leqslant 2 \sum shift_k[/math], что и требовалось.
[math]\triangleleft[/math]

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

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

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

RaitaPre.png

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

Изображение [math](j, bmBc[y[j]])[/math] Описание
Raita1.png [math](7, 1)[/math] Сравниваем последние символы, они неравны, поэтому сдвигаемся на [math]bmGs[7] = bmBc[A]-8+8 = 1[/math].
Tbme2.PNG [math](8, 2)[/math] Последние два символа совпали, сдвигаемся на [math]bmGs[5] = bmBc[C] - 8 + 6 = 4[/math].
Tbme3.PNG [math](12, 2)[/math] Все символы совпали, Продолжим работу (для примера, в обычном варианте на этом этапе мы можем выйти, если требуется найти только одно вхождение) и сдвинемся на [math]bmGs[0] = 7[/math].
Tbme4.PNG [math](19, 2)[/math] Последние два символа совпали, сдвигаемся на [math]bmGs[5] = bmBc[C] - 8 + 6 = 4[/math].
Tbme5.PNG [math](23, 1)[/math] Последние символы совпали, сравниваем предпоследние, сдвигаемся. Строка закончилась, выходим.

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

См. также

Примечания

  1. В этом конспекте приведена реализация за [math]O(n^2)[/math] и неконстантную память, реализацию за [math]O(n)[/math] и константную память можно посмотреть вот тут

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