Изменения

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

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

Пусть <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| Тем не менее, при < |tex> \mathrm{size}(u|===При ) <tex>|\mathrm{size}(v| < |u|)</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>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] x, y: '''char'''[n] y, '''int''' n, '''int''' m): '''List<int>'''

<font color=green>//answer {{---}} массив, в который мы сохраняем индексы, начиная с которых, подстроки текста совпадают с шаблоном</font> '''List<int>''' answer;

{{Утверждение|statement= Фаза препроцессинга требует <tex>O(m + \sigma)</tex> времени и памяти, где <tex>\sigma</tex> {{---}} размер алфавита, <tex>m</tex> {{---}} длина шаблона. |proof= Стадия препроцессинга совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]]<ref>В этом конспекте приведена реализация за <tex>O(n^2)</tex> и неконстантную память, реализацию за <tex>O(n)</tex> и константную память можно посмотреть вот [http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140 тут] </ref>, поэтому рассмотрим только стадию поиска.}}

|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>2shift_k < suf_k + 1</tex>. Тогда эти три типа сдвигов будут: # Стадия Шаг с последующей стадией последующим шагом с прыжком.# Стадия Шаг с длинным сдвигом, без последующей стадии последующего шага с прыжком.# Стадия Шаг с коротким сдвигом, без последующей стадии последующего шага с прыжком.Идея доказательства состоит в [[Амортизационный_анализ|амортизации ]] стоимости сравнения со сдвигами. Определим стоимость шага <tex>cost_k</tex> следующим образом:* Если стадия шаг <tex>k</tex> имеет тип (1), <tex>cost_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>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 sum cost < 2 \leqslant shift_k + shift_{k + 1}sum shifts</tex>.* Случай (б): Во второй <tex>suf_k + shift_k > |p|\sum </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>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>cost_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 + 21}</tex>. Мы#* Случай (б): <tex>suf_k + shift_k > |p|</tex>. По определению турбо-сдвига, наконец, получаем мы имеем <tex>cost_k + cost_suf_{k + 1} \leqslant 2shift_k + 2shift_shift_k + shift_{k + 1} \geqslant m</tex>. Тогда <tex>cost_k \leqslant m \leqslant 2shift_k - 1 + shift_{k + 21}</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 + j1} = 1</tex> таковы, что а затем <tex>suf_k cost_k + cost_{k+1} \leqslant 2shift_k + shift_{k+1}</tex> shift_k,что даже лучше, чем ожидалось... , Если на шаге <tex>k + 1</tex> мы имеем <tex>suf_{k + j1} > \leqslant shift_{k + j1}</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 + j1} \leqslant 2shift_k shift_{k + 1} + shift_{k + 2}</tex>... Мы, наконец, получаем <tex>cost_k + cost_{k + 1} \leqslant 2shift_k + 2shift_{k + j1} + shift_{k + j + 12}</tex>.

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

|Делаем сравнение последних символовСравниваем последние символы, оно неудачноони неравны, поэтому сдвигаемся на <tex>bmGs[7] = bmBc[A]-8+8 = 1</tex>.

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