==Хеш Рабина (matching)==

Пусть 
$$
X=(x_1,\dots,x_n) , Y=(y_1,\dots,y_m)
$$ 
--- бинарные векторы. Проблема сопоставления строк (string matching problem)--- это проблема нахождения одного или нескольких индексов $ i $ таких, что
$$
X=Y_i:=(y_i,y_{i+1},\dots, y_{i+n-1}) \, .
$$
В случае наличия такого $ i $ будем говорить, что сопоставление установлено. Задача: построить алгоритм, который устанавливает факт сопоставления с вероятностью, меньшей наперед заданного $\varepsilon > 0 $. Пусть $ p $ --- наименьшее простое число, такое, что 
$$ 
p>\log_2\left(\frac{nm}{\varepsilon} \right) \, . \qquad {\color{Red}{ (1)} }
$$
Пусть
$$
a(t):=x_1t^{n-1}+\dots+x_n, \ a_i(t):=y_it^{n-1}+\dots+y_{i+n-1} \quad \mbox{при} \ i \in \{1,\dots,m+n-1\} \, .
$$
Очевидно, сопоставление происходит при $ a(t)\equiv a_i(t) $. 

Выбираем случайным образом ((:gruppe/galois#polinomy_neprivodimye_po_modulju неприводимый)) над $ \mathbb Z_2 $ полином
$$
f(t)=t^{p}+b_1t^{p-1}+\dots+b_p \, .
$$
Число таких полиномов ---
$$
\frac{1}{p}  (2^p-2) \, ,
$$
(см. <html>
  <font face="Times">
        <font color="#ff00ff" size="+2"> ☞

</font>
  </font>
</html>  ((:gruppe/galois#polinomy_neprivodimye_po_modulju теорему 4)) ).

Обозначим 
$$
\overline{g(t)}:= g(t) \mod f(t) \, ,
$$
т.е. остаток от деления $ g(t) $ на $ f(t) $, ну еще и коэффициенты потом по $ \mod 2 $ приведем.
Вычисляем
$$
\overline{a(t)}, \overline{t^{n-1}}, \overline{a_1(t)} \, .
$$
Если $\overline{a(t)} = \overline{a_1(t)} $, то сопоставление происходит при $ i=1 $. На шаге $ i $ сохраняются полиномы
$$
\overline{a(t)}, \overline{t^{n-1}}, \overline{a_i(t)}, f(t) \, ,
$$
задаваемые $ p $-разрядными векторами. Вычисляется
$$
 \overline{a_{i+1}(t)}:=( \overline{a_i(t)} + y_i \overline{t^{n-1}}) t + y_{i+n} \mod f(t) \, . \qquad {\color{Red}{ (2)} }
$$
<note> Фактически на каждом шаге алгоритма предполагается всего одна операция деления на полином $ f(t) $ --- если считать,
что остаток $  \overline{t^{n-1}} $ был заранее вычислен.
</note>

Если $\overline{a(t)} = \overline{a_{i+1}(t)} $, то соответствие установлено при $ i+1 $.

!!Т!! **Теорема.** //Вероятность того, что приведенный алгоритм выдаст// $ \ge 1 $ //ошибки, не превосходит// $ \varepsilon $. //Более того, алгоритм обнаружит все сопоставления.//

!!П!! **Пример.** $ n=10^3, m=10^6, \varepsilon = 2^{-30}$, $ p=61 $ удовлетворяет неравенству $  {\color{Red}{ (1)} } $.

<note> В чем, собственно, заключается идея алгоритма Рабина? Вместо того, чтобы по-честному сравнивать векторы  $X$ и $Y_i$ на
 совпадение, мы сравниваем их отпечатки, fingerprint'ы, т.е. наборы коэффициентов их частных, получаемых посредством привлечения операции деления на неприводимый полином $ f(t) $. Если количество разрядов $ n $ велико, то получаем векторы из коэффициентов остатков с количеством разрядов $p$, существенно меньшим $ n $. Их генерация из исходных векторов $ X $ и $ Y_i $ может считаться случайной. И мы сравниваем на предмет совпадения именно эти отпечатки. Если они различны, то совпадения 
 $X=Y_i$ точно нет, а вот если эти отпечатки одинаковы, то есть вероятность, что $X\ne  Y_i$, но выбором $ p $ эту вероятность
можно сделать сколь угодно малой.

Возникает естественный вопрос: в случае бинарных векторов не проще ли было бы просто тупо проверять $X\oplus Y_i = \mathbb O $?

Операция деления полиномов --- дорогая, ну а что может быть проще XOR?
</note>

==Источник==


[1]. **Rabin M.O.** //Fingerprinting by random polynomials.// Technical report, 1981 ((:dedup:rabin1981 .)) 


((:dedup:universal_hash .))