12/08/2018, 16:05
Pattern Matching Algorithms P.2
Như ở phần I : https://viblo.asia/p/pattern-matching-algorithms-p1-YWOZrMVrKQ0 tôi đã giới thiệu khái niệm, phân loại và một số phương pháp đối sánh mẫu từ trái qua phải. Thì ở phần II này tôi tiếp tục giới thiệu một số phương pháp đối sánh mẫu văn bản từ phải qua trái, từ một vị trí cụ thể, hay từ ...
Như ở phần I : https://viblo.asia/p/pattern-matching-algorithms-p1-YWOZrMVrKQ0 tôi đã giới thiệu khái niệm, phân loại và một số phương pháp đối sánh mẫu từ trái qua phải. Thì ở phần II này tôi tiếp tục giới thiệu một số phương pháp đối sánh mẫu văn bản từ phải qua trái, từ một vị trí cụ thể, hay từ một điểm bất kì.
1. Boyer Moore algorithm
1.1 Đặc điểm
- Thuật toán thực thi việc so sánh từ phải sang trái
- Pha cài đặt có độ phức tạp thuật toán và không gian nhớ là O(m+σ)
- Pha thực thi có độ phức tạp là O(mxn)
- 3n kí tự xâu văn bản được so sánh trong trường hợp xấu nhất khi thực thi với mẫu không tuần hoàn
- Độ phức tạp O(n/m) khi thực thi tốt nhất.
1.2 Trình bày thuật toán
- Boyer-Moore quan tâm tới thuật toán đối sánh xâu hiệu quả nhất thường thấy. Các biến thể của nó thường được dùng trong các bộ soạn thảo cho các lệnh như <<search>> và <<subtitute>>.
- Thuật toán sẽ quét các ký tự của mẫu (pattern) từ phải sang trái bắt đầu ở phần tử cuối cùng.
- Trong trường hợp mis-match (hoặc là trường hợp đã tìm được 1 đoạn khớp với mẫu), nó sẽ dùng 2 hàm được tính toán trước để dịch cửa sổ sang bên phải. Hai hàm dịch chuyển này được gọi là good-suffix shift (còn được biết với cái tên phép dịch chuyển khớp) và bad-character shift (còn được biết với cái tên phép dịch chuyển xuất hiện).
- Đối với mẫu x[0..m-1] ta dùng 1 biến chỉ số i chạy từ cuối về đầu, đối với chuỗi y[0..n-1] ta dùng 1 biến j để chốt ở phía đầu.
- G/s rằng trong quá trình so sánh ta gặp 1 mis-match tai vị trí x[i]=a của mẫu và y[i+j]=b trong khi đang thử khớp tại vị trí j.
- Khi đó, x[i+1..m-1]=y[j+i+1..j+m-1]=u và x[i]≠y[i+j] . Bây giờ ta đi xét xem đối với từng trường hợp, 2 hàm trên sẽ thực hiện việc dịch chuyển như thế nào:
- Phép dịch chuyển good-suffix shift sẽ dịch cửa sổ sang bên phải cho đến khi gặp 1 ký tự khác với x[i] trong trường hợp đoạn u lại xuất hiện trong x.
- Fig2: good-suffix shift, trường hợp u lại xuất hiện trong xNếu đoạn u không xuất hiện lại trong x, mà chỉ có 1 phần cuối (suffix) của u khớp với phần đầu (prefix) của x, thì ta sẽ dịch 1 đoạn sao cho phần suffix dài nhất vcủa y[j+i+1..j+m-1] khớp với prefix của x.
- Fig3: good-suffix shift, trường hợp chỉ suffix của u xuất hiện trong x
- Phép dịch chuyển bad-character shift sẽ khớp kí tự y[i+j] với 1 ký tự (bên phải nhất) trong đoạn x[0..m-2] (các bạn thử nghĩ xem tại sao không phải là m-1)
- Fig4: bad-character shift
- Nếu y[i+j] không xuất hiện trong x, ta thấy ngay rằng không có xuất hiện nào của x trong y mà lại chứa chấp y[i+j], do đó ta có thể đặt cửa sổ ngay sau y[i+j], tức là y[j+i+1] .
- Thuật toán Boyer-Moore sẽ chọn đoạn dịch chuyển dài nhất trong 2 hàm dịch chuyển good-suffix shift và bad-character shift. Hai hàm này được định nghĩa như sau:
- Hàm good-suffix shift được lưu trong bảng bmGs có kích thước m+1.
- Ta định nghĩa 2 điều kiện sau:
- Cs(i, s): với mỗi k mà i < k < m, s ≥ k hoặc x[k-s]=x[k] và
- Co(i, s): nếu s <i thì x[i-s] ≠ x[i] Khi đó, với 0≤ i <m: bmGs[i+1]=min{s>0 : Cs(i, s) and Co(i, s) hold} và chúng ta định nghĩa bmGs[0] là độ dài chu kỳ của x. Việc tính toán bảng bmGs sử dụng 1 bảng suff định nghĩa như sau: với 1 ≤ i < m, suff[i]=max{k : x[i-k+1 ..i]=x[m-k .. m-1]}
- Hàm bad-character shift được lưu trong bảng bmBc có kích thước σ. Cho c trong Σ : bmBc[c] = min{i : 1≤ i <m-1 và x[m-1-i]=c} nếu c xuất hiện trong x, m ngược lại.
1.3 Kiểm thử thuật toán
X = “GCAGAGAG” Y =”GCATCGCAGAGAGTATACAGTACG” Pha tiền xử lí: bmBc and bmGs tables used by Boyer-Moore algorithm Pha thực thi: 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 G C A G A G A G Shift by: 1 (bmGs[7]=bmBc[A]-8+8) 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 3 2 1 G C A G A G A G Shift by: 4 (bmGs[5]=bmBc[C]-8+6 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 8 7 6 5 4 3 2 1 G C A G A G A G Shift by: 7 (bmGs[0]) 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 3 2 1 G C A G A G A G Shift by: 4 (bmGs[5]=bmBc[C]-8+6) 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 2 1 G C A G A G A G Shift by: 7 (bmGs[6]) Boyer Moore thực thi 17 lần so sánh kí tự trong ví dụ này.
1.4 Chương trình chạy
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstdio>
#include<cstring>
#define For(i,a,b) for(long i = a;i<=b;i++)
using namespace std;
char x[100001],y[100001];
int m, n, ASIZE = 256,XSIZE;
void nhap(){
printf("Nhap x : "); gets(x); m = strlen(x); XSIZE = m;
printf("Nhap y : "); gets(y); n = strlen(y);
}
void preBmBc(char *x, int m, int bmBc[]) {
int i;
for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
void suffixes(char *x, int m, int *suff) {
int f, g, i;
suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}
void preBmGs(char *x, int m, int bmGs[]) {
int i, j, suff[XSIZE];
suffixes(x, m, suff);
for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= 0; --i)
if (suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
}
void BM(char *x, int m, char *y, int n) {
int i, j, bmGs[XSIZE], bmBc[ASIZE];
/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);
/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
printf("position is %d
",j);
j += bmGs[0];
}
else
j += max(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
}
int main(){
nhap();
BM(x,m,y,n);
return 0;
}
Chạy test : Input : Nhập x : GCAGAGAG Nhập y : GCATCGCAGAGAGTATACAGTACG Output: Position is 5
2. Zhu Kataoka algorithm
2.1 Đặc điểm
- Là một biến thể của Boyer Moore.
- Sử dụng 2 kí tự liên tiếp nhau để tính toán bước dịch bad charater
- Pha cài đặt có độ phức tạp thuật toán và không gian nhớ là O(m+σ2)
- Pha thực thi có độ phức tạp là O(mxn)
2.2 Trình bày thuật toán
- Zhu và Takaoka thiết kế thuật toán mà chúng thực thi dựa trên bad charater. Trong quá trình tìm kiếm, việc so sánh được thực hiện từ phải qua trái, và khi cửa sổ đang ở vị trí y[j…j+m-1] và xuất hiện sự khác nhau giữa x[m- k] và y[j+m-k] trong khi x[m-k+1 .. m-1]=y[j+m-k+1 .. j+m-1] . bước dịch good suffix cũng được sử dụng để tính toán bước dịch.
- Pha tiền xử lí của thuật toán bao gồm việc tính toán mỗi cặp kí tự(a,b) với a,b là mút bên phải của đoạn x[0…m-2]
- Với a,b thuộc : ztBc[a, b]=k và k có các giá trị: K <m-2 và x[m-k .. m-k+1]=ab và ab không xuất hiện trong đoạn x[m-k+2 .. m-2] or k=m-1 và x[0]=b và ab không xuất hiện trong đoạn x[0 .. m-2] or k=m and x[0] bvà ab không xuất hiện trong đoạn x[0 .. m-2]
2.3 Kiểm thử thuật toán
X = “GCAGAGAG” Y =”GCATCGCAGAGAGTATACAGTACG” Pha tiền xử lí: ztBc and bmGs tables used by Zhu-Takaoka algorithm. 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 1 G C A G A G A G Shift by: 5 (ztBc[C][A]) 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 8 7 6 5 4 3 2 1 G C A G A G A G Shift by: 7 (bmGs[0]) 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 3 2 1 G C A G A G A G Shift by: 7 (bmGs[6])
Thuật toán Zhu Taraoka thực hiện 12 lần so sánh xâu kí tự trong ví dụ này.
2.4 Chương trình chạy
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstdio>
#include<cstring>
#define For(i,a,b) for(long i = a;i<=b;i++)
using namespace std;
char x[100001],y[100001];
int m, n,ASIZE = 256, XSIZE;
void nhap(){
printf("Nhap x : "); gets(x); m = strlen(x); XSIZE = m;
printf("Nhap y : "); gets(y); n = strlen(y);
}
void suffixes(char *x, int m, int *suff) {
int f, g, i;
suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}
void preBmGs(char *x, int m, int bmGs[]) {
int i, j, suff[XSIZE];
suffixes(x, m, suff);
for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= 0; --i)
if (suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
}
void preZtBc(char *x, int m, int ztBc[256][256]) {
int i, j;
for (i = 0; i < ASIZE; ++i)
for (j = 0; j < ASIZE; ++j)
ztBc[i][j] = m;
for (i = 0; i < ASIZE; ++i)
ztBc[i][x[0]] = m - 1;
for (i = 1; i < m - 1; ++i)
ztBc[x[i - 1]][x[i]] = m - 1 - i;
}
void ZT(char *x, int m, char *y, int n) {
int i, j, ztBc[256][256], bmGs[XSIZE];
/* Preprocessing */
preZtBc(x, m, ztBc);
preBmGs(x, m, bmGs);
/* Searching */
j = 0;
while (j <= n - m) {
i = m - 1;
while (i < m && x[i] == y[i + j])
--i;
if (i < 0) {
printf("position is %d
",j);
j += bmGs[0];
}
else
j += max(bmGs[i],
ztBc[y[j + m - 2]][y[j + m - 1]]);
}
}
int main(){
nhap();
ZT(x,m,y,n);
return 0;
}
Chạy test : Input : Nhập x : GCAGAGAG Nhập y : GCATCGCAGAGAGTATACAGTACG Output: Position is 5
1. Colussi algorithm
1.1 Đặc điểm
- đây là thuật toán cái tiến từ thuật toán Knuth, Morris and Pratt.
- mẫu tìm kiếm sẽ được chia thành 2 tập con. Tập thứ nhất sẽ được duyệt từ trái sang phải khi không gặp mismatch ta duyệt tập thứ hai từ trái qua phải.
- pha xử lý có độ phức tạp là O(m)
- pha tìm kiếm có độ phức tạp là O(n)
- trong trường hợp xấu nhất quá trình thực thi sẽ mất 3/2 n lần so sánh kí tự.
1.2 Trình bày thuật toán
- Thuật toán Colussi được thiết kế dựa theo những phân tích từ thuật toán knuth, Morris, và Pratt. các vị trí kí tự trong mẫu được chia thành 2 tập riêng biệt. mỗi phép thử sẽ bao gồm 2 pha :
- Trong pha thứ nhất thực hiên so sánh từ trái sang phải lần lượt các kí tự tại những vị trí kmpNext > -1. Những vị trí này gọi là noholes.
- Pha thứ hai so sánh kí tự từ phải sang trái ( các kí tự còn lại ) nhưng kí tự này có kmpNext = -1 và gọi là holes.
- Chiến lược này có 2 lợi thế :
- khi gặp mismath trong pha thứ nhất, sau khi thực hiện shift bước dịch ta không cần phải so sánh lại các kí tự tại những vị trí noholes phía trước.
- khi gặp mismath trong pha thứ hai có nghĩa là đoạn hậu tố đã matches tất cả kí tự
1.3 Kiểm thử thuật toán.
X = “GCAGAGAG” Y =”GCATCGCAGAGAGTATACAGTACG” pha tiền xử lý xác định : Pha 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 G C A G A G A G Shift by: 3 (shift[2]) 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 2 G C A G A G A G Shift by: 2 (shift[1]) 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 8 1 2 7 3 6 4 5 G C A G A G A G Shift by: 7 (shift[8]) 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 Shift by: 1 (shift[0]) 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 Shift by: 1 (shift[0]) 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 G C A G A G A G Shift by: 1 (shift[0]) 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 Shift by: 1 (shift[0]) 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 2 3 G C A G A G A G
Shift by: 3 (shift[2]) Thuật toán Colussi thực hiện 20 lần so sánh kí tự trong ví dụ.
1.4 Chương trình chạy
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstdio>
#include<cstring>
using namespace std;
char x[100001],y[100001];
int XSIZE, m, n;
void nhap(){
printf("Nhap x : "); gets(x); m = strlen(x);
printf("Nhap y : "); gets(y); n = strlen(y);
XSIZE = m;
}
int preColussi(char *x, int m, int h[], int next[],
int shift[]) {
int i, k, nd, q, r, s;
int hmax[XSIZE], kmin[XSIZE], nhd0[XSIZE], rmin[XSIZE];
/* Computation of hmax */
i = k = 1;
do {
while (x[i] == x[i - k])
i++;
hmax[k] = i;
q = k + 1;
while (hmax[q - k] + k < i) {
hmax[q] = hmax[q - k] + k;
q++;
}
k = q;
if (k == i + 1)
i = k;
} while (k <= m);
/* Computation of kmin */
memset(kmin, 0, m*sizeof(int));
for (i = m; i >= 1; --i)
if (hmax[i] < m)
kmin[hmax[i]] = i;
/* Computation of rmin */
for (i = m - 1; i >= 0; --i) {
if (hmax[i + 1] == m)
r = i + 1;
if (kmin[i] == 0)
rmin[i] = r;
else
rmin[i] = 0;
}
/* Computation of h */
s = -1;
r = m;
for (i = 0; i < m; ++i)
if (kmin[i] == 0)
h[--r] = i;
else
h[++s] = i;
nd = s;
/* Computation of shift */
for (i = 0; i <= nd; ++i)
shift[i] = kmin[h[i]];
for (i = nd + 1; i < m; ++i)
shift[i] = rmin[h[i]];
shift[m] = rmin[0];
/* Computation of nhd0 */
s = 0;
for (i = 0; i < m; ++i) {
nhd0[i] = s;
if (kmin[i] > 0)
++s;
}
/* Computation of next */
for (i = 0; i <= nd; ++i)
next[i] = nhd0[h[i] - kmin[h[i]]];
for (i = nd + 1; i < m; ++i)
next[i] = nhd0[m - rmin[h[i]]];
next[m] = nhd0[m - rmin[h[m - 1]]];
return(nd);
}
void COLUSSI(char *x, int m, char *y, int n) {
int i, j, last, nd,
h[XSIZE], next[XSIZE], shift[XSIZE];
/* Processing */
nd = preColussi(x, m, h, next, shift);
/* Searching */
i = j = 0;
last = -1;
while (j <= n - m) {
while (i < m && last < j + h[i] &&
x[h[i]] == y[j + h[i]])
i++;
if (i >= m || last >= j + h[i]) {
printf("position is %d
",j);
i = m;
}
if (i > nd)
last = j + m - 1;
j += shift[i];
i = next[i];
}
}
int main(){
nhap();
COLUSSI(x,m,y,n);
return 0;
}
Chạy test : Input : Nhập x : GCAGAGAG Nhập y : GCATCGCAGAGAGTATACAGTACG Output: Position is 5
2. Skip Search Algorithm
2.1 Đặc điểm
- Sử dụng thùng chứa (bucket) các vị trí xuất hiện của kí tự trong xâu mẫu.
- Pha xử lý có độ phực tạp thời gian và không gian chứa O(m+ ∂)
- Pha tìm kiếm có độ phức tạp thời gian O(mn)
2.2 Trình bày thuật toán
- Với mỗi kí tự trong bảng chữ cái, một thùng chứa (bucket) sẽ chứa tất cả các vị trí xuất hiện của kí tự đó trong xâu mẫu x. khi một kí tự xuất hiện k lần trong mẫu. bucket sẽ lưu k vị trí của kí tự đó. Khi mà xâu y chứa it kí tự hơn trong bản chữ cái thì sẽ có nhiều bucket rỗng.
- Quá trình xử lý của thuật toán Skip Search bao gồm việc tính các buckets cho tất cả các kí tự trong bảng chữ cái. for c in z[c] = {i : 0 i m-1 and x[i] = c}
- Thuật toán Skip Search có độ phức tạp bình phương trong trường hợp tồi nhất. nhưng cũng có trường hợp là O(n).
2.3 Kiểm thử thuật toán
X = “GCAGAGAG” Y = ”GCATCGCAGAGAGTATACAGTACG” Pha tiền xử lý xác định : Pha 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 2 1 G C A G A G A G 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 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 Shift by: 8 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 Shift by: 8 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 2 1 G C A G A G A G
Thuật toán Skip Search thực hiện 14 lần so sánh kí tự trong ví dụ.
2.4 Chương trình chạy
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<list>
using namespace std;
char x[100001],y[100001];
int ASIZE = 256, m, n;
void nhap(){
printf("Nhap x : "); gets(x); m = strlen(x);
printf("Nhap y : "); gets(y); n = strlen(y);
}
void SKIP(char *x, int m, char *y, int n){
int i,j;
list<int> z[ASIZE];
list<int>::iterator it;
/*preprocessing */
for(i = m-1 ; i >=0 ;i--){
z[x[i]].push_back(i);
}
/* search */
for(j = m-1; j < n ; j +=m){
for(it = z[y[j]].begin() ; it!= z[y[j]].end(); it++){
if(memcmp(x,y+j-(*it),m) == 0)
printf("position is %d
",j- (*it));
}
}
}
int main(){
nhap();
SKIP(x,m,y,n);
return 0;
}
Chạy test : Input : Nhập x : GCAGAGAG Nhập y : GCATCGCAGAGAGTATACAGTACG Output : Position is 5
1. Horspool algorithm
1.1 Đặc điểm
- Là thuật toán đơn giản hơn của Boyer Moore
- Sử dụng dụng bad- character
- Dễ để cài đặt
- Pha cài đặt có độ phức tạp thuật toán là O(m+σ) và độ phức tạp bộ nhớ là O(σ)
- Pha thực thi có độ phức tạp là O(mxn)
- Số lượng so sánh trung bình cho một văn bản là trong khoảng 1/và 2/( +1)
1.2 Trình bày thuật toán
- Quy tắc dịch bad- character được sử dụng trong Boyer Moore không có hiệu quả trong đoạn văn bản kí tự nhỏ, nhưng khi đoạn văn bản là lớn và phải so sánh với mẫu dài, nó thường trong trường hợp bảng bã ASCII và tìm kiếm thông thường trong soạn thảo văn bản, chúng rất h ữu dụng. Sử dụng nó như những kết quả riêng biệt lại rất hiệu quả.
1.3 Kiểm thử thuật toán
X = “GCAGAGAG” Y =”GCATCGCAGAGAGTATACAGTACG” Pha tiền xử lí: bảng bmBc của Horspool algorithm Pha tìm kiếm thực hiện : 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 G C A G A G A G Shift by: 1 (bmBc[A]) 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 2 1 G C A G A G A G Shift by: 2 (bmBc[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 2 1 G C A G A G A G Shift by: 2 (bmBc[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 2 3 4 5 6 7 8 1 G C A G A G A G Shift by: 2 (bmBc[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 Shift by: 1 (bmBc[A]) 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 G C A G A G A G Shift by: 8 (bmBc[T]) 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 2 1 G C A G A G A G Shift by: 2 (bmBc[G])
Cần 17 lượt so sánh trong ví dụ này.
1.4 Chương trình chạy
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstdio>
#include<cstring>
#define For(i,a,b) for(long i = a;i<=b;i++)
using namespace std;
char x[100001],y[100001];
int m, n,ASIZE = 256;
void nhap(){
printf("Nhap x : "); gets(x); m = strlen(x);
printf("Nhap y : "); gets(y); n = strlen(y);
}
void preBmBc(char *x, int m, int bmBc[]) {
int i;
for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
void HORSPOOL(char *x, int m, char *y, int n) {
int j, bmBc[ASIZE];
char c;
/* Preprocessing */
preBmBc(x, m, bmBc);
/* Searching */
j = 0;
while (j <= n - m) {
c = y[j + m - 1];
if (x[m - 1] == c && memcmp(x, y + j, m - 1) == 0)
printf("position is %d
",j);
j += bmBc[c];
}
}
int main(){
nhap();
HORSPOOL(x,m,y,n);
return 0;
}
Chạy test : Input : Nhập x : GCAGAGAG Nhập y : GCATCGCAGAGAGTATACAGTACG Output: Position is 5
2. Quick Search algorithm
2.1 Đặc điểm
- Là thuật toán đơn giản của Boyer Moore
- Chỉ sử dụng dụng bad- character
- Dễ để cài đặt
- Pha cài đặt có độ phức tạp thuật toán là O(m+σ) và độ phức tạp bộ nhớ là O(σ)
- Pha thực thi có độ phức tạp là O(mxn)
- Rất nhanh trong thực tế với những mẫu ngắn và anphabets lớn.
2.2 Trình bày thuật toán
- Thuật toán Quick Search chỉ sử dụng bảng bad charater. Giả sử trên cửa sổ dịch chuyển đang là đoạn văn bản y[j….j+m-1], độ dài bước dịch đồng đều là 1 bước. Vì vậy, vị trí tiếp theo có liên quan mật thiết tới số bước dịch chuyển. Quick Search sẽ quan tâm tới vị trí y[j+m]. qsBc[c]=min{i : 0 < i m and x[m-i]=c} if c có trong x hoặc bằng m+1 với trường hợp còn lại.
2.3 Kiểm thử thuật toán
X = “GCAGAGAG” Y =”GCATCGCAGAGAGTATACAGTACG” Pha tiền xử lí: bảng qsBc sử dụng Quick Search algorithm Pha tìm kiếm thực hiện : 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 Shift by: 1 (qsBc[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 Shift by: 2 (qsBc[A]) 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 Shift by: 2 (qsBc[A]) 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 2 3 4 5 6 7 8 G C A G A G A G Shift by: 9 (qsBc[T]) 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 Shift by: 7 (qsBc[C])
Quick Search algorithm thực thi 15 lần so sánh kí tự trong ví dụ này.
2.4 Chương trình chạy
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstdio>
#include<cstring>
#define For(i,a,b) for(long i = a;i<=b;i++)
using namespace std;
char x[100001],y[100001];
int m, n,ASIZE = 256;
void nhap(){
printf("Nhap x : "); gets(x); m = strlen(x);
printf("Nhap y : "); gets(y); n = strlen(y);
}
void preQsBc(char *x, int m, int qsBc[]) {
int i;
for (i = 0; i < ASIZE; ++i)
qsBc[i] = m + 1;
for (i = 0; i < m; ++i)
qsBc[x[i]] = m - i;
}
void QS(char *x, int m, char *y, int n) {
int j, qsBc[ASIZE];
/* Preprocessing */
preQsBc(x, m, qsBc);
/* Searching */
j = 0;
while (j <= n - m) {
if (memcmp(x, y + j, m) == 0)
printf("position is %d
",j);
j += qsBc[y[j + m]]; /* shift */
}
}
int main(){
nhap();
QS(x,m,y,n);
return 0;
}
Chạy test : Input : Nhập x : GCAGAGAG Nhập y : GCATCGCAGAGAGTATACAGTACG Output: Position is 5.
- Handbook of Exact String-Matching Algorithms by Christian Charras, Thierry Lecroq
