Bài giảng Thuật toán ứng dụng: Thuật toán xử lý xâu

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:89

Thêm vào BST

Báo xấu

13
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Thuật toán ứng dụng: Thuật toán xử lý xâu" trình bày các nội dung chính sau đây: Bài toán tìm kiếm xâu mẫu; Thuật toán trực tiếp; Thuật toán Boyer-Moore; Thuật toán Rabin-Karp; Thuật toán Knuth-Morris-Pratt (KMP). Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Thuật toán ứng dụng: Thuật toán xử lý xâu

Thuật Toán Xử Lý Xâu THUẬT TOÁN ỨNG DỤNG
1. Bài toán tìm kiếm xâu mẫu 2. Thuật toán trực tiếp 3. Thuật toán Boyer-Moore 4. Thuật toán Rabin-Karp 5. Thuật toán Knuth-Morris-Pratt (KMP)
Xâu (Strings) § Xâu là dãy ký hiệu lấy từ bảng ký hiệu (alphabet) å § Ký hiệu T [i..j] là xâu con của xâu T bắt đầu từ vị trí i và kết thúc ở vị trí j T [1 .. n] a1 a2 . . . ai – 1 ai ai + 1 . . . aj – 1 aj aj + 1 . . . an – 1 an T [i .. j] Algorithmics Strings 4
Trượt/đẩy (Shifts) § Giả sử T1 và T2 là 2 xâu § trong đó |T1| = m và |T2| = n § Ta nói T1 xuất hiện nhờ trượt (đẩy) đến s trong T2 nếu § T1[1 .. m] = T2[s + 1 .. s + m] T1 = b1 ... bm trượt đến s T2 = a1 ... as + 1 . . . as + m . . . an Algorithmics Strings 5
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 trong T2 thì § s được gọi là vị trí khớp của T1 trong T2 § ngược lại § s được gọi là vị trí không khớp Algorithmics Strings 6
Bài toán tìm kiếm xâu mẫu (The String Matching Problem) § Cho xâu T độ dài n Ø T được gọi là văn bản § Cho xâu P độ dài m Ø P được gọi là xâu mẫu (pattern) § Bài toán: Tìm tất cả các vị trí khớp của P trong T § Ứng dụng: "trong thu thập thông tin (information retrieval) "trong soạn thảo văn bản (text editing) "trong tính toán sinh học (computational biology) "... Algorithmics Strings 7
Ví dụ § Ví dụ: T = 000010001010001 và P = 0001, các vị trí khớp là: Ø s =1 Ø T = 000010001010001 Ø P = 0001 Ø s=5 Ø T = 000010001010001 ØP = 0001 Ø s=11 Ø T = 000010001010001 ØP = 0001
1. Bài toán tìm kiếm xâu mẫu 2. Thuật toán trực tiếp 3. Thuật toán Boyer-Moore 4. Thuật toán Rabin-Karp 5. Thuật toán Knuth-Morris-Pratt (KMP)
Thuật toán trực tiếp Naïve algorithm § Ý tưởng: Dịch chuyể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. vị trí cuối cùng cần xét: n – m b1 . . . bm b1 ... bm vị trí đầu tiên cần xét: 0 a1 ... am . . . an – m + 1 . . . an
Thuật toán trực tiếp Naïve algorithm § Ý tưởng: Dịch chuyể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. void NaiveSM(char *P, int m, char *T, int n) { int i, j; /* Searching */ for (j = 0; j
Thuật toán trực tiếp § Ví dụ: T = 000010001010001 và P = 0001. T = 000010001010001 s=0 P = 0001 Þ không khớp s=1 P = 0001 Þ khớp s=2 P = 0001 Þ không khớp s=3 P = 0001 Þ không khớp s=4 P = 0001 Þ không khớp s=5 P = 0001 Þ khớp s=6 P = 0001 Þ không khớp . . .
1. Bài toán tìm kiếm xâu mẫu 2. Thuật toán trực tiếp 3. Thuật toán Boyer-Moore 4. Thuật toán Rabin-Karp 5. Thuật toán Knuth-Morris-Pratt (KMP)
Boyer-Moore Algorithm § Làm việc tốt khi P dài và å lớn § Chúng ta sẽ xét sự khớp nhau bằng cách duyệt từ phải qua trái. § Trước hết hãy quan sát lại thuật toán trực tiếp làm việc theo thứ tự duyệt này... Robert-Stephen Boyer J. Strother Moore Strings 14
Thuật toán trực tiếp cải biên for s ¬ 0 to n – m do j¬m while j > 0 and T [j + s] = P[j] do j¬j–1 if j = 0 then print s “là vị trí khớp” Strings 15
Xét ví dụ s® P a c a T a a b a c a a b a ¬j+s b không xuất hiện ở bất cứ đâu trong P vì thế có thể di chuyển P bỏ qua b Strings 16
Bỏ qua được một đoạn s® a c a s® a c a a a b a c a a b a ¬j+s Strings 17
Xét ví dụ khác s® a c b a b a a b c b a a b a ¬j+s c xuất hiện ở vị trí 2 trong P vì thế có thể di chuyển P sao cho các c được dóng thẳng Strings 18
Bỏ qua được một đoạn s® a c b a b s® a c b a b a a b c b a a b a ¬j+s Strings 19
Ký tự tồi § Giả sử P[j] ¹ T [j + s] s® ¬j a c b a b b a c a b c b a a b a ¬j+s § Ta gọi T [j + s] là ký tự tồi (bad character) § Sử dụng ký tự tồi ta có thể tránh được việc dóng hàng không đúng Strings 20