Pattern Matching in String

PHẦN 1: GIỚI THIỆU BÀI TOÁN ĐỖI SÁNH MẪU
1.1. Nội dung của bài toán:
Cho mẫu P, |P| = m <=10 3, và dữ liệu T, |T| <=10

100

. Xác định vị trí P trong T (nếu

có)?
1.2 Phân tích bài toán:
Input: Tập các ký tự Σ
Mẫu (Pattern): P với |P| = m <= 103
Dữ liệu: T với |T| = n<=10 100
Output:
P ⊆ T?
Nếu P ⊆ T: vị trí xuất hiện của P trong T?
Đây là bài toán đối sánh mẫu với kích thước dữ liệu đầu vào giới hạn: mẫu P, |P| = m

<= 103, và dữ liệu T, |T| <=10 100
1.3 Cách giải quyết
Bài toán đối sánh chuỗi ký tự có thể được đặc trưng như một bài toán tìm kiếm,
trong đó mẫu P được xem như khoá, tuy nhiên các thuật toán tìm kiếm thông thường
không áp dụng được một cách trực tiếp vì mẫu P có thể dài và nó trải trên văn bản theo
một cách không biết trước được. Đây là một bài toán thú vị có nhiều thuật toán khác
nhau như Brute-Force (BF), Knuth-Morris-Pratt (KMP), Boyer-Moore (BM), KarpRabin (KR), Franek-Jennings-Smyth (FJS) …
Trong đề tài em tìm hiểu thuật toán Knuth-Morris-Pratt(KMP) đưa ra cách tìm vị trí
mẫu P trong văn bản T và từ đó đánh giá được thuật toán đó

Học viên: Nguyễn Tuấn Tùng

1


Pattern Matching in String

PHẦN 2: THUẬT TOÁN ĐỖI SÁNH MẪU ĐƠN GIẢN
2.1. Tư tưởng bài toán:
Kiểm tra từng vị trí trong văn bản từ 1..n, tại mỗi vị trí kiểm tra sự so khớp giữa mẫu
và văn bản, cho đến khi tìm được vị trí khớp hoàn toàn với m kí tự của mẫu hoặc đã
kiểm tra tất cả n vị trí thì dừng.
Input: chuỗi mẫu P và chuỗi văn bản gốc T
Output: Vị trí i là vị trí của P trong T. Nếu không thấy P trong T thì i=0
2.2. Giải thuật đối sánh mẫu đơn giản:
input: P[1…m], T[1…n];
Output: i0= (if P  T[i0……. i0+m-1] , i0 ≥ 1, otherwise i0=0
k:=1;i:=1;j:=1;
while(j<=n and k<=m)
if (T[j]=P[k])
{ j++; k++; }
else
{ i++; j=i; k=1;}

}
if(k>m) i0 :=i
else i0 :=0
2.3. Ví dụ minh họa thuật toán:
I
T:
J

K

1
A B C A B C D A B A B C D A B C D A B D E
1 2 3 4
1 2 3 4

P:

A B C D A B D

I
T:
J
K

2
A B C A B C D A B A B C D A B C D A B D E
1
1

P:

A B C D A B D

Học viên: Nguyễn Tuấn Tùng

2



Pattern Matching in String

I
T:
J
K
P:
I
T:
J
K
P:
I
T:
J
K
P:
I
T:
J
K

3
A B C A B C D A B A B C D A B C D A B D E
1
1
A B C D A B D
4
A B C A B C D A B A B C D A B C D A B D E
1 2 3 4 5 6 7

1 2 3 4 5 6 7
A B C D A B D
5
A B C A B C D A B A B C D A B C D A B D E
1
1
A B C D A B D
6
A B C A B C D A B A B C D A B C D A B D E
1
1

P:
I
T:
J
K

A B C D A B D
7
A B C A B C D A B A B C D A B C D A B D E
1
1

P:

A B C D A B D

…
I

T:
J
K

14
A B C A B C D A B A B C D A B C D A B D E
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8

P:

Học viên: Nguyễn Tuấn Tùng

A B C D A B D

3


Pattern Matching in String
Tìm thấy tại vị trí i=14.

2.4. Đánh giá thuật toán:
Trong trường hợp xấu nhất (ví dụ với T: “BBBBBBBBBBBBB”, P: “BBA”) thì:
Số bước dịch chuyển i sẽ là n-m+1 bước và ứng với mỗi lần i dịch chuyển sẽ phải
thực hiện m phép so sánh (T[j]=P[k]) nên tổng số phép so sánh phải thực hiện trong
trường hợp xấu nhất là m(n-m+1). Thông thường m rất nhỏ so với n vì vậy ta có thể
kết luận số phép so sánh trong trường hợp xấu nhất là m.n
Thuật toán có độ phức tập O(m.n)
2.5. Nhận xét thuật toán:
Trong ví dụ ở trên trên ta nhận thấy mỗi lần so sánh không khớp thì i dịch chuyển đi

đúng 1 đơn vị.
B1:
I
T:
J
K

1
A B C A B C D A B A B C D A B C D A B D E
1 2 3 4
1 2 3 4

P:

A B C D A B D

I
T:
J
K

2
A B C A B C D A B A B C D A B C D A B D E
1
1

B2:

P:


A B C D A B D

Ta nhận thấy việc tăng i=i+1 là chưa tối ưu và hay chăng ta có thể tăng i=i+3, tức là
phải ghi nhận được vị trí của T[4] ở bước 1 là khác P[4] vậy thì cần dịch chuyển sao
cho P[k] nào đó =T[4] như sau:
B1:
I
T:
J
K

1
A B C A B C D A B A B C D A B C D A B D E
1 2 3 4
1 2 3 4

P:

A B C D A B D

Học viên: Nguyễn Tuấn Tùng

4


Pattern Matching in String

B2:
I
T:

J
K
P:

4
A B C A B C D A B A B C D A B C D A B D E
1 2 3 4
1
A B C D A B D

Học viên: Nguyễn Tuấn Tùng

5


Pattern Matching in String
Có nghĩa là ta cần tìm P[k] nào đó gần P[4] nhất mà trùng T[4] để đặt khớp với nhau.
Công việc này sẽ tạo ra bước nhảy lớn hơn thay vì i=i+1, trong trường hợp này i=i+3.
Điều này sẽ làm cho thuật toán chạy nhanh hơn nhiều.

PHẦN 3: THUẬT TOÁN Knuth-Morris-Pratt(KMP)
3.1 Tư tưởng thuật toán:
Ý tưởng cơ bản của thuật toán Knuth-Morris-Pratt(KMP) là khi phát hiện ra có sự
không khớp giữa kí tự T[i] và P[j] ta sẽ dựa vào các ký tự trong mẫu đã biết trước để
dịch chuyển sao cho P[r] nào đó khớp với T[i] (P[r]=T[i]) quá trình này sẽ tạo ra bước
dịch chuyển i >= 1 ( =1 khi T[i]=P[j-1]). Và lặp lại quá trình này đến khi tìm được mẫu P
trong T hoặc khi hết mảng T.

Học viên: Nguyễn Tuấn Tùng


6


Pattern Matching in String
Ví dụ 2: nếu mẫu có dạng là một xâu nhị phân có dạng đặc biệt là abbbbbbb ( ký
tự đầu tiên của mẫu chỉ xuất hiện 1 lần). Khi đó giả sử có 1 khởi đầu sai dài i ký tự (tức
là i ký tự đầu tiên của mẫu là khớp với một đoạn nào đó trong văn bản T). Như vậy nếu
ký tự thứ i+1 là không khớp thì ta biết rằng i ký tự trước trong mẫu đã khớp nhau rồi.
Điều đó có nghĩa là i ký tự này có dạng ở cả trong mẫu lẫn văn bản. Môt điều hiển nhiên
là ta không phải so sánh ký tự thứ nhất của mẫu P[1] với i-1 ký tự tiếp theo trong văn
bản, hay nói cách khác dịch chuyển mẫu sang i đơn vị gán lại (gán lại j=1 còn i vẫn giữ
nguyên). Để so sánh kí tự đầu tiên của mẫu với ký tự thứ i trong văn bản.
Ví dụ trên chỉ là trường hợp đặc biệt, trên thực tế ta hay gặp trường hợp ở ví dụ 1
ở trên, cần xây dựng bước nhảy thích hợp khi xảy ra sự không so khớp dựa vào mẫu đã
biết trước. Thuật toán KMP là sự tổng quá hóa cho tư tưởng xây dựng bước nhảy theo ý
tưởng này.
T:
I
J

A B C A B C D A B A B C D A B C D A B D E
1 2 3 4
1 2 3 4

P:

A B C D A B D

T:
I

J

A B C A B C D A B A B C D A B C D A B D E
4 5 6 7 8 9 10
1 2 3 4 5 6 7

P:

A B C D A B D

Học viên: Nguyễn Tuấn Tùng

7


Pattern Matching in String

Thuật toán:
a. Xây dựng mảng tiền tố Next[1..m]:
Đầu tiên xây dựng bước nhảy theo mẫu P đã biết. Quá trình này được gọi là xây dựng
mảng tiền tố Next[1..m] để dự phòng bước nhảy khi xảy ra sự không ăn khớp của mẫu P
với văn bản T.
Cần dịch chuyển một bản sao k-1 ký tự đầu tiên của mẫu trên chính nó từ trái sang
phải; bắt đầu từ ký tự đầu tiên của bản sao trên ký tự thứ hai của mẫu và ngừng lại khi
các ký tự các khớp nhau, hay không có ký tự nào khớp nhau cả. Khoảng cách để dự
phòng trong mẫu next[k] được xác định chính xác là cộng 1 với số các ký tự gối khớp
nhau. Đặc biệt là một số k>1 thì giá trị của Next[k] là số r lớn nhất mà nhỏ hơn k sao
cho r-1 ký tự đầu tiên của bản sao khớp với k-1 ký tự cuối cùng trong j-1 ký tự đầu tiên
trong mẫu, chúng ta cũng định nghĩa Next[1] = 0.
Ta có thuật toán tính mảng Next như sau:

Next[1] = 0;
For(k=1 ; k<=m; k++)
t=Next[k];
while((t>0 &(P[t]!=P[k])
t= Next[t];
Next[k+1]=t+1;
Ví dụ Xây dựng mảng Next[1..m] cho mẫu P= “ABCDABD”
m=7
Bước
KT
1
2

k t=Next[k] j=0 P[t] so với P[k]
1 0
1 1
Đ
2 1
S
≠
2 0
Đ
3
3 1
S
≠
3 0
Đ
4
4 1

S
≠
4 0
Đ
5
5 1
S
=
6
6 2
S
=
Kết quả mảng Next[k] là:
k
P
Next [k]

Học viên: Nguyễn Tuấn Tùng

1
A
0

2
B
1

8

3

C
1

Công việc

Next[k+1]
Next[1]=0
Next[2]=1

k=2; t=1
t=0;
k=3;t=1
t=0;
k=4;t=1
t=0
k=5;t=1
k=6;t=2
k=7;t=3

4
D
1

5
A
1

Next[3]=1
Next[4]=1
Next[5]=1

Next[6]=2
Next[7]=3

6
B
2

7
D
3


Pattern Matching in String
Đánh giá thời gian giải thuật tính mảng tiền tố Next[]:
Vòng lặp thực hiện đúng m bước lặp,việc gán giá trị trước đó chỉ thực hiện 1 lần .
Vì vậy thuật toán sinh mảng tiền tố Next[..] sẽ có độ phức tạp là O(m).
b. Thuật toán tìm vị trí mẫu P trong T với KMP:
Input: chuỗi mẫu P và chuỗi văn bản gốc T, next là mảng tiền tố lưu khoảng dự phòng
cho bước nhảy.
Output: vị trí tìm thấy của sâu P trong chuỗi văn bản T, nếu vị trí >n thì không tìm
thấy.
input: P[1…m], T[1…n];
Output: i0= (if P  T[i0……. i0+m-1] , i0 ≥ 1, otherwise i0=0
1. k:=1;j:=1;
2. while(j<=n &k<=m)
if ((k=0)|| (T[j]=P[k]) ) { j++; k++; }
else
k=Next(k);
3. if(k>m) i0 :=i
else

i0 :=0
Mô tả thuật toán:
 m: Chiều dài mẫu P
 n: Chiều dài văn bản T.
 j,k là hai chỉ sổ trỏ tương tứng trên văn bản T và mẫu P.
 Lặp lại quá trình tìm kiếm cho tới khi tìm thấy
 Nếu k= hoặc hai kí tự tương ứng còn bằng nhau(T[j]=P[k]) thì tiếp tục so sánh
tiếp (k=k+1,j=j+1)
 Nếu thấy sự không so khớp thì xác định bước nhảy bằng mảng Next(k=Next[k]).
 Nếu k vượt quá m(k>m) đã tìm thấy mẫu P trong văn bản T tại vị trí j-m


Ngược lại không tim thấy trả về vị trí i.

3.2 Ví dụ minh họa thuật toán:
Mảng Next[k] :
k
P
Next [k]

Học viên: Nguyễn Tuấn Tùng

1
A
0

2
B
1


3
C
1

9

4
D
1

5
A
1

6
B
2

7
D
3

8
1


Pattern Matching in String
k=1, j=1,m=7, n=21
T[1]=P[1], k=k+1, j=j+1
T:

J
K

A B C A B C D A B A B C D A B C D A B D E
1 2
1 2

P:

A B C D A B D

T[2]=P[2], k=k+1,j=j+1
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
1 2 3
1 2 3

P:

A B C D A B D

T[3]=P[3], k=k+1, j=j+1
T:
J
K

A B C A B C D A B A B C D A B C D A B D E

1 2 3 4
1 2 3 4

P:

A B C D A B D

T[4]≠P[4],k≠0: k=Next[k]=Next[4]=1
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
4
1

P:

A B C D A B D

T[4]=P[1], k=k+1, j=j+1
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
4 5
1 2

P:


A B C D A B D

T[5]=P[2], i=i+1, j=j+1
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
4 5 6
1 2 3

P:

A B C D A B D

T[6]=P[3], k=k+1, j=j+1
T:
J
K
P:

A B C A B C D A B A B C D A B C D A B D E
4 5 6 7
1 2 3 4
A B C D A B D

Học viên: Nguyễn Tuấn Tùng

10



Pattern Matching in String
T[7]=P[4], k=k+1, j=j+1
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
4 5 6 7 8
1 2 3 4 5

P:

A B C D A B D

T[8]=P[5], k=k+1, j=j+1
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
4 5 6 7 8 9
1 2 3 4 5 6

P:

A B C D A B D

T[9]=P[6], k=k+1, j=j+1

T:
J
K
P:

A B C A B C D A B A B C D A B C D A B D E
4 5 6 7 8 9 10
1 2 3 4 5 6 7
A B C D A B D

T[10]≠P[7], k=Next[k]=Next[7]=3
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
10
3

P:

A B C D A B D

T[10]≠P[3],k=Next[k]=Next[3]=1
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
10

1

P:

A B C D A B D

T[10]=P[1], k=k+1,j=j+1

T:
J
K

A B C A B C D A B A B C D A B C D A B D E
10 11
1 2

P:

Học viên: Nguyễn Tuấn Tùng

A B C D A B D

11


Pattern Matching in String
T[11]=P[2], k=k+1,j=j+1
T:
J
K


A B C A B C D A B A B C D A B C D A B D E
10 11 12
1 2 3

P:

A B C D A B D

T[12]=P[3], k=k+1,j=j+1
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
10 11 12 13
1 2 3 4

P:

A B C D A B D

T[13]=P[4], k=k+1,j=j+1
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
10 11 12 13 14
1 2 3 4 5


P:

A B C D A B D

T[14]=P[5, k=k+1, j=j+1
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
10 11 12 13 14 15
1 2 3 4 5 6

P:

A B C D A B D

T[15]=P[6], k=k+1,j=j+1
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
10 11 12 13 14 15 16
1 2 3 4 5 6 7

P:

A B C D A B D


T[16]≠P[7],k=Next[k]=Next[7]=3
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
16
3

P:

Học viên: Nguyễn Tuấn Tùng

A B C D A B D

12


Pattern Matching in String
T[16]=P[3], k=k+1,j=j+1
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
16 17
3 4

P:


A B C D A B D

T[17]=P[4], k=k+1,j=j+1
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
16 17 18
3 4 5

P:

A B C D A B D

T[18]=P[5], k=k+1,j=j+1
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
16 17 18 19
3 4 5 6

P:

A B C D A B D

T[19]=P[6], k=k+1,j=j+1

T:
J
K

A B C A B C D A B A B C D A B C D A B D E
16 17 18 19 20
3 4 5 6 7

P:

A B C D A B D

T[20]=P[7], k=k+1,j=j+1
T:
J
K

A B C A B C D A B A B C D A B C D A B D E
16 17 18 19 20 21
3 4 5 6 7 8

P:

A B C D A B D

j>m dừng. Tìm thấy.
output: ví trí j-m=21-7=14

Học viên: Nguyễn Tuấn Tùng


13


Pattern Matching in String
3.3 Đánh giá thời gian chạy của giải thuật KMP:
- Thời gian thực hiện mảng tiền tố Next là : O(m)- theo đánh giá ở trên.
- Trong trường hợp xấu nhất, không tìm thấy mẫu P thì vòng lặp phải thực hiện đúng
n bước lặp.
Thời gian chạy của vòng lặp tìm kiếm sẽ là: O(n).
Độ phức tạp của giải thuật KMP sẽ là O(m+n) tốt hơn so với giải thuật thông thường
với độ phức tạp là O(m.n)

Học viên: Nguyễn Tuấn Tùng

14


Pattern Matching in String

PHẦN 4: KẾT LUẬN
Mỗi thuật toán có ưu điểm riêng, thuật toán KMP là tốt khi các mẫu có tính tự lặp lại
cao. Nếu khuôn mẫu P tương đối dài và bảng chữ cái lớn một cách hiệu quả ta nên
sử dụng thuật toán Boyer-Moore. Trong một số trường hợp thì thuật toán KMP trình
bày trong báo cáo này chưa được bước nhảy tối ưu.

Học viên: Nguyễn Tuấn Tùng

15