Cỏc thut toỏn tỡm kim xõu ký t
inh Quang Huy
Bi toỏn tỡm kim xõu ký t (string searching, hay ụi khi gi l i sỏnh xõu - string
matching) l mt trong nhng bi toỏn c bn v quan trng trong cỏc thut toỏn x lý v
xõu ký t hay x lý vn bn (text processing). ng dng ca nú c ỏp dng ph bin
trong cỏc trỡnh son tho vn bn hay cỏc chng trỡnh tỡm kim vn bn trờn internet da
vo cỏc t khúa, tt nhiờn thc thi cỏc bi toỏn phc tp ny cn rt nhiu k thut v
cỏch x lý khỏc i kốm. Trong khuụn kh bi bỏo ginh cho hc sinh ph thụng chuyờn
Tin, tụi mun trỡnh by mt s phng phỏp t n gin n phc tp i vi bi toỏn tỡm
kim xõu ký t th loi n gin nht. Hy vng qua bi bỏo cỏc bn cú mt cỏch nhỡn
ton din v sõu sc v bi toỏn ny, trong bi vit tỏc gi cú chỳ thớch mt s thut ng
ting Anh nhm giỳp bn c cú thờm mt s thut ng hay dựng trong tin hc.
1. Phỏt biu bi toỏn
Bi toỏn c phỏt biu mt cỏch n gin nh sau : Tỡm mt (hoc nhiu) v trớ xut hin
cu mt xõu ký t P[1..m] (thng c gi l mt mu tỡm kim - pattern) trong mt
xõu ký t ln hn hay trong mt on vn bn no ú T[1..n], m<=n. Vớ d ta cú th tỡm
thy v trớ ca xõu abc trong xõu abcababc l 1 v 6.
Phỏt biu hỡnh thc bi toỏn nh sau :
Gi l mt tp hu hn (finite set) cỏc ký t. Thụng thng, cỏc ký t ca c mu tỡm
kim v on vn bn gc u nm trong . Tp tựy tng ng dng c th cú th l bng
ch cỏi ting Anh t A n Z thụng thng, cng cú th l mt tp nh phõn ch gm hai
phn t 0 v 1 ( = {0,1}) hay cú th l tp cỏc ký t DNA trong sinh hc ( =
{A,C,G,T}).
Cú rt nhiu cỏch tip cn, trong khuụn kh bi bỏo, tỏc gi mun trỡnh by cỏch tip cn
u tin v n gin nht, sau ú l mt s cỏch tip cn ni ting, cựng vi nhng phõn
tớch v ỏnh giỏ v tng thut toỏn c th.
2. Cỏch tip cn u tiờn
Phng phỏp u tiờn v n gin nht cú th ngh n ngay l ln lt xột tng v trớ i
trong xõu ký t gc t 1 n n-m+1, so sỏnh T[i(i+m-1)] vi P[1..m] bng cỏch xột tng
cp ký t mt v a ra kt qu tỡm kim. Ngi ta cũn gi phng phỏp ny l cỏch tip
cn ngõy th (Naùve string search).

2. hsub := hash(P[1..m]) // giá trị băm của xâu P
3. hs := hash(T[1..m]) // giá trị băm của xâu T
4. for i from 1 to n-m+1
5. if hs = hsub
6. if T[i..i+m-1] = P
7. return i
8. hs := hash(T[i+1..i+m]) // giá trị băm của xâu T[i+1..i+m]
9. return not found
Vấn đề đặt ra ở đây là khi có quá nhiều xâu sẽ tồn tại các trường hợp các xâu khác nhau có
giá trị băm giống nhau, do đó khi tìm thấy hai xâu có giá trị băm giống nhau vẫn phải kiểm
tra lại xem chúng có thực sự bằng nhau hay không (dòng 6), may mắn là trường hợp này
rất ít xảy ra với một hàm băm thiết kế đủ tốt.
Phân tích thuật toán ta thấy : dòng 2,3,6,8 có độ phức tạp là O(m), nhưng dòng 2,3 chỉ thực
hiện duy nhất một lần, dòng 6 chỉ thực hiện khi giá trị băm bằng nhau (rất ít), chủ yếu là
dòng số 8 sẽ quyết định độ phức tạp của thuật toán. Bởi khi tính giá trị băm cho
T[i+1..i+m] ta mất thời gian là O(m), công việc này được thực hiện trong n-m+1 lần như
vậy độ phức tạp không hơn gì so với phương pháp ở phần 2.
Như vậy ta phải tính lại giá trị hs trong thời gian hằng số (constant time), cách giải quyết
ở đây là tính giá trị băm của T[i+1..i+m] dựa vào giá trị băm của T[i..i+m-1] bằng cách sử
dụng cách băm tròn (rolling hash, là cách băm mà giá trị đầu vào được băm với một kích
thước cửa số cổ định trượt trên độ dài của giá trị cần băm). Cụ thể trong bài toán này, ta sử
dụng công thức sau để tính giá trị băm tiếp theo trong một khoảng thời gian hằng số :
hash(T[i+1…i+m]) = hash(T[i+1…i+m-1]) – ASCII(T[i]) + ASCII (T[i+m]), trong đó
ASCII(i) là mã ASCII của ký tự i.
Như vậy trong trường hợp này độ phức tạp chỉ còn là O(n).
Đó là một cách băm đơn giản, dưới đây sẽ trình bày một hàm băm phức tạp và tốt hơn cho
các trường hợp dữ liệu lớn. Đó là sử dụng các số nguyên tố lớn. Ví dụ như xâu “hi” băm
bằng số nguyên tố 101 sẽ có giá trị băm là 104 × 1011 + 105 × 1010 = 10609 (ASCII của
ký tự 'h' là 104 và của ký tự 'í là 105).
Thêm nữa, ta có thể tính giá trị băm của một xâu con dựa vào các xâu con trước nó, ví dụ

m: 01234567890123456789012
T: ABC ABCDAB ABCDABCDABDE
P: ABCDABD
i: 0123456
Ta thấy m=3 và i=3 xâu T và mẫu P không khớp nhau (T[3] = space, P[3] = ‘D’), nên sẽ
dừng so sánh và bắt đầu lại với m=1. Ta chú ý là ký tự đầu tiên của P là ‘A’ không xuất
hiện trong T từ vị trí 0 đến 3 nên ta chuyển đến xét m=4.
+ m=4, i=0
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456
Tại m=10, i=6 xâu T và mẫu P không khớp nhau (T[10] = space, P[6] = ‘D’). Ta lại thấy
chuỗi “AB” trong mẫu P không xuất hiện trong T từ vị trí 5 đến vị trí 7, nên ta chuyển sang
m=8.
+ m=8
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456
Ta thấy trong mẫu không xuất hiện ký tự space, nên chuyển tiếp m=11
+ m=11
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456
Ta thấy m=17 của T không khớp với i=6 của P nên ta xét tiếp m=15
+m=15
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE