Турбо-алгоритм Бойера-Мура — различия между версиями
Zemskovk (обсуждение | вклад) (→Асимптотика) |
м (rollbackEdits.php mass rollback) |
||
(не показано 49 промежуточных версий 6 участников) | |||
Строка 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> | + | ===Определение турбо-сдвига=== |
+ | Пусть <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]] | |
− | [[Файл:Tbm2.png| | + | Нельзя совместить символы <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'''[] | ||
− | |||
− | |||
'''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) | ||
− | + | answer.add(i) | |
− | shift = | + | shift = bmGs[0] |
u = m - shift | u = m - shift | ||
'''else''' | '''else''' | ||
'''int''' v = m - 1 - j | '''int''' v = m - 1 - j | ||
− | '''int''' | + | '''int''' turboShift = u - v |
− | '''int''' | + | '''int''' bCShift = bmBc[y[i + j]] - m + j + 1 |
− | shift = max( | + | shift = max(turboShift, bCShift, bmGs[j + 1]) |
− | '''if''' (shift == | + | '''if''' (shift == bmGs[j + 1]) |
u = min((m - shift), v) | u = min((m - shift), v) | ||
'''else''' | '''else''' | ||
− | '''if''' ( | + | '''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> {{---}} размер алфавита. |
− | + | |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> {{---}} длина строки, в которой выполняется поиск. | |
− | + | }} | |
− | |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>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> имеет тип (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>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> \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> сравнений символов. | ||
==См. также== | ==См. также== | ||
Строка 92: | Строка 141: | ||
* [[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]] | * [[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]] | ||
* [[Алгоритм Апостолико-Крочемора|Алгоритм Апостолико-Крочемора]] | * [[Алгоритм Апостолико-Крочемора|Алгоритм Апостолико-Крочемора]] | ||
+ | |||
+ | ==Примечания== | ||
+ | |||
+ | <references /> | ||
+ | |||
==Источники информации== | ==Источники информации== | ||
* [[wikipedia:ru:Алгоритм_Бойера_—_Мура|Википедия {{---}} Алгоритм Бойера-Мура]] | * [[wikipedia:ru:Алгоритм_Бойера_—_Мура|Википедия {{---}} Алгоритм Бойера-Мура]] |
Текущая версия на 19:21, 4 сентября 2022
Турбо-алгоритм Бойера-Мура (англ. Turbo Boyer-Moore) является улучшением алгоритма Бойера-Мура. Турбо-алгоритм, разработанный группой учёных во главе с М.Крочемором, предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае. Помимо эвристики стоп-символа и эвристики совпавшего суффикса, применяется третья эвристика — эвристика турбосдвига.
Алгоритм
Турбо-алгоритм Бойера-Мура не нуждается в дополнительном препроцессинге и требует только постоянную дополнительную память относительно оригинального алгоритма Бойера-Мура. Он состоит в запоминании сегмента текста, который соответствует суффиксу шаблона, совпавшему во время предыдущего шага алгоритма (и только тогда, когда сдвиг хорошего суффикса был выполнен). Эта методика представляет два преимущества:
- Можно перепрыгнуть через этот сегмент.
- Она может позволить выполнение «турбо-сдвига».
Турбо-сдвиг может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.
Определение турбо-сдвига
Пусть — запомненный сегмент, а — cуффикс, совпавший во время текущей попытки, такой что — суффикс . Тогда — суффикс , два символа и встречаются на расстоянии в тексте, и суффикс длины имеет период длины , а значит не может перекрыть оба появления символов и в тексте. Наименьший возможный сдвиг имеет длину (его мы и называем турбо-сдвигом).Тем не менее, при
, если длина сдвига плохого символа больше, чем длина сдвига хорошего суффикса и длины турбо-сдвига, то длина фактического сдвига должна быть больше или равна . Действительно, в этом случае два символа и различны, так как мы предположили, что предыдущий сдвиг был сдвигом хороший суффикса. Тогда сдвиг больший, чем турбо-сдвиг, но меньший, чем будет выравнивать и с таким же символом в , в этом случае длина фактического сдвига должна быть по крайней мере равен .Нельзя совместить символы
с одним и тем же символом в .Описание алгоритма
В алгоритм Бойера-Мура дополнительно добавится запоминание длины сегмента текста, который соответствует суффиксу шаблона во время последней попытки, который мы не будем лишний раз рассматривать при сравнении суффиксов двух подстрок, а также запоминании размера сдвига , который мы совершили. Вычислять его будем следующим образом:
Пусть
, и — размер алфавита.- Если текущем шаге у нас подстрока совпала с шаблоном , то ( равен периоду шаблона ), .
- Иначе возможны два случая:
- Если сдвиг хорошего суффикса не меньше турбо-сдвига и сдвига плохого символа, тогда , , где — текущая подстрока.
- В противном случае, , , где — длина турбо-сдвига, — длина сдвига плохого символа. Если турбо-сдвиг меньше сдвига плохого символа, то должен быть не больше , где — сегмент текста, рассматриваемый на прошлом шаге.
Псевдокод
Стадия препроцессинга совпадает со стадией препроцессинга в алгоритме Бойера-Мура, функция вычислений сдвигов плохих символов и функция вычисления хороших суффиксов не меняются, меняется только сам алгоритм, в него добавляется обработка турбо-сдвигов.
//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
Асимптотика
Утверждение: |
Фаза препроцессинга требует времени и памяти, где — размер алфавита. |
Стадия препроцессинга совпадает со стадией препроцессинга в алгоритме Бойера-Мура[1], поэтому рассмотрим только стадию поиска. |
Утверждение: |
Фаза поиска требует времени, где — длина строки, в которой выполняется поиск. |
Утверждение: |
В худшем случае поиск требует сравнений. |
Так как мы запоминаем последний просмотренный сегмент текста, совпадающий с суффиксом шаблона, это позволяет нам пропускать его при нахождении очередного (нам незачем второй раз просматривать сегмент, про который известно, что он совпадает), что уменьшет число сравнений и хождений по строке. Докажем, что число сравнений после такой оптимизаций будет .Разобьём поиск на шаги, каждый из которых будет состоять из двух операций: сканирования и сдвига. На шаге мы будем называть длину суффикса шаблона, что совпадает с текстом, перед суффиксом шаблона будет символ, который не совпадает с соответствующим символом в тексте (в случае когда не соответствует длине шаблона). Мы также будем называть длину сдвига, сделанного на шаге .Рассмотрим три типа шагов в зависимости от характера сканирования и сдвига. Мы говорим, что сдвиг на шаге короткий, если . Тогда эти три типа будут:
Идея доказательства состоит в амортизации стоимости сравнения со сдвигами. Определим стоимость шага следующим образом:
Общее количество сравнений, выполняемых алгоритмом — сумма стоимостей шагов. Мы хотим доказать, что . Во второй длину последнего сдвига заменим . В случае шага типа (1), стоимость соответствует единственному сравнению несовпадающих символов. Другие сравнения, проведенные в течение того же шага, являются стоимостью последующих шагов.Рассмотрим каждый тип шага:
Покажем правильность шагов по индукции: если все шаги |
Пример работы
Пусть нам дана строка
и образец .Построим массив
:Рассмотрим шаги алгоритма:
В итоге, чтобы найти одно вхождение образца длиной
в образце длиной нам понадобилось сравнений символов.