Cài đặt thuật toán Rabin-Karp trong lập trình

Thuật toán Rabin-Karp là một trong những giải pháp hiệu quả để tìm kiếm mẫu (pattern) trong văn bản (text). Được phát triển bởi Michael O. Rabin và Richard M. Karp, thuật toán này kết hợp giữa lý thuyết chuỗi và băm, cung cấp một cơ chế tìm kiếm nhanh chóng và hiệu quả.

Hiểu về thuật toán Rabin-Karp

Thuật toán Rabin-Karp dựa trên kỹ thuật băm để so sánh các chuỗi con trong văn bản với mẫu cần tìm. Cụ thể, nó sử dụng một hàm băm để tính toán giá trị băm cho mẫu và cho mỗi chuỗi con có cùng độ dài trong văn bản. Nếu giá trị băm của một chuỗi con trùng khớp với giá trị băm của mẫu, thuật toán sẽ kiểm tra từng ký tự từ chuỗi con và mẫu để xác nhận.

Các bước cơ bản của thuật toán

Tính toán giá trị băm của mẫu: Đầu tiên, chúng ta cần tính giá trị băm của mẫu cần tìm dựa vào các ký tự trong mẫu và hàm băm được chọn.
Tính giá trị băm của chuỗi con đầu tiên trong văn bản: Giá trị băm này sẽ được dùng để so sánh với giá trị băm của mẫu.
So sánh giá trị băm: Nếu giá trị băm của chuỗi con và mẫu khớp, tiến hành kiểm tra từng ký tự để xác nhận khớp hoàn toàn.
Chuyển đổi giá trị băm: Tính giá trị băm cho chuỗi con kế tiếp bằng cách sử dụng giá trị băm của chuỗi con trước đó để tiết kiệm thời gian.
Lặp lại quá trình: Lặp lại bước 3 và bước 4 cho đến khi duyệt xong văn bản.

Cài đặt thuật toán Rabin-Karp

Dưới đây là một ví dụ cài đặt thuật toán Rabin-Karp bằng Python:

# Hàm tính giá trị băm
def hash_value(s, prime, mod):
    h = 0
    for char in s:
        h = (h * prime + ord(char)) % mod
    return h

# Hàm Rabin-Karp
def rabin_karp(pattern, text, prime=101, mod=1_000_000_007):
    m = len(pattern)
    n = len(text)
    p_hash = hash_value(pattern, prime, mod)
    t_hash = hash_value(text[:m], prime, mod)
    prime_pow = pow(prime, m-1, mod)
    
    for i in range(n - m + 1):
        if p_hash == t_hash:
            if text[i:i+m] == pattern:
                print(f"Pattern found at index {i}")
        if i < n - m:
            t_hash = (t_hash - ord(text[i]) * prime_pow) % mod
            t_hash = (t_hash * prime + ord(text[i + m])) % mod
            t_hash = (t_hash + mod) % mod  # ensure t_hash is positive

pattern = "abc"
text = "abxabcabcaby"
rabin_karp(pattern, text)

Ưu điểm và nhược điểm

Ưu điểm:

Hiệu quả cho tìm kiếm đồng thời nhiều mẫu: Có thể sử dụng để tìm kiếm nhiều mẫu khác nhau trong một văn bản.
Phép tính giá trị băm nhanh chóng: Thay vì so sánh từng ký tự một, giá trị băm cho phép so sánh nhanh hơn.

Nhược điểm:

Đụng độ giá trị băm: Việc hai chuỗi không giống nhau nhưng có giá trị băm giống nhau là có thể, dẫn đến kết quả sai lệch.
Phụ thuộc vào hàm băm: Nếu hàm băm không hiệu quả, kết quả tìm kiếm có thể không tối ưu.

Kết luận

Thuật toán Rabin-Karp là một lựa chọn mạnh mẽ cho các bài toán tìm kiếm chuỗi, đặc biệt khi cần tìm đồng thời nhiều mẫu. Tuy nhiên, cần lựa chọn hàm băm thích hợp và hiểu rõ các yếu tố ảnh hưởng để áp dụng một cách hiệu quả. Thông qua việc cài đặt và tối ưu hóa, bạn có thể khai thác sức mạnh của thuật toán Rabin-Karp trong các ứng dụng thực tế.

Đăng ký