12/08/2018, 15:30
Pattern Matching Algorithms P.1
Hiện nay trên thế giới dữ liệu tồn tại ở nhiều dạng khác nhau, trong đó dữ liệu dạng text chiếm một khối lượng không nhỏ. Việc tìm kiếm trong số những tài liệu này trong một khoảng thời gian nhanh chóng là một công việc có tính quan trọng bậc nhất. Việc so khớp chuỗi chỉ ra những vị trí trong văn ...
- Hiện nay trên thế giới dữ liệu tồn tại ở nhiều dạng khác nhau, trong đó dữ liệu dạng text chiếm một khối lượng không nhỏ. Việc tìm kiếm trong số những tài liệu này trong một khoảng thời gian nhanh chóng là một công việc có tính quan trọng bậc nhất. Việc so khớp chuỗi chỉ ra những vị trí trong văn bản xuất hiện chuỗi đầu vào có sẵn. Ứng dụng tìm kiếm này cho phép người dùng lọc thông tin tìm kiếm nhanh nhất thông qua việc tìm kiếm những từ khóa (keyword). Ngoài ra, việc so sánh chuỗi còn có ứng dụng trong ngành tin sinh học như so khớp gen, xác định vị trí của gen trên ADN, ARM, từ đó xác định được sự phân chia tính trạng khi phân ly. Điều này có ý nghĩa to lớn trong việc thiết lập bản đồ gen người, tiến tới điều trị được những căn bệnh nan y do biến đổi gen gây ra.
- Do những ý nghĩa và vai trò to lớn của đối sánh mẫu, rất nhiều thuật toán được con người nghĩ ra, triển khai và áp dụng vào công việc so khớp chuỗi. Dưới đây là một số những thuật toán đối sánh mẫu như thế.
a. Khái niệm.
- String-matching được hiểu là việc tìm một hoặc nhiều xâu mẫu (pattern) xuất hiện trong một văn bản (có thể là rất dài). Ký hiệu xâu mẫu hay xâu cần tìm là X =(x0, x1,..,xm-1) có độ dài m. Văn bản Y =(y0, y1,..,yn-1) có độ dài n. Cả hai xâu được xây dựng từ một tập hữu hạn các ký tự Alphabet ký hiệu là với kích cỡ là . Như vậy một xâu nhị phân có độ dài n ứng dụng trong mật mã học cũng được xem là một mẫu. Một chuỗi các ký tự ABD độ dài m biểu diễn các chuỗi AND cũng là một mẫu.
- Input: Xâu mẫu X =(x0, x1,.., xm), độ dài m. Văn bản Y =(y0, x1,.., yn), độ dài n.
- Output: Tất cả vị trí xuất hiện của X trong Y.
b. Phân loại.
Ta có thể phân loại các thuật toán tìm kiếm mẫu thành các lớp:
- Tìm kiếm mẫu từ bên trái qua bên phải: Harrison Algorithm, Karp-Rabin Algorithm, Morris-Pratt Algorithm, Knuth- Morris-Pratt Algorithm, Forward Dawg Matching algorithm , Apostolico-Crochemore algorithm, Naive algorithm.
- Tìm kiếm mẫu từ bên phải qua bên trái: Boyer-Moore Algorithm , Turbo BM Algorithm, Colussi Algorithm, Sunday Algorithm, Reverse Factorand Algorithm, Turbo Reverse Factor, Zhu and Takaoka and Berry-Ravindran Algorithms.
- Tìm kiếm mẫu từ một vị trí cụ thể: Two Way Algorithm, Colussi Algorithm , Galil-Giancarlo Algorithm, Sunday's Optimal Mismatch Algorithm, Maximal Shift Algorithm, Skip Search, KMP Skip Search and Alpha Skip Search Algorithms.
- Tìm kiếm mẫu từ bất kỳ: Horspool Algorithm, Boyer-Moore Algorithm, Smith Algorithm , Raita Algorithm.
a. Brute Force Algorithm
Đặc điểm:
- Là 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:
Thuật toán Brute Force bao gồm kiểm tra, tất cả các vị trí trong đoạn văn bản giữa 0 và n-m, không cần quan tâm liệu mẫu này có tồn tại ở vị trí đó hay không. Sau đó, sau mỗi lần kiểm tra mẫu sẽ dịch sang phải một vị trí.
Actions:
for ( j = 0; j <= (n-m); j++) { //duyệt từ trái qua phải xâu X
for (i =0; i<m && X[i] == Y[i+j]; i++) ; //Kiểm tra mẫu
if (i>=m) OUTPUT (j);
}
EndActions
Kiểm thử thuật toán:
- X = “GCAGAGAG”
- Y =”GCATCGCAGAGAGTATACAGTACG”
- Quá trình tìm kiếm :
First attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1 2 3 4
G C A G A G A G
Second attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Third attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Fourth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Fifth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Sixth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1 2 3 4 5 6 7 8
G C A G A G A G
Seventh attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Eighth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Ninth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1 2
G C A G A G A G
Tenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Eleventh attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1 2
G C A G A G A G
Twelfth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Thirteenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1 2
G C A G A G A G
Fourteenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Fifteenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Sixteenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Seventeenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
b. Search with an automaton.
Đặc điểm:
- Yêu cầu xây dựng automation đơ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(nlog(∂)) .
Thuật toán:
Trong thuật toán này, quá trình tìm kiếm được đưa về một quá trình biến đổi trạng thái automat. Hệ thống automat trong thuật toán DFA sẽ được xây dựng dựa trên xâu mẫu. Mỗi trạng thái (nút) của automat lúc sẽ đại diện cho số ký tự đang khớp của mẫu với văn bản. Các ký tự của văn bản sẽ làm thay đổi các trạng thái. Và khi đạt được trạng cuối cùng có nghĩa là đã tìm được một vị trí xuất hiện ở mẫu.
void preAut(char *x, int m, Graph aut){
memset(aut,0,sizeof(aut));
aut[0][x[0]] = 1;
aut[1][x[0]] = 1;
For(i,2,m){
int vt = aut[i-1][x[i-1]];
for(int j = 0; j < ASIZE ; j++){
aut[i][s[j]] = aut[vt][s[j]];
}
aut[i-1][x[i-1]] = i;
}
}
void AUT(){
int state = 0;
for(int i = 0; i < n ; i++){
state = aut[state][y[i]];
if(state == m) printf("position is %d
", i -m +1);
}
}
Kiểm nghiệm thuật toán:
X = “GCAGAGAG” Y =”GCATCGCAGAGAGTATACAGTACG” Pha tìm kiếm : Current state is: 0
G C A T C G C A G A G A G T A T A C A G T A C G 1 G C A T C G C A G A G A G T A T A C A G T A C G 2 G C A T C G C A G A G A G T A T A C A G T A C G 3 G C A T C G C A G A G A G T A T A C A G T A C G 0 G C A T C G C A G A G A G T A T A C A G T A C G 0 G C A T C G C A G A G A G T A T A C A G T A C G 1 G C A T C G C A G A G A G T A T A C A G T A C G 2 G C A T C G C A G A G A G T A T A C A G T A C G 3 G C A T C G C A G A G A G T A T A C A G T A C G 4 G C A T C G C A G A G A G T A T A C A G T A C G 5 G C A T C G C A G A G A G T A T A C A G T A C G 6 G C A T C G C A G A G A G T A T A C A G T A C G 7 G C A T C G C A G A G A G T A T A C A G T A C G 8 G C A T C G C A G A G A G T A T A C A G T A C G 0 G C A T C G C A G A G A G T A T A C A G T A C G 0 G C A T C G C A G A G A G T A T A C A G T A C G 0 G C A T C G C A G A G A G T A T A C A G T A C G 0 G C A T C G C A G A G A G T A T A C A G T A C G 0 G C A T C G C A G A G A G T A T A C A G T A C G 0 G C A T C G C A G A G A G T A T A C A G T A C G 1 G C A T C G C A G A G A G T A T A C A G T A C G 0 G C A T C G C A G A G A G T A T A C A G T A C G 0 G C A T C G C A G A G A G T A T A C A G T A C G 0 G C A T C G C A G A G A G T A T A C A G T A C G
c. Karp-Rabin algorithm.
Đặc điểm:
- Sử dụng hàm băm
- Pha chuẩn bị có độ phức tạp thuật toán và không gian lưu trữ O(m)
- Chương trình chạy có độ phức tạp O(m+n)
Thuật toán:
Hàm băm cung cấp phương thức đơn giản để tránh những con số phức tạp trong việc so sánh những kí tự trong hầu hết các trường hợp thực tế. Thay cho việc kiểm tra từng vị trí trong văn bản nếu như có mẫu xuất hiện, nó chỉ phải kiểm tra những đoạn “gần giống” xâu mẫu. Để kiểm tra sự giống nhau giữa 2 từ sử dụng hàm băm. Giúp cho việc đối chiếu xâu, hàm băm hash:
- Có khả năng tính toán được
- Đánh giá xâu mức cao.
- Hash(y[j+1…j+m]) được tính toán dễ hơn dựa trên hash(y[j…j+m-1]) và hash(y[j+m]).
void KR(char *x, int m, char *y, int n) {
int d, hx, hy, i, j;
/* Preprocessing */
/* computes d = 2^(m-1) with the left-shift operator */
for (d = i = 1; i < m; ++i) d = (d<<1);
for (hy = hx = i = 0; i < m; ++i) {
hx = ((hx<<1) + x[i]);
hy = ((hy<<1) + y[i]);
}
/* Searching */
j = 0;
while (j <= n-m) {
if (hx == hy && memcmp(x, y + j, m) == 0)
printf("position is %d
",j);
hy = REHASH(y[j], y[j + m], hy);
++j;
}
}
Kiểm thử thuật toán:
X = “GCAGAGAG” Y =”GCATCGCAGAGAGTATACAGTACG” Pha tiền xử lí: Tính được hash(X) = 17597 Pha tìm kiếm thực hiện như sau :
First attempt G C A T C G C A G A G A G T A T A C A G T A C G G C A G A G A G hash(y[0 .. 7]) = 17819 Second attempt G C A T C G C A G A G A G T A T A C A G T A C G G C A G A G A G hash(y[1 .. 8]) = 17533 Third attempt G C A T C G C A G A G A G T A T A C A G T A C G G C A G A G A G hash(y[2 .. 9]) = 17979 Fourth attempt G C A T C G C A G A G A G T A T A C A G T A C G G C A G A G A G hash(y[3 .. 10]) = 19389 Fifth attempt G C A T C G C A G A G A G T A T A C A G T A C G G C A G A G A G hash(y[4 .. 11]) = 17339 Sixth attempt G C A T C G C A G A G A G T A T A C A G T A C G 1 2 3 4 5 6 7 8 G C A G A G A G hash(y[5 .. 12]) = 17597 Seventh attempt G C A T C G C A G A G A G T A T A C A G T A C G G C A G A G A G hash(y[6 .. 13]) = 17102 Eighth attempt G C A T C G C A G A G A G T A T A C A G T A C G G C A G A G A G hash(y[7 .. 14]) = 17117 Ninth attempt G C A T C G C A G A G A G T A T A C A G T A C G G C A G A G A G hash(y[8 .. 15]) = 17678 Tenth attempt G C A T C G C A G A G A G T A T A C A G T A C G G C A G A G A G hash(y[9 .. 16]) = 17245 Eleventh attempt G C A T C G C A G A G A G T A T A C A G T A C G G C A G A G A G hash(y[10 .. 17]) = 17917 Twelfth attempt G C A T C G C A G A G A G T A T A C A G T A C G G C A G A G A G hash(y[11 .. 18]) = 17723 Thirteenth attempt G C A T C G C A G A G A G T A T A C A G T A C G G C A G A G A G hash(y[12 .. 19]) = 18877 Fourteenth attempt G C A T C G C A G A G A G T A T A C A G T A C G G C A G A G A G hash(y[13 .. 20]) = 19662 Fifteenth attempt G C A T C G C A G A G A G T A T A C A G T A C G G C A G A G A G hash(y[14 .. 21]) = 17885 Sixteenth attempt G C A T C G C A G A G A G T A T A C A G T A C G G C A G A G A G hash(y[15 .. 22]) = 19197 Seventeenth attempt G C A T C G C A G A G A G T A T A C A G T A C G G C A G A G A G hash(y[16 .. 23]) = 16961
Handbook of Exact String-Matching Algorithms by Christian Charras, Thierry Lecroq
- Vậy ở trong bài viết này, chúng ta đã tìm hiểu được cơ bản về đối sánh mẫu văn bản và 3 thuật toán đối sánh mẫu từ trái qua phải.
- Ở bài viết tiếp theo, tôi sẽ giới thiệu về một số thuật toán đối sánh mẫu từ phải qua trái, từ một vị trí cụ thể và đối sánh mẫu từ bất kì.
