\documentclass{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{fullpage}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}
\usepackage {ngerman}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand {\mathset} [1] {\ensuremath {\mathbb {#1}}}
\newcommand {\R} {\mathset {R}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator{\emst}{emst}
\DeclareMathOperator{\conv}{CH}
\DeclareMathOperator{\argmin}{argmin}
\DeclareMathOperator{\DT}{DT}
\DeclareMathOperator{\UC}{UC}
\DeclareMathOperator{\LC}{LC}
\newcommand{\DKL}{D_\textup{KL}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{problem}[theorem]{Problem}
\newtheorem{obs}[theorem]{Beobachtung}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{definition}[theorem]{Definition}


\title{Suche in Zeichenketten}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

Seien 
$s = s_1 s_2 \dots s_k$ und 
$t = t_1 t_2 \dots t_\ell$
zwei Zeichenketten mit $\ell \leq k$.
Wir wollen entscheiden, ob
$t$ in $s$ enthalten ist, und
falls ja, an welcher Stelle $t$ zum
ersten Mal vorkommt. Der naive
Algorithmus ist wie folgt:
\begin{verbatim}
  for i := 1 to k - l + 1
    // Does s contain t at position i?
    j <- 1
    while j <= k and s[i+j-1] = t[j] do
      j++
    // If yes, return postion i
    if j = k+1 then
      return i
  // Not found, return -1
  return -1
\end{verbatim}

Die Laufzeit ist $O(k\ell)$. Das ist nur akzeptabel,  
wenn $\ell$ klein ist. 
Rabin und Karp haben folgenden Vorschlag gemacht, um die
Laufzeit zu verbessern: Der Flaschenhals besteht darin, dass wir
innerhalb der \texttt{for}-Schleife jedesmal den kompletten Substring
$s_i \dots s_{i+\ell-1}$ mit $t$ vergleichen. Wir k\"onnten die Schleife
beschleunigen, wenn wir vorher einen schnellen Test h\"atten,
ob es wahrscheinlich ist, dass $s_i\dots s_{i+\ell-1} = t$
ist. Hier hilft eine \emph{Hashfunktion}. Eine solche Hashfunktion
weist $s_i\dots s_{i+\ell-1}$ und $t$ jeweils eine Zahl zu. Diese
Zahlen lassen sich schnell vergleichen. Au\ss{}erdem hat eine
gute Hashfunktion wenig Kollisionen, so dass es selten vorkommt,
dass unterschiedliche  Strings $s_i\dots s_{i+\ell-1}$ und $t$ denselben 
Hashwert erhalten.
Dies f\"uhrt zu folgendem Ansatz (Rabin-Karp-Algorithmus).
Sei $h$ eine Hashfunktion.

\begin{verbatim}
  for i := 1 to k - l + 1
    if h(s[i...i+l-1]) = h(t) then
      if s[i...i+l-1] = t then
        return i
  return -1
\end{verbatim}

Wenn Kollisionen selten sind, sollte der Aufwand f\"ur den Vergleich
$s_i\dots s_{i+\ell-1} \stackrel{?}{=} t$ vernachl\"assigbar sein.
Aber es gibt ein neues Problem: Wie kann man $h$ schnell berechnen?
(Ansonsten w\"are die ganze Idee nat\"urlich witzlos.)
Zur Erinnerung: Vor ein paar Monaten hatten wir eine Hashfunktion $h'$ f\"ur einen 
String $a = a_0a_1 \dots a_{\ell-1}$ folgenderma\ss{}en definiert. Interpretiere die Zeichen 
$a_i$ als Zahlen zwischen $0$ und $S-1$ ($S = |\Sigma|$, die 
Alphabetgr\"o\ss{}e) und schreibe
\[
  h'(a) = \left(\sum_{j=0}^{\ell-1} a_j S^{j}\right) \bmod p
\]
F\"ur Rabin-Karp ist es besser, die Hashfunktion etwas anders zu definieren:
\[
  h(s_i...s_{i+\ell-1}) = \left(\sum_{j=0}^{\ell-1} s_{i+j}S^{\ell-1-j}\right) \bmod p
\]
$h$ unterscheidet sich von $h'$ in zwei Punkten: 
  (a) wir addieren zum Index im String immer $i$ (weil es sich um einen 
     Teilstring handelt) und 
  (b) die Potenzen von $S$ sind fallend statt steigend (das macht 
    die Formel unten einfacher).
Der entscheidende Punkt ist nun, dass 
\[
  h(s_{i+1}\dots s_{i+\ell}) = \left(S\cdot h(s_i...s_{i+\ell-1})-S^l\cdot s_i +s_{i+\ell}\right) \bmod p
\]
ist.
Das hei\ss{}t: 
  \emph{kennen wir $h(s_i\dots s_{i+\ell-1})$, so k\"onnen wir
  $h(s_{i+1}\dots s_{i+\ell}$) mit $O(1)$ Operationen berechnen.}
(Beachte: Wir m\"ussen $S^l$ nur einmal ausrechnen und speichern).
Es folgt: wir k\"onnen $h(s_1\dots s_\ell)$, $h(s_2\dots s_{\ell+1})$, 
$\ldots$, $h(s_{k-\ell}\dots s_\ell)$ sowie
$h(t)$ in Gesamtzeit $O(k+\ell)$ berechnen. Heuristisch gesehen sollte der
Algorithmus von Rabin-Karp nun $O(k+\ell)$ Zeit ben\"otigen, da wir hoffen, 
dass Kollisionen selten sind. (Genauer ist die Idee der
Laufzeitanalyse, $p = \Theta(\ell)$ zu w\"ahlen. Dann sollte die
Wahrscheinlichkeit einer Kollision etwa $1/\ell$ betragen, so dass man 
nur in jedem $\ell.$ Schleifendurchlauf den Stringvergleich durchf\"uhren
muss. Dies gibt konstante amortisierte Zeit pro Schleifendurchlauf.)

Bemerkungen:
\begin{enumerate}
  \item Bei der  Implementierung sollte man bei der Berechnung
     von $h$ nach jeder Multiplikation das Ergebnis $\bmod p$ nehmen und sicher
     stellen, dass $p^2$ nicht zu gross ist, um \"Uberl\"aufe zu vermeiden.
  \item Wenn $p$ zuf\"allig gew\"ahlt ist, ben\"otigt der
     Algorithmus von Rabin-Karp $O(k+\ell)$ Zeit im Erwartungswert.
  \item Es gibt Algorithmen zur Suche in Zeichenketten mit $O(k+\ell)$
     worst-case-Zeit (Knuth-Morris-Pratt, Boyer-Moore, Suffix-B\"aume).
     Diese sind aber zum Teil bedeutend komplizierter.
  \item Die Idee, Strings durch Hashfunktionen darzustellen/zu approximieren 
     hat viele weitere Anwendungen (sichere Speicherung von Passw\"ortern,
     digitale Unterschriften, Verifikation von Downloads, \dots)
\end{enumerate}
\end{document}