NỘI DUNG
Giới thiệu Thuật toán Rabin-Karp
Thuật toán Rabin-Karp là một thuật toán tìm kiếm chuỗi được đặt tên theo tên hai nhà toán học Michael O. Rabin và Richard M. Karp, và đã được công bố lần đầu tiên vào năm 1987. Nó được sử dụng để tìm kiếm một chuỗi con trong một chuỗi lớn với độ phức tạp O(n+m), trong đó n là độ dài của chuỗi lớn và m là độ dài của chuỗi con cần tìm.
Thuật toán Rabin-Karp sử dụng phép toán băm (hashing) để so sánh chuỗi con cần tìm với các chuỗi con của chuỗi lớn một cách nhanh chóng. Ý tưởng của phép toán băm là biến đổi một chuỗi thành một giá trị số, được gọi là giá trị băm (hash value), bằng cách sử dụng một hàm băm. Nếu hai chuỗi có cùng giá trị băm, thì chúng có thể giống nhau, nên ta cần kiểm tra chúng bằng cách so sánh từng ký tự.
Các bước thực hiện thuật toán
Thuật toán Rabin-Karp thực hiện các bước sau:
Bước 1. Tính giá trị băm của chuỗi con cần tìm.
Bước 2. Tính giá trị băm của các chuỗi con của chuỗi lớn có độ dài bằng độ dài của chuỗi con cần tìm.
Bước 3. So sánh giá trị băm của chuỗi con cần tìm với các giá trị băm của các chuỗi con của chuỗi lớn.
Bước 4. Nếu hai giá trị băm bằng nhau, kiểm tra từng ký tự của hai chuỗi để xác định xem chúng có giống nhau không.
Thuật toán Rabin-Karp cho phép tìm kiếm nhiều chuỗi con trong một chuỗi lớn một cách hiệu quả. Nó cũng có thể được sử dụng để tìm kiếm trong các tài liệu văn bản để xác định xem liệu có sự trùng lặp nào không. Tuy nhiên, nó cũng có một số hạn chế, bao gồm khả năng xảy ra va chạm giá trị băm và sự chậm trễ trong trường hợp chuỗi lớn và chuỗi con cần tìm có độ dài lớn.
Ví dụ về thuật toán Rabin-Karp
Ví dụ 1. Giả sử chúng ta có chuỗi lớn là “ababcabcabababd” và chuỗi con cần tìm là “abab”. Ta muốn tìm tất cả các vị trí xuất hiện của chuỗi con này trong chuỗi lớn.
Bước 1: Tính giá trị băm của chuỗi con cần tìm “abab”. Ta có thể sử dụng hàm băm đơn giản như hàm ASCII để tính giá trị băm của chuỗi này. Trong trường hợp này, giá trị băm của “abab” là 97 + 98 + 97 + 98 = 390.
Bước 2: Tính giá trị băm của các chuỗi con của chuỗi lớn có độ dài bằng độ dài của chuỗi con cần tìm. Trong trường hợp này, độ dài của chuỗi con cần tìm là 4, vì vậy ta tính giá trị băm của tất cả các chuỗi con có độ dài 4 của chuỗi lớn “ababcabcabababd”.
Đầu tiên, tính giá trị băm của chuỗi “abab”:
a b a b c a b c a b a b a b d 97 98 97 98 97 98
97 98 99 97 97 98 97 98 97 98 98 97 98 100
Với độ dài chuỗi con cần tìm là 4, ta tính giá trị băm của tất cả các chuỗi con có độ dài là 4:
“abab”: 390 “babc”: 389 “abca”: 390 “bcab”: 390 “cabc”: 387 “abcb”: 388 “cbca”: 389 “bcaa”: 386 “caab”: 387 “aaba”: 386 “abab”: 390 “baba”: 389 “abad”: 386
Bước 3: So sánh giá trị băm của chuỗi con cần tìm với các giá trị băm của các chuỗi con của chuỗi lớn.
Ta thấy rằng giá trị băm của “abab” xuất hiện ở vị trí 1, 9 và 11. Điều này cho thấy rằng chuỗi con “abab” xuất hiện ở các vị trí 1, 9 và 11 trong chuỗi lớn “ababcabcabababd”.
Bước 4: Nếu hai giá trị băm bằng nhau, kiểm tra từng ký tự của hai chuỗi để xác định xem chúng có giống nhau không.
Trong trường hợp này, không cần kiểm tra từng ký tự vì giá trị băm của các chuỗi con xuất hiện trong chuỗi lớn là duy nhất, không có hai chuỗi con nào có cùng giá trị băm. Nếu có hai chuỗi con có cùng giá trị băm, ta phải kiểm tra từng ký tự để đảm bảo chúng giống nhau.
Ví dụ 2. Giả sử chúng ta có chuỗi lớn là “abcde” và chuỗi con cần tìm là “bcd”. Tính giá trị băm của chuỗi con cần tìm, ta có giá trị băm là 98 + 99 + 100 = 297.
Tiếp theo, tính giá trị băm của tất cả các chuỗi con có độ dài 3 của chuỗi lớn “abcde”:
“abc”: 97 + 98 + 99 = 294 “bcd”: 98 + 99 + 100 = 297 “cde”: 99 + 100 + 101 = 300
Chuỗi con “bcd” có giá trị băm bằng giá trị băm của chuỗi con cần tìm. Ta phải kiểm tra từng ký tự của hai chuỗi để xác định xem chúng giống nhau hay không. Ta thấy rằng chuỗi con “bcd” xuất hiện trong chuỗi lớn “abcde” tại vị trí 2.
Như vậy, thuật toán Rabin-Karp cho phép tìm kiếm chuỗi con trong chuỗi lớn một cách hiệu quả, đặc biệt là khi có nhiều vị trí xuất hiện của chuỗi con cần tìm trong chuỗi lớn.
Cài đặt thuật toán Rabin-Karp với Python
def rabin_karp(text, pattern):
# Tính giá trị băm của chuỗi con cần tìm
pattern_hash = hash(pattern)
# Duyệt qua từng chuỗi con của chuỗi lớn và tính giá trị băm
for i in range(len(text) - len(pattern) + 1):
substr = text[i:i+len(pattern)]
substr_hash = hash(substr)
# Nếu giá trị băm của chuỗi con trùng với giá trị băm của chuỗi con cần tìm
# Kiểm tra từng ký tự của hai chuỗi để xác định xem chúng giống nhau hay không
if substr_hash == pattern_hash and substr == pattern:
return i
# Không tìm thấy chuỗi con cần tìm trong chuỗi lớn
return -1
Cài đặt Thuật toán Rabin-Karp với C++
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int rabin_karp(string text, string pattern) {
int pattern_hash = hash<string>()(pattern); // Tính giá trị băm của chuỗi con cần tìm
for (int i = 0; i <= text.length() - pattern.length(); i++) {
string substr = text.substr(i, pattern.length()); // Lấy chuỗi con có độ dài bằng độ dài của chuỗi cần tìm
int substr_hash = hash<string>()(substr); // Tính giá trị băm của chuỗi con
if (substr_hash == pattern_hash && substr == pattern) { // Nếu giá trị băm của chuỗi con trùng với giá trị băm của chuỗi con cần tìm
return i; // Trả về vị trí xuất hiện đầu tiên của chuỗi con cần tìm
}
}
return -1; // Không tìm thấy chuỗi con cần tìm trong chuỗi lớn
}
int main() {
string text = "abcde";
string pattern = "bcd";
int result = rabin_karp(text, pattern);
if (result != -1) {
cout << "Chuoi con duoc tim thay tai vi tri: " << result << endl;
} else {
cout << "Khong tim thay chuoi con trong chuoi lon" << endl;
}
return 0;
}
Đánh giá độ phức tạp của thuật toán
Độ phức tạp của thuật toán Rabin-Karp là O(m + n), trong đó m là độ dài của chuỗi cần tìm và n là độ dài của chuỗi lớn.
Thuật toán Rabin-Karp có độ phức tạp thấp hơn so với thuật toán Brute Force vì nó không cần duyệt qua tất cả các chuỗi con có thể có của chuỗi lớn để tìm kiếm chuỗi cần tìm. Thay vào đó, nó chỉ tính toán giá trị băm cho các chuỗi con và so sánh giá trị băm của chuỗi cần tìm với giá trị băm của các chuỗi con trong chuỗi lớn.
Tuy nhiên, nếu các giá trị băm của các chuỗi con trùng nhau thì thuật toán phải kiểm tra từng ký tự trong hai chuỗi để xác định chúng có giống nhau hay không. Vì vậy, nếu chuỗi cần tìm và chuỗi lớn có nhiều chuỗi con có giá trị băm trùng nhau, thì độ phức tạp của thuật toán có thể tăng lên đáng kể.
Tóm lại, thuật toán Rabin-Karp có độ phức tạp trung bình và thường được sử dụng trong các ứng dụng thực tế để tìm kiếm chuỗi trong văn bản.