Изменения
Отмена правки 65481, сделанной 185.220.101.4 (обсуждение)
'''Турбо-алгоритм Бойера-Мура''' (англ. ''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|800px600px|center]]
===Описание алгоритма===
В [[Алгоритм Бойера-Мура|алгоритм Бойера-Мура]] дополнительно добавится запоминание длины <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) : '''List<int>''' n = length(y) '''int''' m = length(x)
'''int''' i = 0
'''int''' u = 0
'''int''' shift = m
<font color=green>//answer {{---}} массив, в который мы сохраняем индексы, начиная с которых, подстроки текста совпадают с шаблоном</font>
'''List<int>''' answer
'''if''' (m == 0)
j -= u
'''if''' (j < 0)
u = m - shift
'''else'''
'''int''' v = m - 1 - j
'''int''' turbo_shift turboShift = u - v '''int''' bc_shift bCShift = bm_bcbmBc[y[i + j]] - m + j + 1 shift = max(turbo_shiftturboShift, bc_shiftbCShift, bm_gsbmGs[j + 1]) '''if''' (shift == bm_gsbmGs[j + 1])
u = min((m - shift), v)
'''else'''
'''if''' (turbo_shift turboShift < bc_shiftbcShift)
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>.В случае стадии типа (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>.
Покажем правильность шагов по индукции: если все шаги <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>y = GCATCGCAGAGAGTATACAGTACG</tex> и образец <tex>x=GCAGAGAG</tex>.
Построим массив <tex>bmBc</tex>:
|[[Файл:Raita1.png|550px]]
|<tex>(7, 1)</tex>
|Делаем сравнение последних символовСравниваем последние символы, оно неудачноони неравны, поэтому сдвигаемся на <tex>bmGs[7] = bmBc[A]-8+8 = 1</tex>.
|-align="center"
|[[Файл:Tbme2.PNG|550px]]
|}
В итоге, чтобы найти одно вхождение образца длиной <tex>m = 8</tex> в образце длиной <tex>n = 24</tex> нам понадобилось <tex>15</tex> сравнений символов.
==См. также==
* [[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]
* [[Алгоритм Апостолико-Крочемора|Алгоритм Апостолико-Крочемора]]
==Примечания==
<references />
==Источники информации==
* [[wikipedia:ru:Алгоритм_Бойера_—_Мура|Википедия {{---}} Алгоритм Бойера-Мура]]