Tác giả: Lê Khắc Minh Tuệ
Chỉnh sửa: Nguyễn RR Thành Trung, Phạm Văn Hạnh
Một lớp những bài toán rất được quan tâm trong khoa học máy tính nói chung và lập trình thi cử nói riêng, đó là xử lý xâu chuỗi. Trong lớp bài toán này, người ta thường rất hay phải đối mặt với một bài toán: tìm kiếm xâu chuỗi.
Có rất nhiều thuật toán có thể giải quyết bài toán này. Người viết xin tóm tắt 2 thuật toán phổ biến được dùng trong các kì thi lập trình:
Trong bài viết này, người viết chỉ tập trung vào thuật toán Hash (Tên chuẩn của thuật toán này là Rabin–Karp hoặc Rolling Hash, tuy nhiên ở Việt Nam thường được gọi là Hash). Theo như bản thân người viết đánh giá, đây là thuật toán rất hiệu quả đặc biệt là trong thi cử. Nó hiệu quả bởi 3 yếu tố: tốc độ thực thi, linh động trong việc sử dụng (ứng dụng hiệu quả) và sự đơn giản trong cài đặt.
Đầu tiên, người viết xin được trình bày về thuật toán này. Sau đó, người viết sẽ trình bày một vài ứng dụng, cách sử dụng và phát triển thuật toán Hash trong các bài toán tin học.
Chúng ta cần tìm ra tất cả các vị trí $i (1 \le i \le m − n + 1)$ thỏa mãn: $T[i..i+n−1] = P$.
Để đơn giản, giả sử rằng $\Sigma = {a, b, …, z}$ (nói cách khác, $\Sigma$ chỉ gồm các chữ cái in thường). Để biểu diễn một xâu, thay vì dùng chữ cái, chúng ta sẽ chuyển sang biểu diễn dạng số. Ví dụ: xâu aczd được viết dưới dạng số là một dãy gồm 4 số: (1,3,26,4). Như vậy, một xâu được biểu diễn dưới dạng một số ở hệ cơ số $base$ với $base > 26$. Từ đây suy ra, 2 xâu bằng nhau khi và chỉ khi biểu diễn của 2 xâu ở hệ cơ số 10 giống nhau.
Lưu ý:
a thành số 1 chứ không phải số 0. Đây là chi tiết vô cùng quan trọng, để tránh 2 xâu: abc và bc bằng nhau khi đổi ra số. Bạn có thể đọc thêm chi tiết ở phần Chi tiết cài đặt.Đây chính là tư tưởng của thuật toán: đổi 2 xâu từ hệ cơ số $base$ ra hệ cơ số 10, rồi đem so sánh ở hệ cơ số 10. Tuy nhiên, chúng ta nhận thấy rằng, khi đổi 1 xâu ra biểu diễn ở hệ cơ số 10, biểu diễn này có thể rất lớn và nằm ngoài phạm vi lưu trữ số nguyên của máy tính.
Để khắc phục điều này, chúng ta chuyển sang so sánh 2 biểu diễn của 2 xâu ở hệ cơ số 10 sau khi lấy phần dư cho một số nguyên đủ lớn. Cụ thể hơn: nếu biểu diễn trong hệ thập phân của xâu $a$ là $x$ và biểu diễn trong hệ thập phân của xâu $b$ là $y$, chúng ta sẽ coi $a$ bằng $b$ ‘khi và chỉ khi’ $x \bmod MOD = y \bmod MOD$ trong đó $MOD$ là một số nguyên đủ lớn.
Lưu ý: Lý do chọn $MOD$ là số nguyên tố được giải thích thêm trong phần Chi tiết cài đặt.
Dễ dàng nhận thấy việc so sánh $x \bmod MOD$ với $y \bmod MOD$ rồi kết luận $a$ có bằng với $b$ hay không là sai. $x \bmod MOD = y \bmod MOD$ chỉ là điều kiện cần để $a$ bằng $b$ chứ chưa phải điều kiện đủ. Tuy nhiên, chúng ta sẽ chấp nhận lập luận sai này trong thuật toán Hash. Và coi điều kiện cần như điều kiện đủ. Trên thực tế, lập luận sai này có thể dẫn đến kết quả sai nếu bạn không hiểu rõ mình đang làm gì. Để hiểu rõ về tỉ lệ sai của thuật toán Hash, các bạn đọc thêm phần Đánh giá độ chính xác. Phần Chi tiết cài đặt cũng nói thêm về cách tránh bị sai số khi cài đặt Hash.
Để đơn giản trong việc trình bày tiếp thuật toán, chúng ta sẽ gọi biểu diễn của một xâu trong hệ thập phân sau khi lấy phần dư cho $MOD$ là mã Hash của xâu đó. Nhắc lại, 2 xâu bằng nhau ‘khi và chỉ khi’ mã Hash của 2 xâu bằng nhau.
Trở lại bài toán ban đầu, chúng ta cần chỉ ra $P$ xuất hiện ở những vị trí nào trong $T$. Để làm được việc này, chúng ta chỉ cần duyệt qua mọi vị trí xuất phát có thể của $P$ trong $T$. Giả sử vị trí đó là $i$, chúng ta sẽ kiểm tra $T[i..i+n−1]$ có bằng với $P$ hay không. Để kiểm tra điều này, chúng ta cần tính được mã Hash của đoạn $T[i..i+n−1]$ và mã Hash của xâu $P$.
Để tính mã Hash của xâu $P$ chúng ta chỉ cần làm đơn giản như sau:
const base = 31;
hashP = 0
for (i : 1 .. n)
hashP = (hashP * base + P[i] - 'a' + 1) mod MODPhần khó hơn của thuật toán Hash là: Tính mã Hash của một đoạn con $T[i..j]$ của xâu $T$ $(1 \le i \le j \le N)$.
pow[0] = 1
for (i : 1 .. m)
pow[i] = (pow[i-1] * base) mod MOD
hashT[0] = 0
for (i : 1 .. m)
hashT[i] = (hashT[i-1] * base + T[i] - 'a') mod MOD
Trong đoạn code trên, chúng ta thu được mảng $pow[i]$ (lưu lại $base^i \bmod MOD$) và mảng $hashT[i]$ (lưu lại mã Hash của $T[1..i]$).
function getHashT(i, j):
// Chú ý rằng `- hashT[i - 1] * pow[j - i + 1]` có thể âm.
// Với 1 số ngôn ngữ như C++, toán tử mod sẽ trả kết quả sai với số âm.
// Do đó ta cần thêm "+ MOD * MOD" để đảm bảo kết quả luôn chính xác.
return (hashT[j] - hashT[i - 1] * pow[j - i + 1] + MOD * MOD) mod MODBài toán chính đã được giải quyết, và đây là chương trình chính:
for (i : 1 .. m - n +1)
if hashP = getHashT(i, i + n - 1):
print("Match position: ", i)Chương trình sau, tôi viết bằng ngôn ngữ C++, là lời giải cho bài SUBSTR:
typedef long long ll;
const int base = 31;
const ll MOD = 1000000003;
const ll maxn = 1000111;
using namespace std;
ll POW[maxn], hashT[maxn];
ll getHashT(int i,int j) {
return (hashT[j] - hashT[i - 1] * POW[j - i + 1] + MOD * MOD) % MOD;
}
int main() {
// Input
string T, P;
cin >> T >> P;
// Initialize
int lenT = T.size(), lenP = P.size();
T = " " + T;
P = " " + P;
POW[0] = 1;
// Precalculate base^i
for (int i = 1; i <= lenT; i++)
POW[i] = (POW[i - 1] * base) % MOD;
// Calculate hash value of T[1..i]
for (int i = 1; i <= lenT; i++)
hashT[i] = (hashT[i - 1] * base + T[i] - 'a' + 1) % MOD;
// Calculate hash value of P
ll hashP=0;
for (int i = 1; i <= lenP; i++)
hashP = (hashP * base + P[i] - 'a' + 1) % MOD;
// Finding substrings of T equal to string P
for (int i = 1; i <= lenT - lenP + 1; i++)
if (hashP == getHashT(i, i + lenP - 1))
printf("%d ", i);
}Độ phức tạp của thuật toán là $O(m + n)$. Nhưng điều quan trọng là: chúng ta có thể kiểm tra 2 xâu có giống nhau hay không trong $O(1)$. Đây là điều tạo nên sự linh động cho thuật toán Hash. Ngoài sự linh động và tốc độ thực thi, chúng ta có thể thấy cài đặt thuật toán này thực sự rất đơn giản nếu so với các thuật toán xử lý xâu khác.
Trong thuật toán hash, có hai yếu tố cần quan tâm là hệ cơ số (base) và modulo (mod).
Ý tưởng của thuật toán Hash là dựa trên một ngộ nhận sai lầm nhưng xảy ra sai sót với xác suất vô cùng nhỏ: $a \bmod M = b \bmod M <=> a = b$. Để xác suất xảy ra sai là $1/M$ cho một truy vấn, các bạn cần chọn hệ cơ số và modulo thỏa mãn đồng thời:
S.Phần chứng minh sai số bạn có thể đọc thêm trong blog rng_58, tuy nhiên phần chứng minh rất phức tạp nên mình sẽ không trình bày ở đây.
Mình khuyến khích các bạn chọn hệ cơ số > 256 (Mình thường chọn là số nguyên tố 311). Nếu bạn chọn hệ cơ số là 31, bạn chỉ làm việc với xâu gồm toàn các kí tự in thường, và phải "mã hóa" các kí tự từ a đến z thành các số từ 1 đến 26. Điều này khiến code của bạn bị dài. Nếu bài toán cho xâu có các kí tự 'A'…'Z', 'a'..'z' và '0'…'9', việc bạn mã hóa chúng thành các số từ 1 đến 64 là phức tạp và không cần thiết.
Chưa kể, nếu bạn quên mất không +1 và mã hoá a thành 0 là hành động tự treo cổ vì rất dễ bị hack.
Nếu bạn chọn hệ cơ số > 256, bạn chỉ cần dùng mã ASCII của các kí tự là xong, và lại tránh bị hack.
Nếu bạn không hiểu rõ về cách đánh giá độ chính xác của thuật Hash (trình bày ở mục Đánh giá độ chính xác), bạn chỉ cần chọn 3-4 số nguyên tố khác nhau làm $MOD$. Bạn có thể tham khảo code của Phạm Văn Hạnh. Tuy nhiên các bạn cũng nên lưu ý là dùng nhiều $MOD$ quá cũng làm chương trình chạy chậm đi.
Trên thực tế, khi cài đặt Hash sử dụng nhiều phép mod sẽ làm chương trình chạy chậm. Vì vậy, để tăng tốc độ, người ta thường cài đặt với $MOD = 2^{64}$. Do đó, nếu sử dụng kiểu dữ liệu số 64-bit, ta không cần dùng phép mod mà cứ để các phép tính tràn số. Kĩ thuật này được gọi là Hash tràn số. Tuy nhiên khi cài đặt như vậy có một vài chú ý:
$Q-), nếu không chương trình sẽ chạy bị lỗi.Chỉ so sánh mã hash của hai xâu có cùng độ dài. Hiển nhiên, hai xâu kí tự không cùng độ dài thì không bằng nhau. Điều này có thể giảm xác suất rủi ro khi hash một modulo đáng kể.
Như đã đề cập ở trên, thuật toán này sẽ có trường hợp chạy sai. Tất nhiên, bên cạnh việc sử dụng Hash, còn có nhiều thuật toán xử lý xâu chuỗi khác, mang lại sự chính xác tuyệt đối. Tôi tạm gọi những thuật toán đó là ‘thuật toán chuẩn’. Việc cài đặt ‘thuật toán chuẩn’ có thể mang lại một tốc độ chạy chương trình cao hơn, độ chính xác của chương trình lớn hơn. Tuy nhiên, người làm bài sẽ phải trả giá là sự phức tạp khi cài đặt các ‘thuật toán chuẩn’ đó.
Sử dụng Hash không chỉ giúp người làm bài dễ dàng cài đặt hơn mà quan trọng ở chỗ: Hash có thể làm được những việc mà ‘thuật toán chuẩn’ không làm được. Sau đây, tôi sẽ xét một vài ví dụ để chứng minh điều này.
Bài toán đặt ra như sau: Bạn được cho một xâu $s$ độ dài $n (n \le 50,000)$. Bạn cần tìm độ dài của xâu đối xứng dài nhất gồm các kí tự liên tiếp trong $s$. (Xâu đối xứng là xâu đọc từ 2 chiều giống nhau).
Bài toán đặt ra như sau: Bạn được cho một dãy $a_1, a_2,… , a_n (n \le 50,000)$. Sắp xếp $n$ hoán vị vòng tròn của dãy này theo thứ tự từ điển. Cụ thể, các hoán vị vòng quanh của dãy này là $(a_1, a_2,… , a_n)$, $(a_2, a_3, …, a_n, a_1)$, $(a_3, a_4, …, a_n, a_1, a_2)$,… Dãy này có thứ tự từ điển nhỏ hơn dãy kia nếu số đầu tiên khác nhau của dãy này nhỏ hơn dãy kia. Yêu cầu bài toán là: In ra dãy có thứ tự từ điển lớn thứ $k$.
Từ đó ta thu được thuật toán với độ phức tạp $O(n*log^2(n))$
Bài toán đặt ra như sau: Bạn được cho xâu $s$ độ dài $n (n \le 50,000)$, bạn cần tìm ra xâu con của $s$ có độ dài lớn nhất, và xâu con này xuất hiện ít nhất $k$ lần.
Thông thường, khi sử dụng Hash, ta thường gặp phải 2 trường hợp như sau:
Giả sử ta chọn $MOD$ là một số nguyên tố khoảng $10^9$, và giả sử dữ liệu được sinh ngẫu nhiên và hàm hash của chúng ta đủ tốt để Hash của các xâu được phân bố đều và ngẫu nhiên.
Giả sử $Q$ khoảng $10^5$, và bộ test có $T = 100$ test.
Thay số vào, xác suất để trả lời đúng tất cả các truy vấn là $0.9900$, đủ lớn để ta yên tâm qua tất cả các test, với điều kiện test không được sinh dựa trên $P$. (Chú ý nếu bạn đang thi những contest như Topcoder/Codeforces, người khác có thể đọc được $P$ của bạn và sinh test để challenge code của bạn).
Theo Birthday Paradox, ta dễ dàng thấy rằng, nếu có $\sqrt{P} = 3*10^4$ xâu, xác suất để 2 xâu bằng nhau là rất lớn. Thật vậy, xác suất để tất cả các xâu khác nhau là:
$(1 - 1 / 10^9) * (1 - 2 / 10^9) * (1 - 3 / 10^9) * … (1 - N / 10^9)$.
Với $N = 30,000$, tích trên là $0.6376$, nghĩa là bạn có gần $0.40$ xác suất trả lời sai. Do vậy, bạn bắt buộc phải dùng nhiều $MOD$ khác nhau.
Ý tưởng thuật toán Hash dựa trên việc đổi từ hệ cơ số lớn sang hệ thập phân, so sánh hai số thập phân lớn bằng cách so sánh phần dư của chúng với một số đủ lớn.
Khi cài đặt Hash, ta cần chọn:
Với những trang web mà người khác có thể đọc code bạn rồi tìm test sai (như Codeforces, Topcoder), nếu Hash tràn số hoặc MOD là 1 số nguyên biết trước, có thể sinh test để làm code bạn sai. Với những kỳ thi như HSG QG, IOI, ACM, và các Online Judge, thông thường sẽ không có những test như vậy. Tóm lại, khi chọn $MOD$ và hệ cơ số ta làm như sau:
Ưu điểm của thuật toán Hash là cài đặt rất dễ dàng. Linh động trong ứng dụng và có thể thay thế các thuật toán chuẩn ‘hầm hố’ khác.
Nhược điểm của thuật toán Hash là tính chính xác. Mặc dù rất khó sinh test để có thể làm cho thuật toán chạy sai, nhưng không phải là không thể. Vì vậy, để nâng cao tính chính xác của thuật toán, người ta thường dùng nhiều modulo khác nhau để so sánh mã Hash (ví dụ như dùng 3 modulo một lúc).