Trong bài này chúng ta sẽ tìm hiểu thuật toán Rabin-Karp áp dụng trong bài toán tìm kiếm xâu. Thuật toán được phát triển bởi Richard Karp và Michael Rabin [1] vào năm 1987. Ý tưởng trung tâm của thuật toán là coi mỗi xâu là một số nguyên và phép toán so sánh hai xâu được đưa về phép toán so sánh các số nguyên. Trước hết ta nhắc lại bài tìm kiếm xâu:

Biểu diễn xâu kí tự bằng số nguyên

Trước hết chúng ta xét ví dụ: văn bản $T[1,2,\ldots,16] = 4387648576298109$ và xâu mẫu $P[1,2,\ldots, 5] = 57629$. Coi xâu mẫu $P$ là một số nguyên, và thực hiện so sánh $P$ với $T$ theo thứ tự từ trái sang phải. Khi so sánh $T[1,2,3,\ldots,5] = 43876$ với $P$, ta sẽ so sánh hai số nguyên $43876$ và $57629$, thay vì so sánh hai xâu. Tương tự như vậy với các bước tiếp theo. Cuối cùng ta sẽ tìm được $T[8,\ldots, 12] = P[1,\ldots,5]$.

Tổng quát hóa, giả sử $\Sigma = \{0,1,2,\ldots,9\}$, gọi $p$ là số nguyên ứng với mẫu $P$:

$p = \sum_{i=1}^m 10^{m-i}P[i] \qquad (1)$

và $t_s$ là số nguyên ứng với xâu con $T[s,s+1,\ldots, s+m-1]$.

$t_s = \sum_{i=1}^m 10^{m-i}T[s+i-1] \qquad (2)$

Bài toán tìm kiếm xâu trở thành:

Để chuyển $P[1,\ldots,m]$ thành 1 số nguyên, thay vì tính các lũy thừa của 10, ta sẽ sử dụng phương pháp Horner. Ta có:

$p = P[m] + 10(P[m-1] + 10(P[m-2]+ (\ldots + 10\cdot P[1]))\ldots )\qquad (3)$

Đặt:

$B[1] = P[1], B[2] = P[2] + 10\cdot B[1], B[i] = P[i] + 10\cdot B[i-1], \ldots, B[m] = P[m] + 10\cdot B[m-1] $

Suy ra $p = B[m]$. Dựa vào định nghĩa đệ quy của $B[1,2,\ldots,m]$, ta có thể tính $B[m]$ sử dụng $O(m)$, phép toán cơ bản (cộng, trừ, nhân, chia), ta có thể tính được $p$ sử dụng $O(m)$ phép toán cơ bản.

Tương tự, với mỗi chỉ số $s, 1 \leq s \leq n-m+1$, sử dụng phương pháp Horner, ta có thể tính được $t_s$ sử dụng $O(m)$ phép toán cơ bản. Do đó, ta có thể tính tất cả các số $t_1,t_2,\ldots, t_{n-m+1}$ sử dụng $O(m(n-m+1)) = O(mn)$ phép toán cơ bản. Tuy nhiên, đó chưa phải là cách tốt nhất. Nhận thấy $m-1$ chữ số cuối của $t_s$ và $m-1$ chữ số đầu của $t_{s+1}$ giống nhau. Do đó ta có:

$t_{s+1} = 10(t_s - 10^{m-1}T[s]) + T[s+m] \qquad (3)$

Do đó, có thể tính $t_s$ từ $t_{s-1}$ sử dụng $O(1)$ phép toán cơ bản.

Giả mã của thuật toán:

Phân tích thuật toán: Để tính $p$, ta sử dụng $O(m)$ phép toán cơ bản. Tính tất cả các gía trị $t_1,2,\ldots,t_{n-m+1}$, ta sử dụng $O(n)$ phép toán cơ bản. Do đó số phép toán cơ bản là $O(m+n)$. Tuy nhiên, do các số $p,t_1,t_2, \ldots $ có độ dài $m$ chữ số. Do đó, để thực hiện các phép toán cơ bản, ta phải sử dụng $O(m)$ thao tác bít. Do đó tổng thời gian của thuật toán vẫn là $O(m(n+m)) = O(mn)$, không tốt hơn thuật toán trâu bò.

Thuật toán Rabin-Karp

Vấn đề của thuật toán NumberMatcher nằm ở chỗ các số biểu diễn xâu $P[1,2,\ldots,m]$ và các xâu con độ dài $m$ của $T$là các số qúa lớn. Dưới góc nhìn của hàm băm, hàm chuyển đổi xâu $P$ và các xâu con của $T$ thành các số ở trên là một hàm băm. Hàm băm này luôn đảm bảo các xâu con khác nhau độ dài $m$ luôn được băm về các giá trị khác nha. Do đó, giá trị đầu ra của hàm băm là các số rất lớn. Do đó, Karp và Rabin đề xuất nới lỏng tính chất của hàm băm trên:

Hàm băm tốt: Chọn một hàm băm $H$ sao cho $(I)$ các thao tác cơ bản được thực hiện hiệu quả và $(II)$ khi băm hai xâu con khác nhau có cùng độ dài $m$, xác suất hai giá trị băm giống nhau là nhỏ.

Để các thao tác cơ bản được thực hiện hiệu qủa, đầu ra của hàm băm phải là các số nguyên không quá lớn. Thông thường các số nguyên đầu ra có độ lớn được biểu diễn bởi $O(\log m)$ bít được coi là không quá lớn. Trong thực tế, các giá trị này sẽ được chọn sao cho đầu ra có thể biểu diễn được bằng số nguyên $32$ hoặc $64$ bít, do đó các thao tác cơ bản coi như hằng số.

Xác xuất trùng nhau (còn gọi là xác suất đụng độ) của hai giá tri băm của hai xâu con khác nhau độ dài $m$, gọi là $a,b$, được coi là nhỏ nếu:

$\mathrm{Pr}_{a \not= b}[H(a) = H(b)] \leq O(\frac{1}{m}) \qquad (4) $

Giả sử chúng ta đã tìm được hàm băm $H$ tốt, gọi:

$F = \{T_{\mathrm{sub}} |T_\mathrm{sub} \not= P, H(T_\mathrm{sub}) = H(P), |T_{\mathrm{sub}}| = m , T_{\mathrm{sub}}\mbox{ is a substring of } T \}$

$F$ là tập các xâu con của $T$ độ dài $m$ có cùng giá trị băm với $P$. Với mỗi xâu con trong tập $F$, ta sẽ phải so sánh với $P$ (mất thời gian $O(m)$) để kiểm tra xâu con đó có thực sự là $P$ hay không. Do đó, tổng thời gian của thuật toán là $O(n + |F|m)$ trong đó $O(n)$ là thời gian để tính $p,t_1,t_2,\ldots, t_{n-m+1}$ và $O(|F|m)$ là thời gian so sánh $P$ với các xâu con trong $F$. Theo $(4)$, về mặt kì vọng, số lượng các xâu con trong $F$ là:

$\mathrm{E}[|F|] \leq O(n/m)$

Do đó, ta có:

Gọi $H_q : \mathbb{N} \rightarrow \mathbb{Z}_q$ là hàm băm modulo $q$ trong đó $q$ là một số nguyên tố. Karp-Rabin đề xuất chọn hàm băm $H_q$ một cách ngẫu nhiên từ một họ các hàm băm:

$\mathcal{H} = \{H_q | q \mbox{ is a prime number } \leq \lceil m^2\log m\rceil\}$.

Do đầu ra của hàm băm là một số nguyên $\leq q \leq \lceil m^2\log m\rceil$, do đó có thể biểu diễn bằng $\log ( m^2\log m\rceil) = O(\log m)$ bít, thỏa mãn tính chất $(I)$ của hàm băm tốt. Áp dụng hàm băm $H_q$, các thao tác cơ bản đều được lấy theo modulo $q$. Giả mã của thuật toán như sau:

 
Code của giả mã bằng C:

typedef unsigned long long int LLU;

int RabinKarpMatcher(int n, int m){
LLU base = (LLU) 26; // the alphabet is {a,b,c,d,...,z}
LLU q = random_prime((LLU)(1<<30) - 1);// generating a random prime number, assume that m^2 log m <= 2^(30)
LLU p = 0;
LLU Ts[n-m+2];
LLU sig = mod_power(base,m-1,q); // base^(m-1) \mod q
Ts[1] = 0;
int i = 0;
for(i = 1; i <=m; i++){
p = (P[i]-'a' + ((base*p)%q))%q;
Ts[1] = (T[i]-'a'+ ((base*Ts[1])%q))%q;
}
for(i = 1; i <= n-m+1; i++){
if(Ts[i] == p){
if(isequal(i,m)){ // compare T[i,i+1,.., i-m+1] with P[1,2,...,m]
return i;
}
} else {
Ts[i+1] =  ((base*((Ts[i]  - ((sig*(T[i]-'a')) %q) + q) %q))%q + T[i+m]-'a')%q;
}
}
return 0;
}

int isequal(int s, int m){
int i = 1;
while(T[s+i-1] == P[i] && i <= m){
i++;
}
if(i > m) return 1;
else return 0;
}

Tính $10^{m-1} \mod q$ có thể thực hiện nhanh bằng hàm ModPower($a,b,p$) trong bài này.

Phân tích thuật toán: Hàm băm chọn theo thuật toán Rabin-Karp thỏa mãn tính chất $(I)$. Ta chỉ cần chứng minh tính chất $(II)$. Trước hết ta có 2 Claim sau:

Claim 1: Số ước số nguyên tố của một số nguyên $k \geq 2$ ít hơn $\log k$

Thật vậy, gọi $p_1,p_2,\ldots, p_i$ là các ước nguyên tố của $k$, ta có $2^i \leq p_1p_2\cdots p_i \leq k$. Từ đó dễ dàng suy ra Claim 1.

Claim 2 (Prime Number Theorem): Gọi $\pi(x)$ là số lượng các số nguyên tố có độ lớn $\leq x$, ta có $\pi(x) \sim \frac{x}{\ln x}$.

Gọi $x,y$ là gía trị (khi chưa lấy modulo) tương ứng với hai xâu kí tự $a \not= b$độ dài $m$. Do $H_q(a) = H_q(b)$, ta có $x \mod q = y \mod q \Rightarrow (x-y) \mod q = 0$. Hay nói cách khác, $q$ là một ước nguyên tố của $(x-y)$. Do $x,y \leq 10^m$, theo Claim 1, số ước nguyên tố của $x-y$ nhỏ hơn $O(m)$. Theo Claim 2, có $m^2 \log m / \log (m^2 \log m) = O(m^2)$ lựa chọn của $q$ vì $q$ là số nguyên tố $\leq \lceil m^2 \log m \rceil$. Do đó, xác suất chọn $q$ là ước của $x-y$ là:

$\mathrm{Pr}_{a \not = b}[H_q(a) = H_q(b)] \leq O(1/m) $

Như vậy, hàm băm chọn ngẫu nhiên từ họ $\mathcal{H}$ thỏa mãn tính chất $(II)$, do đó theo Theorem 1, thời gian kì vọng của thuật toán Rabin-Karp là $O(m+n)$.

Một số vấn đề thực thi thuật toán

Sinh số nguyên tố $p$ trong đoạn $[2, \lceil m^2\log m\rceil]$ không phải là vấn đề đơn giản. Trong thực tế thực thi, để đơn giản, chúng ta có thể thay bước sinh số nguyên tố $q$ bằng cách chọn cố định một số nguyên tố $q$ đủ lớn. Tất nhiên với cách này về mặt lý thuyết, chúng ta không thể đảm bảo thời gian kì vọng của thuật toán là tuyến tính.

Về mặt lý thuyết, chúng ta có thể sinh số nguyên tố ngẫu nhiên bằng cách sinh một số ngẫu nhiên, kiểm tra nó có phải là số nguyên tố hay không. Nếu không phải là số nguyên tố, ta sẽ thử lại:

Code của giả mã bằng C:

LLU random_prime(LLU N){
LLU q = random64()%(N-2)+2;
while(miller_rabin_testing(10, q) != PRIME){
q = random64()%(N-2)+2;
}
return q;
}

Trước hết phân tích xem thuật toán RandomPrime sẽ dừng sau bao nhiêu phép chọn ngẫu nhiên. Theo Claim 2 (Prime Number Theorem), trong mỗi bước chọn ngẫu nhiên, xác suất chọn được một số nguyên tố là:

$\mathrm{Pr}[q \mbox{ is prime}] = \frac{1}{\log N} $

Do đó, sau $10\log N$ bước, xác suất chọn được một số nguyên tố là:

$\mathrm{Pr}[q \mbox{ is prime}] = 1 - (1 - \frac{1}{\log N})^{10 \log N} \sim 1 - 1/e^{10} > 99,99\%$

Ở công thức trên ta sử dụng xấp xỉ $(1-1/n)^n \sim 1/e$.

Để kiểm tra $q$ có phải là số nguyên tố hay không, ta có thể sử dụng thuật toán Rabin-Miller. Thuật toán Rabin-Miller có độ phức tạp $O(\log^3 N)$, do đó, thuật toán RandomPrime($N$) có thời gian $O(\log^4 N)$. Với $N = \lceil m^2\log m \rceil$, ta có thể sinh số nguyên tố ngẫu nhiên với thời gian $O(\log^4 m)$.

Trong trường hợp các kí tự không phải là các số từ $0$ đến $9$, ta có thể sử dụng cơ số $b $ thay vì $10$, trong đó $ b= |\Sigma|$ là số lượng các kí tự trong bảng chữ cái $\Sigma$. Mọi phân tích với cơ số khác $10$ vẫn không thay đổi.

Tìm tất cả các vị trí xuất hiện

Nếu áp dụng thuật toán Rabin-Karp để tìm kiếm tất cả các vị trí xuất hiện của $P$ trong $T$, thuật toán Rabin-Karp có thời gian kì vọng là $O(n+K\cdot m)$ trong đó $K$ là số lần $P$ xuất hiện trong $T$ do mỗi lần so sánh hai giá trị băm, nếu bằng nhau ta phải mất thời gian $O(m)$ để kiểm tra xem hai xâu có bằng nhau hay không. Trong trường hợp $T[1,2,\ldots,n] = AA\ldots A, P[1,\ldots,m] = AA\ldots A$, thuật toán mất thời gian $O(mn)$. Do đó, để thuật toán có thể được thực hiện nhanh, ta phải chấp nhận lỗi. Có nghĩa là mỗi lần thấy hai gía trị băm bằng nhau, chúng ta sẽ trả về vị trí xuất hiện mà không kiểm tra lại xem hai xâu có bằng nhau thật không.

Để thuật toán có độ chính xác cao , chúng ta phải giảm thiểu lỗi. Một cách để giảm thiểu lỗi là tăng tập lựa chọn của $q$. Ví dụ thay vì chọn $q$ ngẫu nhiên trong khoảng $[2, \lceil m^2\log m \rceil]$, ta chọn $q$ trong khoảng $[2, 2nm\log m]$ trong đó $k \geq 1$. Bằng phân tích như trên, ta sẽ có xác suất đụng độ là $\frac{1}{2n}$ và do đó, số lượng xâu con của $T$ khác $P$ mà có cùng giá trị băm sẽ là $\mathrm{E}[|F|] = n/(2n) = 1/2 < 1$. Cách khác là ta có thể áp dụng vài hàm băm khác nhau cùng một lúc. Mình khuyến khích bạn đọc thử thực thi thuật toán và nộp bài tại đây. Code submit cho bài này mình đính ở cuối bài.

Code: Rabin-Karp, Rabin-Karp-accepted-cdoe.

Tham khảo

[1] Karp, Richard M., and Michael O. Rabin. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development 31.2 (1987): 249-260.
[2] Jeff Erickson, Lecture Notes on String matching, UIUC, 2015.
[3] Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Introduction to Algorithms (2nd ed.), Chapter 32. MIT Press and McGraw-Hill (2001). ISBN 0-262-03293-7