zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Bài giảng: Xữ lý tìm kiếm trên chuỗi kí tự

Chia sẻ: Lit Ga | Ngày: | Loại File: PDF | Số trang:16

Báo xấu

197
lượt xem 38
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đối tượng của bài toán string searching là tìm kiếm vị trí của một mẫu văn bản (text pattern) trong nội dung một văn bản lớn hơn (một câu, một đoạn hay một quyển sách, …)

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng: Xữ lý tìm kiếm trên chuỗi kí tự

4/14/2011 Strings Strings and Pattern Matching Strings Strings and Pattern Matching Brute Brute Force,  Rabin Karp, Rabin-Karp, Knuth Knuth-Morris-Pratt Regular Expressions  Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 2 1
4/14/2011 Bài toán tìm kiếm chuỗi ký tự Đối tượng của bài toán string searching là tìm  kiếm vị trí của một mẫu văn bản (text pattern) trong nội dung một văn bản lớn hơn (một câu, một đoạn hay một quyển sách, …) Cũng như phần lớn các thuật toán khác, quan tâm  chính của string searching là tốc độ và hiệu quả. Có nhiều thuật toán tìm kiễm chuỗi ký tự khác  nhau. Tuy nhiên, chúng ta sẽ chỉ khảo sát ba thuật toán là: Brute Force, Rabin-Karp và Knuth- Morris-Pratt. Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 3 Thuật toán Brute Force Brute Thuật toán Brute Force so sánh mẫu tìm kiếm với  văn bản, mỗi lần 1 ký tự, cho đến khi các ký tự không khớp được tìm thấy: Thuật toán có thể được thiết kế sao cho nó sẽ dừng  khi gặp sự xuất hiện đầu tiên của mẫu trong text hoặc cho đến khi đã xét đến cuoái text. Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 4 2
4/14/2011 Thuật toán Brute Force Brute Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 5 Thuật toán Brute Force Brute Algorithm Algorithm Brute Force(P);  Input:String mẫu P với m ký tự  Ouput:Vị trí chuỗi mẫu P trong T hoặc báo không có  do if (text letter == pattern letter)  so sánh text letter kế với pattern letter kế else  chuyển pattern dịch sang phải 1 letter   until (tìm thấy toàn bộ pattern hoặc đến cuối text) Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 6 3
4/14/2011 Thuaä Thuaät toaùn Brute Force Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 7 Thuaä Thuaät toaùn Brute Force Độ phức tạp của thuật toán Brute Force: Giả  sử kích thước của mẫu là M ký tự và text có N ký tự  Trường hợp xấu nhất: so sánh mẫu với mọi chuỗi con chiều dài M trong text  Tổng số phép so sánh: M (N-M+1)  Độ phức tạp trong trường hợp xấu nhất : O(MN) Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 8 4
4/14/2011 Thuaä Thuaät toaùn Brute Force Độ phức tạp của thuật toán Brute Force: Giả sử  kích thước của mẫu là M ký tự và text có N ký tự hợp tốt nhất 1: mẫu xuất hiện ngay đầu  Trường text  Độ phức tạp trong trường hợp tốt nhất 1: O(M)  Trường hợp tốt nhất 2: mẫu không xuất hiện trong text  Độ phức tạp trong trường hợp tốt nhất 2: O(N) Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 9 Ví dụ, với M=5 ta có ví dụ sau: với M=5 ta Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 10 5
4/14/2011 Thuật toán Rabin-Karp Karp Thuật toán Rabin-Karp tính các giá trị băm n (hash value) của mẫu tìm kiếm và của chuỗi con M ký tự cần so sánh trong văn bản. Nếu các giá trị băm không bằng nhau, thuật toán n sẽ tính giá trị băm cho chuỗi con M ký tự kế tiếp. Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 11 Thuật toán Rabin-Karp Karp Nếu các giá trị băm bằng nhau, thuật toán thực  hiện phép so sánh Brute Force giữa mẫu và chuỗi này. Theo cách này, sẽ chỉ có một phép so sánh ứng với  mỗi chuỗi con trong văn bản, và Brute Force sẽ chỉ cần đến khi các giá trị băm bằng nhau. Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 12 6
4/14/2011 Thuật toán Rabin-Karp Karp Hãy xem ví dụ dưới đây để rõ hơn một chút:   Giá trị băm của “AAAAA” là 100  Giá trị băm của “AAAAH” là 37 Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 13 Thuaät toaùn Rabin-Karp Karp Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 14 7
4/14/2011 Thuaät toaùn Rabin-Karp Karp Maãu coù chieàu daøi M kyù töï  hash_p = giaù trò baêm cuûa maãu  hash_t = giaù trò baêm cuûa M kyù töï ñaàu trong text  do if (hash_p == hash_t) So saùnh brute force giöõa maãu vaø chuoãi con hash_t = giaù trò baêm cuûa M kyù töï keá trong text until (keát thuùc text hoaëc keát quaû so saùnh == true) Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 15 Thuật toán Rabin-Karp Những câu hỏi chung của Rabin-Karp:  Chọn hàm băm nào để tính giá trị băm?  Có tốn nhiều thời gian để “băm” các chuỗi con  hay không? Đã kết thúc quá trình tìm kiếm chưa?  Để trả lời những câu hỏi trên ta cần quay lại toán  học một chút. Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 16 8
4/14/2011 Toán học với Rabin-Karp Xem chuỗi ký M tự như là một số M chữ số trong  cơ số b, với b là số ký tự trong bảng chữ cái. Chuỗi ký tự con t[i … i+M-1] được ánh xạ thành h(i)=t[i]×bM-1+t[i+1]×bM-2+...+t[i+M-1]  Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 17 Toán học với Rabin-Karp Hơn nữa, có x(i) ta có thể tính x(i+1) cho  chuỗi con kế tiếp t[i+1 .. i+M] với chi phí cố định (O(1)) như sau: h(i+1)=t[i+1]×bM-1+t[i+2]×bM-  2+...+t[i+M] Shift left 1 digit  h(i+1)=h(i)×b -t[i]×bM Trừ chữ số trái nhất  Cộngchữsố phải nhất +t[i+M]  Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 18 9
4/14/2011 Toán học với Rabin-Karp Karp Bằng cách này, ta không bao giờ thật sự phải tính  một giá trị mới. Đơn giản, ta chỉ phải hiệu chỉnh giá trị sẵn có khi dịch chuyển sang phải 1 ký tự. Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 19 Toán học với Rabin-Karp Xét một ví du n Giả sử bộ chữ cái của chúng ta gồm 10 ký tự [a, b, ¨ c, d, e, f, g, h, i, j] Giả sử “a” tương ứng với 1, “b” tương ứng với 2, ¨ … Giá trị băm của chuỗi “cah” sẽ là: ¨  3*100 + 1*10 + 8*1 = 318 Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 20 10
4/14/2011 Toán học với Rabin-Karp Nếu M lớn, giá trị kết quả sẽ rất lớn (~bM). Để giải  quyết vấn đề này, ta sẽ dùng hàm MOD (% trong C) để chỉ lấy phần dư sau khi chia cho một số nguyên tố p. Hàm MOD được dùng vì một số tính chất sau của  nó: [(x mod p)+(y mod p)]mod p = (x+y)mod p (x mod p) mod p = x mod p Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 21 Toán học với Rabin-Karp Do ñoù:  h(i)=((t[i]×bM-1mod p)+(t[i+1]×bM-2mod p) +...+(t[i+M-1]mod p))mod p // Shift left 1 digit h(i+1)=(h(i)×b mod p - t[i]×bM mod p // Trừ chữ số trái nhất + t[i+M] mod p) // Cộng chữ số phải nhất mod p Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 22 11
4/14/2011 Toán học với Rabin-Karp Độ phức tạp của thuật toán Rabin-Karp   Nếu p là số nguyên tố đủ lớn, giá trị băm nói chung sẽ khác nhau với các chuỗi khác nhau.  Trong trường hợp này, việc tìm kiếm tốn chi phí O(N), trong đó N là số ký tự có trong text.  Ta luôn có thể tìm được ví dụ trong đó, trong trường hợp xấu nhất, chi phí sẽ là O(MN). Tuy nhiên, trường hợp này có lẽ sẽ chỉ xảy ra khi p quá nhỏ. Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 23 Thuật toán Knuth-Morris-Pratt Pratt Thuật toán Knuth-Morris-Pratt (KMP) khác với  thuật toán brute-force ở chỗ nó lưu lại thông tin về những lần so sánh trước để dùng cho lần so sánh kế tiếp. Một hàm•failure function(f) được dùng để tính bao  nhiêu thông tin ở bước trước có thể được dùng lại. Đặc biệt, f có thể định nghĩa như prefix dài nhất  của mẫu P[0,..,j] đồng thời là suffix của P[1,..,j] (chú ý, không phải của P[0,..,j]) Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 24 12
4/14/2011 Thuật toán Knuth-Morris-Pratt Pratt Ví duï:   Giaù trò cuûa KPM failure function: Haøm naøy cho bieát bao nhieâu kyù töï ôû ñaàu cuûa  maãu tính ñeán nôi xaûy ra söï khaùc bieät khôùp vôùi text.  Neáu söï khaùc bieät xaûy ra ôû vò trí 4, ta seõ bieát a, b ôû vò trí 2, 3 töông öùng vôùi a, b ôû vò trí 0, 1. Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 25 Thuật toán so khớp KPM(mã giả): so khớp Algorithm KMPMatch(T,P)  Input:String T (text) với n ký tự và mẫu P với m ký tự.  Output:Chỉ số đầu của chuỗi con đầu tiên trong T khớp với P, hoặc cho biết P không phải là chuỗi con của T.   f ¬ KMPFailureFunction(P); //xây dựng failure function  i ¬ 0; j ¬ 0;  while i < n do if P[j] = T[i] then  if j = m - 1 then  //tìm được một chuỗi con khớp return i - m - 1  i ¬i + 1  j ¬j + 1  //không khớp, nhưng còn dữ liệu else if j > 0 then  //j chỉ đến ngay sau matching prefix trong P j ¬ f(j-1)  else  i ¬i + 1  return “Khong co P trong T” Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 26 13
4/14/2011 Thuaä Thuaät toaùn KPM failure function Algorithm KMPFailureFunction(P);  Input:String mẫu P với m ký tự  Output:Failure function f ứng với P, sẽ ánh xạ j với chiều dài của longest prefix của P là suffix của P[1,..,j]  i ¬ 1; j ¬ 0;  while i £ m-1 do if P[j] = T[j] then //ta có j + 1 ký tự khớp nhau  f(i) ¬ j + 1  i ¬i + 1  j ¬j + 1  else if j > 0 then // j chỉ đến ngay sau matching prefix trong P  j ¬ f(j-1)  //không khớp else  f(i) ¬ 0  i¬i+1  Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 27 Thuật toán Knuth-Morris-Pratt Pratt Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 28 14
4/14/2011 Thuật toán Knuth-Morris-Pratt Pratt Phân tích độ phức tạp của thuật toán   Định nghĩa k = i - j  Trong mỗi lần lặp của vòng lặp while một trong 3 điều sau sẽ xảy ra:  Nếu T[i] = P[j], thì i tăng lên 1, j cũng vậy, k không đổi  Nếu T[i] != P[j] và j > 0, thì i không đổi và k tăng lên ít nhất 1, vì k thay đổi trong khoảng từ i - j đến i-f(j-1)  Nếu T[i]!=P[j] và j = 0, thì i tăng lên 1 và k Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 29 tăng lên 1 vì j không đổi. Thuật toán Knuth-Morris-Pratt Pratt Như vậy, mỗi lần lặp, i hoặc k, tăng lên ít nhất 1  nên số lần lặp tối đa là 2n Dĩ nhiên ta đang giả thiết f đã được tính trước.  Tuy nhiên, cách tính f gần giống như KMPMatch  nên chi phí tính f hoàn toàn tương tự = O(m) Tổng chi phí: O(n + m)  Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 30 15
4/14/2011 Regular Regular Expressions Ký hiệu cho phép ta mô tả các chuõi ký tự, có thể  dài vô hạn  e ký hiệu chuỗi rỗng  ab + c ký hiệu tập hợp {ab, c}  a* ký hiệu tập hợp {e, a, aa, aaa, ...} Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 31 Regular Regular Expressions Ví du   (a+b)* tất các các chuỗi ký tự với bộ chữ cái {a,b}  b*(ab*a)*b* các chuỗi ký tự với một số chẵn ký tự a  (a+b)*sun(a+b)* các chuỗi ký tự có chứa chuỗi con “sun”  (a+b)(a+b)(a+b)a chuỗi 4 ký tự kết thúc bằng a Döông Döông Anh Ñöùc – Nhaäp moân Caáu truùc Döõ lieäu vaø Giaûi thuaät 32 16

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.