Một họ thuật toán sánh mẫu Wu-Manber và thực nghiệm
Một họ thuật toán sánh mẫu Wu-Manber và thực nghiệm
Xem bên trong

Một họ thuật toán sánh mẫu Wu-Manber và thực nghiệm

51 tr. + CD-ROM
Luận văn ThS. Hệ thống thông tin — Trường Đại học Công nghệ. Đại học Quốc gia Hà Nội, 2012
Chương 1: Bài toán và thuật toán sánh mẫu: giới thiệu chung về bài toán sánh mẫu, cho thấy một lượng lớn thuật toán sánh mẫu đã được đề xuất. Các thuật toán sánh mẫu được chia ra hai lớp chính là lớp thuật toán chính xác và lớp thuật toán tương tự; giới thiệu một số thuật toán sánh mẫu điển hình nhất [CL00]. Chương 2: Họ thuật toán Wu – Manber: Giới thiệu thuật toán sánh mẫu văn bản chính xác WM được Sun Wu và Udi Manber công bố vào năm 1994 [WM94] với ý tưởng kết hợp cách thức nhảy của thuật toán BM do R. S. Boyer và J. S. Moore [BM77] và hàm băm. Một số phiên bản nâng cấp thuật toán WM được phân tích trong chương này [SWG06, DX08, ZCP09, ZCP09a]. Chương 3: Thực nghiệm: sử dụng công cụ phần mềm Agrep để thi hành thực nghiệm thuật toán sánh mẫu WM; thực nghiệm sánh mẫu cho 60 cặp file (mẫu, văn bản). Thực nghiệm cho thấy công cụ Agrep thi hành thuật toán chính xác với thời gian nhanh
Electronic Resources

0.00

Tải về miễn phí bản đầy đủ PDF luận văn tại Link bản đầy đủ 1

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THỊ THÚY

MỘT HỌ THUẬT TOÁN SÁNH MẪU WU-MANBER
VÀ THỰC NGHIỆM

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

HÀ NỘI – 2012

ii

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THỊ THÚY

MỘT HỌ THUẬT TOÁN SÁNH MẪU WU-MANBER
VÀ THỰC NGHIỆM

Ngành : Công nghệ thông tin
Chuyên ngành : Hệ thống thông tin
Mã số : 60 48 05

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS Hà Quang Thụy

HÀ NỘI – 2012

v

MỤC LỤC
MỞ ĐẦU …………………………………………………………………………………………….. 1
CHƯƠNG 1: BÀI TOÁN VÀ THUẬT TOÁN SÁNH MẪU ………………………. 3
1.1. Giới thiệu về bài toán sánh mẫu……………………………………………………… 3
1.2. Phát biểu bài toán ………………………………………………………………………… 4
1.3. Một số thuật toán sánh mẫu cơ bản…………………………………………………. 5
1.3.1. Thuật toán Brute Force …………………………………………………………… 5
1.3.2. Thuật toán Knuth-Morris-Pratt ………………………………………………… 7
1.3.3. Thuật toán automat hữu hạn…………………………………………………….. 9
1.3.4. Thuật toán Boyer-Moore ………………………………………………………. 10
1.3.5. Thuật toán Karp-Rabin …………………………………………………………. 13
1.3.6. Các thuật toán khác………………………………………………………………. 14
CHƯƠNG 2: HỌ THUẬT TOÁN WM ………………………………………………….. 16
2.1. Thuật toán WM …………………………………………………………………………. 16
2.1.1. Tổng quan về thuật toán………………………………………………………… 16
2.1.2. Thuật toán…………………………………………………………………………… 17
2.1.2.1. Phác thảo của thuật toán………………………………………………….. 17
2.1.2.2. Giai đoạn tiền xử lý………………………………………………………… 18
2.1.2.3. Giai đoạn tìm kiếm mẫu………………………………………………….. 21
2.1.3. Phân tích thuật toán ……………………………………………………………… 22
2.2. Một thuật toán WM với bảng băm cô đọng…………………………………….. 25
2.2.1. Phác thảo của thuật toán ……………………………………………………….. 25
2.2.2. Cải tiến của thuật toán ………………………………………………………….. 26
2.3. Thuật toán WM đồng thời cao ……………………………………………………… 28
2.3.1. Cải tiến của thuật toán ………………………………………………………….. 28
2.3.2. Giai đoạn tiền xử lý và tìm mẫu của HCWM……………………………. 29
2.3.3. Ví dụ………………………………………………………………………………….. 30
2.4. Thuật toán WM sử dụng bảng tiền tố…………………………………………….. 34
2.4.1. Cải tiến của thuật toán ………………………………………………………….. 34
2.4.2. Giai đoạn tiền xử lý và tìm mẫu trong AFWM………………………….. 34
2.4.3.Ví dụ…………………………………………………………………………………… 35
CHƯƠNG 3: THỰC NGHIỆM……………………………………………………………… 38
3.1. Giới thiệu về agrep …………………………………………………………………….. 38
3.2. Các thuật toán sử dụng trong agrep……………………………………………….. 39
3.2.1. Thuật toán WM trong AGREP……………………………………………….. 39
3.2.2. Thuật toán sánh mẫu xấp xỉ …………………………………………………… 39
3.3. Cách sử dụng Agrep …………………………………………………………………… 41
3.4. Kết quả thực nghiệm…………………………………………………………………… 45
KẾT LUẬN………………………………………………………………………………………… 50
TÀI LIỆU THAM KHẢO…………………………………………………………………….. 51

vi

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT

AC Aho-Corasick
AFWM Address Filtering Based WM
Ba Baeza-Yates
BM Boyer-Moore
CW Commentz-Walter
DFA Deterministic Finite Automaton
HCWM High Concurrence WM
Ho Boyer-Moore-Horspool
Hu Hume
KMP Knuth-Morris-Pratt
KR Karp-Rabin
QS Quick Search
WM Wu-Manber

MỞ ĐẦU

Hiện nay, tìm kiếm thông tin là một trong các vấn đề nghiên cứu được
quan tâm nhiều nhất. Trong bối cảnh bùng nổ thông tin hiện nay, cần phải có các
công cụ tìm kiếm thông tin tự động để hỗ trợ người dùng. Để xây dựng được các
công cụ tìm kiếm tốt, chúng ta phải dựa vào các thuật toán tìm kiếm theo một
câu hỏi dưới dạng một xâu ký tự. Các thuật toán tìm kiếm xâu ký tự được sử
dụng rất nhiều trong các chương trình máy tính, đặt biệt là các thuật toán tìm
kiếm mẫu giải quyết bài toán tìm kiếm một đoạn văn bản (mẫu) trong các văn
bản (đích) thuộc một tập các văn bản của miền tìm kiếm. Bài toán nói trên được
gọi là bài toán sánh mẫu (pattern matching, còn được gọi là so mẫu).
Bài toán sánh mẫu không chỉ có trong miền dữ liệu văn bản mà còn có
trong các miền dữ liệu đa phương tiện khác (ảnh, video, âm thanh,…). Trên thực
tế có rất nhiều ứng dụng sánh mẫu như: cơ chế sánh mẫu của hệ điều hành
(chẳng hạn, lệnh grep, fgrep … trong hệ điều hành UNIX), cơ chế kiểm tra một
file nhiễm virus (sánh mẫu – xâu đặc tả virus – với nội dung file), máy tìm kiếm
(search engine) trên Internet, xác định mẫu gene bệnh xuất hiện trong đoạn gene
của người …
Trong thời đại bùng nổ thông tin với tốc độ lượng thông tin tăng gấp đôi
sau chu kỳ 18 tháng [CL00], dù cho tốc độ và khả năng lưu trữ của máy tính
tăng nhanh thì vấn đề nghiên cứu, phát triển nâng cao hiệu quả của các thuật
toán sánh mẫu luôn là chủ đề nghiên cứu thời sự. Nói riêng, thuật toán sánh mẫu
Wu-Manber do S. Wu và U. Manber công bố vào năm 1994 [WM94] tiếp tục có
nhiều phiên bản nâng cấp gần đây [SWG06, DX08, ZCP09, ZCP09a].
Chính vì thế, luận văn này định hướng nghiên cứu một số thuật toán sánh
mẫu văn bản, tập trung vào họ thuật toán Wu-Manber do họ thuật toán này tỏ ra
có nhiều ưu việt trong bài toán sánh mẫu. Nội dung chủ yếu của luận văn là
nghiên cứu họ thuật toán sánh mẫu văn bản Wu-Manber, phân tích chi tiết một
vài thuật toán trong họ nói trên [SWG06, DX08, ZCP09, ZCP09a], khai thác
công cụ để thực nghiệm thuật toán Wu-Manber (trong một số trường hợp, luận
văn sử dụng cách viết tắt là WM).

2

Nội dung luận văn gồm có phần mở đầu, 3 chương, phần kết luận, tài
liệu tham khảo và phụ lục.
Chương 1: Bài toán và thuật toán sánh mẫu
Chương này cung cấp một giới thiệu chung về bài toán sánh mẫu, cho
thấy một lượng lớn thuật toán sánh mẫu đã được đề xuất. Các thuật toán sánh
mẫu được chia ra hai lớp chính là lớp thuật toán chính xác và lớp thuật toán
tương tự. Luận văn giới thiệu một số thuật toán sánh mẫu điển hình nhất [CL00].
Chương 2: Họ thuật toán Wu – Manber
Giới thiệu thuật toán sánh mẫu văn bản chính xác WM được Sun Wu và
Udi Manber công bố vào năm 1994 [WM94] với ý tưởng kết hợp cách thức
nhảy của thuật toán BM do R. S. Boyer và J. S. Moore [BM77] và hàm băm.
Một số phiên bản nâng cấp thuật toán WM được phân tích trong chương này
[SWG06, DX08, ZCP09, ZCP09a].
Chương 3: Thực nghiệm
Luận văn sử dụng công cụ phần mềm Agrep để thi hành thực nghiệm
thuật toán sánh mẫu WM. Trong phần đầu của chương, luận văn trình bày một
số nội dung liên quan tới công cụ này, đặc biệt cách sử dụng Agrep thi hành
thuật toán WM. Luận văn đã thực nghiệm sánh mẫu cho 60 cặp file (mẫu, văn
bản). Thực nghiệm cho thấy công cụ Agrep thi hành thuật toán chính xác với
thời gian nhanh.

3

CHƯƠNG 1: BÀI TOÁN VÀ THUẬT TOÁN SÁNH MẪU

1.1. Giới thiệu về bài toán sánh mẫu
Kiểu dữ liệu văn bản (Text) là dạng trình bày thông tin gần gũi nhất với
con người, vì vậy, đây cũng là dạng trình bày thông tin số rất phổ biến. Chính vì
lẽ đó, bài toán tìm kiếm văn bản (text searching) là một trong những bài toán
quan trọng nhất trong hoạt động tìm kiếm thông tin của con người. Trong thời
đại ngày nay, văn bản số hóa đang tăng trưởng “bùng nổ” trong các cơ sở dữ liệu
trên Internet, dung lượng tăng gấp đôi sau mỗi chu kỳ 18 tháng [CL00]. Trong
bối cảnh đó, vấn đề tìm kiếm văn bản một cách tự động đã rất quan trọng thì lại
ngày càng quan trọng hơn.
Dạng phổ biến nhất của bài toán tìm kiếm văn bản là: Cho trước nguồn
tìm kiếm là một tập D các văn bản (hoặc là cơ sở dữ liệu văn bản, hoặc là tập
các văn bản trên Internet). Cho một câu hỏi dạng văn bản q (thường là một từ,
một xâu văn bản ngắn), hãy tìm tất cả các văn bản thuộc D mà có chứa q. Trong
nhiều trường hợp (chẳng hạn, tìm kiếm thông qua máy tìm kiếm) thì q còn được
gọi là “truy vấn” và bài toán còn có tên gọi là “tìm kiếm theo truy vấn”. Để tìm
được các văn bản có chứa văn bản truy vấn q, hệ thống tìm kiếm cần phải kiểm
tra văn bản truy vấn q có là một xâu con của các văn bản thuộc tập D hay không
(sánh mẫu) và đưa ra các văn bản đáp ứng. Trong nhiều trường hợp, bài toán còn
đòi hỏi tìm tất cả các vị trí của các xâu con trong văn bản trùng với q. Đồng
thời, điều kiện tìm kiếm có thể được làm “xấp xỉ” theo nghĩa văn bản kết quả có
thể không cần chứa q (không cần có một xâu con của văn bản trùng một cách
hoàn toàn chính xác với q) mà chỉ cần “liên quan” tới q (có xâu con trong văn
bản “xấp xỉ” q). Có thể thấy, các máy tìm kiếm sử dụng cả cơ chế tìm kiếm xấp
xỉ khi mà văn bản kết quả tìm kiếm không chứa hoàn toàn chính xác văn bản
truy vấn.
Thời gian gần đây, bài toán sánh mẫu càng trở nên quan trọng và được
quan tâm nhiều do sự tăng trưởng nhanh chóng của các hệ thống tìm kiếm thông
tin và các hệ thống sinh- tin học. Một lý do nữa, con người ngày nay không chỉ
đối mặt với một lượng thông tin khổng lồ mà còn đòi hỏi những yêu cầu tìm
kiếm ngày càng phức tạp. Các mẫu đưa vào không chỉ đơn thuần là một xâu ký
tự mà còn có thể chứa các ký tự thay thế, các khoảng trống và các biểu thức
chính quy. Sự “tìm thấy” không đơn giản là xuất hiện chính xác mẫu trong văn

4

bản mà còn cho phép “một xấp xỉ” giữa mẫu và xuất hiện của nó trong văn bản.
Từ đó, bên cạnh vấn đề kinh điển là “tìm kiếm chính xác”, nảy sinh một hướng
nghiên cứu là “sánh mẫu xấp xỉ / tìm kiếm xấp xỉ” (approximate matching /
approximate searching).
1.2. Phát biểu bài toán
Như đã giới thiệu, đối sánh mẫu là một bài toán cơ bản trong xử lý văn
bản; bài toán yêu cầu tìm ra một hoặc nhiều vị trí xuất hiện của mẫu P trên một
văn bản S. Mẫu P và văn bản S là các chuỗi có độ dài M và N (M ≤ N); P và S là
các xâu ký trên cùng một bảng chữ cái Σ có δ ký tự.
Bài toán sánh mẫu (chính xác) tổng quát được phát biểu như sau [CL00]:
“Cho mẫu P độ dài M và văn bản S độ dài N trên cùng bảng chữ A. Tìm
một (hoặc tất cả) các lần xuất hiện của mẫu P trong S”.
Sánh mẫu để tìm tất cả các lần xuất hiện của các chuỗi mẫu có thể được
thi hành bằng một lần quét duy nhất, diễn ra với nhiều lần thử trên các đoạn
khác nhau của văn bản. Mỗi lần thử chương trình sẽ kiểm tra sự giống nhau giữa
mẫu với cửa sổ hiện thời. Theo Christian Charras và Thierry Lecroq [CL00], độ
phức tạp của thuật toán tìm tất cả các lần xuất hiện của x trong y trong thời gian
O (M×N).
Trong bài toán tìm kiếm văn bản trên tập văn bản D, bài toán sánh mẫu
được thực hiện đối với mọi cặp gồm mẫu (truy vấn) q và mọi văn bản d ∈ D.
Trong trường hợp độ dài N của d rất lớn và số lượng văn bản trong D rất nhiều
(|D|>>1) thì thời gian tìm kiếm văn bản phù hợp với câu hỏi q sẽ là rất tốn kém.
Chính vì lý do đó, nghiên cứu đề xuất các thuật toán sánh mẫu mới, cải tiến các
thuật toán sánh mẫu sẵn có luôn là một chủ đề nghiên cứu được hết sức quan
tâm.
Thực tiễn cũng tồn tại nhiều tình huống tìm kiếm xấp xỉ trong đó cho
phép có sự “sai khác không đáng kể” giữa mẫu P và xâu con S’ của xâu S. Cũng
chính vì lý do đó, bài toán sánh mẫu xấp xỉ được đặt ra, trong đó, tìm một (hay
tất cả) các xâu con S’ của xâu S mà S’ “sai khác không đáng kể” với mẫu P
[WM92]. Tồn tại một số tiêu chí cho độ đo “sai khác không đáng kể”, chẳng hạn
như số lượng ký tự cùng vị trí trong hai xâu S’ và P là khác nhau chiếm tỷ lệ rất
nhỏ so với độ dài M của xâu P.
Thông thường, các thuật toán sánh mẫu làm việc với mẫu có độ dài ngắn
(M≤30), tuy nhiên trong thực tiễn, bài toán sánh mẫu có độ dài mẫu lên tới con

5

số hàng chục ngàn. Người ta gọi các bài toán sánh mẫu với mẫu dài như vậy là
bài toán sánh mẫu “nặng” để phân biệt với bài toán sánh mẫu “nhẹ” mà độ dài
mẫu không quá 30. Thực tiễn cũng chỉ ra rằng hầu hết các ứng dụng của sánh
mẫu là sánh mẫu nhẹ.
Luận văn này đề cập tới bài toán sánh mẫu chính xác và tập trung vào
sánh mẫu nhẹ.
1.3. Một số thuật toán sánh mẫu cơ bản
Theo Christian Charras và Thierry Lecroq [CL00], bốn cách tiếp cận chủ
yếu của các thuật toán sánh mẫu được phân loại theo thứ tự đối sánh các ký tự
của mẫu với văn bản: (1) tuần tự từ trái sang phải; (2) tuần tự từ phải sang trái;
(3) xác định giới hạn lý thuyết để đưa ra thứ tự đối sánh ký tự; (4) xác định thứ
tự theo quá trình thực hiện. Các tác giả cũng cho nhận định rằng nhóm thuật
toán sánh mẫu tiến hành theo thứ tự tuần tự từ phải sang trái thường cho hiệu
quả sánh mẫu tốt nhất trong thực tế.
Trong thập niên 1970, thuật toán sánh mẫu của A. V. Aho và M. J.
Corasick, 1975 [AC75] và thuật toán sánh mẫu của R. S. Boyer và J. S. Moore,
1977 [AC77] là hai trong số thuật toán điển hình nhất mà nhiều phiên bản thuật
toán sánh mẫu được phát triển dựa trên ý tưởng của các thuật toán này. Đặc biệt,
thuật toán Boyer-Moore vẫn còn thường xuyên áp dụng hiện nay. Dưới đây là
một số giới thiệu về một số thuật toán sánh mẫu cơ bản nhất. Trong [CL00],
Christian Charras và Thierry Lecroq giới thiệu khá cụ thể về các thuật toán này.
1.3.1. Thuật toán Brute Force
Đặc điểm chính thuật toán Brute Force là: không có giai đoạn tiền xử lý,
liên tục thêm không gian cần thiết, dịch chuyển cửa sổ sánh mẫu sang bên phải
1 vị trí, so sánh được thực hiện theo thứ tự bất kỳ, giai đoạn tìm kiếm có độ
phức tạp thời gian là O(M*N), số ký tự dự kiến cần so sánh là 2N.
Thuật toán Brute Force kiểm tra tất cả các vị trí trên văn bản từ 0 cho đến
N-M. Sau mỗi lần thử thuật toán Brute Force dịch mẫu sang phải một ký tự cho
đến khi kiểm tra hết văn bản.
Thuật toán Brute Force không cần giai đoạn tiền xử lý 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). Cụ thể quá trình sánh mẫu diễn ra như sau:

6

Lần kiểm tra thứ nhất

y G C A T C G C A G A G T A T A C A G T A C G
1 2 3 4
x G C A G A G A G

Dịch 1
Lần kiểm tra thứ hai

y G C A T C G C A G A G T A T A C A G T A C G
1

x G C A G A G A G

Dịch 1
Lần kiểm tra thứ ba

y G C A T C G C A G A G T A T A C A G T A C G
1

Dịch 1

Thuật toán Brute Force sẽ thực hiện 30 so sánh như vậy cho đến hết văn bản
Ví dụ:
TWO ROADS DIVERGED IN A YELLOW WOOD
ROADS
TWO ROADS DIVERGED IN A YELLOW WOOD
ROADS
TWO ROADS DIVERGED IN A YELLOW WOOD
ROADS
TWO ROADS DIVERGED IN A YELLOW WOOD
ROADS
TWO ROADS DIVERGED IN A YELLOW WOOD
ROADS

x G C A G A G A G

7

Việc tìm kiếm bằng Brute-Force có thể là rất chậm đối với một số mẫu nào
đó, ví dụ nếu xâu cần xét là một xâu nhị phân chỉ gồm hai ký tự thường xuất
hiện trong các ứng dụng xử lý ảnh và lập trình hệ thống.
1.3.2. Thuật toán Knuth-Morris-Pratt
Thuật toán Knuth-Morris-Pratt [CL00] có những đặc điểm chính sau:
thuật toán thực hiện so sánh từ trái qua phải, độ phức tạp về thời gian trong giai
đoạn tiền xử lý là O(M), độ phức tạp thời gian trong giai đoạn tìm mẫu là
O(M+N), trong quá trình sánh mẫu thuật toán thực hiện nhiều nhất 2N-1 lần so
sánh, giới hạn trì hoãn là logφ(M) với φ=
2
51+
Thuật toán Knuth-Morris-Pratt là thuật toán có độ phức tạp tuyến tính đầu
tiên được phát hiện ra, dựa trên thuật toán Brute Force với ý tưởng lợi dụng lại
những thông tin của lần thử trước cho lần sau. Trong thuật toán brute force vì
chỉ dịch cửa sổ đi một ký tự lên có đến M-1 ký tự của cửa sổ mới là những ký tự
của cửa sổ vừa xét. Trong đó có thể có rất nhiều ký tự đã được so sánh giống với
mẫu và bây giờ lại nằm trên cửa sổ mới nhưng được dịch đi về vị trí so sánh với
mẫu. Việc xử lý những ký tự này có thể được tính toán trước rồi lưu lại kết quả.
Nhờ đó lần thử sau có thể dịch đi được nhiều hơn một ký tự, và giảm số ký tự
phải so sánh lại.
Xét lần thử tại vị trí j, khi đó cửa sổ đang xét bao gồm các ký tự
y[j…j+m-1] giả sử sự khác biệt đầu tiên xảy ra giữa hai ký tự x[i] và y[j+i-1].
Khi đó x[1…i]=y[j…i+j-1]=u và a=x[i]≠y[i+j]=b. Với trường hợp này, dịch
cửa sổ phải thỏa mãn v là phần đầu của xâu x khớp với phần đuôi của xâu u trên
văn bản. Hơn nữa ký tự c ở ngay sau v trên mẫu phải khác với ký tự a. Trong
những đoạn như v thoả mãn các tính chất trên ta chỉ quan tâm đến đoạn có độ
dài lớn nhất.
j i+j
y u b

x u a

x v c

Dịch cửa sổ sao cho v phải khớp với u và c ≠ a

8

Thuật toán Knuth-Morris-Pratt sử dụng mảng Next[i] để lưu trữ độ dài lớn
nhất của xâu v trong trường hợp xâu u=x[1…i-1]. Mảng này có thể tính trước
với chi phí về thời gian là O(M) (việc tính mảng Next thực chất là một bài toán
qui hoạch động một chiều).
Thuật toán Knuth-Morris-Pratt có chi phí về thời gian là O(M+N) với
nhiều nhất là 2N-1 lần số lần so sánh ký tự trong quá trình tìm kiếm.
Ví dụ 1:
Tìm kiếm một ký tự ababac. Đầu tiên ta tiến hành tính mảng next:
Result:
1:i=1,j=0:i:= 2;j:= 1;next[2] := 1;
2:i=2,j=1:j:=next[1] = 0;
3:i=2,j=0:i:= 3;j:= 1;next[3] := 1;
4:i=3,j=1:i:= 4;j:= 2;next[4] := 2;
5:i=4,j=2:i:= 5;j:= 3;next[5] := 3;
6:i=5,j=3:i:= 6;j:= 4;next[6] := 4;
7:i=6,j=4:j:=next[4] = 2;
8:i=6,j=2:j:=next[2] = 1;
9:i=6,j=1:j:=next[1] = 0;
10:i=6,j=0:i:= 7;j:= 1;next[7] := 1;
Và khi quá trình tìm kiếm được thực hiện:
12345678910…
1: ababbabaa
2: ababac j=next[5]=3
3: ababac j=next[3]=1
4: ababac j=next[1]=0
5: ababac j=next[4]=2
6: ababac j=next[2]=1
7: ababac

Ví dụ 2:
Một ví dụ khác của thuật toán sẽ cho ta thấy nếu như trong mẫu các ký tự
từng đôi một khác nhau thì Knuth-Morris-Pratt sẽ không khác gì so với Brute-
Force. Khi đó next[1] = 0 còn next[j] = 1với mọi j >1

9

Tuy nhiên trong nhiều ứng dụng thực tế thuật toán Knuth-Morris-Pratt
nhanh hơn không đáng kể so với thuật toán Brute-Force, do ít khi xảy ra trường
hợp tìm kiếm các mẫu có tính tự lặp lại cao trong các văn bản cũng có tính lặp
lại cao. Mặc dù vậy nhưng phương pháp này có một giá trị thực tế quan trọng là:
ta có thể tiến hành tìm kiếm tuần tự trong văn bản và không bao giờ phải dự
phòng trong văn bản đó. Điều này rất có ý nghĩa khi áp dụng trên một tệp tin lớn
được đọc từ một thiết bị ngoại vi nào đó thì các thuật toán yêu cầu dự phòng sẽ
tiêu tốn bộ đệm hơn.
1.3.3. Thuật toán automat hữu hạ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.
Thuật toán này có phần giống thuật toán Knuth-Morris-Pratt trong việc
nhảy về trạng thái trước khi gặp một ký tự không khớp, nhưng thuật toán DFA

10

có sự đánh giá chính xác hơn vì việc xác định vị trí nhảy về dựa trên ký tự
không khớp của văn bản (trong khi thuật toán KMP lùi về chỉ dựa trên vị trí
không khớp).
Việc xây dựng hệ automat khá đơn giản khi được cài đặt trên ma trận kề.
Khi đó thuật toán có thời gian xử lý là O(N) và thời gian để tạo ra hệ automat là
O(M*N) (tùy cách cài đặt)
Nhưng ta nhận thấy rằng trong DFA chỉ có nhiều nhất M cung thuận và M
cung nghịch, vì vậy việc lưu trữ các cung không cần thiết phải lưu trên ma trận
kề mà có thể dùng cấu trúc danh sách kề Forward Star để lưu trữ. Như vậy thời
gian chuẩn bị và lượng bộ nhớ chỉ là O(M). Tuy nhiên thời gian tìm kiếm có thể
tăng lên một chút so với cách lưu ma trận kề.
1.3.4. Thuật toán Boyer-Moore
Thuật toán Boyer Moore là thuật toán tìm kiếm chuỗi rất có hiệu quả
trong thực tiễn, các dạng khác nhau của thuật toán này thường được cài đặt trong
các chương trình soạn thảo văn bản.
Đặc điểm chính của thuật toán là kiểm tra các ký tự của mẫu từ phải sang
trái và khi phát hiện sự khác nhau đầu tiên thuật toán sẽ tiến hành dịch cửa sổ đi,
độ phức tạp về thời gian ở giai đoạn tiền xử lý là O(M+δ), ở giai đoạn tìm mẫu
là O(M*N), trong trường hợp tốt nhất là O(N/M).
Trong thuật toán này có hai cách dịch cửa sổ:
Cách thứ 1: gần giống như cách dịch trong thuật toán KMP, dịch sao cho
những phần đã so sánh trong lần trước khớp với những phần giống nó trong lần
sau.
Trong lần thử tại vị trí j, khi so sánh đến ký tự i trên mẫu thì phát hiện ra
sự khác nhau giữa ký tự x[i]=a của mẫu và ký tự y[i+j]=b của văn bản, lúc đó
x[i+1…m-1]=y[i+j+1…j+m-1]=u và y[i+j-1]=b và x[i]≠ y[i+j] khi đó thuật
toán sẽ dịch cửa sổ sao cho đoạn u=y[i+j+1…j+m-1] giống với một đoạn mới
trên mẫu (trong các phép dịch ta chọn phép dịch nhỏ nhất)

Dịch sao cho u xuất hiện lại và c ≠ a
y b u
x a u shift
x c u

11

Nếu không có một đoạn nguyên vẹn của u xuất hiện lại trong x, ta sẽ chọn
sao cho phần đôi dài nhất của u xuất hiện trở lại ở đầu mẫu.

Dịch để một phần đôi của u xuất hiện lại trên x

Cách thứ 2: Coi ký tự đầu tiên không khớp trên văn bản là b=y[i+j] ta sẽ
dịch sao cho có một ký tự giống b trên xâu mẫu khớp vào vị trí đó (nếu có nhiều
vị trí xuất hiện b trên xâu mẫu ta chọn vị trí phải nhất).

Dịch để ký tự b ăn khớp với văn bản.

Nếu không có ký tự b nào xuất hiện trên mẫu ta sẽ dịch cửa sổ sao cho ký tự trái
nhất của cửa sổ vào vị trí ngay sau ký tự y[i+j-1]=b để đảm bảo sự ăn khớp

Dịch khi b không xuất hiện trong x

Trong hai cách dịch chuyển, thuật toán sẽ chọn cách dịch có lợi nhất.
y b u
x b u shift
x u
y b u
x a u shift
x b không chứa b
y b u
x a u shift
x

không chứa b

Tác giả

Nguyễn Thị Thúy

Nhà xuất bản

ĐHCN

Năm xuất bản

2012

Người hướng dẫn

Hà Quang Thụy

Định danh

00050001540

Kiểu

text

Định dạng

text/pdf

Chủ đề

Thuật toán,Công nghệ thông tin,Phần mềm Agrep,Thuật toán sánh mẫu

Nhà xuất bản

Khoa công nghệ thông tin,

Trường đại học Công nghệ

Các đánh giá

Hiện chưa có đánh giá cho sản phẩm.

Hãy là người đầu tiên đánh giá “Một họ thuật toán sánh mẫu Wu-Manber và thực nghiệm”

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *