Các thuật toán đối sánh mẫu, thuật toán tìm kiếm mẫu từ trái qua phải, thuật toán tìm kiếm mẫu từ phải qua trái, thuật toán tìm kiếm mẫu từ vị trí cụ thể, thuật toán tìm kiếm mẫu từ vị trí bất kỳ
Các thuật toán đối sánh mẫu
1 Thuật toán Knuth-Morris-Partt
5 Thuật toán Automat hữu hạn
25 Backward Nondeterministic Dawg 2.38 Matching algorithm
Phân loại các thuật toán đối sánh mẫu
Phân loại các thuật toán:
Nhóm 1: các thuật toán duyệt từ trái sang phải:
Nhóm 2: các thuật toán duyệt từ phải sang trái:
Nhóm 3: các thuật toán duyệt tại vị trí cụ thể:
Nhóm 4: các thuật toán duyệt tại vị trí bất kỳ:
Trình bày các thuật toán tìm kiếm mẫu từ trái qua phải
Not so naive algorithm
Nhóm 2: các thuật toán duyệt từ phải sang trái:
Nhóm 3: các thuật toán duyệt tại vị trí cụ thể:
Nhóm 4: các thuật toán duyệt tại vị trí bất kỳ:
III Trình bày các thuật toán tìm kiếm mẫu từ trái qua phải
- Không có pha chuẩn bị
- Bộ nhớ cần dùng cố định
- Luôn luôn dịch 1 bước sang phải
- Việc so sánh có thể phải dùng trong các trường hợp
- Độ phức tạp pha thực thi là O(m x n)
Thuật toán Brute Force thực hiện việc kiểm tra tất cả các vị trí trong đoạn văn bản từ 0 đến n-m mà không cần xác định sự tồn tại của mẫu tại các vị trí đó Sau mỗi lần kiểm tra, mẫu sẽ được dịch sang phải một vị trí.
- Yêu cầu xây dựng automaton đơn định (DFA)
- Pha xử lý có độ phức tạp tính toán là O(n∂)
- Quá trình tìm kiếm có độ phức tạp là O(n) Trường hợp DFA đươc xây dựng bằng cây cân bằng thì độ phức tạp là O(n*log(∂))
Trong thuật toán DFA, quá trình tìm kiếm được chuyển thành một quá trình biến đổi trạng thái của automat Hệ thống automat được xây dựng dựa trên xâu mẫu, trong đó mỗi trạng thái (nút) đại diện cho số ký tự khớp giữa mẫu và văn bản Các ký tự trong văn bản sẽ tác động đến việc thay đổi các trạng thái, và khi đạt được trạng thái cuối cùng, điều đó có nghĩa là đã tìm thấy vị trí xuất hiện của mẫu trong văn bản.
Thuật toán DFA tương tự như thuật toán Knuth-Morris-Pratt ở điểm nhảy về trạng thái trước khi gặp ký tự không khớp, nhưng nó có độ chính xác cao hơn Điều này là do DFA xác định vị trí nhảy dựa trên ký tự không khớp trong văn bản, trong khi KMP chỉ dựa vào vị trí không khớp.
Việc xây dựng hệ automat trên ma trận kề khá đơn giản với thời gian xử lý O(n) và bộ nhớ O(m*d), nhưng trong DFA chỉ có tối đa m cung thuật và m cung nghịch Do đó, việc lưu trữ các cung có thể sử dụng cấu trúc danh sách kề Forward Star thay vì ma trận kề, giúp giảm thời gian chuẩn bị và bộ nhớ xuống còn O(m) Tuy nhiên, thời gian tìm kiếm có thể tăng nhẹ so với việc sử dụng ma trận kề.
Pha tiền xử lý xây đựng DFA:
2.4 Chương trình chạy package traisangphai.Automaton; public class Demo_Automaton { public static void main(String[] args) { char[] pat = "ABCABAB".toCharArray(); char[] txt = "ABABDABACDABABCABAB".toCharArray(); searchAtm(pat, txt);
The function `getNextState` is designed to determine the next state in a pattern matching algorithm It takes an array of characters representing the pattern, its length, the current state, and a character `x` as input If the current state is less than the pattern's length and the character at that state matches `x`, the function returns the next state If not, it checks for potential matches by iterating backwards through the pattern The function compares characters to find the longest prefix that matches the suffix, ultimately returning the new state based on the findings.
} static void compute(char[] pat, int M, int[][] TF) { int state, x; for (state = 0; state 1); return (int) lim;
} static void searchSO(char[] x, char[] y) { int m = x.length; int n = y.length; long lim, state; long[] S = new long[256]; int j; lim = preSo(x, m, S); for (state = ~0, j = 0; j < n; ++j) { state = (state
