Thuật toán Rabin-Karp ứng dụng trong đối sánh mẫu

Trong bài viết này, ta sẽ cùng tìm hiểu về thuật toán Rabin-Karp. Ngoài ra, ta sẽ triển khai ví dụ về cách làm việc của kiểu thuật toán này được viết bằng ngôn ngữ lập trình C.

Thuật toán Rabin-Karp

Thuật toán Rabin-Karp là một thuật toán được sử dụng để tìm kiếm hoặc đối sánh các mẫu trong đoạn 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 đối sánh chuỗi thông thường, nó sẽ không đi qua mọi ký tự trong giai đoạn đầu mà nó sẽ 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.

Cách hoạt động của thuật toán Rabin-Karp

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

Ta sẽ cùng tìm hiểu thuật toán với các bước sau:

Bước 1: Giả sử ta có đoạn văn bản như sau:

- Và chuỗi được tìm kiếm trong văn bản trên có dạng là:

Bước 2: Ta sẽ gán một giá trị số (v)/trọng số cho các ký tự mà chúng ta sẽ sử dụng trong bài toán. Ở đây, chúng ta chỉ lấy mười chữ cái đầu tiên trong bảng chữ cái tiếng anh (tức là từ A đến J).

Bước 3: m là chiều dài của mẫu và n là chiều dài của đoạn văn bản. Ở đây, m = 10 và n = 3. Gọi d là số ký tự trong tập đầu vào. Ở đây, chúng ta đã lấy tập đầu vào là {A, B, C, …, J}. Vì vậy, d = 10. Ta có thể giả sử bất kỳ giá trị phù hợp nào cho d.
Bước 4: Ta sẽ tính toán giá trị băm của mẫu cần tìm như sau:

Giá trị băm cho mẫu(p) = Σ(v * dm-1) mod 13
                = ((3 * 102) + (4 * 101) + (4 * 100)) mod 13
                = 344 mod 13
                = 6

Giá trị băm cho mẫu(p) = Σ(v * dm-1) mod 13

= ((3 * 102) + (4 * 101) + (4 * 100)) mod 13

= 344 mod 13

= 6

- Trong phép tính ở trên, ta sẽ chọn một số nguyên tố (ở đây là 13), bằng cách này, chúng ta có thể thực hiện tất cả các phép tính với số học có độ chính xác đơn.
Bước 5: Tính giá trị băm cho đoạn văn bản có kích thước m.

Đối với tập đầu tiên ABC,
Giá trị băm cho đoạn văn bản(t) = Σ(v * dn-1) mod 13
                  = ((1 * 102) + (2 * 101) + (3 * 100)) mod 13
                  = 123 mod 13 
                  = 6

Đối với tập đầu tiên ABC,

Giá trị băm cho đoạn văn bản(t) = Σ(v * dn-1) mod 13

= ((1 * 102) + (2 * 101) + (3 * 100)) mod 13

= 123 mod 13

= 6

Bước 6: 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 đối sánh ký tự sẽ được thực hiện. Trong các ví dụ trên, giá trị băm của tập đầu tiên (tức là t) khớp với p, vì vậy, ta sẽ đối sánh ký tự giữa ABC và CDD. Vì chúng không khớp nên ta sẽ chuyển sang tập tiếp theo.
Bước 7: Chúng ta sẽ tính toán giá trị băm của tập tiếp theo bằng cách trừ số hạng đầu tiên và cộng số hạng tiếp theo như dưới đây.

t = ((1 * 102) + ((2 * 101) + (3 * 100)) * 10 + (3 * 100)) mod 13
  = 233 mod 13 
  = 12

t = ((1 * 102) + ((2 * 101) + (3 * 100)) * 10 + (3 * 100)) mod 13

= 233 mod 13

= 12

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

t = ((d * (t - v[Ký tự bị loại bỏ] * h) + v[Ký tự được thêm] ) mod 13  
  = ((10 * (6 - 1 * 9) + 3 )mod 13 
  = 12
Trong đó, h = d^(m-1)= 10^(3-1) = 100.

t = ((d * (t - v[Ký tự bị loại bỏ] * h) + v[Ký tự được thêm] ) mod 13

= ((10 * (6 - 1 * 9) + 3 )mod 13

= 12

Trong đó, h = d^(m-1)= 10^(3-1) = 100.

Bước 8: Đối với BCC, t = 12 (≠ 6). Do đó, ta sẽ chuyển sang tập tiếp theo. Sau một vài lượt tìm kiếm, chúng ta sẽ nhận được kết quả khớp cho tập CDA trong đoạn văn bản.

Thuật toán được triển khai như sau:

n = t.length
m = p.length
h = dm-1 mod q
p = 0
t0 = 0
Sử dụng vòng lặp for với i = 1 cho tới m
    p = (dp + p[i]) mod q
    t0 = (dt0 + t[i]) mod q
Sử dụng vòng lặp for với s = 0 cho đến n - m
    Nếu p = ts
        Nếu p[1.....m] = t[s + 1..... s + m]
            In ra thông báo là đã tìm thấy
    Nếu s < n-m
        ts + 1 = (d (ts - t[s + 1]h) + t[s + m + 1]) mod q

n = t.length

m = p.length

h = dm-1 mod q

p = 0

t0 = 0

Sử dụng vòng lặp for với i = 1 cho tới m

p = (dp + p[i]) mod q

t0 = (dt0 + t[i]) mod q

Sử dụng vòng lặp for với s = 0 cho đến n - m

Nếu p = ts

Nếu p[1.....m] = t[s + 1..... s + m]

In ra thông báo là đã tìm thấy

Nếu s < n-m

ts + 1 = (d (ts - t[s + 1]h) + t[s + m + 1]) mod q

Ví dụ: Triển khai thuật toán bằng ngôn ngữ lập trình C.

#include <stdio.h>
#include <string.h>

#define d 10

void RabinKarp_match(char pattern_to_find[], char text[], int q) {
  int m = strlen(pattern_to_find);
  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;
  for (i = 0; i < m; i++) {
    p = (d * p + pattern_to_find[i]) % q;
    t = (d * t + text[i]) % q;
  }
  for (i = 0; i <= n - m; i++) {
    if (p == t) {
      for (j = 0; j < m; j++) {
        if (text[i + j] != pattern_to_find[j])
          break;
      }
      if (j == m)
        printf("Mẫu được tìm ở vị trí:  %d\n", 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_to_find[] = "CDD";
  int q = 13;
  RabinKarp_match(pattern_to_find, text, q);
}

#include <stdio.h>

#include <string.h>

#define d 10

void RabinKarp_match(char pattern_to_find[], char text[], int q) {

int m = strlen(pattern_to_find);

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;

for (i = 0; i < m; i++) {

p = (d * p + pattern_to_find[i]) % q;

t = (d * t + text[i]) % q;

}

for (i = 0; i <= n - m; i++) {

if (p == t) {

for (j = 0; j < m; j++) {

if (text[i + j] != pattern_to_find[j])

break;

}

if (j == m)

printf("Mẫu được tìm ở vị trí: %d\n", 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_to_find[] = "CDD";

int q = 13;

RabinKarp_match(pattern_to_find, text, q);

}

Kết quả:

Mẫu được tìm ở vị trí:&nbsp; 4

1	Mẫu được tìm ở vị trí:  4

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

Khi giá trị băm của mẫu khớp với giá trị băm của một tập trong đoạn văn bản nhưng tập đó không phải là mẫu thực thì đó được gọi là hiện tượng trùng khớp nhầm.

Trùng khớp nhầm sẽ làm tăng độ phức tạp về thời gian của thuật toán. Để giảm thiểu hiện tượng này, chúng ta sẽ sử dụng phép toán modulo (phép chia lấy phần dư).

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

Độ phức tạp của trường hợp trung bình và trường hợp tốt nhất của thuật toán Rabin-Karp là $O(m + n)$ và độ phức tạp của 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 hiện tượng trùng khớp nhầm xảy ra cho tất cả các tập ký tự con.

Ứng dụng

Được sử dụng để đối sánh mẫu trong một đoạn văn bản nhất định.
Được sử dụng để tìm kiếm chuỗi trong đoạn văn bản lớn hơn.

Trên đây là khái niệm và ví dụ cơ bản về thuật toán Rabin-Karp. Hy vọng mọi người có thể áp dụng vào trong chương trình của mình. Nếu mọi người có đóng góp gì thêm thì có thể để các bình luận bên dưới bài viết này. Mọi người hãy tiếp tục theo dõi các bài tiếp theo và cập nhật các bài mới nhất trên tek4 nhé!

P/s: Cảm ơn mọi người đã tin tưởng tek4!

Bài trước: Thuật toán Boyer-Moore trong tìm kiếm xâu con

Bài tiếp theo: Thuật toán Wu-Manber trong đối sánh đa mẫu

0 0 vote

Article Rating