Bài giảng Phân tích và thiết kế giải thuật (Analys And Design Algorithms) - Chương 3: Phân tích các giải thuật tìm kiếm

PHÂN TÍCH  CÁC GIẢI THUẬT TÌM KIẾM1Nội dungGiải thuật tìm kiếm tuần tự, nhị phân trên danh sách liên kếtPhân tích các thao tác trên cây tìm kiếm nhị phânPhân tích các kỹ thuật băm Phân tích một vài giải thuật so trùng chuỗi 22. Tìm tuyến tính (Linear Seach)Ý tưởng:Bắt đầu từ phần tử đầu tiên của danh sách, so sánh lần lượt từng phần tử của danh sách với giá trị X cần tìmNếu có phần tử bằng X thì trả về vị trí tìm thấy, thuật toán dừng lại (thành công)Nếu đến cuối danh sách mà không có phần tử nào bằng X, thuật toán dừng lại (không thành công)3Tìm tuyến tính (Linear Seach)5Khóa tìm 7135216281501234567Vị trí = 2Tìm thành côngSố lần so sánh: 3497135216281501234567Không tìm thấySố lần so sánh: 8Khóa tìm 2. Tìm tuyến tính (Linear Seach)5Tìm tuyến tính (Linear Seach)int LSearch(int list[], int n, int key){ int find= -1; for (int i=0; idata==x) return p; p=p->pNext; } return NULL;}• Tìm kiếm mất tối đa O(n) nếu danh sách có n phần tử• Trường hợp tốt nhất là O(1)Binary Search Tree - Định nghĩaCây nhị phân tìm kiếm (CNPTK) là cây nhị phân trong đó tại mỗi nút, khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phảiNhờ ràng buộc về khóa trên CNPTK, việc tìm kiếm trở nên có định hướngNếu số nút trên cây là N thì chi phí tìm kiếm trung bình chỉ khoảng log2NTrong thực tế, khi xét đến cây nhị phân chủ yếu người ta xét CNPTK18Binary Search Tree – Ví dụ194418881337591081523405571Binary Search Tree – Khai báo20Khai báo cấu trúc cây nhị phân tìm kiếm:Để quản lý cây nhị phân tìm kiếm chỉ cần quản lý địa chỉ nút gốc: Tree root;struct TNode{ DataType data; TNode *pLeft, *pRight;};typedef TNode* Tree; Binary Search Tree – Duyệt cây212510316518122013372935325041Duyệt inorder(LNR): 1 3 5 6 10 12 13 18 20 25 29 32 35 37 41 50Duyệt giữa trên CNPTK (LNR)Binary Search Tree – Duyệt cây222510316518122013372935325041Duyệt postorder(LRN): 1 5 6 3 13 12 20 18 10 32 35 29 41 50 37 25Duyệt sau trên CNPTK (LRN)Binary Search Tree – Duyệt cây232510316518122013372935325041Duyệt preorder(NLR): 25 10 3 1 6 5 18 12 13 20 37 29 35 32 50 41Duyệt trước trên CNPTK(NLR)Thuật Toán Inorder TraversalInorder-Tree-Walk (x)1. if x  NIL2. then Inorder-Tree-Walk(left[p])3. print key[x]4. Inorder-Tree-walk(right[p])56262001828190213122427Độ phức tạp của giải thuật:Mất (n) thời gian để duyệt câySau lần gọi đầu tiên, thủ tục gọi đệ qui 2 lần, một lần cho cây con bên trái và một lần cho cây con bên phảiBinary Search Tree – Tìm kiếm252510316518122013372935325041Tìm kiếm 13Khác nhauGiống nhauNode gốc nhỏ hơnNode gốc lớn hơnTìm thấySố node duyệt: 5Tìm kiếm trên CNPTKBinary Search Tree – Tìm kiếm262510316518122013372935325041Tìm kiếm 14Khác nhauNode gốc nhỏ hơnNode gốc lớn hơnKhông tìm thấySố node duyệt: 5Tìm kiếm trên CNPTKBinary Search Tree – Tìm kiếmTìm một phần tử x trong CNPTK (dùng đệ quy):27TNode* searchNode(Tree T, DataType X){ if (T) { if(T->data ==X) return T; if(T->data >X) return searchNode(T->pLeft, X); return searchNode(T->pRight, X); } return NULL;}Binary Search Tree – Tìm kiếmTìm một phần tử x trong CNPTK (dùng vòng lặp):28TNode* searchNode(Tree T, DataType x){ TNode *p = T; while (p != NULL) { if(x == p->data) return p; else if(x data) p = p->pLeft; else p = p->pRight; } return NULL;}Binary Search Tree – Độ phức tạp của thuật toán29Số bước xử lý để thực hiện các thao tác tìm kiếm trên cây nhị phân tìm kiếm là không vượt quá độ dài đường đi lớn nhất từ gốc đến lá của câySố bước xử lý để thực hiện các thao tác tìm kiếm trên cây nhị phân không vượt quá h+1, trong đó h là chiều cao của câyGọi n là số nút trong cây nhị phân T, độ phức tạp tìm kiếm trong cây nhị phân tìm kiếm là O(h)=O(g(n)), với g(n) phụ thuộc vào hBinary Search Tree – Độ phức tạp của thuật toán30Trường hợp tốt nhấtKhi đường cao h của cây là nhỏ nhất (cây tìm kiếm là đầy đủ, tất cả các nút đều có 2 con, trừ các nút ở mức thấp nhất)Suy ra 1+2+22++2h-1<n và 1+2+22++2h ≥nHay lg (n+1)-1≤h <lg(n+1) hay h=|lg(n+1)|Thời gian tìm kiếm là O(lgn)Binary Search Tree – Độ phức tạp của thuật toán31Trường hợp xấu nhấtKhi cây suy biến thành danh sách (đường cao h = n-1)Thời gian tìm kiếm là O(n)Binary Search Tree – Độ phức tạp của thuật toán32Trường hợp trung bìnhGiả sử các khóa là a1, , an, trong đó a1 là khóa của nút gốc và có i khóa nhỏ hơn a1, n-i -1 khóa lớn hơn a1, với xác suất Pr(i)=1/nGọi S(n) là độ dài trung bình của đường đi trung bình từ gốc đến đỉnh bất kỳ trong cây, thì S(1)=0Binary Search Tree – Độ phức tạp của thuật toán33Trường hợp trung bìnhGọi S(i) và S(n-i -1) lần lượt là độ dài trung bình của đường đi trong cây con trái và phải, thì độ dài trung bình trong T ứng với mỗi i (với xác suất Pr(i)=1/n) Binary Search Tree – Độ phức tạp của thuật toán34Binary Search Tree – Độ phức tạp của thuật toán35Binary Search Tree – Độ phức tạp của thuật toán36Binary Search Tree – Độ phức tạp của thuật toán37Binary Search Tree – Độ phức tạp của thuật toán38Trường hợp trung bìnhVì Hn= O(lg n) nên S(n)=O(lg n) Như vậy độ dài đường đi trung bình từ gốc tới đỉnh bất kỳ trong cây nhị phân tìm kiếm là O(lg n)Vậy độ phức tạp trung bình của các thuật toán tìm kiếm trong cây nhị phân tìm kiếm là O(lg n)Minimum and Maximum39Từ node gốc luôn luôn có thể tìm ra node có giá trị khóa nhỏ nhất (minimum) nếu đi theo con trỏ trái cho đến khi gặp Null.Từ node gốc luôn luôn có thể tìm ra node có giá trị khóa lớn nhất (maximum) nếu đi theo con trỏ phải cho đến khi gặp Null.Minimum key là 2Maximum key là 20Minimum and Maximum40Độ phức tạp của giải thuật là O(h)Successor41Nếu tất cả khóa của BST khác nhau, successor của node x là node có khóa nhỏ nhất trong số những khóa lớn hơn key[x]Dựa vào cấu trúc cây: nếu cây được duyệt theo thứ tự LNR thì successor của node x luôn là node kế tiếp theo thứ tự duyệt LNR.Successor42Có 2 khả năng xảy ra khi tìm successor của node x theo kiểu duyệt LNR:Nếu cây con phải của x khác rỗng, successor của x sẽ là node trái nhất(leftmost node) của cây con phải.Nếu cây con phải của x là rỗng và x có successor y thì y là cụ tổ (lowest anvestor) của x mà cụ tổ này có con trái cũng là tổ tiên của x.Successor43Case 1: successor của node 15 là node 17Case 1: successor của node 13 là node 15Giải thuật tìm Successor44Giải thuật chèn45Để chèn giá trị mới v vào cây BST T:Tạo nút mới z với key[z] = v, left[z] = NIL, right[z]=NIL.Cần phải sửa đổi cây T và một số trường hợp của z sao cho z khi được chèn vào cây sẽ ở vị trí thích hợpGiải thuật chèn46Giải thuật chèn47Chèn giá trị 13 vào cây TREE-INSERT(T,z) với key[z] =13Giải thuật xóa48Để xóa node z khỏi cây BST T, có 3 khả năng:Nếu z không có con: chỉ cần cho cha của nó p[z] trỏ đến nil.Nếu z chỉ có 1 con: nối tắt z bằng cách tạo 1 link mới giữa cha và con của nó.Nếu z có cả hai con: tìm successor y của z mà không có con trái, nối tắt y và thay thế giá trị khóa của z với khóa của y.Giải thuật xóa49Giải thuật xóa50Phân tích các kỹ thuật băm Khái niệm bảng bămGiải quyết đụng độ bằng kết nốiGiải quyết đụng độ bằng địa chỉ mởKhái niệm bảng băm_Hash tableBảng băm là một cấu trúc dữ liệu có thể lưu trữ một tập các đối tượng có số phần tử tùy ýDùng để truy tìm dữ liệu theo từ điểnViệc tìm 1 phần tử trong bảng hash có thể lâu như dò tìm trong danh sách liên kết, Thời gian trong trường hợp xấu nhất là O(1).Dưới những giả định thích hợp thì thời gian dò tìm 1 phần tử trong bảng Hash là O(1)Bảng địa chỉ trực tiếp-Direct-address table Giả sử ta có một tập phần tử gồm các giá trị khoá bất kỳ được tổ chức lưu trữ dưới dạng bảng chỉ mục m phần tử như sau gọi là bảng truy xuất trực tiếp (Direct access table)Phần tử có giá trị khoá k được lưu trữ tương ứng tại vị trí thứ k trong bảng chỉ mục Để tìm kiếm một phần tử nào đó ta sẽ dựa vào khoá của nó và tra trong bảng chỉ mục, nếu tại vị trí đó có phần tử thì chính là phần tử cần tìm, nếu không có phần tử nào có nghĩa là phần tử cần tìm không có trong bảng chỉ mụcBảng địa chỉ trực tiếp-Direct-address table Giả sử ứng dụng cần 1 tập động(dynamic set) mà mỗi phần tử có khóa nằm trong tập U={0,1,,m-1} với m không quá lớn. Giả sử không có 2 phần tử nào cùng khóa.Bảng địa chỉ trực tiếp được biểu diễn dưới dạng 1 mảng T[0,..m-1], mà mỗi vị trí hay slot tương ứng với một khóa trong tập U.Nếu tập không chứa phần tử nào thì T[k]=NILU: chứa tất cả các khóaK: Tập tất cả các khóa thực sự lưu trong từ điển|K| = n.|K| << |U|.Bảng địa chỉ trực tuyệt đốiBảng Hash0m–1h(k1)h(k4)h(k2)=h(k5)h(k3)U(universe of keys)K(actualkeys)k1k2k3k5k4collisionSo sánh bảng địa chỉ tuyệt đối và bảng hash Comp 122, Fall 2003HashingHash function h: Ánh xạ tập U thành các slots của bảng hash T[0..m–1]. h : U  {0,1,, m–1}Với bảng địa chỉ tuyệt đối khóa k được lưu trữ trong slot k.Với bảng hash, khóa k được lưu trữ trong slot h[k], dùng hàm hash để tính slot từ khóa k là T[h[k]], h[k] là giá trị hash của khóa k.Cách tạo hàm hash tốt Một hàm hash tốt phải thỏa mãn giả thuyết hashing là mỗi key có thể được hash vào bất kỳ slot nào, bất kể khóa khác đã được hash vào slot đó hay chưa.Thường các kỹ thuật heuristic được dùng để tạo hàm hashDựa vào việc phân phối các khóa. Ví dụ các từ khóa rất giống nhau như pt và ptshàm hash tốt nên giảm tối thiểu cơ hội sao cho các từ gần giống nhau này được hash vào cùng 1 slot.Cách tạo hàm hash tốt Hầu hết các hàm hash đều giả thuyết miền key như tập các số tự nhiên N ={0,1,2,}Nếu khóa không phải là số tự nhiên thì nên biến đổi khóa như 1 số tự nhiên.Ví dụ: Từ khóa là CLRS:Mã ASCII: C=67, L=76, R=82, S=83.Biểu diễn như số nguyên cơ số 128 (radix-128 integer)CLRS = 67·1283+76 ·1282+ 82·1281+ 83·1280 = 141,764,947.Nếu biểu diễn từ khóa pt?112 * 128 +116 =14452Các kỹ thuật tạo hàm hash Division methodMultiplication methodUniversal hashing methodDivision MethodÁnh xạ khóa k vào 1 trong m slot bằng cách tìm phần dư của phép chia nguyên k cho m h(k) = k mod mVí dụ: m = 31 and k = 78  h(k) = 16.Advantage: Nhanh, chỉ thực hiện 1 phép toán chiaDisadvantage: Phải tránh việc chọn m.Không chọn m=2p thì h(k) luôn là p bit thứ tự thấp nhất của k(lowest order bits of k).Nên chọn m: là số nguyên tố không bằng lũy thừa của 2 là tốt nhấtDivision MethodVí dụ: cần 1 bảng hash giải quyết xung đột bằng chaning với trung bình là 3 phần tử cho mỗi lần dò tìm không thành công, nếu có n=2000 chuỗi ký tự thì nên chọn m=701 là 1 số nguyên tố gần bằng với 2000/3 và không bằng với bất kỳ số nào của lũy thừa h(k) = k mod 701Multiplication MethodGồm 2 bước:B1: Nhân khóa k với một hằng số A, 0 < A < 1 và tách lấy phần số lẻ của kA.B2: Nhân giá trị vừa tách với m và dùng hàm floor để có kết quảh(k) = m (kA mod 1)Disadvantage: chậm hơn division method.Advantage: Giá trị m không quan trọng, có thể chọn m = 2p để tiện trong tính toán.Giới hạn A là phần số lẻ của s/2w, với s là số 0<s<2w Knuth đề nghị A  (5 – 1)/2 =0.6180339887Example: m = 1000, k = 123, A  0.6180339887 h(k) = 1000(123 · 0.6180339887 mod 1) = 1000 · 0.018169...  = 18.Multiplication-ImplementationChọn m = 2p, p là số nguyên.Giả sử kích cỡ word của máy là w bits.k chỉ chiếm 1 word. (k mất w bits.)Đặt 0 < s < 2w. (s mất w bits.)A là phân số lẻ của s/2w.Đặt k  s = r1 ·2w+ r0 .R1 giữ phần nguyên của kA (kA) và r0 giử phần lẻ của kA (kA mod 1 = kA – kA).Sử dụng r0, và bỏ qua r1.Multiplication– Implementationks = A·2wr0r1w bitsh(k)extract p bits·Giá trị hask h(k) tương ứng với p bit thứ tự cao nhất của r0binary pointVí dụGiả sử k=123456, p=14, m=214 = 16384, w = 32Theo Knuth, chọn A là phần số lẻ của s/232 và gần bằng (5 – 1)/2 s = A.232 =0.6180339887.232 s =2654435769 A =2654435769/232 Nhân k với sk.s =327706022297664 = (76300.232) +17612864R1 giữ phần nguyên của kA (kA) và r0 giử phần lẻ của kA (kA mod 1 = kA – kA).r1 = 123456*0.6180339887=76300 và r0 = 1761286414 bit có thứ tự cao nhất của r0 là giá trị của h(k) =m(kA mod 1)=16384(123456*0.6180339887 mod 1) = 67Multiplication– ImplementationKỹ thuật giải quyết đụng độ Đụng độ (collision) xảy ra khi có nhiều khóa cùng hash vào 1 slot, ví dụ k2 đụng độ k5, nghĩa là h(k2)= h(k5) Các phương pháp giải quyết đụng độGiải quyết dụng độ bằng kết nối(collision resolution by chaining)Giải quyết đụng độ bằng địa chỉ mở (open addressing)0m–1h(k1)h(k4)h(k2)=h(k5)h(k3)U(universe of keys)K(actualkeys)k1k2k3k5k4Collision(xung đột)Methods of Collision ResolutionChaining: Đặt tất cả các phần tử có cùng hash vào 1 slot vào một danh sách liên kếtBảng hash sẽ lưu trữ con trỏ chỉ đến phần tử đầu của danh sáchOpen Addressing:Tất cả các phần tử được lưu trong bảng hash của chính nó.Khi xảy ra đụng độ sử dụng thủ tục systematic (consistent) để lưu trữ những phần tử vào các slot trống của bảng hashk20m–1k1k4k5k6k7k3k8Collision Resolution by Chaining0m–1h(k1)=h(k4)h(k2)=h(k5)=h(k6)h(k3)=h(k7)U(universe of keys)K(actualkeys)k1k2k3k5k4k6k7k8h(k8)XXXCollision Resolution by Chainingk20m–1U(universe of keys)K(actualkeys)k1k2k3k5k4k6k7k8k1k4k5k6k7k3k8Hashing with ChainingDictionary Operations: Các thao tác trên bảng HashChained-Hash-Insert (T, x)Chèn một phần tử x vào đầu của danh sách T[h(key[x])].Độ phức tạp trong trường hợp xấu nhất – O(1).Chained-Hash-Delete (T, x)Xóa x từ danh sách T[h(key[x])].Độ phức tạp trong trường hợp xấu nhất – phụ thuộc vào chiều dài của danh sáchChained-Hash-Search (T, k)Tìm một phần tử có khóa k trong danh sách T[h(k)].Độ phức tạp trong trường hợp xấu nhất– phụ thuộc vào chiều dài của danh sáchHashing with ChainingCách lưu trữ dữ liệu trong bảng Hash với chainCho bảng hash T với m slot để lưu trữ n phần tử:Load factor  đối với bảng hash là n/m (số trung bình các phần tử được lưu trữ trong chain)  có thể nhỏ hơn, bằng hay lớn hơn 1Analysis on Chained-Hash-SearchLoad factor =n/m = trung bình các khóa trong 1 slot.m – số slot n – số phần tử được lưu trữ trong bảng hash.Worst-case complexity: (n) + thời gian tính h(k).ĐPT trung bình phụ thuộc vào việc phân bổ các khóa vào m slotGiả sử Simple uniform hashing.Mỗi khóa có thể hash vào bất kỳ slot nào bất kể các khóa khác đã hash vào slot đó hay chưa.Thời gian tính h(k) là O(1)Giải quyết đụng độ bằng kết nốiCHAINED-HASH-INSERT(T, x): Chèn một phần tử vào bảng băm TCHAINED-HASH-SEARCH(T, k): Tìm một phần tử có khoá k trong TCHAINED-HASH-DELETE(T, x): Xoá một phần tử khỏi T Giải quyết đụng độ bằng kết nốiCHAINED-HASH-INSERT(T, x) 1 Insert x at the head of list T[h(key[x])]LIST-INSERT(L, x)1 next[x] ←head[L]2 head[L] ←xGiải quyết đụng độ bằng kết nốiCHAINED-HASH-SEARCH(T, k)1 Search for an element with key k in list T[h(k)]LIST-SEARCH(L, k)1 x ←head[L]2 while (x ≠NUL and key[x] ≠k)3 dox ←next[x]4 returnxGiải quyết đụng độ bằng kết nốiCHAINED-HASH-DELETE(T, x) 1 Delete x from the list T[h(key[x])]LIST-DELETE(L, x)1 if head[L] = x2 then head_delele(L, x)3 else p ←head[L]4 while p ≠NUL and next[p] ≠x 5 do p ←next[p]6 if next[p]=x7 then next[p] ←next[x]Giải quyết đụng độ bằng kết nốiThời gian chèn vào bảng là O(1) (chèn vào đầu danh sách)Thời gian trung bình tìm kiếm và xóa trên bảng là O(1+α), trong đó α= n/m <1 với m, n lần lượt là số slot và số phần tử được lưu trữ trong bảng, α gọi là hệ số tải (load factor) của TOpen AddressingCác phần tử được lưu trữ trong chính bảng hashMỗi ô hoặc chứa 1 phần tử của dynamic set hoặc chứa Nil.Linear Probing :- tìm tuần tự tất cả các slot có trong bảng, tăng chỉ số cho đến khi tìm thấy ô chứa nil H(k,i) = (h’(k) + i ) mod mTrong open Addressing bảng hash có thể đầy và không cho phép chèn thêm bất kỳ phần tử nào. Thừa số  có thể không vượt quá 1.So sánh Open Addressing và ChainingGiải quyết đụng độ bằng địa chỉ mởGiải quyết đụng độ bằng địa chỉ mởGiải quyết đụng độ bằng địa chỉ mởGiải quyết đụng độ bằng địa chỉ mởGiải thuật giải quyết đụng độ bằng địa chỉ mởXóa bằng địa chỉ mởÁp dụng thực tế bằng địa chỉ mởDouble HashingDouble HashingDouble HashingDouble HashingSo trùng dòng ký tự: tìm tất cả sự xuất hiện của một khuôn mẫu (pattern) trong một văn bản (text).Văn bản là một mảng ký tự T[1..n] chiều dài n và một khuôn mẫu là một mảng P[1..m] chiều dài m. Các phần tử của P và T là những ký tự lấy từ một tập ký tự (alphabet) .Khuôn mẫu P xuất hiện với bước dịch chuyển(shift) s trong văn bản T (tức là, P xuất hiện bắt đầu từ vị trí s+1 trong văn bản T) nếu 1  s  n – m và T[s+1..s+m] = P[1..m].Nếu P xuất hiện với bước dịch chuyển s trong T, thì ta bảo s là một bước dịch chuyển hợp lệ (valid shift); ngược lại ta bảo s là một bước dịch chuyển không hợp lệ (invalid shift).Phân tích một vài giải thuật so trùng chuỗi Bài toán so trùng dòng ký tự là bài toán tìm tất cả những bước dịch chuyển hợp lệ mà một khuôn mẫu P xuất hiện trong một văn bản T cho trước.Văn bản abcabaabcabacKhuôn mẫu abaabcabacBước dịch chuyển: s = 3Giải thuật Rabin-Karp vận dụng những khái niện căn bản trong lý thuyết số chẳng hạn sự tương đương của hai số modulo một số thứ ba.Phân tích một vài giải thuật so trùng chuỗi Giải thuật Rabin-KarpGiả sử  = {0, 1, 2, , 9}, tức mỗi ký tự là một ký số thập phân. (Trong trường hợp tổng quát, mỗi ký tự là một ký số của cơ hệ d, tức là d = | |.)Ta có thể xem một dòng gồm k ký tự kế tiếp diễn tả một số thập phân có chiều dài k. Dòng ký tự “31415” tương ứng với trị số thập phân 31415.Cho một khuôn mẫu P[1..m], gọi p là giá trị thập phân tương ứng với khuôn mẫu.Cho một văn bản T[1..n], gọi ts là trị số thập phân của dòng con chiều dài m T[s+1...s+m], với s = 0, 1, , n-m.ts = p nếu và chỉ nếu T[s+1..s+m] = P[1..m] và s là một bước dịch chuyển hợp lệ nếu và chỉ nếu ts = pTa có thể tính p trong thời gian O(m) dùng qui tắc Horner: p = P[m] + 10*(P[m-1] + 10*(P[m-2] + + 10*(P[2] + 10*P[1])))Giá trị t0 có thể được tính một cách tương tự từ T[1..m] trong thời gian O(m).Chú ý: ts+1 có thể được tính từ ts: ts+1 = 10(ts – 10m-1T[s+1]) + T[s+m+1] (5.1)Thí dụ: Nếu m = 5 và ts = 31415, thì ta sẽ bỏ ký số bậc cao T[s+1] = ‘3’ và đưa vào ký số bậc thấp là ‘2’ để đạt giá trị: ts+1 = 10(31415 – 10000.3) + 2 = 14152Giải thuật Rabin-KarpMỗi lần thực thi phương trình (5.1) sẽ cần tiến hành một số lượng phép toán số học cố định. Việc tính toán t1, t2,, tn-m tỉ lệ với O(n-m).Như vậy, p và t0, t1, , tn-m có thể được tính trong chi phí thời gian O(m) +O(m) + O(n-m)  O(n + m).Nhưng p và ts có thể quá lớn đến nỗi máy tính không thể biểu diễn được. Để khắc phục vấn đề này, ta tính p và các ts modulo một đại lượng q thích hợp. Đại lượng q thường được chọn là một số nguyên tố sao cho 10q thì chứa được trong một từ của máy tính.Trong trường hợp tổng quát, với bộ mẫu tự gồm d ký tự {0, 1, , d-1}, ta chọn q sao cho dq chứa được trong một từ của máy tính. Giải thuật Rabin-KarpVà phương trình (5.1) trở thành: ts+1 = d(ts – hT[s+1]) + T[s+m+1])mod q (5.2) với h = dm-1 (mod q)Tuy nhiên, ts  p (mod q) không hàm ý ts = p.Mặt khác, nếu ts  p (mod q) thì ta có thể khẳng định ts  p, và như vậy bước dịch chuyển s là không hợp lệ. Chúng ta có thể dùng cách thử ts  p (mod q) để loại bỏ những bước dịch chuyển không hợp lệ s. Một bước dịch chuyển s mà thỏa ts  p (mod q) thì phải được thử nghiệm thêm để xem s có thực sự là bước dịch chuyển hợp lệ hay chỉ là một sự khớp trùng giả (spurious hit) mà thôi .Giải thuật Rabin-Karp thể hiện rõ nét tinh thần chiến lược Biến thể-để-trịGiải thuật Rabin-KarpThí dụ:|2| 3| 5| 9| 0| 2| 3| 1| 4| 1| 5| 2| 6| 7| 3| 9| 9| 2| 1|  ______   | 7||2| 3| 5| 9| 0| 2| 3| 1| 4| 1| 5| 2| 6| 7| 3| 9| 9| 2| 1|  _______   ______   ______      | 8| 9| 3|11| 0| 1| 7| 8| 4| 5|10|11| 7| 9|11| valid spurious match match | 3| 1| 4| 1| 5| 2|  ______    | 7| 8|14152 = (31415 – 3  1000)  10 + 2 (mod 13) = 8 (mod 13)void RABIN-KARP-MATCHER(T, P, d, q)/* T is the text, P is the pattern, d is the radix and q is the prime */{ n = |T|; m = |P|; h = dm-1 % q; p = 0; t0 = 0; for (int i = 1;i<=m;i++) { p = (d*p + P[i]) % q; t0: = (d*t0 + T[i]) % q’ } for (int s = 0;s<= n – m.s++) { if (p = t) /* there may be a hit */ if (P[1..m] = T[s+1..s+m]) cout<< “Pattern occurs with shift “<<s; if (s < n – m) ts+1 = (d(ts –T[s + 1]h) + T[s+m+1]) % q; } }Thời gian thực thi của RABIN-KARP-MATCHER là O((n – m + 1)m) trong trường hợp xấu nhất vì khi đó giải thuật phải kiểm tra lại mọi bước dịch chuyển hợp lệ.Trong nhiều ứng dụng, thường chỉ có một vài bước dịch chuyển hợp lệ và do đó thời gian chạy thường là O(n+m) cọng với thời gian đòi hỏi để kiểm tra lại các sự khớp trùng giả.Giải thuật Rabin-KarpĐọc thêmTham khảo chương 12 (Hash table), 13 (Binary search tree), sách Cormen và cộng sự