Page 1
goupee.vn goupee.com Phần 3: Cấu trúc dữ liệu và Giải thuật Chương 13: Các giải thuật tìm kiếm cuu duong than cong . com fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Contenu du document
Page 2
goupee.vn goupee.com Các nội dung chính 1. Giới thiệu 2. Các giải thuật tìm kiếm phần tử 3. Các giải thuật tìm kiếm chuỗi con cuu duong than cong . com fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 3
goupee.vn goupee.com 1. Giới thiệu • Bài học này sẽ trình bầy một số giải thuật tìm kiếm cho hai bài toán tìm kiếm cơ bản: – Thứ nhất, là bài toán tìm một phần tử trong một dãy phần tử cho trước theo một khoá tìm kiếm – Thứ hai, là tìm sự xuất hiện của một chuỗi con trong một chuỗi cho trước cuu duong than cong . com fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 4
goupee.vn goupee.com 1. Giới thiệu • Với bài toán thứ nhất, có hai chiến lược tìm kiếm là tìm kiếm bằng cách so sánh hay tìm kiếm trực tiếp dựa vào giá trị khoá cần tìm • Với bài toán thứ hai cũng có nhiều giải thuật khác nhau, từ giải thuật tìm kiếm đơn giản (còn gọi là tìm kiếm thô), cho đến các giải thuật khá phức tạp như của Knuthcuu duong than cong . com-Morris-Pratt và của Boyer-Moore fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 5
goupee.vn goupee.com 2. Các giải thuật tìm kiếm phần tử • Đặt bài toán: – Để đơn giản cho việc trình bầy ý tưởng các giải thuật, ta sẽ chọn bài toán ở dạng đơn giản nhất như sau: Cho một dãy N số A = (a0, a1,…, aN-1) và giá trị cần tìm K (khoá tìm kiếm). Yêu cầu tìm vị trí một phần tử có giá trị bằng K. • Có 2 chiến lược tìm kiếm: – Tìm kiếm bằng cách so sánh:cuu duong than cong . com – Tìm kiếm dựa trực tiếp vào giá trị khóa: fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 6
goupee.vn goupee.com Tìm kiếm bằng so sánh • Ý tưởng chung: từ khóa tìm kiếm K, ta chưa biết được vị trí của phần tử cần tìm, nên tiến hành so sánh K với lần lượt các phần tử trong dãy cần tìm cho đến khi ra kết quả (hoặc tìm thấy hoặc không tìm thấy) • Có 2 loại giải thuật tìm kiếm theo cách này: – Tìm kiếm tuần tự (Sequential Search)cuu duong than cong . com – Tìm kiếm nhị phân (Binary Search) fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 7
goupee.vn goupee.com Tìm kiếm tuần tự • Ý tưởng giải thuật: – Để tìm phần tử bằng K trong dãy N số A = (a0, a1,…, aN-1), tiến hành so sánh K với lần lượt các phần tử trong dãy, cho đến khi: • Hoặc tìm thấy phần tử ai = K, thì trả về vị trí i cần tìm • Hoặc đã so sánh với toàn bộ các phần tử của dãy nhưng vẫn không thấy, thì trả về kết quả không tìm thấy. cuu duong than cong . com fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 8
goupee.vn goupee.com Tìm kiếm tuần tự • Cài đặt hàm int SequentialSearch(int A[], int N, int K) { int i=0; while (i<N && A[i] != K) i++; if (i<N) return i; //Tìm thấy return -1; //Không tìm thấy } cuu duong than cong . com fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 9
goupee.vn goupee.com Tìm kiếm nhị phân • Ý tưởng giải thuật: – Để tìm phần tử bằng K trong dãy N số A = (a0, a1,…, aN-1), thì giải thuật này có một yêu cầu là dãy A đã được sắp xếp, giả sử là theo chiều tăng dần. Các bước của giải thuật đệ quy này như sau: • So sánh K với phần tử am ở giữa dãy (m=N/2). Có 3 khả năng xảy ra: – Nếu K = am thì trả về vị trí tìm thấy m – Nếu K < am thì tìm K trong dãy (a0,a1,…,am-1) – Trái lại, thì tìm K trong dãy (acuu duong than cong . comm+1,am+2,…,aN-1) • Điểm dừng: khi tìm thấy hoặc khi dãy không còn phần tử nào thì trả về kết quả không tìm thấy. fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 10
goupee.vn goupee.com Tìm kiếm nhị phân • Cài đặt hàm int BSearch(int K, int A[], int b, int e) { if (b>e) return -1; //Không tìm thấy int m= (b+e)/2; if (K==A[m]) return m; //Tìm thấy else if (K<A[m]) return BSearch(K, A, int b, m-1); else return BSearch(K, A, m+1,e); } cuu duong than cong . com int BinarySearch(int K, int A[], int N){ return BSearch(K,A,0,N-1); } fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 11
goupee.vn goupee.com Tìm kiếm trực tiếp • Tham khảo tài liệu. cuu duong than cong . com fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 11 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 12
goupee.vn goupee.com 3. Tìm kiếm chuỗi con • Giới thiệu bài toán • Giải thuật tìm kiếm thô (brute-force) • Giải thuật Knuth-Morris-Pratt (KMP) cuu duong than cong . com fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 12 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 13
goupee.vn goupee.com Giới thiệu bài toán • Cho trước một văn bản V gồm n kí tự (v0,v1,…,vn- 1) và một chuỗi con P (gọi là mẫu) gồm m kí tự (p0,p1,…,pm-1). Yêu cầu tìm vị trí xuất hiện đầu tiên của P trong V. • Bài toán này có nhiều giải thuật. Giải thuật thô khá đơn giản nhưng có thời gian xử lý tồi nhất tỉ lệ với m x n. Giải thuật KMP cần các thao tác tiền xử lý trên chuỗi mẫu nên khá phức tạp, nhưng cócuu duong than cong . com thời gian tốt hơn nhiều, chỉ tỉ lệ với m + n. fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 13 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 14
goupee.vn goupee.com Giải thuật tìm kiếm thô • Ý tưởng giải thuật: – So sánh lần lượt các ký tự của mẫu P với các kí tự của văn bản V bắt đầu từ vị trí i (0 i n-m) cho đến khi hoặc khớp tất cả các kí tự của P với các kí tự trong V thì i là vị trí cần tìm, hoặc so đến kí tự cuối cùng trong V vẫn không khớp thì kết luận tìm kiếm không thấy, hoặc gặp bất kì kí tự nào không khớp thì quay lại so sánh từ đầu của mẫu P với cáccuu duong than cong . com kí tự của V bắt đầu từ vị trí i+1. fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 14 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 15
goupee.vn goupee.com Giải thuật tìm kiếm thô V = v0, v1,…, vn-1 P = p0, p1,…, pm-1 i = j = 0; p p … P … P do { 0 1 j-1 m-1 while (j<m && p == v ) { k i+j j j++; } if (j<m && i<n-m) { v0 v1 … vi vi+1 … vi+j-1 … … vn-1 i++; j=0; p p … p … p } 0 1 j-1 m-1 } while (i<=n-m && j<m); i cuu duong than cong . com if (j==m) return i; //FOUND v v … … v … … … … v else return -1; //NOT FOUND 0 1 n-m n-1 fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 15 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 16
goupee.vn goupee.com Giải thuật tìm kiếm thô – cài đặt int BFSearch(char V[N], char P[M] ) { if (i<=N-M && j<M ) { /*Ham tra ve vi tri tim thay dau tien, tra i++; ve -1 neu khong tim thay*/ j=0; if (N<M) return -1; } int i, j; i=j=0; } while (i<=N-M && j<M) ; if (j==M) return i; do { else return -1; while (j<M && V[i+j]==P[j]) { }//end BFSearch j++; cuu duong than cong . com } fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 16 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 17
goupee.vn goupee.com Cải tiến giải thuật tìm kiếm thô a b b a Có thể bỏ qua (2), (3)? a b b a (1) (4) a b b b a b b a a b a b b b a b b a a b a b b a a b b a (2) (5) a b b b a b b a a b a b b b a b b a a b a b b a (3) a b b b a bcuu duong than cong . comb a a b Giải thuật Knuth-Morris-Pratt fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 17 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 18
goupee.vn goupee.com Giải thuật Knuth-Morris-Pratt • Ý tưởng của giải thuật: – Trong giải thuật này, khi ta đã so sánh bắt đầu từ vị trí kí tự thứ i trong văn bản và đến kí tự thứ j trong mẫu mà có sự không khớp với văn bản (j-1 kí tự đầu tiên đã khớp), thì thay vì phải quay lại so sánh từ kí tự đầu tiên của mẫu với kí tự thứ i+1 như trong giải thuật thô ở trên, ta thấy có thể tận dụng thông tin trong j-1 kí tự đã khớp để bắt đầu việc so sánh từ một kí tự thứ k xác định trong mẫu (0 k M- 1) với kí tự hiện đang không khớp trong văn bản (không phải dịch lại vị trí i+1). – Vị trí k cần tìm thoả mãn điều kiện: k là giá trị lớn nhất < j sao cho k-1 kí tự đầu tiên trong mẫu trùng/khớp với kcuu duong than cong . com-1 kí tự cuối cùng của j-1 kí tự đầu tiên trong mẫu. fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 18 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 19
goupee.vn goupee.com Giải thuật Knuth-Morris-Pratt p0 p1 … pj-1 pj … pm-1 v0 v1 … vi vi+1 … vi+j-1 vi+j … … … vn-1 Tìm k max sao cho: p0, p1, …, pk-1 = vi+j-k, …, vi+j-1 = pj-k, …, pj-1 p … p … p … p Giải thuật tìm 0 k j-1 m-1 overlap cuu duong than cong . com fb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 19 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 20
goupee.vn goupee.com Giải thuật tìm overlap Cho trước p[m]. Với j>0, tìm k max (0 k j-1) p0 … pj-k … Pk-1 … pj-1 pj … pm-1 sao cho: p0, p1, …, pk-1 = pj-k, …, pj-1 p , p , …, p 0 1 k-1 int Overlap(p[m], j) { if (j<2) return 0; p , …, p j-k j-1 i = 1; // Tìm i = j-k //Tìm vị trí đầu tiên j-k sao cho p0 = pj-k do { while (i<=j-1 && pi != p0) i++; if (i==j) return 0; //Không tìm thấy else { //Tìm thấy, kiểm tra xem đây có phải là k cần tìm k = i+1;while (k<=j-1&&pcuu duong than cong . com==p ) k++; k k-i if (k==j) return j-i; //OK trả về giá trị cần tìm else i++; //tiếp tục tìm vị trí j-k } } while (i<=j-1); // vẫn còn khả năng tìm ifb.com/goupee.vn Chương 12: Các Giải thuật Tìm Kiếm 20 } CuuDuongThanCong.com https://fb.com/tailieudientucntt
Affichage des 20 premières pages. Téléchargez le document pour le voir en entier.
Commentaires (0)
Aucun commentaire pour le moment. Soyez le premier !