Thuật toán Rabin-Karp

Trong hướng dẫn này, bạn sẽ tìm hiểu thuật toán rabin-karp là gì. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của thuật toán rabin-karp trong C, C ++, Java và Python.

Thuật toán Rabin-Karp là một thuật toán được sử dụng để tìm kiếm / đối sánh các mẫu trong văn bản bằng cách sử dụng một hàm băm. Không giống như thuật toán so khớp chuỗi Naive, nó không đi qua mọi ký tự trong giai đoạn đầu mà nó lọc các ký tự không khớp và sau đó thực hiện so sánh.

Hàm băm là một công cụ để ánh xạ giá trị đầu vào lớn hơn với giá trị đầu ra nhỏ hơn. Giá trị đầu ra này được gọi là giá trị băm.

Thuật toán Rabin-Karp hoạt động như thế nào?

Một chuỗi ký tự được lấy và kiểm tra khả năng có mặt của chuỗi được yêu cầu. Nếu khả năng được tìm thấy thì quá trình khớp ký tự được thực hiện.

Hãy để chúng tôi hiểu thuật toán với các bước sau:

  1. Đặt văn bản là: Văn bản
    Và chuỗi cần tìm trong văn bản trên là: Mẫu
  2. Hãy để chúng tôi gán một numerical value(v)/weightký tự mà chúng tôi sẽ sử dụng trong bài toán. Ở đây, chúng tôi chỉ lấy mười bảng chữ cái đầu tiên (tức là từ A đến J). Trọng lượng văn bản
  3. m là chiều dài của mẫu và n là chiều dài của văn bản. Ở đây, m = 10 and n = 3.
    Gọi d là số ký tự trong tập đầu vào. Ở đây, chúng tôi đã lấy tập hợp đầu vào (A, B, C,…, J). Vì vậy d = 10,. Bạn có thể giả định bất kỳ giá trị phù hợp nào cho d.
  4. Hãy để chúng tôi tính toán giá trị băm của mẫu. Giá trị băm của văn bản
giá trị băm cho mẫu (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

Trong phép tính trên, hãy chọn một số nguyên tố (ở đây, 13) theo cách mà chúng ta có thể thực hiện tất cả các phép tính với số học chính xác một lần.

Lý do tính toán mô đun được đưa ra dưới đây.

  1. Tính giá trị băm cho cửa sổ văn bản có kích thước m.
Đối với cửa sổ đầu tiên ABC, giá trị băm cho văn bản (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 mod 13 = 6
  1. So sánh giá trị băm của mẫu với giá trị băm của văn bản. Nếu chúng khớp thì quá trình khớp ký tự sẽ được thực hiện.
    Trong các ví dụ trên, giá trị băm của cửa sổ đầu tiên (tức là t) khớp với p, vì vậy, hãy so khớp ký tự giữa ABC và CDD. Vì chúng không khớp nên hãy chuyển sang cửa sổ tiếp theo.
  2. Chúng tôi tính toán giá trị băm của cửa sổ tiếp theo bằng cách trừ số hạng đầu tiên và cộng số hạng tiếp theo như hình dưới đây.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Để tối ưu hóa quá trình này, chúng tôi sử dụng giá trị băm trước đó theo cách sau.

t = ((d * (t - v (ký tự bị xóa) * h) + v (ký tự được thêm vào)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 Trong đó , h = d m-1 = 10 3-1 = 100.
  1. Đối với BCC, t = 12 ( ≠ 6). Do đó, hãy chuyển sang cửa sổ tiếp theo.
    Sau một vài tìm kiếm, chúng tôi sẽ nhận được kết quả khớp cho CDA cửa sổ trong văn bản. Giá trị băm của các cửa sổ khác nhau

Thuật toán

 n = t. chiều dài m = p. chiều dài h = dm-1 mod qp = 0 t0 = 0 for i = 1 to mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q for s = 0 to n - m if p = ts if p (1… m) = t (s + 1… s + m) in "pattern found at position" s Nếu s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Ví dụ về Python, Java và C / C ++

Python Java C C ++ 
 # Rabin-Karp algorithm in python d = 10 def search(pattern, text, q): m = len(pattern) n = len(text) p = 0 t = 0 h = 1 i = 0 j = 0 for i in range(m-1): h = (h*d) % q # Calculate hash value for pattern and text for i in range(m): p = (d*p + ord(pattern(i))) % q t = (d*t + ord(text(i))) % q # Find the match for i in range(n-m+1): if p == t: for j in range(m): if text(i+j) != pattern(j): break j += 1 if j == m: print("Pattern is found at position: " + str(i+1)) if i < n-m: t = (d*(t-ord(text(i))*h) + ord(text(i+m))) % q if t < 0: t = t+q text = "ABCCDDAEFG" pattern = "CDD" q = 13 search(pattern, text, q)
 // Rabin-Karp algorithm in Java public class RabinKarp ( public final static int d = 10; static void search(String pattern, String txt, int q) ( int m = pattern.length(); int n = txt.length(); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern.charAt(i)) % q; t = (d * t + txt.charAt(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (txt.charAt(i + j) != pattern.charAt(j)) break; ) if (j == m) System.out.println("Pattern is found at position: " + (i + 1)); ) if (i < n - m) ( t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + m)) % q; if (t < 0) t = (t + q); ) ) ) public static void main(String() args) ( String txt = "ABCCDDAEFG"; String pattern = "CDD"; int q = 13; search(pattern, txt, q); ) )
 // Rabin-Karp algorithm in C #include #include #define d 10 void rabinKarp(char pattern(), char text(), int q) ( int m = strlen(pattern); int n = strlen(text); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern(i)) % q; t = (d * t + text(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (text(i + j) != pattern(j)) break; ) if (j == m) printf("Pattern is found at position: %d ", i + 1); ) if (i < n - m) ( t = (d * (t - text(i) * h) + text(i + m)) % q; if (t < 0) t = (t + q); ) ) ) int main() ( char text() = "ABCCDDAEFG"; char pattern() = "CDD"; int q = 13; rabinKarp(pattern, text, q); )
 // Rabin-Karp algorithm in C++ #include #include using namespace std; #define d 10 void rabinKarp(char pattern(), char text(), int q) ( int m = strlen(pattern); int n = strlen(text); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern(i)) % q; t = (d * t + text(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (text(i + j) != pattern(j)) break; ) if (j == m) cout << "Pattern is found at position: " << i + 1 << endl; ) if (i < n - m) ( t = (d * (t - text(i) * h) + text(i + m)) % q; if (t < 0) t = (t + q); ) ) ) int main() ( char text() = "ABCCDDAEFG"; char pattern() = "CDD"; int q = 13; rabinKarp(pattern, text, q); )

Hạn chế của thuật toán Rabin-Karp

Spurious Hit

Khi giá trị băm của mẫu khớp với giá trị băm của cửa sổ văn bản nhưng cửa sổ đó không phải là mẫu thực thì đó được gọi là lần truy cập giả.

Lần truy cập giả làm tăng độ phức tạp về thời gian của thuật toán. Để giảm thiểu hit giả, chúng tôi sử dụng mô-đun. Nó làm giảm đáng kể cú đánh giả mạo.

Độ phức tạp của thuật toán Rabin-Karp

Trường hợp trung bình và trường hợp phức tạp tốt nhất của thuật toán Rabin-Karp là O(m + n)và độ phức tạp trường hợp xấu nhất là O (mn).

Độ phức tạp trong trường hợp xấu nhất xảy ra khi số lần truy cập giả xảy ra một số cho tất cả các cửa sổ.

Ứng dụng thuật toán Rabin-Karp

  • Để khớp mẫu
  • Để tìm kiếm chuỗi trong một văn bản lớn hơn

thú vị bài viết...