Изменения

'''Алгоритм Турбо-алгоритм Бойера-Мура за линейное время''' (Турбоангл. ''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]] Тем не менее, при <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>.[[Файл:Tbm2.png|600px|center]]Нельзя совместить символы <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>''' '''int''' i =Асимптотики0 '''int''' u =0 '''int''' shift =m <font color=green>//answer {{---}} массив, в который мы сохраняем индексы, начиная с которых, подстроки текста совпадают с шаблоном</font> '''List<int>''' answer '''if''' (m == 0) '''return''' <font color=green>//Предварительные вычисления</font> '''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 ==Асимптотика=={{Утверждение|statement= Фаза препроцессинга требует <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>, поэтому рассмотрим только стадию поиска.}}{{Утверждение|statement= Фаза поиска требует <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} длина строки, в которой выполняется поиск.}}{{Утверждение|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>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>. Общее количество сравнений, выполняемых алгоритмом {{---}} сумма стоимостей шагов. Мы хотим доказать, что <tex> \sum cost < 2 \sum shifts</tex>. Во второй <tex> \sum </tex> длину последнего сдвига заменим <tex>m</tex>.В случае шага типа (1), стоимость соответствует единственному сравнению несовпадающих символов. Другие сравнения, проведенные в течение того же шага, являютсястоимостью последующих шагов. Рассмотрим каждый тип шага:# <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> \sum cost_k \leqslant 2 \sum shift_k</tex>, что и требовалось.}} ==Пример работы==Пусть нам дана строка <tex>y = GCATCGCAGAGAGTATACAGTACG</tex> и образец <tex>x=GCAGAGAG</tex>. Построим массив <tex>bmBc</tex>: [[Файл:RaitaPre.png|250px]] Рассмотрим шаги алгоритма: {| class = "wikitable"! Изображение !! <tex>(j, bmBc[y[j]])</tex> !! Описание|-align="center"|[[Файл:Raita1.png|550px]]|<tex>(7, 1)</tex>|Сравниваем последние символы, они неравны, поэтому сдвигаемся на <tex>bmGs[7] = bmBc[A]-8+8 = 1</tex>.|-align="center"|[[Файл:Tbme2.PNG|550px]]|<tex>(8, 2)</tex>|Последние два символа совпали, сдвигаемся на <tex>bmGs[5] = bmBc[C] - 8 + 6 = 4</tex>.|-align="center"|[[Файл:Tbme3.PNG|550px]]|<tex>(12, 2)</tex>|Все символы совпали, Продолжим работу (для примера, в обычном варианте на этом этапе мы можем выйти, если требуется найти только одно вхождение) и сдвинемся на <tex>bmGs[0] = 7</tex>. |-align="center"|[[Файл:Tbme4.PNG|550px]]|<tex>(19, 2)</tex>|Последние два символа совпали, сдвигаемся на <tex>bmGs[5] = bmBc[C] - 8 + 6 = 4</tex>.|-align="center"|[[Файл:Tbme5.PNG|550px]]|<tex>(23, 1)</tex>|Последние символы совпали, сравниваем предпоследние, сдвигаемся. Строка закончилась, выходим. |-|} В итоге, чтобы найти одно вхождение образца длиной <tex>m = 8</tex> в образце длиной <tex>n = 24</tex> нам понадобилось <tex>15</tex> сравнений символов. 

*[[Алгоритм Апостолико-Крочемора|Алгоритм Апостолико-Крочемора]] ==СсылкиПримечания== <references /> ==Источники информации==