Викиконспекты - Вклад участника [ru]

Турбо-алгоритм Бойера-Мура

2016-04-18T16:47:02Z

188.162.65.23: /* Псевдокод */

'''Турбо-алгоритм Бойера-Мура''' (англ. ''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>|uzv|</tex> имеет период длины <tex>p</tex>, а значит не может перекрыть оба появления символов <tex>a</tex> и <tex>b</tex> в тексте. Наименьший возможный сдвиг имеет длину <tex>|u| - |v|</tex> (его мы и называем турбо-сдвигом).[[Файл:Tbm1.png|800px|center]]

===Применение турбо-сдвига в случае |v| < |u|===
При <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|800px|center]]
Нельзя совместить символы <tex>c \neq d</tex> с одним и тем же символом <tex>v</tex>.

==Псевдокод==
Стадия препроцессинга совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]].

В сам алгоритм добавляется обработка турбо-сдвигов.
'''function''' TBM('''char'''[] x, '''char'''[] y)
'''int''' n = length(y)
'''int''' m = length(x)
'''int''' i = 0
'''int''' u = 0
'''int''' shift = m

'''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)
print(i)
shift = bm_gs[0]
u = m - shift
'''else'''
'''int''' v = m - 1 - j
'''int''' turbo_shift = u - v
'''int''' bc_shift = bm_bc[y[i + j]] - m + j + 1
shift = max(turbo_shift, bc_shift, bm_gs[j + 1])
'''if''' (shift == bm_gs[j + 1])
u = min((m - shift), v)
'''else'''
'''if''' (turbo_shift < bc_shift)
shift = min(shift, (u + 1))
u = 0
i += shift

==Асимптотика==
{{Утверждение|statement=
* Фаза препроцессинга требует <tex>O(m + \sigma)</tex> времени и памяти, где <tex>\sigma</tex> {{---}} размер алфавита.
* Фаза поиска требует <tex>O(n)</tex> времени.
* В худшем случае поиск требует <tex>O(2n)</tex> сравнений.
|proof= Стадия препроцессинга совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]], поэтому рассмотрим только стадию поиска.

Разобьём поиск на стадии. Каждая стадия делится на две операции: сканирование и сдвиг. На этапе <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 \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>.

Пусть <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>, что и требовалось.}}

==См. также==
* [[Алгоритм Бойера-Мура]]
* [[Алгоритм Райта]]
* [[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]
* [[Алгоритм Апостолико-Крочемора|Алгоритм Апостолико-Крочемора]]
==Источники информации==
* [[wikipedia:ru:Алгоритм_Бойера_—_Мура|Википедия {{---}} Алгоритм Бойера-Мура]]
* [[wikipedia:Boyer–Moore_string_search_algorithm|Wikipedia {{---}} Boyer–Moore string search algorithm]]
* [http://www-igm.univ-mlv.fr/~lecroq/string/node15.html#SECTION00150 Turbo Boyer-Moore algorithm]
* [http://algolist.manual.ru/search/esearch/turbo_bm.php Турбо Боуер-Мур]
* [http://igm.univ-mlv.fr/~mac/Articles-PDF/CCGJLPR94algo-speedup.pdf Speeding Up Two String-Matching Algorithms]

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Поиск подстроки в строке]]
[[Категория:Точный поиск]]

Бинарное отношение

2014-07-10T21:04:25Z

188.162.65.23: Отмена правки 39364 участника Mtcomscxstart (обсуждение) Какой ещё счётчик Кнута?

{{Определение
|definition =
'''Бинарным отношением''' (англ. ''binary relation'') <tex>R</tex> из множества <tex>A</tex> в множество <tex>B</tex> называется подмножество прямого произведения <tex>A</tex> и <tex>B</tex> и обозначается:
<tex>R \subset A \times B</tex>.
}}

Часто используют инфиксную форму записи:
<tex>aRb, \ \langle x, y \rangle\in R</tex>.

Если отношение определено на множестве <tex>A</tex>, то возможно следующее определение:
{{Определение
|definition =
'''Бинарным''' (или '''двуместным''') '''отношением''' <tex>R</tex> на множестве <tex>A</tex> называется множество упорядоченных пар элементов этого множества.
}}
Примерами множеств с введёнными на них бинарными отношениями являются [[Ориентированный граф|графы]] и частично упорядоченные множества.

== Свойства отношений ==
Для <tex>R \subset A^2</tex> определены свойства:
* [[Рефлексивное отношение|Рефлексивность]] (англ. ''reflexivity''): <tex>\mathcal {8} x \in A \ (xRx)</tex>;
* [[Рефлексивное отношение|Антирефлексивность]] (англ. ''irreflexivity''): <tex>\mathcal {8} x \in A \ (\neg xRx)</tex>;
* [[Симметричное отношение|Симметричность]] (англ. ''symmetry''): <tex>\mathcal {8} x,y \in A \ (xRy \Rightarrow yRx)</tex>;
* [[Антисимметричное отношение|Антисимметричность]] (англ. ''antisymmetry''): <tex>\mathcal {8} x,y \in A \ (xRy \land yRx \Rightarrow x = y)</tex>;
* [[Транзитивное отношение|Транзитивность]] (англ. ''transitivity''): <tex>\mathcal {8} x,y,z \in A \ (xRy \land yRz \Rightarrow xRz)</tex>;
* Связность: <tex>\mathcal {8} x,y \in A \ (xRy \lor yRx)</tex>;
* [[Антисимметричное отношение|Ассимметричность]] (англ. ''assymetric relation''): <tex>\mathcal {8} x,y \in A \ (xRy \Rightarrow \neg (yRx))</tex>.

== Виды отношений ==
Выделяются следующие виды отношений:
* квазипорядка — рефлексивное транзитивное;
* [[Отношение эквивалентности|эквивалентности]] — рефлексивное симметричное транзитивное;
* [[Отношение порядка|частичного порядка]] — рефлексивное антисимметричное транзитивное;
* [[Отношение порядка|строгого порядка]] — антирефлексивное антисимметричное транзитивное;
* [[Отношение порядка|линейного порядка]] — полное антисимметричное транзитивное;
* [[Отношение порядка|доминирования]] — антирефлексивное антисимметричное.

== Примеры отношений ==
*Примеры [[Рефлексивное отношение|'''рефлексивных отношений''']]: равенство, одновременность, сходство.
*Примеры [[Рефлексивное отношение|'''нерефлексивных отношений''']]: «заботиться о», «развлекать», «нервировать».
*Примеры [[Транзитивное отношение|'''транзитивных отношений''']]: «больше», «меньше», «равно», «подобно», «выше», «севернее».
*Примеры [[Симметричное отношение|'''симметричных отношений''']]: равенство (=), неравенство, отношение эквивалентности, подобия, одновременности, некоторые отношения родства (например, отношение братства).
*Примеры [[Антисимметричное отношение|'''антисимметричных отношений''']]: больше, меньше, больше или равно.
*Примеры '''асимметричных отношений''': отношение «больше» (>) и «меньше» (<).

== См. также ==
* [[Композиция_отношений|Композиция отношений]]

== Ссылки ==
* [http://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B5_%D0%BE%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5 wikipedia.org — Бинарное отношение]
* [http://ru.math.wikia.com/wiki/%D0%91%D0%B8%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B5_%D0%BE%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5 wikia.com - Бинарное отношение]
* http://www.studfiles.ru/dir/cat14/subj266/file9092/view94463/page2.html

[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Отношения ]]