Trong bài viết này, chúng ta sẽ cùng tìm hiểu về thuật toán Boyer-Moore được ứng dụng trong việc tìm kiếm chuỗi xâu con trong một chuỗi khác.

1. Khái niệm

Thuật toán Boyer-Moore, giống như thuật toán Knuth-Morris-Pratt hoặc Rabin-Karp, là một thuật toán tìm kiếm chuỗi hiệu quả. Nó được phát triển bởi Robert Boyer và J Strother Moore vào năm 1977. Thuật toán này xử lý trước cho mẫu cần tìm kiếm.

Thuật toán tìm kiếm chuỗi này hiệu quả vì nó không đi qua toàn bộ không gian tìm kiếm khi nó đang thực hiện tìm kiếm một mẫu phù hợp. Nó sẽ bỏ qua một cách thông minh để giảm số lượng ký tự so sánh mà mỗi lần tìm kiếm được thực hiện.

Có hai giai đoạn cho quá trình tìm kiếm chuỗi này. Giai đoạn đầu tiên là tạo một bảng chỉ số cho mẫu tìm kiếm. Bảng tìm kiếm này được sử dụng để bỏ qua chuỗi tìm kiếm nhằm giảm số lượng các thao tác đối sánh.

2. Ý tưởng của thuật toán

Thuật toán tìm kiếm chuỗi Boyer-Moore được dựa trên 2 cách tiếp cận heuristics:

Cách 1: Thực hiện so sánh mẫu tìm kiếm P với chuỗi ký tự con của T.
Cách 2: Nếu một sự sai lệch không trùng khớp xảy ra tại T[i] = c:
1. Nếu mẫu tìm kiếm P có chứa ký tự c, thực hiện dịch chuyển mẫu P sang phải sao cho ký tự c cuối cùng trong P nằm thẳng hàng với T[i]
2. Mặt khác, thực hiện dịch chuyển P sao cho P[0] thẳng hàng với T[i+1]

3. Hàm tìm kiếm lần xuất hiện cuối cùng của ký tự

Thuật toán Boyer-Moore sẽ thực hiện xử lý mẫu tìm kiếm P và một bảng chữ cái $\sum$ để xây dựng hàm tìm kiếm lần xuất hiện cuối cùng của ký tự và thực hiện ánh xạ bảng $\sum$ tới các số nguyên, trong đó, $L(c)$ được định nghĩa như sau:

Chỉ số lớn nhất i sao cho $P[i] = c$ hoặc
Bằng -1 nếu chỉ số không tồn tại.

Ví dụ:

$\sum = a, b, c, d$
$P = abacab$

c	a	b	c	d
L(c)	4	5	3	-1

RUN_CODE (*** phân biệt ***)

C

#include<stdio.h>
#include<string.h>
int main() 
{
    char t[1000] = "abadabacab",p[1000] = "abacab";
    int l[127]; 
    int lap=0;
    for(int i=0;i<(int)strlen(t);i++)
    { 
        l[(int)t[i]]=-1;
    } 
    for(int i=0;i<(int)strlen(p)-1;i++)
    {
        l[(int)p[i]]=i; 
    }
    for(int i=0;i<(int)strlen(t)-1;i++)
    { 
        printf("%c ",t[i]);
        printf("%d \n",l[(int)t[i]]);
    } 
}

Hàm tìm kiếm lần xuất hiện cuối cùng của chữ cái được tính trong thời gian $O(m + s)$, trong đó m là kích thước của $P$ và $s$ là kích thước của bảng $\sum$.

4. Giải thuật Boyer-Moore

$\text{BoyerMooreMatch}$ $(T, P, \sum)$

$L \leftarrow \text{lastOccurenceFunc}$$(P, \sum)$
$i \leftarrow m - 1$
$j \leftarrow m - 1$
Thực hiện vòng lặp
- Nếu $T[i] = P[j]$
  - Nếu $j = 0$
    - Trả về $i$ (kết quả trùng khớp xảy ra tại i)
  - Mặc khác
    - $i \leftarrow i - 1$
    - $j \leftarrow j - 1$
- Mặc khác
  - (Thực hiện nhảy cách ký tự)
  - $l \leftarrow L[T[i]]$
  - $i \leftarrow i + m - \text{min}(j, 1+ l)$
  - $j \leftarrow m - 1$
Cho tới khi $i > n - 1$
Trả về $-1$ (Không có trường hợp trùng khớp)

Ví dụ: Chúng ta sẽ thực hiện tìm kiếm mẫu APPLE từ chuỗi ký tự APPSTOREAPPLE.

thuat-toan-boyer-moore

Trong lần so sánh đầu tiên, vì ký tự T không hề có xuất hiện trong mẫu tìm kiếm P = “APPLE”. Do đó, số ký tự ta cần dịch chuyển là 5 ký tự. Hay nói cách khác với cách tiếp cận của giải thuật Boyer-Moore, mình sẽ thực hiện dịch chuyển mẫu tìm kiếm P sang phải sao cho ký tự A (Phần tử đầu tiên của mẫu P[0]) của mẫu tìm kiếm nằm thẳng hàng với ký tự O (Phần tử T[i+1] của chuỗi ký tự).

thuat-toan-boyer-moore_1

Tiếp theo, trong lần so sánh thứ 2, vì ký tự P của chuỗi ký tự có xuất hiện trong mẫu tìm kiếm P, và vị trí là 2. Do đó, mình sẽ thực hiện dịch chuyển mẫu cần tìm kiếm sang phải 2 ký tự để sao cho ký tự P của chuỗi ký tự thẳng hàng với ký tự P (xuất hiện lần cuối cùng) của mẫu tìm kiếm.

thuat-toan-boyer-moore_3

Tiếp theo, trong lần so sánh thứ 3, ký tự L có xuất hiện trong mẫu tìm kiếm, do đó, giống như cách làm bên trên, mình sẽ thực hiện dịch chuyển mẫu tìm kiếm sang bên phải 1 vị trí. Và tiếp theo, mình sẽ thực hiện so sánh từng ký tự trong mẫu tìm kiếm P với chuỗi ký tự T.

thuat-toan-boyer-moore_4 thuat-toan-boyer-moore_5 thuat-toan-boyer-moore_6 thuat-toan-boyer-moore_7 thuat-toan-boyer-moore_8

Như vậy, việc so sánh đã thực hiện trên toàn bộ mẫu tìm kiếm P và kết quả trả về là nó trùng khớp với chuỗi ký tự con trong T. Như vậy, mình đã hoàn thành xong việc tìm kiếm chuỗi ký tự bằng giải thuật Boyer-Moore.

Chúng ta cùng thực hiện thêm một ví dụ nữa nhé!

Ví dụ 2: Mình sẽ thực hiện tìm kiếm mẫu APPLE từ chuỗi ký tự RIPPLEAPPLE.

thuat-toan-boyer-moore_9

Trong lần so sánh đầu tiên, vì ký tự L có xuất hiện trong mẫu tìm kiếm P, do đó, mình sẽ dịch chuyển mẫu tìm kiếm sang phải sao cho ký tự L trong mẫu nằm thẳng hàng với ký tự L trong chuỗi ký tự (dịch sang phải 1 ký tự).

thuat-toan-boyer-moore_11 thuat-toan-boyer-moore_12 thuat-toan-boyer-moore_13 thuat-toan-boyer-moore_14

Và mình sẽ thực hiện so sánh từng ký tự trong mẫu tìm kiếm P cho đến khi gặp ký tự A trong mẫu, kết quả là một sự không trùng khớp đã xảy ra, do đó, mình sẽ dịch chuyển mẫu tìm kiếm P sang bên phải 1 vị trí, hay nói cách khác, dịch chuyển sao cho P[0] thẳng hàng với ký tự T[i+1].

thuat-toan-boyer-moore_15

Tiếp theo, mình lại thực hiện so sánh như cách làm bên trên, dịch chuyển mẫu tìm kiếm P sang 4 vị trí để A trong chuỗi ký tự thẳng hàng với ký tự A trong mẫu tìm kiếm P. thuat-toan-boyer-moore_16

thuat-toan-boyer-moore_17 thuat-toan-boyer-moore_18 thuat-toan-boyer-moore_19

Cuối cùng, mình thực hiện so sánh từng ký tự trong mẫu tìm kiếm với chuỗi ký tự con của T và kết quả trả về là sự trùng khớp. Do đó, mình đưa ra thông báo là đã tìm thấy mẫu tìm kiếm P trong chuỗi ký tự T.

5. Trường hợp tệ nhất của thuật toán Boyer-Moore

Thuật toán Boyer-moore trong trường hợp tồi tệ nhất là O(n*m+A). Với A là số lượng chữ cái trong chuỗi ban đầu. Thuật toán này chỉ thực hiện tốt nếu bảng chữ cái A lớn. Bảng chữ cái A càng nhỏ thì tốc độ xử lý thuật toán càng chậm. Vì vậy, không nên sử dụng thuật toán Boyer-Moore cho tệp nhị phân.

Ví dụ cho trường hợp tệ nhất của thuật toán Boyer-Moore:

Trong ví dụ này ta có thể thấy thuật toán Boyer-Moore phải mất tận 24 bước chỉ để in ra kết quả "Không trùng khớp!!!"

Như vậy, chúng ta đã tìm hiểu về thuật toán Boyer-Moore, và cách hoạt động của nó cùng với ví dụ. Hy vọng rằng các bạn đã hiểu được thuật toán và cách hoạt động. Nếu các bạn có thắc mắc hoặc đóng góp ý kiến, các bạn hãy để lại bình luận bên dưới cho mình nhé, rất vui vì được chia sẻ những bài học hay cho các bạn.

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é!

Thuật toán Boyer-Moore trong tìm kiếm xâu con