Rabin-Karp - The Magic of Rolling Hash

"Khi Toán học thay thế so sánh từng ký tự." - HPN

Định nghĩa

Rabin-Karp là thuật toán pattern matching sử dụng hash values thay vì so sánh ký tự.

Ý tưởng cốt lõi:

• Tính hash của pattern: $H_p$
• Trượt cửa sổ qua text, tính hash của mỗi substring
• Nếu hash match → kiểm tra exact match (tránh false positive)

📘 Key Insight

Rolling Hash cho phép tính hash của window tiếp theo trong $O(1)$ thay vì $O(M)$.

Tại sao cần Rabin-Karp?

So sánh các thuật toán

Algorithm	Preprocess	Search	Best For
Brute-force	$O(1)$	$O(NM)$	Không dùng
KMP	$O(M)$	$O(N)$	Single pattern
Rabin-Karp	$O(M)$	$O(N)$ avg	Multiple patterns

Rabin-Karp sáng giá khi:

• Cần tìm nhiều patterns có cùng độ dài
• Plagiarism detection (so sánh document similarity)
• File synchronization (rsync algorithm)

Công thức Rolling Hash

Polynomial Hash

$$H(s)=\sum _{i=0}^{M-1}s[i]\times d^{M-1-i}\mathrm{mod}q$$

Với:

• $s$: String cần hash
• $d$: Base (thường = 256 cho ASCII)
• $q$: Prime modulus (tránh overflow)
• $M$: Độ dài pattern

Rolling Formula

Khi trượt window từ vị trí $i$ sang $i+1$:

$$H_{i+1}=(H_i-s[i]\times d^{M-1})\times d+s[i+M]\mathrm{mod}q$$

Window [i, i+M-1] → Window [i+1, i+M]

Bước 1: Trừ đi ký tự đầu (s[i]) với weight d^(M-1)
Bước 2: Nhân với d (shift left)
Bước 3: Cộng ký tự mới (s[i+M])

Visualization

Text:    A B C D E F G H
Pattern: C D E (length M = 3)

Step 1: Hash("ABC") = A×d² + B×d + C
Step 2: Hash("BCD") = (Hash("ABC") - A×d²) × d + D
Step 3: Hash("CDE") = (Hash("BCD") - B×d²) × d + E
        → Match với Hash("CDE")! → Verify exact match

Production Implementation

# HPN Engineering Standard
# Implementation: Rabin-Karp with Rolling Hash

from typing import List, Optional


class RabinKarp:
    """
    Rabin-Karp pattern matching với Rolling Hash.
    
    Time: O(N + M) expected, O(NM) worst case
    Space: O(1) auxiliary
    
    Use Cases: Plagiarism detection, rsync, multi-pattern search
    """
    
    # Large prime to minimize collisions
    PRIME = 1_000_000_007
    BASE = 256  # ASCII character range
    
    def __init__(self, base: int = 256, prime: int = 1_000_000_007) -> None:
        self.base = base
        self.prime = prime
    
    def search(self, text: str, pattern: str) -> List[int]:
        """
        Find all occurrences of pattern in text.
        
        Returns:
            List of starting indices where pattern is found
        """
        if not pattern or not text or len(pattern) > len(text):
            return []
        
        n, m = len(text), len(pattern)
        result: List[int] = []
        
        # Precompute d^(m-1) mod prime
        h = pow(self.base, m - 1, self.prime)
        
        # Calculate initial hash values
        pattern_hash = 0
        window_hash = 0
        
        for i in range(m):
            pattern_hash = (self.base * pattern_hash + ord(pattern[i])) % self.prime
            window_hash = (self.base * window_hash + ord(text[i])) % self.prime
        
        # Slide the window
        for i in range(n - m + 1):
            # Check hash match
            if pattern_hash == window_hash:
                # Verify exact match (avoid false positive from collision)
                if text[i:i + m] == pattern:
                    result.append(i)
            
            # Calculate hash for next window
            if i < n - m:
                # Rolling hash formula
                window_hash = (
                    self.base * (window_hash - ord(text[i]) * h) + ord(text[i + m])
                ) % self.prime
                
                # Handle negative modulo
                if window_hash < 0:
                    window_hash += self.prime
        
        return result
    
    def search_multiple(self, text: str, patterns: List[str]) -> dict:
        """
        Search multiple patterns of SAME LENGTH efficiently.
        
        Returns:
            Dict mapping pattern to list of positions
        """
        if not patterns or not text:
            return {}
        
        # Group patterns by length
        pattern_len = len(patterns[0])
        if not all(len(p) == pattern_len for p in patterns):
            raise ValueError("All patterns must have same length")
        
        if pattern_len > len(text):
            return {}
        
        # Precompute pattern hashes
        pattern_hashes = {}
        for pattern in patterns:
            h = self._compute_hash(pattern)
            if h not in pattern_hashes:
                pattern_hashes[h] = []
            pattern_hashes[h].append(pattern)
        
        result = {p: [] for p in patterns}
        
        # Compute d^(m-1)
        h_power = pow(self.base, pattern_len - 1, self.prime)
        
        # Initial window hash
        window_hash = self._compute_hash(text[:pattern_len])
        
        for i in range(len(text) - pattern_len + 1):
            if window_hash in pattern_hashes:
                substring = text[i:i + pattern_len]
                for pattern in pattern_hashes[window_hash]:
                    if substring == pattern:
                        result[pattern].append(i)
            
            # Roll hash
            if i < len(text) - pattern_len:
                window_hash = (
                    self.base * (window_hash - ord(text[i]) * h_power) 
                    + ord(text[i + pattern_len])
                ) % self.prime
                if window_hash < 0:
                    window_hash += self.prime
        
        return result
    
    def _compute_hash(self, s: str) -> int:
        """Compute polynomial hash of string."""
        h = 0
        for char in s:
            h = (self.base * h + ord(char)) % self.prime
        return h


def rabin_karp_search(text: str, pattern: str) -> List[int]:
    """Convenience function for single pattern search."""
    return RabinKarp().search(text, pattern)


# ============================================
# USAGE EXAMPLE
# ============================================
if __name__ == "__main__":
    rk = RabinKarp()
    
    text = "ABABDABACDABABCABAB"
    pattern = "ABAB"
    
    positions = rk.search(text, pattern)
    print(f"Pattern '{pattern}' found at: {positions}")
    # Output: [0, 10, 15]
    
    # Multi-pattern search (same length)
    patterns = ["ABAB", "ABCD", "DABA"]
    results = rk.search_multiple(text, patterns)
    print(f"Multi-pattern results: {results}")

Phân tích Độ phức tạp

Time Complexity

Case	Complexity	Khi nào xảy ra
Best/Average	$O(N+M)$	Hash collisions ít
Worst	$O(NM)$	Mọi hash đều match (cần verify)

Worst case example:

Text:    "AAAAAAAAAA"
Pattern: "AAAA"
→ Mọi window đều có cùng hash → verify tất cả

Space Complexity

$O(1)$ auxiliary (chỉ cần vài biến hash)

Hash Collision Probability

Với modulus $q$ prime:

$$P(\text{collision})\approx \frac{1}{q}$$

Với $q={10}^9+7$, xác suất collision ~1 trong 1 tỷ.

Ứng dụng Thực tế

1. Plagiarism Detection

Thuật toán:

1. Chia document thành k-grams (k ký tự liên tiếp)
2. Hash tất cả k-grams
3. So sánh hash sets giữa 2 documents
4. Similarity = |intersection| / |union|

def plagiarism_score(doc1: str, doc2: str, k: int = 5) -> float:
    """Calculate Jaccard similarity using k-gram hashes."""
    rk = RabinKarp()
    
    hashes1 = set()
    hashes2 = set()
    
    for i in range(len(doc1) - k + 1):
        hashes1.add(rk._compute_hash(doc1[i:i+k]))
    
    for i in range(len(doc2) - k + 1):
        hashes2.add(rk._compute_hash(doc2[i:i+k]))
    
    intersection = len(hashes1 & hashes2)
    union = len(hashes1 | hashes2)
    
    return intersection / union if union > 0 else 0.0

2. Rsync Algorithm

Rsync sử dụng rolling checksum để detect changed blocks:

File A (source): [Block1][Block2][Block3]
File B (target): [Block1'][Block2][Block3']

1. Compute rolling hash của blocks trong B
2. Slide qua A, tìm matching blocks
3. Chỉ transfer blocks KHÔNG match

3. Git Diff

Git sử dụng variant của Rabin fingerprint cho content-defined chunking.

Anti-patterns

❌ SAI LẦM PHỔ BIẾN

1. Không verify exact match

# ❌ WRONG: Hash match ≠ String match
if window_hash == pattern_hash:
    result.append(i)  # FALSE POSITIVE!

# ✅ RIGHT: Always verify
if window_hash == pattern_hash:
    if text[i:i+m] == pattern:  # Exact match
        result.append(i)

2. Không xử lý negative modulo

# ❌ WRONG: Python modulo có thể âm trong một số cases
hash = (hash - old_char * h) * d + new_char
hash = hash % prime  # Có thể vẫn âm

# ✅ RIGHT: Handle explicitly
if hash < 0:
    hash += prime

3. Prime quá nhỏ

# ❌ WRONG: High collision rate
prime = 101  # Chỉ 101 giá trị hash

# ✅ RIGHT: Large prime
prime = 1_000_000_007  # Standard competitive programming prime

So sánh Algorithms

Tiêu chí	KMP	Boyer-Moore	Rabin-Karp
Preprocess	$O(M)$	$O(M+\mathrm{\Sigma })$	$O(M)$
Search	$O(N)$	$O(N/M)$ best	$O(N)$ avg
Multi-pattern	❌	❌	✅
Streaming	✅	❌	✅

💡 HPN's Decision

Chọn Rabin-Karp khi:

• Cần tìm nhiều patterns cùng độ dài
• Plagiarism/similarity detection
• Rolling window problems