Giáo trình Cấu trúc dữ liệu và thuật toán - Chương 6: Tìm kiếm

Nội dung text: Giáo trình Cấu trúc dữ liệu và thuật toán - Chương 6: Tìm kiếm

1. Chương 6 : Tìm kiếm Trịnh Anh Phúc 1 1Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường Đại Học Bách Khoa Hà Nội. Ngày 30 tháng 11 năm 2015 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học Bách KhoaNgày Hà 30 Nội. tháng ) 11 năm 2015 1 / 96
2. Giới thiệu 1 Tìm kiếm tuần tự và tìm kiếm nhị phân Tìm kiếm tuần tự Tìm kiếm nhị phân 2 Cây nhị phân tìm kiếm Định nghĩa Biểu diễn cây nhị phân tìm kiếm Sắp xếp nhờ sử dụng BST Cây nhị phân tìm kiếm cân bằng AVL 3 Bảng băm (Mappping and Hashing) Đặt vấn đề Địa chỉ trực tiếp Hàm băm 4 Tìm kiếm xâu mẫu Thuật toán trực tiếp Thuận toán Rabin-Karp Thuận toán Knuth-Morris-Pratt Thuận toán Boyer-Moore 5 Tổng kết Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học Bách KhoaNgày Hà 30 Nội. tháng ) 11 năm 2015 2 / 96
3. Tìm kiếm tuần tự và tìm kiếm nhị phân Định nghĩa bài toán tìm kiếm Bài toán đặt ra Cho danh sách list[0 n-1] và phần tử target, ta cần tìm vị trí i sao cho list[i] = target hoặc trả lại giá trị -1 nếu không có phần tử như vậy trong danh sách Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học Bách KhoaNgày Hà 30 Nội. tháng ) 11 năm 2015 3 / 96
4. Tìm kiếm tuần tự và tìm kiếm nhị phân Tìm kiếm tuần tự (linear search or sequential search) Thuật toán tìm kiếm tuần tự được thực hiện theo ý tưởng sau đây : Bắt đầu từ phần tử đầu tiên, duyệt qua từng phần tử cho đến khi tìm được phần tử đích hoặc kết luận không tìm được. -7 9 -5 2 8 3 -4 Độ phức tạp : O(n) int linearSearch(dataArray list, int size, dataElem target){ int i; for(i = 0;i<size;i++){ if(list[i]==target) return i; } return -1; } Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học Bách KhoaNgày Hà 30 Nội. tháng ) 11 năm 2015 4 / 96
5. Tìm kiếm tuần tự và tìm kiếm nhị phân Tìm kiếm nhị phân (binary search) Điều kiện để thực hiện tìm kiếm nhị phân là : Danh sách phải được sắp xếp Phải cho phép truy vấn trực tiếp Mã nguồn ngôn ngữ C int binarySearch(dataArray list, int size, dataElem target){ int lower = 0, upper = size-1, mid; while(lower target) upper = mid - 1; else if(list[mid]<target) lower = mid+1; else return mid; } return -1; } Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học Bách KhoaNgày Hà 30 Nội. tháng ) 11 năm 2015 5 / 96
6. 1 Tìm kiếm tuần tự và tìm kiếm nhị phân Tìm kiếm tuần tự Tìm kiếm nhị phân 2 Cây nhị phân tìm kiếm Định nghĩa Biểu diễn cây nhị phân tìm kiếm Sắp xếp nhờ sử dụng BST Cây nhị phân tìm kiếm cân bằng AVL 3 Bảng băm (Mappping and Hashing) Đặt vấn đề Địa chỉ trực tiếp Hàm băm 4 Tìm kiếm xâu mẫu Thuật toán trực tiếp Thuận toán Rabin-Karp Thuận toán Knuth-Morris-Pratt Thuận toán Boyer-Moore 5 Tổng kết Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học Bách KhoaNgày Hà 30 Nội. tháng ) 11 năm 2015 6 / 96
7. Cây nhị phân tìm kiếm Đặt vấn đề Ta cần xây dựng cấu trúc dữ liệu biểu diễn các tập động Các phần tử có khóa (key) và thông tin (satellite data) Tập động cần hỗ trợ các truy vấn (queries) như : I Search(S,k) : Tình phần tử có khóa k I Minimum(S), Maximum(S) : Tìm phần tử có khóa nhỏ nhất, lớn nhất I Predecessor(S,x), Successor(S,x) : Tìm phần tử kế cận trước, kế cận sau đồng thời cũng hỗ trợ các thao tác biến đổi (modifying operations) như : I Insert(S,x) : Bổ sung (chèn) I Delete(S,x) : Loại bỏ (xóa) Cây nhị phân tìm kiếm là cấu trúc dữ liệu quan trọng để biểu diễn tập động, trang đó tất cả các thao tác đều thực hiện với thời gian O(h) trong đó h là chiều cao của cây. Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học Bách KhoaNgày Hà 30 Nội. tháng ) 11 năm 2015 7 / 96
8. Cây nhị phân tìm kiếm Định nghĩa Cây nhị phân tìm kiếm (Binary Search Tree - BST) là cây nhị phân có các tính chất sau : left key right parent mỗi nút ngoài thông tin đi kèm có thêm các trường : I left : con trỏ đến con trái I right : con trỏ đến con phải I parent : con trỏ đến cha (tùy chọn) I key : khóa giả sử x là gốc của một cây con, khi đó I với mọi nút y thuộc cây con trái của x thì : key(y) key(x) Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học Bách KhoaNgày Hà 30 Nội. tháng ) 11 năm 2015 8 / 96
9. Cây nhị phân tìm kiếm Các phép toán với cây nhị phân tìm kiếm Tìm kiếm (search) : Tìm kiếm một phần tử khóa trước Tìm cực tiểu, cực đại (maximum, minimum) : Tìm phần tử với khóa nhỏ nhất (lớn nhất) trên cây Kế cận sau, kế cận trước (predecessor, successor) : Tìm phân tử kế cận sau (kế cận trước) của một phần tử trên cây Chèn (insert) : Bổ sung vào cây một phần tử với khóa cho trước Xóa (delete) : Loại bỏ khỏi cây một phần tử khóa cho trước Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học Bách KhoaNgày Hà 30 Nội. tháng ) 11 năm 2015 9 / 96
10. Cây nhị phân tìm kiếm Ví dụ minh họa về cây nhị phân tìm kiếm 43 31 64 20 40 56 89 28 33 47 59 Duyệt BST theo thứ tự giữa thì ra dãy khóa được sắp xếp 20, 28, 31, 33, 40, 43, 47, 56, 59, 64, 89 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 10 / 96
11. Cây nhị phân tìm kiếm Biểu diễn cây nhị phân tìm kiếm Với khóa số nguyên struct TreeNodeRec{ int key; struct TreeNodeRec *leftPtr; struct TreeNodeRec *rightPtr; }; typedef struct TreeNodeRec TreeNode; Với khóa là chuỗi ký tự # define MAXLEN 15 struct TreeNodeRec{ char key[MAXLEN]; struct TreeNodeRec *leftPtr; struct TreeNodeRec *rightPtr; }; typedef struct TreeNodeRec TreeNode; Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 11 / 96
12. Cây nhị phân tìm kiếm Các phép toán cơ bản makeTreeNode(value) - Tạo một nút với khóa cho bởi value search(nodePtr,k) - Tìm kiếm nút có giá trị khóa bằng k trên BST trỏ bởi nodePtr; find-min(nodePtr) - Trả lại nút có khóa có giá trị nhỏ nhất trên BST find-max(nodePtr) - Trả lại nút có khóa có giá trị lớn nhất trên BST successor(nodePtr, x) - Trả lại nút kế cận sau nút x predecessor(nodePtr, x) - Trả lại nút kế cận trước nút x insert(nodePtr, item) - Chèn một nút với khóa cho bởi item vào BST delete(nodePtr, item) - Xóa nút có giá trị bằng khóa trên BST Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 12 / 96
13. Cây nhị phân tìm kiếm Các mô tả trên C đối với các phép toán struct TreeNodeRec { float key; struct TreeNodeRec *leftPtr; struct TreeNodeRec *rightPtr; }; typedef struct TreeNodeRec TreeNode; TreeNode* makeTreeNode(float value); TreeNode* delete(TreeNode* T, float x); TreeNode* findmin(TreeNode* T); TreeNode* findmax(TreeNode* T); TreeNode* insert(TreeNode* nodePtr, float item); TreeNode* search(TreeNode* nodePtr, float item); void PrintInorder(const TreeNode* nodePtr); Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 13 / 96
14. Cây nhị phân tìm kiếm Cấu trúc dữ liệu và giải thuật Các mô tả trên C đối với các phép toán struct TreeNodeRec { float key; Cây nhị phân tìm kiếm struct TreeNodeRec *leftPtr; struct TreeNodeRec *rightPtr; }; typedef struct TreeNodeRec TreeNode; Biểu diễn cây nhị phân tìm kiếm TreeNode* makeTreeNode(float value); TreeNode* delete(TreeNode* T, float x); TreeNode* findmin(TreeNode* T); Cây nhị phân tìm kiếm TreeNode* findmax(TreeNode* T); TreeNode* insert(TreeNode* nodePtr, float item); TreeNode* search(TreeNode* nodePtr, float item); 2015-11-30 void PrintInorder(const TreeNode* nodePtr); Trong các thao tác trên, thao tác loại bỏ (delete) một nút trong cây là phức tạp nhất. Trong khi thao tác tìm kiếm (search) lại đặc trưng nhất cùng với thao tác chèn (insert) một phần tử vào cây BST.
15. Cây nhị phân tìm kiếm Thuật toán bổ sung trên BST Thuật toán bổ sung Tạo nút mới chứa phần tử cần chèn Di chuyển trên cây từ gốc để tìm cha của nút mới : So sánh khóa của nút mới với nút đang xét (bắt đầu là gốc của cây), nếu khóa của phần tử cần chèn lớn hơn (nhỏ hơn) khóa của nút đang xét thì rẽ theo con phải (con trái) của nút đang xét. Nếu gặp NULL thì dừng, nút đang xét là cha cần tìm. Gắn nút con là nút con của nút cha tìm được. Chú ý là nút mới luôn là nút lá. Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 14 / 96
16. Cây nhị phân tìm kiếm Thuật toán bổ sung trên BST (tiếp) Mã giả của giải thuật bổ sung Function Insert(T, item) 1 if (T=NULL) then T ← makeTreeNode(item) 2 else if (item T.key) then 5 T ← Insert(T.right,item) endif 6 endif 7 endif 8 return T End Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 15 / 96
17. Cây nhị phân tìm kiếm Thuật toán bổ sung trên BST (tiếp) Cài đặt ngôn ngữ lập trình C TreeNode *insert(TreeNode * nodePtr, float item){ if(nodePtr==NULL) nodePtr = makeTreeNode(item); else if(item key) nodePtr->leftPtr = insert(nodePtr->leftPtr, item); else if(item > nodePtr->key) nodePtr->rightPtr = insert(nodePtr->rightPtr, item); return nodePtr; } Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 16 / 96
18. Cây nhị phân tìm kiếm Thuật toán tìm kiếm trên BST Để tìm kiếm một khóa trên cây BST ta tiến hành như sau : Nếu khóa cần tìm nhỏ hơn nút hiện tại thì tìm tiếp cây con trái ngược lại, tìm cây con phải ngược lại, nếu bằng giá trị tại nút hiện tại thì đưa ra ngược lại, trả về giá trị NULL không tìm thấy Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 17 / 96
19. Cây nhị phân tìm kiếm Thuật toán tìm kiếm trên BST (tiếp) Mã giả của thuật toán Function search(T, target) 1 if (T not NULL) then 2 if (target T.key) then 6 T ← search(T.right, target) endif 7 endif 8 endif 9 return T End Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 18 / 96
20. Cây nhị phân tìm kiếm Thuật toán tìm kiếm trên BST (tiếp) TreeNode *search(TreeNode *nodePtr, float target){ if(nodePtr!=NULL){ if(target key){ nodePtr = search(nodePtr->leftPtr, target); }else{ if(target > nodePtr->key) nodePtr = search(nodePtr->rightPtr, target); } return nodePtr; } Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 19 / 96
21. Cây nhị phân tìm kiếm Thuật toán tìm phân tử lớn nhất, nhỏ nhất trên BST Việc tìm phần tử nhỏ nhất (lớn nhất) trên cây nhị phân tìm kiếm có thể thực hiện nhờ việc di chuyển trên cây Để tìm phần tử nhỏ nhất, ta đi theo con trái đến khi gặp NULL Để tìm phần tử lớn nhất, ta đi theo con phải đến khi gặp NULL Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 20 / 96
22. Cây nhị phân tìm kiếm Thuật toán tìm phân tử lớn nhất, nhỏ nhất trên BST (tiếp) Mã giả của hai giải thuật Function find-min(T) Function find-max(T) 1 while (T.left 6= NULL) do 1 while (T.right 6= NULL) do 2 T ← T.left 2 T ← T.right 3 endwhile 3 endwhile 4 return T 4 return T End End Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 21 / 96
23. Cây nhị phân tìm kiếm Thuật toán loại bỏ trên BST Khi loại bỏ một nút, cần phải đảm bảo cây thu được vẫn là cây nhị phân tìm kiếm. Vì thế khi xóa cần phải xét cẩn thận các con của nó. Có bốn tình huống xảy ra : Tình huống 1 : Nút cần xóa là lá Tình huống 2 : Nút cần xóa chỉ có con trái Tình huống 3 : Nút cần xóa chỉ có con phải Tình huống 4 : Nút cần xóa có hai con Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 22 / 96
24. Cây nhị phân tìm kiếm Thuật toán loại bỏ trên BST (tiếp) Tình huống 1 : Nút cần xóa x là nút lá Thao tác : Chữa lại nút cha của x có con rỗng 25 15 40 20 30 45 17 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 23 / 96
25. Cây nhị phân tìm kiếm Thuật toán loại bỏ trên BST (tiếp) Tình huống 2 : Nút cần xóa x có con trái mà không có con phải Thao tác : Gắn cây con trái của x vào cha 25 15 40 25 20 30 45 15 40 17 17 30 45 ⇒ Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 24 / 96
26. Cây nhị phân tìm kiếm Thuật toán loại bỏ trên BST (tiếp) Tình huống 3 : Nút cần xóa x có con phải mà không có con trái Thao tác : Gắn cây con phải của x vào cha 25 15 40 25 20 30 45 20 40 17 17 30 45 ⇒ Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 25 / 96
27. Cây nhị phân tìm kiếm Thuật toán loại bỏ trên BST (tiếp) Tình huống 4 : Nút cần xóa x có cả con phải lẫn con trái Thao tác : 1 Chọn nút y để thế vào chỗ của nút x, nút y sẽ là nút kế tiếp (successor) của x. Như vậy, y là giá trị nhỏ nhất còn lớn hơn x, nói cách khác y là giá trị nhỏ nhất của cây con phải của x. 2 Gỡ nút y khỏi cây 3 Nối con phải của y vào cha của y 4 Thay thế y vào nút cần xóa Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 26 / 96
28. Cây nhị phân tìm kiếm Thuật toán loại bỏ trên BST (tiếp) r x r y A B A z B y z D C C D ⇒ Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 27 / 96
29. Cây nhị phân tìm kiếm Thuật toán loại bỏ trên BST (tiếp) 40 30 65 40 25 35 50 33 65 10 28 33 25 35 50 34 10 28 34 ⇒ Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 28 / 96
30. Cây nhị phân tìm kiếm Cấu trúc dữ liệu và giải thuật Thuật toán loại bỏ trên BST (tiếp) 40 Cây nhị phân tìm kiếm 30 65 40 25 35 50 Biểu diễn cây nhị phân tìm kiếm 33 65 Cây nhị phân tìm kiếm 10 28 33 25 35 50 2015-11-30 34 10 28 34 ⇒ Vậy nút thế chỗ của nút 30 cần xóa là nút 33. Nút 33 là nút kế cận của nút 30 khi ta duyệt theo thứ tự giữa để đảm bảo thứ tự giá trị các nút trên cây BST.
31. Cây nhị phân tìm kiếm Mã giả của thao tác loại bỏ Funtion delete(T,x) 1 if (T=NULL) then "Không tìm thấy" 2 else if (x T.key) then /* Đi bên phải */ 5 T.right ← delete(T.right,x) 6 else /* Tìm được phần tử cần xóa */ 7 if (T.left 6= NULL and T.right 6= NULL) then 8 /* Tình huống 4 : có cả cây con phải lẫn con trái */ 9 tmp ← find-min(T.right) /* Thế chỗ ptử min cây con phải */ 10 T.key ← tmp.key Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 29 / 96
32. Cây nhị phân tìm kiếm Mã giả của thao tác loại bỏ (tiếp) 11 T.right ← delete(T.right,T.key) 12 else /* Có một con hoặc không có con*/ 13 tmp ← T 14 if (T.left = NULL) then T ← T.right /* Chỉ con phải */ 15 else if (T.right = NULL) then T ← T.left /* Chỉ con trái */ 16 endif endif 17 free(tmp) 18 endif endif 19 endif 20 endif 21 return T End Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 30 / 96
33. Cây nhị phân tìm kiếm Thuật toán loại bỏ trên BST (tiếp) TreeNode *delete(TreeNode *T, float x){ TreeNode tmp; if(T==NULL) printf("not found"); else if(x key) T->leftPtr = delete(T->leftPtr,x); else if(x> T->key) T->rightPtr = delete(T->rightPtr,x); else /*Tìm được phần tử cần xóa */ if(T->leftPtr && T->rightPtr){/* Tình huống 4 */ tmp = findmin(T->right); T->key = tmp->key; T->rightPtr = delete(T->key,T->rightPtr); }else{/* có một con hoặc không có con*/ tmp = T; Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 31 / 96
34. Cây nhị phân tìm kiếm Thuật toán loại bỏ trên BST (tiếp) if(T->leftPtr==NULL)/* chỉ có con phải */ T = T->rightPtr; else /* chỉ có con trái */ T = T->leftPtr; free(tmp); } return(T); } Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 32 / 96
35. Cây nhị phân tìm kiếm Sắp xếp nhờ sử dụng BST Do duyệt cây BST theo thứ tự giữa ra dãy các từ khóa được sắp xếp nên ta có thể sử dụng cây BST để giải quyết bài toán sắp xếp như sau Xây dựng cây BST tương ứng với dãy số đã cho bằng cách chèn (insert) từng khóa trong dãy vào cây BST. Duyệt cây BST thu được theo thứ tự giữa để đưa ra dãy được sắp xếp. Minh họa cây BST với dãy khóa chưa sắp xếp : 40, 65, 33, 35, 34, 25, 50, 28, 10 40 33 65 25 35 50 10 28 34 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 33 / 96
36. Cây nhị phân tìm kiếm Phân tích hiệu quả của sắp xếp nhờ sử dụng cây BST Tình huống trung bình : O(n log n) vì chèn phần tử thứ (i + 1) tốn quãng thời gian log2(i) phép so sánh. Ví dụ như dãy : 9, 15, 7, 8, 1, 11, 17 9 7 15 1 8 11 17 Tình huống tồi nhất : O(n2) bởi vì bổ sung phần tử thứ (i + 1) tốn quãng i phép so sánh. Ví dụ dãy đã đc sắp xếp : 1, 3, 7, 9, 11, 15, 17 1 3 7 9 11 15 17 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 34 / 96
37. Cây nhị phân tìm kiếm Sắp xếp nhờ sử dụng BST (tiếp) Độ phức tạp trung bình của các thao tác Ta biết được rằng độ cao trung bình của cây BST là : h = O(log n) từ đó suy ra độ phức tạp trung bình của các thao tác với BST Chèn O(log n) Xóa O(log n) Tìm giá trị lớn nhất O(log n) Tìm giá trị nhỏ nhất O(log n) Sắp xếp O(n log n) Tất nhiên trường hợp tồi nhất là khi cây nhị phân BST bị mất cân đối do dãy đã được sắp xếp làm tối đa hóa chiều cao của cây h = n, như ví dụ ở slice trước Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 35 / 96
38. Cây nhị phân tìm kiếm Sắp xếp nhờ sử dụng BST (tiếp) Vấn đề đặt ra : Có cách nào để tạo ra một cây nhị phân BST sao cho chiều cao của cây là nhỏ nhất có thể, hay nói cách khác chiều cao h = log n. Có hai cách tiếp cận để nhằm đảm bảo độ cao của cây là nhỏ nhất O(log n) Luôn giữ cho cây cân bằng tại mọi thời điểm (AVL tree) Thỉnh thoảng lại kiểm tra lại xem cây có "quá mất cân bằng" không (Splay tree). Trong giáo trình này ta chỉ đề cập đến cây nhị phân tìm kiếm cân bằng AVL Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 36 / 96
39. Cây nhị phân tìm kiếm cân bằng Cây nhị phân tìm kiếm cân bằng Định nghĩa Cây AVL (Adelson-Velskii-Landis) là cây nhị phân tìm kiếm thỏa mãn tính chất Chiều cao của cây con trái và cây con phải của nút gốc bất kỳ sai khác nhau không quá một đơn vị. Cả cây con phải và cây con trái cũng đều là AVL Tính chất : Chênh lệch độ cao của cây con trái và cây con phải của một nút bất kỳ trong cây là không quá một. Hệ số cân bằng (balance factor) : của nút x, ký hiệu bal(x), là bằng hiệu giữa chiều cao của cây con phải trừ cây con trái của x. bal(x) = height(x.left) − height(x.right) Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 37 / 96
40. Cây nhị phân tìm kiếm cân bằng Biểu diễn cây nhị phân tìm kiếm cân bằng Biểu diễn cấu trúc cây AVL trong ngôn ngữ C struct treeNode{ int key; struct TreeNode* left; struct TreeNode* right; int height;/* Dùng tính hệ số cân bằng */ } typedef struct TreeNode AvlTree; height key left right Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 38 / 96
41. Cây nhị phân tìm kiếm cân bằng Hai phép quay cơ bản không làm mất tính chất cây BST k1 k2 k2 k1 C A A B B C ⇔ Quay phải quanh k1 Quay trái quanh k2 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 39 / 96
42. Cây nhị phân tìm kiếm cân bằng Mã nguồn phép quay phải AvlTree ∗ rightRotate(AvlTree ∗k1 , int key) { AvlTree ∗k2 = k1−>l e f t ; AvlTree ∗B = k2−>r i g h t ; // Xoay k2−>r i g h t = k1 ; k1−>l e f t = B ; // Cap nhat chieu cao k1−>height = max(height(k1−>left), height(k1−>right))+1; k2−>height = max(height(k2−>left), height(k2−>right))+1; // Tra lai goc moi r e t u r n k2; } Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 40 / 96
43. Cây nhị phân tìm kiếm cân bằng Mã nguồn phép quay trái AvlTree ∗ leftRotate(AvlTree ∗k2 , int key) { AvlTree ∗k1 = k2−>r i g h t ; AvlTree ∗B = k1−>l e f t ; // Xoay k1−>l e f t = k2 ; k2−>r i g h t = B ; // Cap nhat chieu cao k1−>height = max(height(k1−>left), height(k1−>right))+1; k2−>height = max(height(k2−>left), height(k2−>right))+1; // Tra lai goc moi r e t u r n k1; } Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 41 / 96
44. Cây nhị phân tìm kiếm cân bằng Khôi phục tính cân bằng của cây AVL Trước khi khôi phục tính chất này cây đang cây cân bằng AVL Sau khi thực hiện thao tác bổ sung hay loại bỏ cây có thể trở thành mất cân bằng Chiều cao của cây con chỉ có thể hoặc giảm nhiều nhất là 1, vì thế nếu xảy ra mất cân bằng thì chênh lệch chiều cao giữa hai cây con chỉ có thể tối đa là 2. Có tất cả 4 tình huống với chênh lệch chiều cao là 2 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 42 / 96
45. Cây nhị phân tìm kiếm cân bằng Khôi phục tính cân bằng của cây AVL Tình huống 1 (left left case): Cây con trái cao hơn cây con phải bởi cây con trái của con trái k1 k2 C B A Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 43 / 96
46. Cây nhị phân tìm kiếm cân bằng Khôi phục tính cân bằng của cây AVL : Tình huống 1 k1 k2 k2 k1 C B A A B C ⇒ Quay phải quanh k1 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 44 / 96
47. Cây nhị phân tìm kiếm cân bằng Khôi phục tính cân bằng của cây AVL (tiếp) Tình huống 2 (right right case) : Cây con phải cao hơn cây con trái bởi cây con phải của con phải k1 k2 A B C Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 45 / 96
48. Cây nhị phân tìm kiếm cân bằng Khôi phục tính cân bằng của cây AVL : Tình huống 2 k1 k2 k2 k1 A B C A B C ⇒ Quay trái quanh k1 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 46 / 96
49. Cây nhị phân tìm kiếm cân bằng Khôi phục tính cân bằng của cây AVL (tiếp) Tình huống 3 (left right case) : Cây con trái cao hơn cây con phải nguyên do bởi cây con phải của con trái k1 k2 k3 C A B1 B2 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 47 / 96
50. Cây nhị phân tìm kiếm cân bằng Khôi phục tính cân bằng của cây AVL : Tình huống 3 k1 k1 k2 k3 k3 k2 C C A B2 B B A B1 1 2 ⇒ Trước tiên là quay trái quanh k2 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 48 / 96
51. Cây nhị phân tìm kiếm cân bằng Khôi phục tính cân bằng của cây AVL : Tình huống 3 (tiếp) k1 k3 k3 k2 k2 k1 C B2 A B A B B C 1 ⇒ 1 2 Quay phải quanh k1 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 49 / 96
52. Cây nhị phân tìm kiếm cân bằng Khôi phục tính cân bằng của cây AVL (tiếp) Tình huống 4 (right left case) : Cây con phải cao hơn cây con trái nguyên do bởi cây con trái của con phải k1 k2 k3 A C B1 B2 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 50 / 96
53. Cây nhị phân tìm kiếm cân bằng Khôi phục tính cân bằng của cây AVL : Tình huống 4 Quay phải quanh k2, sau đó quay trái quanh k1 k1 k2 k2 k3 k1 k3 A C B B A B1 B2 C 1 2 ⇒ Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 51 / 96
54. Cây nhị phân tìm kiếm cân bằng Hai thao tác có thể gây mất cân bằng trên cây AVL Thao tác chèn thêm một khóa mới k - insert Thao tác xóa bỏ một khóa k - delete Ý tưởng thực hiện lập trình cài đặt cây AVL Dùng trường dữ liệu chiều cao - height - để xác định hệ số cân bằng cho nút cha Nút mới luôn có chiều cao là 1 Khi chèn cũng như xóa một nút khóa cần cập nhật giá trị chiều cao để phát hiện sự mất cân bằng Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 52 / 96
55. Cây nhị phân tìm kiếm cân bằng Các bước giải thuật chèn đệ quy - Insert(k) 1 Thực hiện chèn như cây BST bình thường 2 Nút hiện tại sẽ là nút tổ tiên của nút mới k đang chèn, cập nhật lại chiều cao của nó 3 Tính hệ số cân bằng mới, chiều cao cây con trái - chiều cao cây con phải, của nút hiện tại 4 Nếu hệ số lớn hơn 1, sẽ có thể xảy ra hai tình huống I Tình huống 1 I Tình huống 3 5 Nếu hệ số nhỏ hơn -1, sẽ có thể xảy ra hai tình huống I Tình huống 2 I Tình huống 4 Để xác định đúng tình huống cụ thể, so sánh khóa mới chèn k với k2 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 53 / 96
56. Cây nhị phân tìm kiếm cân bằng Mã nguồn thao tác chèn AvlTree ∗ insert(AvlTree ∗ node ) {/ ∗ 1 . Chen binh thuong(Khong viet lai code) ∗/ /∗ 2 . Cap nhat chieu cao nut hien tai ∗/ node−>height=max(height(node−>left ),height(node−>right))+1; /∗ 3 . Tinh he so can bang ∗/ i n t balance = getBalance(node);// Co4 tinh huong i f (balance > 1 && key l e f t −>key )// Tinh huong1 r e t u r n rightRotate(node); i f (balance node−>r i g h t −>key )// Tinh huong2 r e t u r n leftRotate(node); i f (balance > 1 && key > node−>l e f t −>key ){// Tinh huong3 node−>left = leftRotate(node−>l e f t ) ; r e t u r n rightRotate(node);} i f (balance r i g h t −>key ){// Tinh huong4 node−>right = rightRotate(node−>r i g h t ) ; r e t u r n leftRotate(node);} r e t u r n node;// Tra lai nut hien tai } Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 54 / 96
57. Cây nhị phân tìm kiếm cân bằng Các bước giải thuật xóa đệ quy - Delete(k) 1 Thực hiện xóa như cây BST bình thường 2 Nút hiện tại sẽ là nút tổ tiên của nút k bị xóa, cập nhật lại chiều cao của nó 3 Tính hệ số cân bằng mới của nút hiện tại 4 Nếu hệ số lớn hơn 1, sẽ có thể xảy ra hai tình huống I Tình huống 1 I Tình huống 3 5 Nếu hệ số nhỏ hơn -1, sẽ có thể xảy ra hai tình huống I Tình huống 2 I Tình huống 4 Để xác định đúng tình huống cụ thể, kiểm tra tiếp hệ số cân bằng của cây con gốc k2 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 55 / 96
58. Cây nhị phân tìm kiếm cân bằng Mã nguồn thao tác xóa AvlTree ∗ delete(AvlTree ∗ node ){ /∗ 1 thuc hien xoa binh thuong(Khong viet lai code) ∗/ /∗ 2 cap nhat chieu cao not hien tai ∗/ node−>height=max(height(node−>left ),height(node−>right))+1; /∗ 3 tinh he so can bang ∗/ i n t balance = getBalance(node);// Co4 tinh huong i f (balance>1 && getBalance(node−>l e f t )>=0)// Tinh huong1 r e t u r n rightRotate(node); i f (balance>1 && getBalance(node−>l e f t ) left = leftRotate(node−>l e f t ) ; r e t u r n rightRotate(node);} i f (balance right) right) > 0){// Tinh huong4 node−>right = rightRotate(node−>r i g h t ) ; r e t u r n leftRotate(node);} r e t u r n node; } 1 1Xem thêm về cây đỏ-đen (Red-Black tree) Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 56 / 96
59. 1 Tìm kiếm tuần tự và tìm kiếm nhị phân Tìm kiếm tuần tự Tìm kiếm nhị phân 2 Cây nhị phân tìm kiếm Định nghĩa Biểu diễn cây nhị phân tìm kiếm Sắp xếp nhờ sử dụng BST Cây nhị phân tìm kiếm cân bằng AVL 3 Bảng băm (Mappping and Hashing) Đặt vấn đề Địa chỉ trực tiếp Hàm băm 4 Tìm kiếm xâu mẫu Thuật toán trực tiếp Thuận toán Rabin-Karp Thuận toán Knuth-Morris-Pratt Thuận toán Boyer-Moore 5 Tổng kết Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 57 / 96
60. Bảng băm Đặt vấn đề Cho bảng T và các bản ghi x với từ khóa và dữ liệu đi kèm, ta cần hỗ trợ các thao tác sau : Chèn : Insert(T,x) Xóa : Delete(T,x) Search(T,x) Ta muốn thực hiện thao tác này một cách nhanh chóng mà không phải thực hiện việc sắp xếp các bản ghi. Bảng băm là các tiếp cận giải quyết vấn đề đặt ra. Chú ý Ta sẽ chỉ xét các khóa là số nguyên dương Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 58 / 96
61. Bảng băm Ứng dụng Xây dựng chương trình của ngôn ngữ lập trình (Compiler) : Ta cần thiết lập bảng ký hiệu trong đó khóa của các phần tử là dãy ký tự Bảng băm là cấu trúc dữ liệu hiệu quả để cài đặt từ điển Mặc dù trong tình huống xấu nhất việc tìm kiếm đòi hỏi thời gian O(n) giống như tìm kiếm tuyến tính, nhưng trên thực tế bảng băm làm việc hiệu quả hơn nhiều. Với một số giả thiết hợp lý, việc tìm kiếm phần tử trong bảng băm đòi hỏi thời gian O(1) Bảng băm có thể xem như sự mở rộng mảng thông thường. Việc địa chỉ hóa trực tiếp trong mảng cho phép truy cập đến phần tử bất kỳ trong thời gian O(1) Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 59 / 96
62. Bảng băm Địa chỉ trực tiếp - Direct addressing Giả thiết rằng : Các khóa là các số trong khoảng từ 0 đến m-1 Các khóa là khác nhau từng đôi một Ý tưởng : Thiết lập mảng T[0 m-1] trong đó T[i] = x nếu x ∈ T và key[x] = i T[i] = NULL nếu trái lại T được gọi là bảng địa chỉ trực tiếp (direct-address table) các phần tử trong bảng T sẽ được gọi là các ô. Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 60 / 96
63. Bảng băm Địa chỉ trực tiếp (tiếp) Tạo bảng địa chỉ trực tiếp T. Mỗi khóa trong tập U = {0,1,2, ,9} tương ứng với một chỉ số trong bảng. Tập K = {2,3,6,8} gồm các khóa thực có xác định các ô trong bảng chứa con trỏ trỏ đến các phần tử. 0 1 2 2 8 3 3 3 2 4 5 6 6 6 7 8 8 9 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 61 / 96
64. Bảng băm Địa chỉ trực tiếp (tiếp) Cấu trúc dữ liệu và giải thuật Tạo bảng địa chỉ trực tiếp T. Mỗi khóa trong tập U = {0,1,2, ,9} tương ứng với một chỉ số trong bảng. Tập K = {2,3,6,8} gồm các khóa thực có Bảng băm (Mappping and Hashing) xác định các ô trong bảng chứa con trỏ trỏ đến các phần tử. 0 1 2 2 8 Địa chỉ trực tiếp 3 3 3 2 4 5 Bảng băm 6 6 6 7 2015-11-30 8 8 9 Tập U, hay tập khóa toàn bộ, được minh họa bởi hình tròn mầu đen bao ngoài. Tập K, hay tập khóa thực, được minh họa bởi hình tròn mầu trắng nằm trong. Bảng địa chỉ trực tiếp T được minh họa bởi cột giá trị tương ứng của tập khóa toàn bộ U.
65. Bảng băm Địa chỉ trực tiếp (tiếp) Các phép toán được cài đặt một cách trực tiếp DIRECT-ADDRESS-SEARCH(T,k) return T[k] DIRECT-ADDRESS-INSERT(T,k) T[key[x]] ← x DIRECT-ADDRESS-DELETE(T,k) T[key[x]] ← NULL Thời gian thực hiện các phép toán đều là O(1) Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 62 / 96
66. Bảng băm Địa chỉ trực tiếp (tiếp) Hạn chế của địa chỉ trực tiếp là việc chỉ thích hợp nếu biên độ m của các khóa là nhỏ. Giả sử các khóa là số nguyên dương có chiều dài 32 bit thi sao ? Vấn đề 1 : bảng địa chỉ trực tiếp sẽ phải có 232 (hơn 4 tỷ) phần tử Vấn đề 2 : ngay cả khi bộ nhớ không là vấn đề thì thời gian khởi tạo các phần tử NULL cũng rất tốn kém Cách giải quyết là ánh xạ khóa vào khoảng biến đổi nhỏ hơn 0 m-1. Ánh xạ này được gọi là hàm băm (hash function) Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 63 / 96
67. Bảng băm Hàm băm - Hash Function Khi sử dụng hàm băm, vấn đề nảy sinh là xung đột (collision), hiện tượng khi nhiều khóa được ánh xạ tương ứng vào cùng một ô trong bảng địa chỉ T. 0 h(k2) k8 h(k3) k3 k2 h(k5) k5 h(k6)=k(k8) k6 m-1 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 64 / 96
68. Bảng băm Cấu trúc dữ liệu và giải thuật Hàm băm - Hash Function Khi sử dụng hàm băm, vấn đề nảy sinh là xung đột (collision), hiện tượng khi nhiều khóa được ánh xạ tương ứng vào cùng một ô trong bảng địa chỉ Bảng băm (Mappping and Hashing) T. 0 h(k2) k8 Hàm băm h(k3) k3 k2 h(k5) k5 h(k6)=k(k8) Bảng băm k6 2015-11-30 m-1 Trong hình minh họa, vị trí xung đột khi hai khóa k6 và k8, cùng được trỏ vào cùng ô địa chỉ trong bảng T
69. Bảng băm Hàm băm (tiếp) Để giải quyết xung đột khi dùng hàm băm, ta có hai cách tiếp cận chính để giải quyết xung đột Cách 1 : Dùng địa chỉ mở (open addressing) Cách 2 : Tạo chuỗi (chaining) Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 65 / 96
70. Bảng băm Địa chỉ mở Trong phương pháp địa chỉ mở, tất cả các phần tử đều được cất giữ vào bảng. Do đó mỗi ô của bảng hoặc là chứa khóa hoặc là NULL. Ý tưởng chính của phương pháp này là Để thực hiện việc bổ sung, nếu ô tìm được là bận, ta sẽ tiến hành khảo sát lần lượt (hay còn gọi là dò thử) các ô của bảng cho đến khi tìm được ô rỗng để nạp khóa vào. Khi khảo sát, hay dò thử ô còn trống, ta sẽ tìm dọc theo dãy các phép thử khi thực hiện chèn phần tử vào bảng. I Nếu tìm được phần tử với khóa đã cho thì trả lại nó. I Nếu tìm được con trỏ NULL, thì phần cần tìm không có trong bảng Để xác định được ô dò thử, ta cần mở rộng định nghĩa hàm băm như sau h : U × {0, 1, ··· , m − 1} 7→ {0, 1, ··· , m − 1} Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 66 / 96
71. Bảng băm Địa chỉ mở (tiếp) Trong phương pháp địa chỉ mở ta đòi hỏi, với mỗi khóa k, dãy dò thử phải là hoán vị của do đó mỗi vị trí trong bảng sẽ được xét như là một ô để chứa khóa mới khi ta tiến hành bổ sung vào bảng Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 67 / 96
72. Bảng băm Địa chỉ mở (tiếp) Việc bổ sung khóa k sẽ được mô tả trong đoạn mã giả sau HASH-INSERT(T,k) 1 i ← 0 2 repeat 3 j ← h(k,i) 4 if (T[j] = NULL) then T[j] ← k return j 5 else i ← i+1 6 endif 7 until (i=m) 8 error "lỗi tràn bảng băm" TrịnhEnd Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 68 / 96
73. Bảng băm Địa chỉ mở (tiếp) Việc tìm kiếm khóa k sẽ được mô tả trong đoạn mã giả sau HASH-SEARCH(T,k) 1 i ← 0 2 repeat 3 j ← h(k,i) 4 if (T[j]=j) then return j endif 5 i ← i+1 6 until ((T[j]=NULL) or (i=m)) 7 return NULL End Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 69 / 96
74. Bảng băm Cấu trúc dữ liệu và giải thuật Địa chỉ mở (tiếp) Việc tìm kiếm khóa k sẽ được mô tả trong đoạn mã giả sau HASH-SEARCH(T,k) Bảng băm (Mappping and Hashing) 1 i ← 0 2 repeat 3 j ← h(k,i) Hàm băm 4 if (T[j]=j) then return j endif 5 i ← i+1 6 until ((T[j]=NULL) or (i=m)) Bảng băm 7 return NULL 2015-11-30 End Việc loại bỏ gặp khó khăn hơn. Thông thường ta sẽ đánh dấu loại bỏ chứ không bỏ thực sự.
75. Bảng băm Địa chỉ mở (tiếp) Việc dò thường dùng 3 kỹ thuật sau Dò tuyến tính (linear probing) h(k, i) = (h0(k) + i) mod m Dò toàn phương (quadratic probing) 0 2 h(k, i) = (h (k) + c1i + c2i ) mod m Băm kép (double hashing) h(k, i) = (h1(k) + ih2(k)) mod m trong đó h1(k) và h2(k) là hàm băm bổ trợ Với i=0,1,··· m-1, h’(k) là hàm băm ban đầu còn c1 và c2 6= 0 là hằng số cho trước. Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 70 / 96
76. Bảng băm Tạo chuỗi (chaining) Theo phương pháp này, ta sẽ tạo ra danh sách móc nối để chứa các phần tử được gắn vào cùng vị trí 0 k1 k2 NULL k1 k8 k3 NULL k4 k3 k2 k5 NULL k5 k8 k4 k6 NULL k6 m-1 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 71 / 96
77. Bảng băm Tạo chuỗi (tiếp) Vấn đề khi thực hiện việc tạo chuỗi Ta nên thực hiện bổ sung phần tử như thế nào ? Trả lời : được bổ sung như danh sách móc nối với hình minh họa trên. Ta cần loại bỏ phần tử như thế nào ? Trả lời : Nên dùng danh sách móc nối đơn cho việc loại bỏ dữ liệu được dễ dàng. Thực hiện tìm kiếm phần tử khóa cho trước như thế nào ? Trả lời : Chúng ta dùng hàm băm xác định ô trên T, sau đó duyệt tuần tự theo danh sách móc nối để xác định vị trí phần tử. Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 72 / 96
78. Bảng băm Tạo chuỗi (tiếp) Chọn hàm băm - choising hash funtion : Thời gian tính của hàm băm là bao nhiêu ? Thời gian tìm kiếm phân tử sẽ như thế nào ? Do đó này sinh ra hai yêu cầu Phải phân bố đều các khóa vào các ô Không phụ thuộc vào khuôn mẫu của dữ liệu Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 73 / 96
79. Bảng băm Tạo chuỗi (tiếp) Hàm băm được xác định bởi phương pháp chia (the division method) Ta xác định hàm băm theo công thức h(k) = k mod m phương pháp nhân (the multiplication method) Ta nhân k với hằng số A, 0<a<1 và lấy phân thập phân của kA. Sau đó nhân giá trị này với m rồi lấy phần nguyên của kết quả. I Chọn hằng số A, 0<A<1 I h = bm(kA − bkAc)c Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 74 / 96
80. Bảng băm Cấu trúc dữ liệu và giải thuật Tạo chuỗi (tiếp) Hàm băm được xác định bởi Bảng băm (Mappping and Hashing) phương pháp chia (the division method) Ta xác định hàm băm theo công thức h(k) = k mod m Hàm băm phương pháp nhân (the multiplication method) Ta nhân k với hằng số A, 0<a<1 và lấy phân thập phân của kA. Sau đó nhân giá trị này với m rồi lấy phần nguyên của kết quả. Bảng băm I Chọn hằng số A, 0<A<1 I h = bm(kA − bkAc)c 2015-11-30 Đối với phương pháp chia, nếu m là luy thừa của 2 chẳng hạn 2p thì h(k) chính là số p bit cuối của k. Vì thế người ta thường chọn kích thước bảng m là số nguyên tố không quá gần với lũy thừa của 2. Đối với phương pháp nhân, thông thường m = 2p còn A thì không quá gần 0 √ hoặc 1 Knuth khuyên A = ( 5 − 1)/2
81. 1 Tìm kiếm tuần tự và tìm kiếm nhị phân Tìm kiếm tuần tự Tìm kiếm nhị phân 2 Cây nhị phân tìm kiếm Định nghĩa Biểu diễn cây nhị phân tìm kiếm Sắp xếp nhờ sử dụng BST Cây nhị phân tìm kiếm cân bằng AVL 3 Bảng băm (Mappping and Hashing) Đặt vấn đề Địa chỉ trực tiếp Hàm băm 4 Tìm kiếm xâu mẫu Thuật toán trực tiếp Thuận toán Rabin-Karp Thuận toán Knuth-Morris-Pratt Thuận toán Boyer-Moore 5 Tổng kết Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 75 / 96
82. Tìm kiếm xâu mẫu - string searching Phát biểu bài toán Xâu (String) T là một dãy ký hiệu lấy từ bảng chữ cái (alphabet) P. Ký hiệu T [i ··· j] là xâu con của T bắt đầu từ vị trí i kết thúc ở vị trí j. T [1···n] z }| { a1a2 ··· ai−1 ai ai+1 ··· aj−1aj aj+1 ··· an−1an | {z } T [i···j] Trượt Cho T1 và T2 là hai xâu, trong đó chiều dài hai xâu |T1| = m và |T2| = n với m < n. Ta nói T1 xuất hiện nhờ trượt đến s trong T2 nếu T1[1 ··· m] = T2[s + 1 ··· s + m] T1 z }| { a1 ··· as+1 ··· as+m ··· an | {z } T2 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 76 / 96
83. Tìm kiếm xâu mẫu - string searching Phát biểu bài toán (tiếp) Ví trị khớp và không khớp Giả sử T1 và T2 là hai xâu. Nếu T1 xuất hiện nhờ trượt đến s được gọi là vị trí khớp của T1 trong T2. Trong trường hợp ngược lại, vị trí s được gọi là ví trí không khớp. Bài toán tìm kiếm xâu mẫu - the string matching problem Cho xâu T độ dài |T | = n và xâu mẫu P trong đó |P| = m có độ dài m << n. Tìm tất cả vị trí khớp s của P trong T . Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 77 / 96
84. Thuật toán trực tiếp - Naive algorithm Ý tưởng Trượt đến từng vị trí s = 0, 1, ··· , n − m với mỗi vị trí kiểm tra xem xâu mẫu có xuất hiện ở vị trí đó hay không. Mã nguồn ngôn ngữ C void NaiveSM(char *P, int m, char *T, int n) { int i,s; for(s=0;s =m) OUTPUT(s); } } Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 78 / 96
85. 1 Tìm kiếm tuần tự và tìm kiếm nhị phân Tìm kiếm tuần tự Tìm kiếm nhị phân 2 Cây nhị phân tìm kiếm Định nghĩa Biểu diễn cây nhị phân tìm kiếm Sắp xếp nhờ sử dụng BST Cây nhị phân tìm kiếm cân bằng AVL 3 Bảng băm (Mappping and Hashing) Đặt vấn đề Địa chỉ trực tiếp Hàm băm 4 Tìm kiếm xâu mẫu Thuật toán trực tiếp Thuận toán Rabin-Karp Thuận toán Knuth-Morris-Pratt Thuận toán Boyer-Moore 5 Tổng kết Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 79 / 96
86. Thuận toán Rabin-Karp Ý tưởng Coi mẫu P là một khóa khi chuyển nó thành số nguyên p, tương tự như vậy ta cũng chuyển đổi các xâu con của T [1 ··· n] thành các số nguyên tương ứng với n − m vị trí, như vậy ta chuyển đổi các xâu con liên tiếp của T[] thành các số nguyên Với s = 0, 1, ··· , n − m chuyển thành các số nguyên tương đương ts Như vậy, mẫu xuất hiện ở vị trí s khi và chỉ khi p = ts Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 80 / 96
87. Thuận toán Rabin-Karp Tính số mẫu p Giả sử P = {0, 1} ta có số nguyên p được tính như sau p = 2m−1P[0] + 2m−2P[1] + ··· + 2P[m − 2] + P[m − 1] hoặc có thể viết lặp theo sơ đồ Horner p = P[m − 1] + 2 ∗ (P[m − 2] + 2 ∗ (P[m − 2] + ··· + 2 ∗ P[0]) ··· ) ta có cài đặt trên C đoạn chương trình tính p như sau : p = 0; for(i=0;i<m;i++) p = 2*p + P[i]; thủ tục đòi hỏi thời gian tính toán là O(m) nếu phép toán gán tính là O(1) Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 81 / 96
88. Thuận toán Rabin-Karp Tính các số nguyên trong xâu T[] Một cách tương tự, tính (n-m+1) số nguyên ts từ xâu văn bản thực hiện trong ngôn ngữ C là : for(s=0;s<=n-m;s++){ t[s] = 0; for(i=0;i<m;i++) t[s] = 2*t[s] + T[s+i]; } Việc này đòi hỏi thời gian O((n − m + 1)m) với giả thiết các phép toán số học được thực hiện với thời gian O(1) trên đây rõ ràng là công đoạn tốn kém. Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 82 / 96
89. Thuận toán Rabin-Karp Tính các số nguyên trong xâu T[] cải tiến Để ý rằng ta có có thể tính t[s] từ t[s − 1] như sau t[s − 1] = 2m−1T [s − 1] + 2m−2T [s] + ··· + 2T [s + m − 3] + T [s + m − 2] t[s] = 2m−1T [s] + 2m−2T [s + 1] + ··· + 2T [s + m − 2] + T [s + m − 1] Suy ra, ta có công thức sau t[s] = 2 ∗ (t[s − 1] − 2m−1 ∗T [s − 1]) + T [s + m − 1] | {z } offset Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 83 / 96
90. Thuận toán Rabin-Karp Tính các số nguyên trong xâu T[] cải tiến Ta có thể cải tiến công đoạn trên như sau t[0] = 0; offset = 1; for(i=1;i<m;i++) offset = 2*offset; for(i=0;i<m;i++) t[0] = 2*t[0]+T[i]; for(s=1;s<=n-m;s++) t[s] = 2*(t[s-1]-offset*T[s-1])+T[s+m-1]; Việc này đòi hỏi thời gian O(n + m) với giả thiết các phép toán số học được thực hiện với thời gian O(1) Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 84 / 96
91. 1 Tìm kiếm tuần tự và tìm kiếm nhị phân Tìm kiếm tuần tự Tìm kiếm nhị phân 2 Cây nhị phân tìm kiếm Định nghĩa Biểu diễn cây nhị phân tìm kiếm Sắp xếp nhờ sử dụng BST Cây nhị phân tìm kiếm cân bằng AVL 3 Bảng băm (Mappping and Hashing) Đặt vấn đề Địa chỉ trực tiếp Hàm băm 4 Tìm kiếm xâu mẫu Thuật toán trực tiếp Thuận toán Rabin-Karp Thuận toán Knuth-Morris-Pratt Thuận toán Boyer-Moore 5 Tổng kết Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 85 / 96
92. Thuận toán Knuth-Morris-Pratt Sử dụng hàm bổ trợ (prefix) Định nghĩa của prefix : Xâu W được gọi là prefix của xâu X nếu X=WY với một xâu Y nào đó, ký hiệu là W ⊂ X. Định nghĩa của suffix : Xâu W được gọi là suffix của xâu X nếu X= YW với một xâu Y nào đó, ký hiệu là W ⊃ X. Ví dụ : W = ab là prefix của X=abefac, trong đó Y = efac. Ngược lại, W = cdaa là suffix của X = acbecdaa, trong đó Y = acbe Chú ý : Xâu rỗng, ký hiệu , là prefix và suffix của mọi xâu. Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 86 / 96
93. Thuận toán Knuth-Morris-Pratt Bổ đề Giả sử X ⊃ Z và Y ⊃ Z khi đó 1 nếu |X| ≤ |Y| thì X ⊃ Y 2 nếu |X| ≥ |Y| thì Y ⊃ X 3 nếu |X| = |Y| thì Y = X Dịch chuyển tối thiểu Vấn đề đặt ra : Biết rằng prefix P[1 q] của xâu mẫu là khớp với đoạn T[(s+1) (s+q)] tìm giá trị nhỏ nhất s’>s sao cho : P[1 k] = T [(s0 + 1) (s0 + k)], trong đó s0 + k = s + q Khi đó, tại vị trí s’, không cần thiết so sánh k ký tự đầu của P với các ký tự tương ứng của T, bởi vì ta biết chắc chúng khớp nhau. Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 87 / 96
94. Thuận toán Knuth-Morris-Pratt Hàm tiền tố prefix function : π[q] là độ dài của prefix dài nhất của P[1 m] đồng thời là suffix thực sự của P[1 q] nghĩa là π[q] = max{k : k < q và P[1 k] là suffix của P[1 q]} Ví dụ Xét xâu mẫu P = ababababca còn bảng dưới đây cho giá trị của hàm tiền tố i 1 2 3 4 5 6 7 8 9 10 P[i] a b a b a b a b c a π[i] 0 0 1 2 3 4 5 6 0 1 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 88 / 96
95. Thuận toán Knuth-Morris-Pratt Giải thuật tính giá trị hàm prefix Compute-Prefix-Function(P) 1 m ← length(P) 2 π[1] ← 0 3 k ← 0 4 for q ← 2 to m do 5 while (k>0) and (P[k+1] 6= P[q]) do k ← π[k] endwhile 6 if (P[k+1] = P[q]) then k ← k+1 endif 7 π[q] ← k 8 endfor 9 return π End Thời gian tính giải thuật Θ(m) Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 89 / 96
96. Thuận toán Knuth-Morris-Pratt KMP-Matcher(T,P) // n = |T| và m = |P| 1 π ← Compute-Prefix-Function(P) 2 q ← 0 3 for i ← 1 to n do 4 while (q > 0) and (P[q+1] 6= T[i]) do q ← π[q] endwhile 5 if (P[q+1] = T[i]) then q ← q+1 endif 6 if (q=m) then 7 In ra pattern ở vị trí i-m 8 q ← π[q] 9 endif 10 endfor End Thời gian tính giải thuật Θ(m + n) Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 90 / 96
97. 1 Tìm kiếm tuần tự và tìm kiếm nhị phân Tìm kiếm tuần tự Tìm kiếm nhị phân 2 Cây nhị phân tìm kiếm Định nghĩa Biểu diễn cây nhị phân tìm kiếm Sắp xếp nhờ sử dụng BST Cây nhị phân tìm kiếm cân bằng AVL 3 Bảng băm (Mappping and Hashing) Đặt vấn đề Địa chỉ trực tiếp Hàm băm 4 Tìm kiếm xâu mẫu Thuật toán trực tiếp Thuận toán Rabin-Karp Thuận toán Knuth-Morris-Pratt Thuận toán Boyer-Moore 5 Tổng kết Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 91 / 96
98. Thuận toán Boyer-Moore Ý tưởng Ta hãy xác định yếu tố ký tự tồi trong một xâu mẫu trong giải thuật trực tiếp, do việc duyệt từ trái sang phải nên vị trí càng bên phải thì càng tồi. nếu ký tự không có trong xâu mẫu thì ta có thể trượt sang vị trí bên phải không cần kiểm tra nữa. bởi vậy, ta tạo ra hàm last gồm chỉ số vị trí cực phải của các ký tự trong bảng chữ P nằm trong xâu mẫu P. Ví dụ Cho xâu mẫu của các ký tự P = {a, b, c, d} gồm 6 phần tử như sau a c a b a c Như vậy hàm last : last(a) = 5, last(b) = 4, last(c) = 6 và last(d) = 0 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 92 / 96
99. Thuận toán Boyer-Moore Các tình huống tăng vị trí dịch chuyển Giả sử ký tự tồi được dóng ở vị trí j của P 1 Ký tự tồi có mặt trong P và last(c) j, khi đó trượt đến s ← s + 1 3 Ký tự tồi không có mặt trong P vì thế last(c)=0, khi đó trượt đến s ← s + (j − last(c)) Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 93 / 96
100. Thuận toán Boyer-Moore Mã giả của giải thuật Boyer-Moore s ← 0 while (s ≤ n − m) do j ← m while (j > 0 and T [j + s] = P[j]) do j ← j − 1 endwhile if (j=0) then In s là vị trí khớp s ← s + 1 else// Tăng vị trí dịch chuyển k ← last(T [j + s]) s ← s + max(j − k, 1) endif endwhile Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 94 / 96
101. Thuận toán Boyer-Moore Thời gian chạy Việc tính hàm last() đòi hỏi thời gian O(m+| P |) Tình huống tồi nhất, ta có O(nm + | P |) Thuật toán làm việc kém hiệu quả nếu bảng P nhỏ Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 95 / 96
102. Tổng kết Định nghĩa bài toán tìm kiếm Thuật toán tìm kiếm tuyến tính và nhị phân Định nghĩa và cài đặt cây nhị phân tìm kiếm Định nghĩa cây AVL Bài toán tìm kiếm xâu mẫu Bảng băm, lưu trữ và tìm kiếm Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc & dữ TT, liệu Trườngvà giải thuật Đại Học BáchNgày Khoa 30Hà tháng Nội. ) 11 năm 2015 96 / 96