Bài giảng Cấu trúc dữ liệu 2 - Bài 1: Bảng băm (Hash Table)

gt;key[i]); dem++; } // duyet cay con cuoi cung Traverse(proot->Branch[proot->numtrees-1]); } } c) Thêm node mới void Insert(NODEPTR s, int k, int position) { NODEPTR nd,nd2,f,newnode; int pos,newkey,midkey; // khoi dong cac gia tri nd = s; newkey = k; newnode = NULL; pos = position; f = Father(nd); // vong lap tach cac node day nd while (f!=NULL && nd->numtrees==ORDER) { Split(nd,newkey,newnode,pos,&nd2,&midkey); // gan lai cac tri sau lan tach node truoc nd = f; newkey = midkey; newnode = nd2; pos = NodeSearch(f,midkey); f = Father(nd); } // truong hop node nd chua day va nd khong phai la node goc if (nd->numtrees<ORDER) { // chen newkey va newnode tai vi tri pos cua node nd InsertNode(nd,newkey,newnode,pos); return; } // truong hop node nd la node goc bi day // tach node goc nay va tao node goc moi Split(nd,newkey,newnode,pos,&nd2,&midkey); Root = MakeRoot(midkey); // tao node goc moi // gan lai hai nhanh cay con cua node goc moi la nd va nd2 Root->Branch[0] = nd; Root->Branch[1]= nd2; } NODEPTR Father(NODEPTR son) { int i; NODEPTR father, ptmp; father = NULL; ptmp = Root; while (ptmp!=son && ptmp!=NULL) { i = NodeSearch(ptmp,son->key[0]); father = ptmp; ptmp = ptmp->Branch[i]; } if (ptmp==NULL) return NULL; return father; } NODEPTR MakeRoot(int k) { NODEPTR p; p = GetNode(); p->numtrees=2; p->key[0]=k; return p; } NODEPTR GetNode() { NODEPTR p; int i; p = new Node; for (i=0; i<ORDER; i++) p->Branch[i]=NULL; p->numtrees = 0; return p; } void Split(NODEPTR nd, int newkey, NODEPTR newnode, int pos, NODEPTR *pnd2, int *pmidkey) { NODEPTR p; p = GetNode(); // truong hop newkey va newnode vao node nua phai if (pos>NDiv2) { Copy(nd,NDiv2+1,ORDER-2,p); InsertNode(p,newkey,newnode,pos-NDiv2-1); nd->numtrees = NDiv2+1; // so nhanh cay con con lai cua node trai *pmidkey = nd->key[NDiv2]; *pnd2 = p; return; } // truong hop newkey la midkey if (pos==NDiv2) { Copy(nd,NDiv2,ORDER-2,p); nd->numtrees=NDiv2+1; // so nhanh cay con con lai cua node nua trai // dieu chinh lai node con dau tien cua node nua phai p->Branch[0] = newnode; *pmidkey = newkey; *pnd2 = p; return; } // truong hop chen newkey va newnode vao node nua phai if (pos<NDiv2) { Copy(nd,NDiv2,ORDER-2,p); nd->numtrees = NDiv2; //so nhanh cay con con lai cua node nua trai *pmidkey = nd->key[NDiv2-1]; InsertNode(nd,newkey,newnode,pos); *pnd2 = p; return; } } void InsertNode(NODEPTR p, int newkey, NODEPTR newnode, int pos) { int i; //doi cac nhanh cay con va cac khoa tu vi tri pos tro ve sau xuong 1 vi tri for (i=p->numtrees-1; i>=pos+1; i--) { p->Branch[i+1] = p->Branch[i]; p->key[i] = p->key[i-1]; } // gan khoa newkey vao vi tri pos p->key[pos] = newkey; // gan thanh newnode la nhanh cay con ben phai cua khoa newkey p->Branch[pos+1] = newnode; // tang so nhanh cay con cua node p len 1 p->numtrees++; } void Copy(NODEPTR nd, int first, int last, NODEPTR nd2) { int i; // copy cac khoa tu node nd qua node nd2 for (i=first; i<=last; i++) nd2->key[i-first] = nd->key[i]; // copy cac nhanh cay con tu node nd qua nd2 for (i=first;i<=last+1;i++) nd2->Branch[i-first] = nd->Branch[i]; nd2->numtrees = last-first+2; // so nhanh cay con cua node nd2 } Bài 7: Tìm kiếm và so khớp chuỗi Nội dung 7.1) Giới thiệu bài toán tìm kiếm chuỗi 7.2) Một số thuật toán tìm kiếm chuỗi cơ bản a) Thuật toán Brute Force b) Thuật toán Knuth Morris Pratt c) Thuật Toán Boyer More 7.3) So khớp chuỗi Giới thiệu bài toán tìm kiếm chuỗi (String Searching) Vấn đề tìm kiếm một chuỗi bên trong một chuỗi khác là rất phổ biến trong thực tế. Ví dụ như : Tìm tên file hoặc thư mục trên ổ đĩa, tìm kiếm các đoạn gene DNA, tìm kiếm một từ, câu, đoạn văn trong văn bản Cũng như phần lớn các thuật toán khác, quan tâm chính cuả string searching là tốc độ và hiệu quả Có rất nhiều thuật toán khác nhau đã được xây dựng cho mục đích này. Trong phạm vi bài học chúng ta chỉ tìm hiểu 3 thuật toán cơ bản là: Brute Force, Boyer More và Knuth Morris Pratt Một số thuật toán cơ bản tìm kiếm chuỗi a) Thuật toán Brute Force Thuật toán Brute Force so sánh mẫu (Pattern) tìm kiếm với văn bản (Text), 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 văn bản hoặc cho đến khi đã xét đến cuối văn bản Thuật toán 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) Ví dụ: Độ 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 tốt nhất 1: mẫu xuất hiện ngay đầu 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) 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) Cài đặt thuật toán char *Brute_Force(char *source, char *substr, int *k) { int i = 0, j = 0, m, n; n = strlen(source) - 1; m = strlen(substr) - 1; do { if (source[i] == substr[j]) { i++; j++; } else { i = i - j + 2; j = 0; } } while (j <= m && i <= n); if (j > m) { *k = i - m - 1; return source + i - m - 1; } else return NULL; } b) Thuật toán Knuth Morris Pratt Thuật toán được phát minh năm 1977 bởi hai giáo sư của ĐH Stanford, Hoa Kỳ (1 trong số ít các trường đại học xếp hàng số một về khoa học máy tính trên thế giới cùng với MIT, CMU cũng của Hoa Kỳ và Cambridge của Anh) Donal Knuth và Vaughan Ronald Pratt, Knuth (giải Turing năm 1971) còn rất nổi tiếng với cuốn sách Nghệ thuật lập trình (The Art of Computer Programming) hiện nay đã có đến tập 6, 3 tập đầu tiên đã có xuất bản ở Việt Nam, cuốn sách gối đầu giường cho bất kỳ lập trình viên nói riêng và những ai yêu thích lập trình máy tính nói chung trên thế giới. Thuật toán này còn có tên là KMP lấy tên viết tắt của ba người phát minh ra nó, chữ “M” là chỉ giáo sư J.H.Morris, một người cũng rất nổi tiếng trong khoa học máy tính. Ý tưởng chính của phương pháp này như sau : trong quá trình tìm kiếm vị trí của mẫu P trong xâu gốc T, nếu tìm thấy một vị trí sai ta chuyển sang vị trí tìm kiếm tiếp theo và quá trình tìm kiếm sau này sẽ được tận dụng thông tin từ quá trình tìm kiếm trước để không phải xét các trường hợp không cần thiết. Thuật toán Knuth-Morris-Pratt là thuật toán có độ phức tạp tuyến tính đầu tiên được phát hiện ra, nó dựa trên thuật toán brute force với ý tưởng lợi dụng lại những thông tin của lần thử trước cho lần sau. Trong thuật toán Brute Force vì chỉ dịch cửa sổ đi một ký tự nên có đến m-1 ký tự của cửa sổ mới là những ký tự của cửa sổ vừa xét. Trong đó có thể có rất nhiều ký tự đã được so sánh giống với mẫu và bây giờ lại nằm trên cửa sổ mới nhưng được dịch đi về vị trí so sánh với mẫu. Việc xử lý những ký tự này có thể được tính toán trước rồi lưu lại kết quả. Nhờ đó lần thử sau có thể dịch đi được nhiều hơn một ký tự, và giảm số ký tự phải so sánh lại. Xét lần thử tại vị trí j, khi đó cửa sổ đang xét bao gồm các ký tự y[jj+m-1] giả sử sự khác biệt đầu tiên xảy ra giữa hai ký tự x[i] và y[j+i-1]. Khi đó x[1i]=y[ji+j-1]=u và a=x[i]¹y[i+j]=b. Với trường hợp này, dịch cửa sổ phải thỏa mãn v là phần đầu của xâu x khớp với phần đuôi của xâu u trên văn bản. Hơn nữa ký tự c ở ngay sau v trên mẫu phải khác với ký tự a. Trong những đoạn như v thoả mãn các tính chất trên ta chỉ quan tâm đến đoạn có độ dài lớn nhất. u u v b c a x y x j i+j-1 Dịch cửa sổ sao cho v phải khớp với u và c ¹ a Thuật toán Knuth-Morris-Pratt sử dụng mảng Next[i] để lưu trữ độ dài lớn nhất của xâu v trong trường hợp xâu u=x[1i-1]. Mảng này có thể tính trước với chi phí về thời gian là O(m) (việc tính mảng Next thực chất là một bài toán qui hoạch động một chiều). Thuật toán Knuth-Morris-Pratt có chi phí về thời gian là O(m+n) với nhiều nhất là 2n-1 lần số lần so sánh ký tự trong quá trình tìm kiếm. int KMP(char *source, char *find) { int next[MAX], i = 0, len, j=-1, lensource; len = strlen(find); lensource = strlen(source); next[0] = -1; do { if (j == -1 || find[i] == find[j]) { i++; j++; next[i] = j; } else j = next[j]; } while (i < len-1); i = j = 0; do { if (j==0 || source[i] == find[j]) { i++; j++; } else j = next[j]; } while (j<len && i<lensource); if (j>=len) return i-len; else return -1; } c) Thuật toán Boyer Moore Thuật toán Boyer Moore là thuật toán có tìm kiếm chuỗi rất có hiệu quả trong thực tiễn, các dạng khác nhau của thuật toán này thường được cài đặt trong các chương trình soạn thảo văn bản. Khác với thuật toán Knuth-Morris-Pratt (KMP), thuật toán Boyer-Moore kiểm tra các ký tự của mẫu từ phải sang trái và khi phát hiện sự khác nhau đầu tiên thuật toán sẽ tiến hành dịch cửa sổ đi Trong thuật toán này có hai cách dịch của sổ: Cách thứ 1: gần giống như cách dịch trong thuật toán KMP, dịch sao cho những phần đã so sánh trong lần trước khớp với những phần giống nó trong lần sau. Trong lần thử tại vị trí j, khi so sánh đến ký tự i trên mẫu thì phát hiện ra sự khác nhau, lúc đó x[i+1m]=y[i+j...j+m-1]=u và a=x[i]¹y[i+j-1]=b khi đó thuật toán sẽ dịch cửa sổ sao cho đoạn u=y[i+jj+m-1] giống với một đoạn mới trên mẫu (trong các phép dịch ta chọn phép dịch nhỏ nhất) u b c a x y x u dịch u Dịch sao cho u xuất hiện lại và c ¹ a Nếu không có một đoạn nguyên vẹn của u xuất hiện lại trong x, ta sẽ chọn sao cho phần đôi dài nhất của u xuất hiện trở lại ở đầu mẫu. u b a y x dịch u u x Dịch để một phần đôi của u xuất hiện lại trên x Cách thứ 2: Coi ký tự đầu tiên không khớp trên văn bản là b=y[i+j-1] ta sẽ dịch sao cho có một ký tự giống b trên xâu mẫu khớp vào vị trí đó (nếu có nhiều vị trí xuất hiện b trên xâu mẫu ta chọn vị trí phải nhất) u b a y x dịch u b x không chứa b Dịch để ký tự b ăn khớp với văn bản. Nếu không có ký tự b nào xuất hiện trên mẫu ta sẽ dịch cửa sổ sao cho ký tự trái nhất của cửa sổ vào vị trí ngay sau ký tự y[i+j-1]=b để đảm bảo sự ăn khớp u b a y x dịch u x không chứa b Dịch khi b không xuất hiện trong x Trong hai cách dịch thuật toán sẽ chọn cách dịch có lợi nhất. int BoyerMoore(char *source, char *find) { int skip[MAX], i = 0, len, j=-1, lensource; len = strlen(find); lensource = strlen(source); for (i=0; i<MAX; i++) skip[i] = len-1; for (i=0; i<len; i++) if (skip[find[i]] == len-1) skip[find[i]] = len-i-1; i = j = len-1; do { if (source[i] == find[j]) { i--; j--; } else { if (len-j+1 > skip[source[i]]) i += len-j+1; else i += skip[source[i]]; j = len-1; } } while (j>0 && i<lensource); if (j<=0) return i; else return -1; } Thuật toán Boyer-Moore có thể đạt tới chi phí O(n/m) là nhờ có cách dịch thứ 2 “ký tự không khớp”. Cách chuyển cửa sổ khi gặp “ký tự không khớp” cài đặt vừa đơn giản lại rất hiệu quả trong các bảng chữ cái lớn nên có nhiều thuật toán khác cũng đã lợi dụng các quét mẫu từ phải sang trái để sử dụng cách dịch này. Tuy nhiên chi phí thuật toán của Boyer-Moore là O(m*n) vì cách dịch thứ nhất của thuật toán này không phân tích triệt để các thông tin của những lần thử trước, những đoạn đã so sánh rồi vẫn có thể bị so sánh lại. Có một vài thuật toán đã cải tiến cách dịch này để đưa đến chi phí tính toán của thuật toán Boyer-Moore là tuyến tính. So khớp chuỗi (String Matchching) Ý nghĩa của ký tự đại diện (wildcard) Có hai ký tự wildcard thông thường là ? và * . Dấu hỏi (?) đại diện cho một ký tự duy nhất bất kỳ. Dấu sao (*) đại diện cho nhiều ký tự bất kỳ hoặc không có ký tự nào cả. Bạn hãy quan sát vài ví dụ dưới đây: Mẫu Chuỗi so sánh Kết quả w?ldcard wildcard khớp w?ldcard waldcard khớp w*ldcard wldcard khớp (không có ký tự) w*ldcard willdcard khớp (có hai ký tự) w*ldcard* wldcards khớp Thuật toán Việc xử lý dấu hỏi khá đơn giản. Nếu không có dấu * trong chuỗi mẫu, ta chỉ cần duyệt lần lượt qua từng cặp ký tự trong chuỗi mẫu và chuỗi cần so sánh. Nếu gặp ký tự ? bên chuỗi mẫu thì ta luôn luôn bỏ qua (coi như cặp ký tự ở hai chuỗi là khớp). Ta chỉ cần lưu ý là hai chuỗi phải có cùng chiều dài. int Match(char *pattern, char *str) { int i; int j; for (i=0, j=0;( i<strlen(pattern) ) && ( j <strlen(str)) ;i++,j++) { if ( pattern[i] == '?') continue; else if (pattern[i] != str[j]) return 0; } if ( (i==strlen(pattern)) && (j == strlen(str)) ) return 1; else return 0; } Bước tiếp theo là xử lý trường hợp dấu *. Vì dấu sao đại diện cho nhiều hoặc không ký tự nào nên việc so khớp có vẻ rắc rối. Tuy nhiên, nếu ta xử lý theo kiểu đệ quy thì vấn đề sẽ dễ hiểu và đơn giản hơn. Mục tiêu của đệ quy là đưa bài toán về một bài toán cùng dạng nhưng độ phức tạp giảm dần cho đến khi đạt đến những bài toán cơ bản, dễ giải quyết. Việc xử lý dấu * chỉ có nghĩa khi phần đầu của chuỗi mẫu và chuỗi so sánh đã khớp với nhau, nếu không thì ta đã có thể kết luận ngay là không khớp. Do vậy để đơn giản mà không làm mất tính tổng quát, ta có thể giả sử chuỗi mẫu bắt đầu bằng ký tự * Như vậy chuỗi mẫu sẽ gồm 2 phần: dấu * và phần còn lại. Chuỗi cần so sánh cũng sẽ có 2 phần tương ứng: ký tự tại vị trí dấu * và phần còn lại. Có 3 trường hợp sau dẫn đến kết quả là chuỗi mẫu và chuỗi so sánh khớp nhau: Dấu * là ký tự duy nhất của chuỗi mẫu. Đây là trường hợp hiển nhiên. Phần còn lại của chuỗi mẫu khớp với toàn bộ chuỗi so sánh (tính chất dấu * đại diện cho không có ký tự nào) Toàn bộ chuỗi mẫu khớp với phần còn lại của chuỗi so sánh (tính chất dấu * đại diện cho 1 hoặc nhiều ký tự) Hai trường hợp (b) và (c) sẽ dẫn đến việc thực hiện lại bài toán so khớp giữa chuỗi con của chuỗi mẫu và chuỗi con của chuỗi so sánh. Bạn dễ dàng thấy được tính dừng của phép đệ quy này vì mỗi lần đệ quy ta đều giảm chiều dài của chuỗi mẫu hoặc chuỗi so sánh đi một ký tự. Nếu cả 3 trường hợp trên đều không thỏa thì chuỗi mẫu và chuỗi so sánh không khớp nhau.Bây giờ ta chỉ cần sửa lại chương trình ban đầu để đưa lời gọi đệ quy vào là xong int Match(char *pattern, char *str) { int i; int j; for (i=0, j=0;( i<strlen(pattern) ) && ( j <strlen(str)) ;i++,j++) { if ( pattern[i] == '?') continue; else if (pattern[i] == '*') { if (i==strlen(pattern)-1) return 1; else if (Match(&pattern[i+1], &str[i])) return 1; else if (Match(&pattern[i], &str[j+1])) return 1; else return 0; } else if (pattern[i] != str[j]) return 0; } if ( (i==strlen(pattern)) && (j == strlen(str)) ) return 1; else return 0; }