Rabin–Karp erklärt: String-Suche mit Rolling Hash

Rabin–Karp ist ein klassischer Algorithmus zur Suche eines Patterns innerhalb eines Textes.

Anstatt an jeder Position alle Zeichen direkt zu vergleichen, berechnet der Algorithmus zuerst einen Hashwert für das Pattern und für gleich große Textfenster.

Die Kernidee lautet:

Zuerst Hashwerte vergleichen, danach nur mögliche Treffer vollständig prüfen.

Rolling Hash

Beim Wechsel von:

ABC

zu:

BCD

wird der Hash nicht vollständig neu berechnet.

Der Beitrag von A wird entfernt, die restlichen Werte werden verschoben und D wird hinzugefügt.

Dieses Verfahren nennt man Rolling Hash.

Hash Collision

Unterschiedliche Strings können denselben Hashwert besitzen.

Daher muss nach einem Hash-Treffer eine exakte Prüfung erfolgen:

Hash Match
↓
String Comparison
↓
Match oder Collision

Polynomial Rolling Hash

Ein String kann konzeptionell als Polynom dargestellt werden:

A × base² + B × base + C

Mit Modulo einer Primzahl bleiben die Zahlen handhabbar.

TypeScript

function rabinKarp(
  text: string,
  pattern: string
): number {
  const n = text.length;
  const m = pattern.length;

  if (m === 0) return 0;
  if (m > n) return -1;

  const base = 256;
  const prime = 101;

  let patternHash = 0;
  let windowHash = 0;
  let highOrder = 1;

  for (let i = 0; i < m - 1; i++) {
    highOrder = (highOrder * base) % prime;
  }

  for (let i = 0; i < m; i++) {
    patternHash = (
      base * patternHash + pattern.charCodeAt(i)
    ) % prime;

    windowHash = (
      base * windowHash + text.charCodeAt(i)
    ) % prime;
  }

  for (let i = 0; i <= n - m; i++) {
    if (
      patternHash === windowHash &&
      text.slice(i, i + m) === pattern
    ) {
      return i;
    }

    if (i < n - m) {
      windowHash = (
        base * (
          windowHash -
          text.charCodeAt(i) * highOrder
        ) +
        text.charCodeAt(i + m)
      ) % prime;

      if (windowHash < 0) {
        windowHash += prime;
      }
    }
  }

  return -1;
}

Komplexität

Typischer Durchschnitt:

O(n + m)

Worst Case bei vielen Collisions:

O(n × m)

Zusätzlicher Speicher:

O(1)

Vergleich mit KMP

KMP nutzt die interne Struktur des Patterns und eine LPS-Tabelle.

Rabin–Karp nutzt dagegen Hashing und Rolling Hash.

KMP garantiert lineare Laufzeit, während Rabin–Karp im Worst Case durch viele Kollisionen langsamer werden kann.

Mehrere Patterns

Hash-basierte Suche ist besonders interessant, wenn viele Patterns gleicher Länge gesucht werden.

Ihre Hashwerte können in einem Set gespeichert werden und jedes Textfenster wird dagegen geprüft.

Anwendungen

Rolling Hash findet sich bei:

• Textsuche
• Duplicate Detection
• Dokumentvergleich
• Plagiarism Detection
• DNA-Sequenzen
• Substring Queries
• Fingerprinting

Double Hashing

Zwei unabhängige Hashwerte reduzieren die Wahrscheinlichkeit einer zufälligen Collision erheblich.

Ein Candidate muss dann beide Hashbedingungen erfüllen.

Typische Fehler

• Hashgleichheit als endgültigen Beweis behandeln.
• Jeden Window-Hash komplett neu berechnen.
• Modulo vergessen.
• Ungeeignete Hashparameter wählen.
• Das ausgehende Zeichen falsch entfernen.

Interviewperspektive

Rabin–Karp kombiniert mehrere wichtige Konzepte:

• Hashing
• Sliding Window
• Modular Arithmetic
• String Matching
• Collision Handling

Das Verständnis des Rolling Hash ist wichtiger als das Auswendiglernen des Codes.

Fazit

Rabin–Karp kombiniert Pattern Hashing mit einem gleitenden Textfenster.

Window
↓
Rolling Hash
↓
Hash Comparison
↓
Exact Verification

Die wichtigste übertragbare Idee ist Rolling Hash, also die effiziente Aktualisierung des Hashwerts eines verschobenen Substrings.