4/14/2011
1
Strings and Strings and
Pattern Matching Pattern Matching
Dương Anh Đức Dương Anh Đức –– Nhập môn Cấu trúc Dữ liệu và Giải thuậtNhập môn Cấu trúc Dữ liệu và Giải thuật
22
Strings and Strings and
Pattern Matching Pattern Matching
 Brute Force, Brute Force,
RabinRabin Karp, Karp,
KnuthKnuth MorrisMorris PrattPratt
 RegularRegular ExpressionsExpressions
4/14/2011
2
Dương Anh Đức Dương Anh Đức –– Nhập môn Cấu trúc Dữ liệu và Giải thuậtNhập môn Cấu trúc Dữ liệu và Giải thuật
33
BàiBài tốntốn tìmtìm kiếmkiếm chuỗichuỗi kýký tựtự
 ĐốiĐối tượngtượng củacủa bàibài tốntốn stringstring searchingsearching làlà tìmtìm
kiếmkiếm vịvị trítrí củacủa mộtmột mẫumẫu vănvăn bảnbản (text(text pattern)pattern)
trongtrong nộinội dungdung mộtmột vănvăn bảnbản lớnlớn hơnhơn (một(một câu,câu,
mộtmột đoạnđoạn hayhay mộtmột quyểnquyển sách,sách, ……))
 CũngCũng nhưnhư phầnphần lớnlớn cáccác thuậtthuật tốntốn khác,khác, quanquan tâmtâm
chínhchính củacủa stringstring searchingsearching làlà tốctốc độđộ vàvà hiệuhiệu quảquả
 CóCó nhiềunhiều thuậtthuật tốntốn tìmtìm kiễmkiễm chuỗichuỗi kýký tựtự kháckhác
nhaunhau TuyTuy nhiênnhiên,, chúngchúng tata sẽsẽ chỉchỉ khảokhảo sátsát baba thuậtthuật
tốntốn làlà:: BruteBrute ForceForce,, RabinRabin KarpKarp vàvà KnuthKnuth
MorrisMorris PrattPratt
Dương Anh Đức Dương Anh Đức –– Nhập môn Cấu trúc Dữ liệu và Giải thuậtNhập môn Cấu trúc Dữ liệu và Giải thuật
44
ThuậtThuật tốntốn Brute Force Brute Force
 ThuậtThuật tốntốn BruteBrute ForceForce soso sánhsánh mẫumẫu tìmtìm kiếmkiếm vớivới

 ĐộĐộ phứcphức tạptạp củacủa thuậtthuật tốntốn BruteBrute ForceForce:: GiảGiả
sửsử kíchkích thướcthước củacủa mẫumẫu làlà MM kýký tựtự vàvà texttext cócó
NN kýký tựtự
 TrườngTrường hợphợp xấuxấu nhấtnhất:: soso sánhsánh mẫumẫu vớivới mọimọi
chuỗichuỗi concon chiềuchiều dàidài MM trongtrong texttext
 TổngTổng sốsố phépphép soso sánhsánh:: MM (N(N M+M+11))
 ĐộĐộ phứcphức tạptạp trongtrong trườngtrường hợphợp xấuxấu nhấtnhất ::
O(MN)O(MN)
4/14/2011
5
DươngDương AnhAnh ĐứcĐức –– NhậpNhập mônmôn CấuCấu trúctrúc DữDữ liệuliệu vàvà GiảiGiải thuậtthuật
99
Thuật toán Brute Force Thuật toán Brute Force
 ĐộĐộ phứcphức tạptạp củacủa thuậtthuật tốntốn BruteBrute ForceForce:: GiảGiả sửsử
kíchkích thướcthước củacủa mẫumẫu làlà MM kýký tựtự vàvà texttext cócó NN kýký
tựtự
 TrườngTrường hợphợp tốttốt nhấtnhất 11:: mẫumẫu xuấtxuất hiệnhiện ngayngay đầuđầu
texttext
 ĐộĐộ phứcphức tạptạp trongtrong trườngtrường hợphợp tốttốt nhấtnhất 11:: O(M)O(M)
 TrườngTrường hợphợp tốttốt nhấtnhất 22:: mẫumẫu khơngkhơng xuấtxuất hiệnhiện
trongtrong texttext
 ĐộĐộ phứcphức tạptạp trongtrong trườngtrường hợphợp tốttốt nhấtnhất 22:: O(N)O(N)
Dương Anh Đức Dương Anh Đức –– Nhập môn Cấu trúc Dữ liệu và Giải thuậtNhập môn Cấu trúc Dữ liệu và Giải thuật
1010
VíVí dụdụ, , vớivới M=5 M=5 tata cócó víví dụdụ sausau: :
4/14/2011
6
Dương Anh Đức Dương Anh Đức –– Nhập môn Cấu trúc Dữ liệu và Giải thuậtNhập môn Cấu trúc Dữ liệu và Giải thuật
1111
ThuậtThuật tốntốn RabinRabin Karp Karp

 MẫuMẫu cócó chiềuchiều dàidài MM kýký tựtự
 hash_phash_p == giágiá tròtrò bămbăm củacủa mẫumẫu
 hash_thash_t == giágiá tròtrò bămbăm củacủa MM kýký tựtự đầầu trongtrong texttext
dodo
ifif ((hash_phash_p ==== hash_thash_t))
SoSo sánhsánh brutebrute forceforce giữagiữa mẫumẫu vàvà chuỗichuỗi concon
hash_thash_t == giágiá tròtrò bămbăm củacủa MM kýký tựtự kếkế trongtrong texttext
untiluntil (kết(kết thúcthúc texttext hoặchoặc kếtkết quảquả soso sánhsánh ==== true)true)
Dương Anh Đức Dương Anh Đức –– Nhập môn Cấu trúc Dữ liệu và Giải thuậtNhập môn Cấu trúc Dữ liệu và Giải thuật
1616
ThuậtThuật tốntốn RabinRabin KarpKarp
 NhữngNhững câucâu hỏihỏi chungchung củacủa RabinRabin KarpKarp::
 ChọnChọn hàmhàm bămbăm nàonào đểđể tínhtính giágiá trịtrị băm?băm?
 CóCó tốntốn nhiềunhiều thờithời giangian đểđể “băm”“băm” cáccác chuỗichuỗi concon
hayhay khơng?khơng?
 ĐãĐã kếtkết thúcthúc qq trìnhtrình tìmtìm kiếmkiếm chưa?chưa?
 ĐểĐể trảtrả lờilời nhữngnhững câucâu hỏihỏi trêntrên tata cầncần quayquay lạilại tốntốn
họchọc mộtmột chútchút
4/14/2011
9
Dương Anh Đức Dương Anh Đức –– Nhập môn Cấu trúc Dữ liệu và Giải thuậtNhập môn Cấu trúc Dữ liệu và Giải thuật
1717
TốnTốn họchọc vớivới RabinRabin KarpKarp
 XemXem chuỗichuỗi kýký MM tựtự nhưnhư làlà mộtmột sốsố MM chữchữ sốsố trongtrong
cơcơ sốsố bb,, vớivới bb làlà sốsố kýký tựtự trongtrong bảngbảng chữchữ cáicái
ChuỗiChuỗi kýký tựtự concon t[it[i …… i+Mi+M 11]] đượcđược ánhánh xạxạ thànhthành
 h(i)=t[i]h(i)=t[i]××bb
MM 11
+t[i+1]+t[i+1]××bb
MM 22

¨¨ GiảGiả sửsử bộbộ chữchữ cáicái củacủa chúngchúng tata gồmgồm 1010 kýký tựtự [a,[a, b,b,
c,c, d,d, e,e, f,f, g,g, h,h, ii,, j]j]
¨¨ GiảGiả sửsử “a”“a” tươngtương ứngứng vớivới 11,, “b”“b” tươngtương ứngứng vớivới 22,,
……
¨¨ GiáGiá trịtrị bămbăm củacủa chuỗichuỗi “cah”“cah” sẽsẽ làlà::
 3*100 + 1*10 + 8*1 = 3183*100 + 1*10 + 8*1 = 318
4/14/2011
11
Dương Anh Đức Dương Anh Đức –– Nhập môn Cấu trúc Dữ liệu và Giải thuậtNhập môn Cấu trúc Dữ liệu và Giải thuật
2121
TốnTốn họchọc vớivới RabinRabin KarpKarp
 NếuNếu MM lớn,lớn, giágiá trịtrị kếtkết quảquả sẽsẽ rấtrất lớnlớn (~b(~b
MM
)) ĐểĐể giảigiải
quyếtquyết vấnvấn đềđề này,này, tata sẽsẽ dùngdùng hàmhàm MODMOD ((%% trongtrong
C)C) đểđể chỉchỉ lấylấy phầnphần dưdư sausau khikhi chiachia chocho mộtmột sốsố
ngunngun tốtố pp
 HàmHàm MODMOD đượcđược dùngdùng vìvì mộtmột sốsố tínhtính chấtchất sausau củacủa
nónó::
[(x mod p)+(y mod p)]mod p = ([(x mod p)+(y mod p)]mod p = (x+yx+y)mod p)mod p
(x mod p) mod p = x mod p(x mod p) mod p = x mod p
Dương Anh Đức Dương Anh Đức –– Nhập môn Cấu trúc Dữ liệu và Giải thuậtNhập môn Cấu trúc Dữ liệu và Giải thuật
2222
TốnTốn họchọc vớivới RabinRabin KarpKarp
 DoDo đóđó::
h(h(ii)=((t[)=((t[ii]]××bb
MM 11
modmod p)+(t[i+p)+(t[i+11]]××bb
MM 22
modmod p)p)

 ĐặcĐặc biệt,biệt, ff cócó thểthể địnhđịnh nghĩanghĩa nhưnhư prefixprefix dàidài nhấtnhất
củacủa mẫumẫu P[P[00,, ,j],j] đồngđồng thờithời làlà suffixsuffix củacủa P[P[11,, ,j],j]
((chúchú ý,ý, khơngkhơng phảiphải củacủa P[P[00,, ,j],j]))
4/14/2011
13
Dương Anh Đức Dương Anh Đức –– Nhập môn Cấu trúc Dữ liệu và Giải thuậtNhập môn Cấu trúc Dữ liệu và Giải thuật
2525
 VíVí dụdụ::
 GiáGiá tròtrò củacủa KPMKPM failurefailure functionfunction::
 HàmHàm nàynày chocho biếtbiết baobao nhiêunhiêu kýký tựtự ởở đầầu củacủa
mẫumẫu tínhtính đếnđến nơinơi xảyxảy rara sựsự kháckhác biệtbiệt khớpkhớp vớivới
texttext
 NếuNếu sựsự kháckhác biệtbiệt xảyxảy rara ởở vòvò trítrí 44,, tata sẽsẽ biếtbiết a,a,
bb ởở vòvò trítrí 22,, 33 tươngtương ứngứng vớivới a,a, bb ởở vòvò trítrí 00,, 11
ThuậtThuật tốntốn KnuthKnuth MorrisMorris Pratt Pratt
Dương Anh Đức Dương Anh Đức –– Nhập môn Cấu trúc Dữ liệu và Giải thuậtNhập môn Cấu trúc Dữ liệu và Giải thuật
2626
ThuậtThuật tốntốn so so khớpkhớp KPMKPM((mãmã giảgiả):):
returnreturn
““
KhongKhong
coco
PP
trongtrong
TT
””
AlgorithmAlgorithm KMPMatcKMPMatchh(T,P)(T,P)
 InputInput::StringString TT (text)(text) vớivới nn kýký tựtự vàvà mẫumẫu PP vớivới mm kýký tựtự
 OutputOutput::ChỉChỉ sốsố đầuđầu củacủa chuỗichuỗi concon đầuđầu tiêntiên trongtrong TT khớpkhớp vớivới P,P, hoặchoặc chocho biếtbiết
 PP khơngkhơng phảiphải làlà chuỗichuỗi concon củacủa TT

 ifif P[j]P[j] == T[j]T[j] thenthen ////tata cócó jj ++ 11 kýký tựtự khớpkhớp nhaunhau
 f(f(ii)) ¬¬ jj ++ 11
 ii ¬¬ ii ++ 11
 jj ¬¬ jj ++ 11
 elseelse ifif jj >> 00 thenthen //// jj chỉchỉ đếnđến ngayngay sausau matchingmatching prefixprefix trongtrong PP
 jj ¬¬ f(jf(j 11))
 elseelse ////khơngkhơng khớpkhớp
 f(f(ii)) ¬¬ 00
 ii ¬¬ ii ++ 11
Dương Anh Đức Dương Anh Đức –– Nhập môn Cấu trúc Dữ liệu và Giải thuậtNhập môn Cấu trúc Dữ liệu và Giải thuật
2828
ThuậtThuật tốntốn KnuthKnuth MorrisMorris Pratt Pratt
4/14/2011
15
Dương Anh Đức Dương Anh Đức –– Nhập môn Cấu trúc Dữ liệu và Giải thuậtNhập môn Cấu trúc Dữ liệu và Giải thuật
2929
 PhânPhân tíchtích độđộ phứcphức tạptạp củacủa thuậtthuật tốntốn
 ĐịnhĐịnh nghĩanghĩa kk == ii jj
 TrongTrong mỗimỗi lầnlần lặplặp củacủa vòngvòng lặplặp whilewhile mộtmột trongtrong
33 điềuđiều sausau sẽsẽ xảyxảy rara::
 NếuNếu T[i]T[i] == P[j],P[j], thìthì ii tăngtăng lênlên 11,, jj cũngcũng vậy,vậy, kk
khơngkhơng đổiđổi
 NếuNếu T[i]T[i] !=!= P[j]P[j] vàvà jj >> 00,, thìthì ii khơngkhơng đổiđổi vàvà kk
tăngtăng lênlên ítít nhấtnhất 11,, vìvì kk thaythay đổiđổi trongtrong khoảngkhoảng
từtừ ii jj đếnđến ii f(jf(j 11))
 NếuNếu T[i]!=P[j]T[i]!=P[j] vàvà jj == 00,, thìthì ii tăngtăng lênlên 11 vàvà kk
tăngtăng
lênlên
11
vìvì

 b*(b*(abab*a)*b**a)*b* cáccác chuỗichuỗi kýký tựtự vớivới mộtmột sốsố chẵnchẵn kýký
tựtự aa
 ((a+ba+b)*sun()*sun(a+ba+b)*)* cáccác chuỗichuỗi kýký tựtự cócó chứachứa chuỗichuỗi
concon “sun”“sun”
 ((a+ba+b)()(a+ba+b)()(a+ba+b)a)a chuỗichuỗi 44 kýký tựtự kếtkết thúcthúc bằngbằng aa