- 1 -
Số hóa bởi Trung tâm Học liệu ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG ĐỖ QUỲNH ANH

NGHIÊN CỨU THUẬT TOÁN KNUTH-MORRIS-PRATT
VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
1.5.5.3. Độ tƣơng tự giữa hai xâu 19
1.5. Một số thuật toán so mẫu 20
1.5.1. Thuật toán Brute Force 20
1.5.2. Thuật toán Karp-Rabin 21
1.5.3. Thuật toán BM ( Boyer- Moor) 24
1.5.4. Các thuật toán khác 27
1.6. Khớp chuỗi với otomat hữu hạn 28
1.6.1. Otomat hữu hạn 28
1.6.1.1. Ôtômát hữu hạn đơn định DFA 29
1.6.1.2. Ôtômát hữu hạn không đơn định NFA 33
1.6.2. Otomat khớp chuỗi 36
1.6.2.1. Giới thiệu 36
1.6.2.2. Thuật toán xây dựng Otomat so khớp chuỗi 38
1.7. Kết luận chƣơng 40
CHƢƠNG 2. THUẬT TOÁN SO KHỚP CHUỖI KNUTH-MORRIS-PRATT 41
2.1. Thuật toán KMP 41
- 3 -
Số hóa bởi Trung tâm Học liệu 2.1.1. Giới thiệu thuật toán 41
2.1.2. Bảng so sánh một phần 45
2.1.3. Độ phức tạp của thuật toán KMP 47
2.2. Thuật toán KMP mờ 48
2.2.1. Otomat so mẫu 48
2.2.2. Thuật toán 49
2.2.2.1 Thuật toán tạo lập TFuzz 49
2.2.2.2. Thuật toán tìm kiếm mẫu dựa vào bảng TFuzz 51
2.2.3. So sánh KMP và thuật toán KMP mờ 52
2.3. Thuật toán KMP - BM mờ 53

TÀI LIỆU THAM KHẢO 76

- 5 -
Số hóa bởi Trung tâm Học liệu DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
BM
Thuật toán Boyer - Moore
DFA
Deterministic Finite Automata - Ôtômát hữu hạn đơn định
DOC
Document
FA
Finite Automata - Ôtômát hữu hạn
HTML
HyperText Markup Language
IDF
Inverse document frequency - Tần suất tài liệu ngƣợc
KMP
KNUTH-MORRIS-PRATT
LAN
Local area network
NFA
Nondeterministic Finite Automata - Ôtômát hữu hạn không đơn định
TF
Term frequency - Tần suất từ

- 6 -
Số hóa bởi Trung tâm Học liệu

- 7 -
Số hóa bởi Trung tâm Học liệu
MỞ ĐẦU
1. Lý do chọn đề tài
Máy tính ngày nay đã đƣợc sử dụng trong hầu hết các lĩnh vực và đã góp
phần quan trọng vào việc thúc đẩy sự phát triển kinh tế, xã hội, khoa học kỹ
thuật, … Máy tính ra đời nhằm phục vụ cho những mục đích nhất định của con
ngƣời. Với tất cả sự xử lý của máy tính để lấy thông tin hữu ích và trong quá
trình xử lí đó một vấn đề đặc biệt quan trọng là tìm kiếm thông tin với khối
lƣợng lớn, độ chính xác cao, thời gian nhanh nhất.
Cùng với sự phổ biến của công nghệ thông tin, số lƣợng các tài liệu điện
tử cũng gia tăng từng ngày. Đến nay, số lƣợng các tài liệu đƣợc lƣu trữ lên đến
hàng tỷ trang. Trong khi đó, nhu cầu khai thác trong kho tài liệu khổng lồ này để
tìm kiếm những thông tin cần thiết đang là nhu cầu thƣờng ngày và thiết thực
của ngƣời sử dụng. Tuy nhiên, một trong những khó khăn con ngƣời gặp phải
trong việc khai thác thông tin là khả năng tìm chính xác thông tin họ cần trong
kho tài liệu. Để trợ giúp công việc này, các hệ thống tìm kiếm đã lần lƣợt đƣợc
phát triển nhằm phục vụ cho nhu cầu tìm kiếm của ngƣời sử dụng.
Những hệ thống tìm kiếm bắt đầu phát triển và đƣa vào ứng dụng, phổ
biến là các hệ thống tìm kiếm theo từ khóa. Nhiều hệ thống hoạt động hiệu quả
trên Internet nhƣ Google, Bing, Yahoo!… Tuy nhiên, phần lớn các công cụ tìm
kiếm này là những sản phẩm thƣơng mại và mã nguồn đƣợc giữ bí mật. Hoặc
các hệ thống tìm kiếm trên máy cá nhân nhƣ Windows Search, Google
Desktop… đã đáp ứng phần nào nhu cầu của ngƣời sử dụng, miễn phí cho cá
nhân, tuy nhiên cũng chỉ đáp ứng đƣợc trên phạm vi nhỏ và mới chỉ dừng lại ở
mức độ tìm kiếm từ khóa theo tiêu đề và phần tóm tắt.
Có một cách tiếp cận hiệu quả để giải quyết vấn đề này là thực hiện việc

- 9 -
Số hóa bởi Trung tâm Học liệu khai phá dữ liệu, đặc biệt các kết quả nghiên cứu liên quan đến thuật toán tìm kiếm
thông tin.
Thực nghiệm thuật toán tìm kiếm KMP với dữ liệu mẫu. Nhận xét, đánh
giá kết quả thử nghiệm.
6. Ý nghĩa khoa học của đề tài
Luận văn nghiên cứu kỹ thuật, thuật toán tìm kiếm thông tin là cơ sở hỗ
trợ cho công tác dự báo, lập kế hoạch, quy hoạch, phân tích dữ liệu quản lý,
chuyên môn, nghiệp vụ. - 10 -
Số hóa bởi Trung tâm Học liệu CHƢƠNG 1. SO KHỚP CHUỖI
1.1. Khái niệm so khớp chuỗi
So khớp chuỗi là một kỹ thuật đóng vai trò nền tảng trong lĩnh vực xử lý
văn bản. Hầu nhƣ tất cả các trình soạn thoải và xử lý văn bản đều cần phải có
một cơ chế để so khớp các chuỗi trong tài liệu hiện tại. Việc tích hợp các thuật
toán so khớp chuỗi là một trong những khâu cơ bản đƣợc sử dụng trong việc
triển khai phần mềm và đƣợc thực hiện trên hầu hết các hệ điều hành.
Mặc dù hiện nay dữ liệu đƣợc lƣu trữ dƣới nhiều hình thức khác nhau,
nhƣng văn bản vẫn là hình thức chủ yếu để lƣu trữ và trao đổi thông tin. Trong
nhiều lĩnh vực nhƣ so khớp, trích chọn thông tin, tin sinh học…, một lƣợng lớn
dữ liệu thƣờng đƣợc lƣu trữ trong các tập tin tuyến tính. Hơn nữa khối lƣợng dữ
liệu thu thập đƣợc tăng lên rất nhanh nên đòi hỏi phải có các thuật toán xử lý và

lệ với (M+N) trong trƣờng hợp xấu nhất.
D.E.Knuth và V.R.Pratt đã kiên trì theo đuổi kiến trúc mà Cook đã dùng
để chứng minh cho định lý của ông và nhận đƣợc một thuật toán tƣơng đối đơn
giản. Đồng thời J.H.Morris cũng khám phá ra thuật toán này.
Knuth, Morris, Pratt đã không giới thiệu thuật này của họ cho đến năm
1976, và trong thời gian này R.S.Boyer và J.S.Moore đã khám phá ra một thuật toán
nhanh hơn nhiều.
Tháng 6 – 1975, Alfred V. Aho và Margret J. Corasick đã giới thiệu thuật
toán so khớp chuỗi đa mẫu Aho Corasick trong tài liệu “Communications of the
ACM 18”.
Năm 1980, Nigel Horspool đã giới thiệu thuật toán so khớp chuỗi tƣơng
tự thuật toán KMP, nhƣng đảo ngƣợc thứ tự so sánh trong tài liệu Software -
Practice & Experience, 10(6):501-506.
Tháng 3 - 1987, R.M.Karp và M.O.Rabin đã giới thiệu thuật toán đơn
giản gần nhƣ thuật toán Brute Force có thời gian thực thi tỉ lệ với m+n trong tài
liệu IBM J. Res develop – vol 31 no.2.

- 12 -
Số hóa bởi Trung tâm Học liệu
1.3. Các cách tiếp cận
Có 4 cách tiếp cận chính của các thuật toán so khớp chuỗi:
Thuật toán cổ điển: là các thuật toán chủ yếu dựa vào sự so sánh
giữa các ký tự. Các thuật toán điển hình bao gồm Brute Force,
Naïve,…
Thuật toán máy tự động hậu tố: là các thuật toán sử dụng cấu trúc
dữ liệu hậu tố tự động để nhận ra tất cả các hậu tố của mẫu. Các
thuật toán điển hình bao gồm Knuth – Morris – Pratt, Boyer –

mềm độc hại.
Trong lĩnh vực an toàn mạng và an toàn thông tin….
1.5. Các dạng so khớp chuỗi
Phân loại các thuật toán so khớp dựa trên các đặc tính của mẫu ta có các
dạng: so khớp đơn mẫu, so khớp đa mẫu (mẫu là tập các xâu), so khớp mẫu mở
rộng, so khớp biểu thức chính qui với hai hƣớng tiếp cận là so khớp chính xác
và xấp xỉ.
1.5.1. So khớp đơn mẫu
Cho xâu mẫu P dộ dài m, P = P
1

P
2…

P
m
, và xâu độ dài n, S = S
1
S
2…
S
n
(S thƣờng dài, là một văn bản) trên cùng một bảng chữ A. Tìm tất cả các xuất
hiện của xâu P trong S.
Trong các thuật toán so mẫu thƣờng sử dụng các khái niệm: Khúc đầu,
khúc cuối, khúc con hay xâu con của một xâu, đƣợc định nghĩa nhƣ sau: Cho 3
xâu x, y, z. Ta nói x là khúc đầu (prefix) của xâu xy, là khúc cuối (suffix) của
xâu yx và là khúc con hay xâu con (factor) của xâu yxz.
- 14 -
Số hóa bởi Trung tâm Học liệu

, w
2
,….,w
k
và xâu vào S =
- 15 -
Số hóa bởi Trung tâm Học liệu S
1
S
2
…S
n
trên cùng bảng chữ A. Tìm sự xuất hiện của các từ khoá w
i
trong S.
Một cách đơn giản để tìm nhiều từ khoá trong một xâu đích là sử dụng
thuật toán so đơn mẫu nhanh nhất đối với mỗi từ khoá. Rõ ràng phƣơng pháp
này không hiệu quả khi số lƣợng từ khoá lớn.
Cả ba tiếp cận tìm đơn mẫu ở trên đều đƣợc mở rộng cho tìm đa mẫu. Hai
điển hình theo tiếp cận thứ nhất là thuật toán nổi tiếng Aho- Corasisk, có tốc độ
cải thiện đáng kể khi số từ khoá nhiều và thuật toán Multiple Shift- And, đƣợc
sử dụng hiệu quả khi tổng độ dài của mẫu P rất nhỏ 2 .
Theo tiếp cận thứ hai có thuật toán nổi tiếng Commentz - Walter, trong đó
kết hợp ý tƣởng của Boyer - Moore và Aho- Corasisk , nhanh về lý thuyết, song
lại không hiệu quả trong thực hành. Một mở rộng của thuật toán Horspool là Set
Horspool. Cuối cùng là thuật toán Wu-Manber, một phƣơng pháp pha trộn giữa
tiếp cận so khớp hậu tố (suffix search approach) và một kiểu hàm băm, đƣợc

các ký tự. Thông thƣờng, các ký tự của cả mẫu so khớp và đoạn văn bản gốc đều
nằm trong Σ. Tập Σ tùy từng ứng dụng cụ thể có thể là bảng chữ cái tiếng Anh từ
A đến Z thông thƣờng, cũng có thể là một tập nhị phân chỉ gồm hai phần tử 0 và
1 (Σ = {0,1}) hay có thể là tập các ký tự DNA trong sinh học (Σ = {A,C,G,T}).
Phƣơng pháp đơn giản nhất là lần lƣợt xét từng vị trí i trong xâu ký tự gốc
từ 1 đến n-m+1, so sánh T[i…(i+m-1)] với P[1 m] bằng cách xét từng cặp ký tự
một và đƣa ra kết quả so khớp. Ngƣời ta còn gọi phƣơng pháp này là cách tiếp
cận ngây thơ (Naïve string search). Dƣới đây là thủ tục đặc tả của phƣơng pháp này:
NAÏVE_STRING_MATCHER (T, P)
1. n ← length [T]
2. m ← length [P]
3. for s ← 1 to n-m+1 do
4. j ← 1
5. while j ≤ m and T[s + j] = P[j] do
6. j ← j +1
- 17 -
Số hóa bởi Trung tâm Học liệu 7. If j > m then
8. return s // s là vị trí tìm được
9. return false. // không có vị trí nào thỏa mãn
Độ phức tạp trung bình của thuật toán là O(n+m), nhƣng trong trƣờng hợp
xấu nhất độ phức tạp là O(n.m), ví dụ nhƣ so khớp mẫu “”aaaab” trong xâu
“aaaaaaaaab”.

1.5.5. So khớp xấp xỉ
1.5.5.1. Phát biểu bài toán
So mẫu xấp xỉ là bài toán tìm sự xuất hiện của một mẫu trong văn bản,
trong đó sự “khớp” giữa mẫu và xuất hiện của nó có thể chấp nhận k “lỗi” (k là

2) Các thuật toán sử dụng otomat so khớp: Trƣớc tiên xây dựng một hàm
của mẫu P và số lỗi k, sau đó tạo otomat đa định hữu hạn. Đây là hƣớng tiếp cận
đƣợc quan tâm nhiều vì có độ phức tạp thời gian trong trƣờng hợp xấu nhất là
O(n) (tuy nhiên đòi hỏi độ phức tạp không gian lớn hơn).
3) Các thuật toán sử dụng cơ chế song song bit: cách tiếp cận này cho ra
rất nhiều thuật toán hiệu quả nhờ khai thác bản chất song song của các phép toán
bit trên một từ máy trong bộ vi xử lý. Nói chung song song bit đƣợc dùng để
song song hoá các kỹ thuật khác, nhƣ tạo otomat đa định, lập ma trận quy hoạch
động. Nói chung kỹ thuật này làm việc khá tốt với mẫu ngắn và tăng tốc đáng kể
so với những cài đặt không tận dụng khả năng song song của thanh ghi. Một số
thuật toán dùng cơ chế song song bit là BPR và BPD để tái tạo một otomat đa
định hữu hạn và BDM để tái tạo các thuật toán quy hoạch động.
4) Các thuật toán sử dụng cơ chế lọc: Cố gắng thu hẹp không gian so
khớp của bài toán bằng cách loại đi các văn bản mà chắc chắn không chứa một
đoạn nào “khớp” với mẫu. Nói chung, phƣơng pháp này đạt đƣợc bằng cách áp
- 19 -
Số hóa bởi Trung tâm Học liệu dụng kỹ thuật so mẫu chính xác cho các mẫu nhỏ của mẫu. Hai thuật toán hiệu
quả nhất theo tiếp cận này là PEX và ABNDM. Trong PEX, mẫu đƣợc chia
thành k + 1 đoạn và sắp xếp để so khớp đa mẫu trên các đoạn này, vì ít nhất một
đoạn phải có mặt trong một xuất hiện bất kỳ. Thuật toán ABNDM là một mở
rộng của thuật toán BNDM, trong đó tái tạo otomat đa định hữu hạn cho so khớp
xấp xỉ. Nói chung, các thuật toán sử dụng cơ chế lọc làm việc tốt hơn tỷ lệ k/m
nhỏ. Đối với trƣờng hợp tỷ lệ k/m lớn, các thuật toán sử dụng cơ chế song song
bit đƣợc đánh giá tốt hơn.
Đối với bài toán so khớp đa mẫu cũng đã có một số phát triển theo hƣớng
xấp xỉ. Thuật toán MultiHash chỉ làm việc với k = 1 song rất hiệu quả khi số
lƣợng mẫu lớn; MultiPEX là thuật toán hiệu quả nhất khi tỷ lệ k/m nhỏ; Multi

2) Xâu con chung dài nhất (hay khúc con chung dài nhất): Một xâu w là
xâu con hay khúc con (substring or factor) của xâu x nếu x = uwv (u, v có thê
rỗng). Xâu w là khúc con chung của hai xâu x, y nếu w đồng thời là khúc con
của x và y. Khúc con chung dài nhất của hai xâu x và y, ký hiệu LCF (x,y), là một
khúc con có độ dài lớn nhất.
3) Dãy con chung dài nhất: Một dãy con của xâu x là một dãy các ký tự có
đƣợc bằng cách xoá đi không, một hoặc nhiều ký tự từ x. Dãy con chung của
hai xâu x, y là một dãy con của cả hai xâu x và y. Dãy con chung của x và y có
độ dài lớn nhất đƣợc gọi là dãy con chung dài nhất LCS (x,y). Có thể dùng độ
dài dãy con chung của hai xâu x, y để tính khoảng cách Levenstein giữa x và y
theo công thức:
LevDistance (x,y) = m + n - 2 length(LCS( x,y))
1.5. Một số thuật toán so mẫu
1.5.1. Thuật toán Brute Force
Thuật toán Brute Force thử kiểm tra tất cả các vị trí trên văn bản từ 1 cho
đến n-m+1. Sau mỗi lần thử thuật toán brute force dịch mẫu sang phải một ký tự
- 21 -
Số hóa bởi Trung tâm Học liệu cho đến khi kiểm tra hết văn bản. Thuật toán không cần công việc chuẩn bị cũng
nhƣ các mảng phụ cho quá trình tìm kiếm. Độ phức tạp tính toán của thuật toán
này là O(n*m).
function IsMatch(const X: string; m: integer;
const Y: string; p: integer): boolean;
var i: integer;
begin
IsMatch := false;
Dec(p);
for i := 1 to m do

mod có tốc độ rất nhanh.
Việc chuẩn bị trong thuật toán Karp-Rabin có độ phức tạp O(m). Tuy vậy
thời gian tìm kiếm lại tỉ lệ với O(m*n) vì có thể có nhiều trƣờng hợp hàm băm
của chúng ta bị lừa và không phát huy tác dụng. Nhƣng đó chỉ là những trƣờng
hợp đặc biệt, thời gian tính toán của thuật toán KR trong thực tế thƣờng tỉ lệ với
O(n+m). Hơn nữa thuật toán KR có thể dễ dàng mở rộng cho các mẫu, văn bản
dạng 2 chiều, do đó khiến cho nó trở nên hữu ích hơn so với các thuật toán còn
lại trong việc xử lý ảnh.
procedure KR(const X: string; m: integer;
const Y: string; n: integer);
var
dM, hx, hy: longint;
i, j: integer;
begin
dM := 1;
for i := 1 to m - 1 do dM := dM shl 1;
hx := 0;
hy := 0;
for i := 1 to m do
begin
hx := (hx shl 1) + Ord(X);
hy := (hy shl 1) + Ord(Y);
end;
- 23 -
Số hóa bởi Trung tâm Học liệu j := 1;
while j <= n - m do
begin

thể an toàn trƣợt cửa sổ sang phải qua m vị trí trên S và bắt đầu quá trình tìm
kiếm mới bởi việc so sánh P
m
và S
k+ m
.
Giả sử tại một thời điểm đang xét cửa sổ S
k - m+ 1
S
k - m + 2
S
k
và bắt đầu
so sánh P
m
với S
k
.
(1) Giả sử P
m
S
k
có hai khả năng:
Nếu vị trí xuất hiện phải nhất của ký tự S
k
trong P là m - g, ta có thể
dịch mẫu P sang phải g vị trí sao cho P
m-g
dóng thẳng với S
k

. Nếu
P
i-g
nằm bên phải của P
i
(khi g < 0) thì mẫu P chỉ dịch sang phải 1
vị trí.
Giả sử suf
i
(P) là một xâu con của P
i+1-g
P
i+2-g
P
m-g
và P
i-g
P
i
(nếu
có nhiều xuất hiện nhƣ vậy của suf
i
(P) thì chọn vị trí phải nhất).
Khi đó sẽ dịch mẫu P sang phải một đoạn dài hơn so với trƣờng
hợp (2a) sao cho khúc P
i+1-g
P
i+2-g
P
m-g

Bảng d
2
bao hàm trƣờng hợp (2b): Với mỗi i, 1 i m, d
2
i đƣợc xác
định là: d
2
i = min g + m - i| g 1 và (g i hoặc P
i-g
P
i
) và ((g k hoặc P
k-g

= P
k
) với i k m)
Có nhiều cách tính toán bảng d
2
đƣợc đƣa ra. Thuật toán dƣới đây tính
bảng dịch chuyển d
2
là của Knuth, có sự sửa đổi của Mehlhorn. Thuật toán sử
dụng hàm f có tính chất f[m] = m+1 và với 1 j < m, f j = min i j < i < m và
P
i+1
P
i+2
P
m