Hash: Một Thuật Toán Về Xâu Chuỗi | CODING DIARY

[Le Khac Minh Tue]

1. Giới thiệu:

a. Hoàn cả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.

b. Phát biểu bài toán:

i. Cho một đoạn văn bản, gồm 𝑚 ký tự.

ii. Cho một đoạn mẫu, gồm 𝑛 ký tự.

iii. Máy tính cần trả lời câu hỏi: đoạn mẫu xuất hiện bao nhiêu lần trong đoạn văn bản và chỉ ra các vị trí xuất hiện đó.

c. Thuật toán:

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:

i. Brute-force approach: Với một cách tiếp cận trực tiếp, chúng ta có thể thu được thuật toán để giải. Tuy nhiên độ phực tạp của nó là rất lớn trong trường hợp xấu nhất. Thuật toán brute-force so khớp tất cả các vị trí xuất hiện của đoạn mẫu trong đoạn văn bản. Cụ thể độ phức tạp cho thuật toán này là 𝑂(𝑚𝑛).

ii. Knuth-Morris-Pratt algorithm Hay còn được viết tắt là KMP, được phát minh vào năm 1974, bởi Donald Knuth, Vaughan Pratt và James H. Morris. Thuật toán này sử dụng một correction-array, là một thuật toán rất hiệu quả, có độ phức tạp là 𝑂(𝑚 + 𝑛).

d. Mục đích bài viết:

Trong bài viết này, người viết chỉ tập trung vào một thuật toán. Tác giả xin gọi thuật toán này 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.

2. Thuật toán Hash:

a. Ký hiệu:

i. Tập hợp các chữ cái được sử dụng: Σ.

ii. Đoạn văn bản: 𝑇[1. . 𝑚].

iii. Đoạn mẫu: 𝑃[1. . 𝑛].

iv. Đoạn con từ 𝑖 đến 𝑗 của một xâu 𝑠: 𝑠[𝑖. .𝑗].

v. Chúng ta cần tìm ra tất cả các vị trí 𝑖 (1 ≤ 𝑖 ≤ 𝑚 − 𝑛 + 1) thỏa mãn: 𝑇[𝑖. . 𝑖 + 𝑛 − 1] = 𝑃.

b. Mô tả thuật toán:

Để đơn giản, giả sử rằng Σ = {𝑎, 𝑏, … , 𝑧}, nghĩa là Σ chỉ gồm các chữ cái Latin 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 𝑎𝑐𝑧𝑑 được viết dưới dạng số là một dãy gồm 4 số: (0,2,25,3). Như vậy, một xâu được biểu diễn dưới dạng một số ở hệ cơ số 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.

Đây chính là tư tưởng của thuật toán: đổi 2 xâu từ hệ cơ số 26 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 𝑎 là 𝑥 và biểu diễn trong hệ thập phân của xâu 𝑏 là 𝑦, chúng ta sẽ coi 𝑎 bằng 𝑏 ‘khi và chỉ khi’ 𝑥 𝑚𝑜𝑑 𝑏𝑎𝑠𝑒 = 𝑦 𝑚𝑜𝑑 𝑏𝑎𝑠𝑒, trong đó 𝑏𝑎𝑠𝑒 là một số nguyên đủ lớn.

Dễ dàng nhận thấy việc so sánh 𝑥 𝑚𝑜𝑑 𝑏𝑎𝑠𝑒 với 𝑦 𝑚𝑜𝑑 𝑏𝑎𝑠𝑒 rồi kết luận 𝑎 có bằng với 𝑏 hay không là sai. 𝑥 𝑚𝑜𝑑 𝑏𝑎𝑠𝑒 = 𝑦 𝑚𝑜𝑑 𝑏𝑎𝑠𝑒 chỉ là điều kiện cần để 𝑎 bằng 𝑏 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ó những lúc dẫn đến so sánh xâu không chính xác và chương trình bị chạy ra kết quả sai. Nhưng cũng thực tế cho thấy rằng, khi chọn 𝑏𝑎𝑠𝑒 là một số nguyên lớn, số lượng những trường hợp sai rất ít, và ta có thể coi Hash là một thuật toán chính xác.

Để đơ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 𝑏𝑎𝑠𝑒 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 𝑃 xuất hiện ở những vị trí nào trong 𝑇. Để 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 𝑃 trong 𝑇. Giả sử vị trí đó là 𝑖, chúng ta sẽ kiểm tra 𝑇[𝑖. . 𝑖 + 𝑛 − 1] có bằng với 𝑃 hay không. Để kiểm tra điều này, chúng ta cần tính được mã Hash của đoạn 𝑇[𝑖. . 𝑖 + 𝑛 − 1] và mã Hash của xâu 𝑃.

Để tính mã Hash của xâu 𝑃 chúng ta chỉ cần làm đơn giản như sau:

hashP = 0 for (i : 1 .. n) hashP = (hashP * 26 + P[i] - 'a') mod base

Phần khó hơn của thuật toán Hash là: Tính mã Hash của một đoạn con từ 𝑖 đến 𝑗 𝑇[𝑖. .𝑗] của xâu 𝑇 (1 ≤ 𝑖 ≤ 𝑗 ≤ 𝑚).

Để hình dung cho đơn giản, xét ví dụ sau: Xét xâu 𝑠 và biểu diễn của nó dưới cơ số 26: (4,1,2,5,1,7,8). Chúng ta cần lấy mã Hash của đoạn con từ phần tử thứ 3 đến phần tử thứ 6, nghĩa là cần lấy mã Hash của xâu (2,5,1,7). Nhận thấy, để lấy được xâu 𝑠[3. .6], chỉ cần lấy số 𝑠[1. .6] là (4,1,2,5,1,7) trừ cho số (𝑠[1. .2] nối thêm (0,0,0,0)) là (4,1,0,0,0,0) ta sẽ thu được (2,5,1,7). Tương tự, để lấy được mã Hash của xâu 𝑠[3. .6], chỉ cần lấy mã Hash của 𝑠[1. .6]trừ đi (mã Hash của 𝑠[1. .2] nhân với 26^4 ). Để cài đặt ý tưởng này, chúng ta cần khởi tạo 26^𝑥 𝑚𝑜𝑑 𝑏𝑎𝑠𝑒 (0 ≤ 𝑥 ≤ 𝑚) và mã Hash của tất cả những tiền tố của 𝑠, cụ thể là mã Hash của những xâu 𝑠[1. . 𝑖] (1 ≤ 𝑖 ≤ 𝑚).

pow[0] = 1 for (i : 1 .. m) pow[i] = (pow[i-1] * 26) mod base hashT[0] = 0 for (i : 1 .. m) hashT[i] = (hashT[i-1] * 26 + T[i] - 'a') mod base

Trên đoạn code trên, chúng ta thu được mảng 𝑝𝑜𝑤[𝑖] (lưu lại 26^𝑖 𝑚𝑜𝑑 𝑏𝑎𝑠𝑒) và mảng ℎ𝑎𝑠ℎ𝑇[𝑖] (lưu lại mã Hash của 𝑇[1. . 𝑖]).

Để lấy mã Hash của 𝑇[𝑖. .𝑗] ta viết hàm sau:

function getHashT(i, j): return (hashT[j] - hashT[i - 1] * pow[j - i + 1] + base * base) mod base

Bà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)

c. Mã chương trình:

Chương trình sau, tôi viết bằng ngôn ngữ C++, là lời giải cho bài 𝑆𝑈𝐵𝑆𝑇𝑅 trên hệ thống chấm bài trực tuyến VOJ.

#include <iostream> #include <cstdio> #include <cstring> #define FOR(i,a,b) for(int i=a;i<=b;i++) #define base 1000000003LL #define ll long long #define 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]+base*base)%base; } int main() { string T,P; cin >> T >> P; int m=T.size(),n=P.size(); T=" "+T;P=" "+P; POW[0]=1; FOR(i,1,m) POW[i]=(POW[i-1]*26) % base; FOR(i,1,m) hashT[i]=(hashT[i-1]*26+T[i]-'a') % base; ll hashP=0; FOR(i,1,n) hashP=(hashP*26+P[i]-'a') % base; FOR(i,1,m-n+1) if(hashP==getHashT(i,i+n-1)) printf("%d ",i); }

d. Đánh giá:

Độ phức tạp của thuật toán là 𝑂(𝑚 + 𝑛). 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 𝑂(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.

3. Ứng dụng:

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.

a. Longest palindrome substring

Bài toán đặt ra như sau: Bạn được cho một xâu 𝑠 độ dài 𝑛 (𝑛 ≤ 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 𝑠. (Xâu đối xứng là xâu đọc từ 2 chiều giống nhau).

Một ‘thuật toán chuẩn’ không thể áp dụng vào bài toán này đó là thuật toán KMP. Ngoài KMP ra, có 2 ‘thuật toán chuẩn’ có thể áp dụng được. Thuật toán thứ nhất đó là sử dụng thuật toán Manachar để tính bán kính đối xứng tại tất cả vị trí trong xâu. Thuật toán thứ 2 đó là sử dụng Suffix Array và LCP (Longest Common Prefix) cho xâu được nối bởi 𝑠 và xâu s viết theo thứ tự ngược lại. 2 thuật toán này đều không dễ dàng để cài đặt, và nằm ngoài phạm vi bài viết, nên tôi chỉ nêu sơ qua mà không đi vào chi tiết.

Bây giờ, chúng ta sẽ xét thuật toán ‘không chuẩn’ là thuật toán Hash. Để đơn giản, chúng ta xét trường hợp độ dài của xâu đối xứng là lẻ (trường hợp chẵn xử lý hoàn toàn tương tự). Giả sử xâu đối xứng độ dài lẻ dài nhất có độ dài là 𝑙. Dễ thấy, trong xâu 𝑠 tồn tại xâu đối xứng độ dài 𝑙 − 2, 𝑙 − 4, … Tuy nhiên, xâu 𝑠 không tồn tài xâu đối xứng độ dài 𝑙 + 2,𝑙 + 4, … Như vậy, 𝑙 thỏa mãn tính chất chia nhị phân. Chúng ta sẽ chia nhị phân để tìm độ dài lớn nhất có thể. Với mỗi độ dài 𝑙, chúng ta cần kiểm tra xem trong xâu có tồn tại một xâu con là xâu đối xứng độ dài 𝑙 hay không. Để làm việc này, ta duyệt qua tất cả tất cả các xâu con độ dài 𝑙 trong 𝑠.

Bài toán còn lại là: kiểm tra xem 𝑠[𝑖. .𝑗](1 ≤ 𝑖 ≤ 𝑗 ≤ 𝑛; (𝑗 − 𝑖 + 1) 𝑚𝑜𝑑 2 = 1) có phải là xâu đối xứng hay không.

Cách làm như sau. Gọi 𝑡 là xâu 𝑠 viết theo thứ tự ngược lại. Bằng thuật toán Hash, chúng ta có thể kiểm tra được một xâu con nào đó của 𝑡 có bằng một xâu con nào đó của 𝑠 hay không. Như vậy, chúng ta cần kiểm tra 𝑠[𝑖. . 𝑘] có bằng 𝑡[𝑛 − 𝑗 + 1. . 𝑛 − 𝑘 + 1] hay không với 𝑘 là tâm đối xứng, nói cách khác 𝑘 = 𝑖+𝑗 2 . Như vậy bài toán đã được giải. Độ phức tạp cho cách làm này là 𝑂(𝑛 log(𝑛)).

b. k-th alphabetical cyclic

Bài toán đặt ra như sau: Bạn được cho một dãy 𝑎1, 𝑎2, … , 𝑎𝑛 (𝑛 ≤ 50 000). Sắp xếp 𝑛 hoán vị vòng quanh 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à (𝑎1, 𝑎2, … , 𝑎𝑛 ), (𝑎2, 𝑎3, … , 𝑎𝑛, 𝑎1 ), (𝑎3, 𝑎4, … , 𝑎𝑛, 𝑎1, 𝑎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ứ 𝑘.

Nếu tiếp cận một cách trực tiếp, chúng ta sẽ sinh ra tất cả các dãy hoán vị vòng quanh, rồi sau đó dùng một thuật toán sắp xếp để sắp xếp lại chúng theo thứ tự từ điển, cuối cùng chỉ việc in ra dãy thứ 𝑘 sau khi sắp xếp. Tuy nhiên độ phức tạp của thuật toán này là rất lớn và không thể đáp ứng được yêu cầu về thời gian. Cụ thể, cách này có độ phức tạp là 𝑂(𝑛 2 ∗ log(𝑛)), đây là tích của độ phức tạp của sắp xếp và độ phức tạp của mỗi phép so sánh dãy.

Vẫn giữ tư tưởng là sắp xếp lại tất cả các dãy hoán vị vòng quanh rồi in ra dãy đứng ở vị trí thứ 𝑘, chúng ta cố gắng cải tiến độ phức tạp của việc so sánh thứ tự từ điển của 2 dãy.

Nhắc lại định nghĩa về thứ tự từ điển của 2 dãy: Xét 2 dãy 𝑎 và 𝑏 có cùng số phần tử. Gọi ví trí thứ 𝑖 là vị trí đầu tiên từ trái sang mà 𝑎𝑖 ≠ 𝑏𝑖 . 𝑎 < 𝑏 ↔ 𝑎𝑖 < 𝑏𝑖 . Như vậy, ta phải tìm đoạn tiền tố giống nhau dài nhất của 𝑎 và 𝑏, rồi so sánh kí tự tiếp theo. Để tìm được đoạn tiền tố giống nhau dài nhất, ta có thể sử dụng Hash kết hợp với chia nhị phân.

Để giải được bài này, cần sử dụng thêm một kỹ thuật nhỏ nữa: Thay vì sinh ra tất cả các hoán vị vòng quanh, chúng ta chỉ cần nhân đôi dãy a lên, dãy mới sẽ có 2 ∗ 𝑛 phần tử (𝑎1, 𝑎2, … , 𝑎𝑛, 𝑎1, 𝑎2, … , 𝑎𝑛 ). Một hoán vị vòng quanh sẽ là một dãy con liên tiếp độ dài 𝑛 của dãy nhân đôi này.

c. Longest substring and appear at least k times

Bài toán đặt ra như sau: Bạn được cho xâu 𝑠 độ dài 𝑛 (𝑛 ≤ 50000), bạn cần tìm ra xâu con của 𝑠 có độ dài lớn nhất, và xâu con này xuất hiện ít nhất 𝑘 lần.

Bài toán này có thể được giải bằng Suffix Array, tuy nhiên cách cài đặt phức tạp và không phải trọng tâm của bài viết nên tôi sẽ không nêu ra ở đây.

Tiếp tục bàn đến thuật toán Hash để thay thế thuật toán chuẩn. Nhận xét rằng, giả sử độ dài lớn nhất tìm được là 𝑙, thì với mọi 𝑙 ′ ≤ 𝑙, luôn tồn tại xâu có độ dài 𝑙′ xuất hiện ít nhất 𝑘 lần. Tuy nhiên, với mọi 𝑙 ′ > 𝑙, không tồn tại xâu có độ dài 𝑙′ xuất hiện ít nhất 𝑘 lần (do 𝑙 đã là lớn nhất). Như vậy, 𝑙 thỏa mãn tính chất chia nhị phân. Chúng ta có thể áp dụng thuật toán tìm kiếm nhị phân để tìm ra 𝑙 lớn nhất.

Bây giờ, với mỗi 𝑙 khi đang chia nhị phân, chúng ta sẽ phải kiểm tra liệu có tồn tại xâu con nào xuất hiện ít nhất 𝑘 lần hay không. Điều này được làm rất đơn giản, bằng cách sinh mọi mã Hash của các xâu con độ dài 𝑙 trong 𝑠. Sau đó sắp xếp lại các mã Hash này theo chiều tăng dần, rồi kiếm tra xem có một đoạn liên tiếp các mã Hash nào giống nhau độ dài 𝑘 hay không.

Như vậy, độ phức tạp để chia nhị phân là 𝑂(log(𝑛)), độ phức tạp của sắp xếp là 𝑂(𝑛 log(𝑛)), vậy độ phức tạp của cả bài toán là 𝑂(𝑛 log(𝑛) 2 ).

4. Tổng kết:

a. Thuật toán:

Ý 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.

b. Ưu điểm:

Ư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.

c. Nhược điểm:

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).

Chia sẻ:

• X
• Facebook

Like Loading...

Related