%\def\proof{{\it Доказательство. \/}}

\Section{Алгоритм Бойера-Мура, Хеширование}{19 апреля}{Горохов Никита}

\Subsection{Алгоритм Бойера-Мура}

\THEE{Алгоритм Бойера-Мура-Хорспула}

\vspace*{0.5em}

Пусть дан алфавит $\Sigma$, текст $t$ и шаблон $s$. Требуется найти хотя бы одно вхождение $s$ в $t$ или сказать, что их нет. АБМХ -- сублинейный алгоритм, решающий эту задачу за время $\O(\frac{|t|}{|s|})$ в среднем. В худшем случае алгоритм работает за время $\O(|t| \cdot |s|)$.

\down

\THEE{Алгоритм:}

\vspace*{0.5em}

Совместим начала текста и шаблона. Сравним последний символ шаблона с символом строки. Если они совпадают, сравним предпоследний. И так далее. Если все символы шаблона совпали с символами строки, вхождение найдено. Если в какой-то момент символы не совпали, тогда сдвинем шаблон вправо на несколько символов. Пусть $i$ -- позиция в тексте, которая сейчас совмещена с последним символом шаблона. Тогда сдвинем шаблон вправо на минимальное ненулевое количество символов так, чтобы буква шаблона, которая теперь соответствует позиции $i$, равнялась $t[i]$, либо, если $t[i]$ не встречается в $s$, на всю длину шаблона.

\down

\THEE{Пример:}

\vspace*{0.5em}

{\it t = "abcabcabbababa" \ \ \ \ \ s = "baba" \/}

\vspace*{0.5em}

$\begin{tabular}{|*{14}{c|}}
\hline
a & b & c & \red{a}& b & \red{c}& a & b & b & \red{a}& b & a & b & a \\
\hline
b & a & b & a          &    &            &    &    &    &             &    &    &    &    \\
   &    & b & \red{a}& b & a         &    &    &    &             &    &    &    &    \\
   &    &    &             &    &            & b & a & b & a          &    &    &    &    \\
   &    &    &             &    &            &    &    & b & \red{a}& b & a &    &    \\
\hline
\end{tabular}$

\down

Пусть символы строки нумеруются с 0. Посчитаем для каждого символа $c$ величину $last[c]$ -- позиция последнего вхождения символа $c$ в $s$ или -1, если символ $c$ не встречается в $s$ или стоит только на последней позиции. $\O(|\Sigma| + |s|)$

Тогда если при очередном сравнении символы не совпали, а $c$ -- символ текста, на который сейчас накладывается последний  символ шаблона, шаблон нужно сдвинуть на $|s| - last[c] - 1$.

\pagebreak

\THEE{Алгоритм Бойера-Мура}

\vspace*{0.5em}

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

Что же это за правило? Пусть на текущем этапе у $s$ с $t$ совпал некий суффикс $u$. Тогда можно сдвинуть $s$  так, чтобы под этим $u$ в $t$ оказалось самое правое вхождение $u$ из $s$, не считая самого суффикса. Если же $u$ в $s$ больше не встречается, можно попробовать провернуть то же самое с суффиксом поменьше. В результате этим самым правым вхождением может оказаться некоторый префикс $v$.

\begin{center}
\includegraphics[scale=0.5]{gorokhov/boyer_good_suff_1.png}

\vspace*{0.5em}

\includegraphics[scale=0.5]{gorokhov/boyer_good_suff_2.png}
\end{center}

Сдвиги для суффиксов можно предподсчитать с помощью z/префикс функции.

\vspace*{0.5em}


Таким образом для текущей позиции высчитываются сдвиги по двум правилам и выбирается лучший сдвиг. Асимптотически АБМ работает столько же, сколько и АБМХ. На случайных тестах АБМХ работает быстрее. На реальных тестах с неравномерным распределением символов АБМ может дать как выигрыш, так и проигрыш.

\pagebreak

\Subsection{Хеширование}

Хэш-функция преобразует строку в число. Если две строки равны, то равны и их хеши. При этом далеко не всегда из равенства хешей следует равенство строк.

\THEE{Полиномиальный хеш}

Пусть есть строка $s = s_0s_1s_2...s_{n-1}$. Можно сделать из неё многочлен, используя символы в качестве коэффициентов:

$H_0 = 0, \ H_{i + 1} = H_i \cdot p + s_i, \ H_n = s_0 \cdot p^{n-1} + s_1 \cdot p^{n-2} + ... + s_{n-1}$, где $p$ -- точка, в которой считается значение многочлена.

Такое преобразование можно использовать в качестве хеша. Причём если $p > |\Sigma|$, то отображение получается инъективным, то есть хеш каждой строки уникален. И всё бы хорошо, да вот только при таком подходе получаются слишком большие числа, с которыми абсолютно неудобно работать. Поэтому будем брать хеши по модулю:

$H_0 = 0, \ H_{i + 1} = (H_i \cdot p + s_i) \ \% \ M$, где $M$ -- некоторый выбранный нами модуль.

При таком подходе в процессе работы могут возникнуть коллизии -- ситуации, когда хеши двух различных строк равны. Далее сделаем несколько оценок на вероятность возникновения коллизий.

\begin{Thm}
Пусть $s_1, \ s_2, ..., \ s_k$ -- различные фиксированные строки. $M$ -- фиксированное натуральное число. $P$ -- случайное натуральное число. Тогда 
\begin{center}
$Pr[Hash(s_1), \ Hash(s_2), ..., \ Hash(s_k)$ -- различны] $\ge$ 
$\ge 1 - \sum\limits_{i < j} Pr[Hash(s_i) = Hash(s_j)] = 1 - \frac{k(k-1)}{2} \cdot \frac{1}{M}$
\end{center}
\end{Thm}

Увы, без доказательства.

\begin{Lm}
$Hash(s_1) = Hash(s_2) \Leftrightarrow Hash(s_1 - s_2) = 0$
\end{Lm}

\begin{proof}
$Hash(s_1 - s_2) = \sum p^i \cdot (s_1 - s_2)[n - i - 1]$
\end{proof}

\vspace*{0.5em}

Таким образом, вероятность того, что у двух различных строк совпадут хеши, равна вероятности того, что хеш случайной строки будет равен нулю. С такой формулировкой куда проще оценивать.

\begin{Lm}
Пусть $p, M$ -- фиксированные натуральные числа, $s = s_0s_1...s_{n-1}$ -- случайная строка, $s_i \in [0;M-1]$. Тогда
\begin{center}
$Pr[Hash(s) = 0] = \frac{1}{M}$
\end{center}
\end{Lm}

\begin{proof}
Возьмём полином от строки -- $S(x)$. Разделим его с остатком на $x - p$: $S(x) = (x - p)Q(x) + r$. Видно, что при $x = p$ получаем $S(p) = r$. $Q(x)$ -- полином $(n-1)$-ой степени. При этом какие бы он не имел коэффициенты $q_0, \ q_1,..., \ q_{n-2}$, всё равно $S(p) = r$. Всего наборов $(q_0, q_1,...,q_{n-2},r)$ -- $M^n$. При этом $Hash(s) = 0$ на наборах, где $r = 0$, а таких $M^{n-1}$. 
\end{proof}

Таким образом, $Pr[Hash(s) = 0] = \frac{M^{n-1}}{M^n} = \frac{1}{M}$.

\pagebreak

\begin{Lm}
Пусть $M$ и $s$ -- фиксированные модуль и строка. $p$ -- случайное число из промежутка $[0; M-1]$. $M$ -- простое. Тогда
\begin{center}
$Pr[Hash(s) = 0] \le \frac{|s|}{M}$ 
\end{center}
\end{Lm}
\begin{proof}
Количество корней многочлена $S(x)$ не больше $|s|$.
\end{proof}

\begin{Lm}
Пусть $M$ -- фиксированный модуль, а $s$ и $p$ -- случайные строка и число. Тогда
\begin{center}
$Pr[Hash(s) = 0] = \frac{1}{M}$ 
\end{center}
\end{Lm}

\begin{proof}
\t{Lm 3.2.3} $\Rightarrow$ \t{Lm 3.2.5}. В данной лемме у нас дано случайное $p$. Зафиксируем какое-нибудь одно $p$. Вероятность будет равна $\frac{1}{M}$. И так для любого $p \in [0; M-1]$. Тогда
\begin{center}
$Pr[Hash(s) = 0] = \frac{1}{M} \cdot \sum\limits_{p = 0}^{M - 1} Pr[Hash(s) = 0, p$ и $M$ фикс] $= \frac{1}{M} \cdot M \cdot \frac{1}{M} = \frac{1}{M}$ 
\end{center}
\end{proof}

\THEE{Вывод.} Как приготовить качественные хеши?

$M$ -- фиксированное простое число. $p$ -- случайное число из промежутка $[|\Sigma| + 1; M - |\Sigma|]$.

Как мы уже доказали выше, $Pr[$возникновение коллизии$] \le \frac{n(n-1)}{2} \cdot \frac{1}{M}$, где $n$ -- количество различных строк. Поэтому, если взять достаточно большой модуль, даже при большом количестве строк вероятность возникновения коллизии будет очень мала. Например, если взять $M = 10^{18} + 3$, то при количестве строк до $10^7$ вероятность возникновения коллизии будет не более 0.005\%.

И ещё несколько фактов/трюков:

\begin{enumerate}
  \setlength{\parskip}{3pt}
  \setlength{\itemsep}{15pt}

\item Не стесняйтесь использовать \_\_int128, он существует и работает довольно быстро.

\item Модуль можно использовать как один, так и два, и три, и сколько угодно. В таком случае, если модули простые, вероятность коллизии будет обратно пропорциональна произведению модулей.

\item При равенстве хешей можно вручную проверить строки на равенство. Это не универсальный способ, но в ситуациях, где совпадение хешей маловероятно, это беспроигрышный вариант. Особенно если использовать \t{memcmp}, коротый работает ну очень быстро.

\item Можно использовать $M = 2^{64}$, это намного удобнее и работает быстрее. И в большинстве случаев этого хватит. Но не стоит использовать на серьёзных соревнованиях/проектах, поскольку очень легко генерируется строка Туэ-Морса, на которой такой модуль выдаст множество коллизий.

\item Для любой пары $(M, p)$ существует алгоритм для построения тестов, на которых полиномиальный хеш с такими параметрами будет встречать коллизии. Из чего следует, что хеши не очень надёжная вещь и лучше использовать их только в случаях крайней необходимости.

\end{enumerate}
