BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

PHẠM CÔNG HỒNG

CÁC THUẬT TOÁN ĐỐI SÁNH MẪU VÀ ỨNG
DỤNG TÌM KIẾM TRÊN WEBSITE

LUẬN VĂN THẠC SĨ KỸ THUẬT
TOÁN TIN

Hà Nội – Năm 2014


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

PHẠM CÔNG HỒNG

CÁC THUẬT TOÁN ĐỐI SÁNH MẪU VÀ ỨNG DỤNG
TÌM KIẾM TRÊN WEBSITE

Chuyên ngành: TOÁN TIN
Mã đề tài:
TOAN-VINH06

LUẬN VĂN THẠC SĨ KỸ THUẬT
TOÁN TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC
TIẾN SĨ: NGUYỄN THỊ THANH HUYỀN

DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT
Các ký hiệu
ε

Xâu rỗng

wi

Kí tự thứ i của xâu w

Pi

Kí tự thứ i của xâu P

Sj

Kí tự thứ j của xâu S

Ci,j

Là độ dài dãy con lớn nhất của hai dãy P1..i và S1..j

Các chữ viết tắt
CSDL

Cơ sở dữ liệu

DFA

Otomat đơn định hữu hạn



MỤC LỤC
MỞ ĐẦU ............................................................................................................ 1
1. Lý do chọn đề tài ........................................................................................ 1
2. Mục tiêu và nội dung .................................................................................. 1
3. Phạm vi nghiên cứu .................................................................................... 2
Chương 1: TỔNG QUAN VỀ VẤN ĐỀ ĐỐI SÁNH MẪU ............................. 3
1.1. Đối sánh mẫu ........................................................................................... 3
1.2. Bài toán đối sánh mẫu và tình hình nghiên cứu hiện nay ........................ 4
1.3. Các dạng của bài toán đối sánh mẫu ........................................................ 6
1.3.1. So đơn mẫu .................................................................................... 6
1.3.2. So đa mẫu ....................................................................................... 7
1.3.3. Đối sánh mẫu mở rộng ................................................................... 8
1.4. Đối sánh mẫu xấp xỉ .............................................................................. 11
1.4.1. Phát biểu bài toán ......................................................................... 11
1.4.2. Độ tương tự giữa hai xâu ............................................................. 12
1.4.3. Các tiếp cận giải bài toán đối sánh mẫu xấp xỉ ............................ 13
Chương 2. CÁC THUẬT TOÁN ĐỐI SÁNH MẪU CHÍNH XÁC ............... 15
2.1. Thuật toán KMP ( Knuth- Morris- Pratt)............................................... 15
2.2. Thuật toán BM ( Boyer- Moore) ........................................................... 19
2.3. Thuật toán KMP mờ .............................................................................. 23
2.3.1. Khái niệm Độ mờ ............................................................................ 23
2.3.2 Otomat mờ so mẫu ........................................................................... 24
2.3.3 Thuật toán ......................................................................................... 25
2.4. Kết luận chương 2 .................................................................................. 28
Chương 3. ĐỐI SÁNH MẪU XẤP XỈ ........................................................... 29
3.1 Vấn đề đối sánh mẫu xấp xỉ .................................................................... 29
3.2 Độ tương tự dựa trên độ dài khúc con chung của hai xâu ...................... 30
3.2.1 Phát biểu bài toán ............................................................................. 30

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.
Ngày nay số lượng thông tin cũng như kích thước của hệ thống tin càng ngày
càng lớn, trong khi nhu cầu tìm kiếm của con người dùng đòi hỏi ngày càng cao và
phức tạp. Người dùng luôn luôn mong muốn có được kết quả với thời gian nhanh
nhất, đáp ứng linh hoạt, đa dạng các yêu cầu tìm kiếm, không những chính xác mà
cho ta các kết quả gần đúng, phù hợp với những từ khóa đưa vào. Để nâng cao tốc
độ tìm kiếm và đáp ứng yêu cầu người dùng. Vậy việc nghiên cứu tìm hiểu các
thuật toán đối sánh mẫu để ứng dụng trong công việc rất cần thiết.
Để tìm kiếm thông tin thì cần phải xem thông tin đó lưu trữ dưới dạng dữ
liệu nào? Dữ liệu được lưu trữ dưới nhiều dạng, song phổ biến nhất vẫn là dạng text
nên tôi chọn đề tài này cụ thể Các thuật toán đối sánh mẫu và ứng dụng tìm kiếm
trên website.
2. Mục tiêu và nội dung
Luận văn tập trung nghiên cứu các thuật toán đối sánh mẫu và ứng dụng tìm
kiếm trên website.
- Tìm hiểu về vấn đề tìm kiếm thông tin và đối sánh mẫu
- Nghiên cứu một số thuật toán đối sánh mẫu chính xác và xấp xỉ
- Cài đặt một số thuật toán đối sánh mẫu và ứng dụng xây dựng tính năng tìm
kiếm trên một website

1


3. Phạm vi nghiên cứu

kiểu dữ liệu nào, từ văn bản đến các loại dữ liệu đa phương tiện (ảnh, video, âm
thanh,...). Mặc dù dữ liệu được ghi dưới nhiều dạng, song văn bản (text) vẫn là
dạng phổ biến nhất, vì vậy vấn đề so xâu mẫu (string pattern matching) thực sự là
một chủ đề trở nên quan trọng của lĩnh vực xử lý văn bản và được rất nhiều người
quan tâm.
Vấn đề đặt ra trong bài toán so xâu mẫu là cần phát hiện được sự xuất hiện
của xâu mẫu trong một chuỗi (xâu) các kí hiệu cho trước (gọi là xâu đích, trong
thực tế xâu đích có thể là một văn bản). Phụ thuộc vào đặc tính của mẫu, ta có thể
phân thành bốn dạng bài toán cụ thể: so đơn mẫu, so đa mẫu, đối sánh mẫu mở
rộng và so biểu thức chính qui. Dạng đơn giản nhất song phổ dụng nhất và cũng
được quan tâm nhiều nhất là bài toán so đơn mẫu, với mẫu là một xâu (điều này
được thể hiện bởi sự phong phú của các thuật toán so đơn mẫu). Khi mẫu là một
tập các từ khoá, ta có bài toán so đa mẫu. Trong bài toán đối sánh mẫu mở rộng,
mẫu không đơn giản là một dãy kí tự mà được mở rộng theo nhiều kiểu khác
nhau. Cuối cùng, dạng tổng quát nhất bao hàm cho tất cả các loại bài toán kể trên
là so biểu thức chính qui.
Một vấn đề kinh điển khác của khoa học máy tính là tìm kiếm xấp xỉ, được
đặt ra từ các ứng dụng nhận dạng tiếng nói, sinh–tin học, xử lý tín hiệu, so sánh

3


tệp. Ngày nay, việc xây dựng công cụ tìm kiếm hiệu quả, đặc biệt là tính năng tìm
kiếm xấp xỉ, trong các hệ thống trích rút văn bản đang được rất nhiều người quan
tâm. Đó là do sự tăng trưởng nhanh chóng và không ngừng của các hệ thống thông
tin, trong khi nhu cầu khai thác của người dùng ngày càng phức tạp. Người ta
mong muốn có kết quả phù hợp trả về ngay cả khi có "lỗi" trong thông tin đưa vào
hay trong cơ sở dữ liệu của hệ thống và có thể thấy ngay nội dung cần tìm trong
trang kết quả đầu tiên, với thời gian ngắn nhất. Nhu cầu tìm kiếm văn bản xấp xỉ
thể hiện rõ nhất ở các ứng dụng như: thư viện điện tử, máy tìm kiếm (search

và các hệ thống sinh–tin học. Một lý do nữa, đó là vì 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ế (wild card), các khoảng trống và các biểu thức chính
qui. Sự "tìm thấy" không đơn giản là xuất hiện chính xác mẫu mà còn cho phép có
"một ít sai khác" giữa mẫu và xuất hiện của nó trong văn bản. Từ đó nảy sinh một
hướng nghiên cứu hết sức thú vị là "so xâu mẫu xấp xỉ" (approximate string
matching) hiện nay đang được quan tâm rất nhiều và những dạng phức tạp khác của
bài toán đối sánh mẫu là đối sánh mẫu mở rộng, so đa mẫu và so biểu thức chính
qui.
Các kết quả đạt được hiện nay về đối sánh mẫu chủ yếu tập trung vào trường
hợp đơn giản nhất là tìm ra một xâu mẫu trong văn bản, còn với những dạng phức
tạp khác, cho đến nay vẫn chưa có nhiều công trình được công bố. Tuy nhiên, ta có
thể phân loại các thuật toán đối sánh mẫu theo hai hướng. Thứ nhất là các thuật toán
trực tuyến (on–line), trong đó chỉ mẫu được tiền xử lý (thường sử dụng otomat hoặc
dựa trên các đặc tính kết hợp trên xâu), còn văn bản thì không. Thứ hai là các thuật
toán off–line, sử dụng giải pháp tiền xử lý văn bản theo cách xây dựng một cấu trúc
dữ liệu trên văn bản (lập chỉ mục). Mặc dù đã có những thuật toán trực tuyến nhanh,
song với nhiều ứng dụng phải điều khiển một lượng văn bản quá lớn nên không có
thuật toán trực tuyến nào có thể thực hiện một cách hiệu quả. Khi đó, giải pháp
được lựa chọn là sử dụng các thuật toán off–line. Tìm kiếm trên chỉ mục thực ra
cũng dựa trên tìm kiếm on–line.

5


1.3. Các dạng của bài toán đối sánh mẫu
Dựa trên đặc tính của mẫu, bài toán đối sánh mẫu được phân loại như sau: so
đơn mẫu, so đa mẫu, đối sánh mẫu mở rộng, so biểu thức chính qui theo hai hướng
chính xác và xấp xỉ. Nội dung của luận văn tập trung giải quyết bài toán so đơn

về thực hành đối với mẫu P đủ dài. Ý tưởng chung của tiếp cận này cũng tương tự
như tiếp cận thứ hai, song tại mỗi thời điểm sẽ tìm khúc cuối dài nhất của cửa sổ mà
là một khúc con của mẫu. Thuật toán đầu tiên theo tiếp cận này là BDM và khi P đủ
ngắn, một phiên bản đơn giản hơn, hiệu quả hơn là thuật toán BNDM. Với những
mẫu dài, thuật toán BOM được đánh giá là nhanh nhất
Ngoài ba tiếp cận trên cũng có một vài thuật thoán khác, chẳng hạn các
phương pháp dựa trên hàm băm, song chúng không hiệu quả lắm nên ít phổ dụng.
1.3.2. So đa mẫu
Bài toán 1.2. Cho một mẫu P gồm tập các từ khoá {w1, w2,....,wk} và xâu S
= S1S2....Sn trên cùng bảng chữ A. Tìm sự xuất hiện của các từ khoá wi trong S.
Một cách đơn giản để tìm nhiều từ khóa 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–Corasick, 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ỏ.
Theo tiếp cận thứ hai có các thuật toán Commentz–Walter , Set Horspool,
Wu–Manber,… Thuật toán Commemtz–Walter là sự kết hợp ý tưởng của
Boyer– Moore và Aho–Corasick, còn Set Horspool là một mở rộng của thuật toán
Horspool. Hiện nay, thuật toán Wu–Manber được đánh giá là nhanh trong thực
hành, trong đó có sự pha trộn giữa tiếp cận tìm kiếm hậu tố (suffix search approach)
và một kiểu hàm băm.
7


Một số thuật toán theo tiếp cận thứ ba được mở rộng từ thuật toán BOM,
SBOM và Shift–Or BNDM,...
1.3.3. Đối sánh mẫu mở rộng
Trong nhiều ứng dụng, xâu mẫu được đưa vào để tìm kiếm không chỉ đơn

- Với r1 và r2 là hai biểu thức chính qui, khi đó (r1|r2) là một biểu thức chính
qui khớp với xâu r1 hoặc r2.
- Với r1 và r2 là hai biểu thức chính qui, khi đó (r1)(r2) là một biểu thức chính
qui khớp với xâu bất kỳ có dạng xy, mà r1 khớp x và r2 khớp y.
- Với r là một biểu thức chính qui, khi đó (r)* là một biểu thức chính qui khớp
với một xâu bất kỳ có dạng x1x2...xn, n ≥ 0, trong đó r khớp với các xi, 1 ≤ i ≤ n.
Đặc biệt, (r)* khớp với xâu rỗng ε.
- Với r là một biểu thức chính qui khớp với xâu x, khi đó (r) cũng là một biểu
thức chính qui khớp với xâu x.
Qui ước thứ tự ưu tiên của các phép toán được viết theo chiều giảm dần như
sau: *, phép ghép, và |.
Tập chính qui là tập tất cả các xâu khớp với một biểu thức chính qui.
Ví dụ: với a,b,c,d,e, là các chữ cái, biểu thức chính qui:
(a|b)(a|c|d)(a)*e

khớp với các xâu: aae, acae, acaae, acaaae,...., baae,

bdaae,.....
Bài toán so biểu thức chính qui phát biểu như sau:
Bài toán 1.3. Cho một mẫu gồm một biểu thức chính qui r và xâu S =
S1S2...Sn.
Cho biết r có khớp với một khúc con của xâu S hay không. Quá trình so biểu
thức chính qui trải qua hai giai đoạn xử lý:

9


Giai
- đoạn 1: Phân tích để biểu diễn biểu thức chính qui dưới dạng cấu
trúc cây dễ duyệt hơn.

hạn của Glushkov.
1.4. Đối sánh mẫu xấp xỉ
1.4.1. Phát biểu bài toán
Đối sánh 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à một
giới hạn cho trước). Các “lỗi” thường gặp là: lỗi đánh máy hay lỗi chính tả trong hệ
thống trích rút thông tin, những sự biến đổi chuỗi gen hay các lỗi đo đạc trong sinh–
tin học và những lỗi truyền dữ liệu trong các hệ thống xử lý tín hiệu,...Vì trong các
hệ thống tin học khó có thể tránh được các “lỗi” nên vấn đề tìm kiếm xấp xỉ càng
trở nên quan trọng.
Đặc biệt, khi sử dụng các hệ thống trích rút thông tin, người dùng ngày nay
còn đòi hỏi cả những kết quả gần giống hoặc vẫn có được kết quả phù hợp trả về
nếu có sự sai sót trong mẫu hay văn bản. Trong trường hợp này “lỗi” có thể do
nhiều nguyên nhân khác nhau, chẳng hạn như:
- Câu truy vấn sai chính tả, xâu tìm kiếm không đúng cú pháp so với văn
bản.
- Lỗi in ấn, lỗi chính tả, xâu tìm kiếm không đúng cú pháp so với văn bản.
- Sự biến đổi hình thái từ trong một số ngôn ngữ.
- Dữ liệu đưa vào cơ sở dữ liệu không chính xác, thường xảy ra với tên
người, địa chỉ.
- Thông tin người tìm đưa vào không chính xác, chỉ “đại loại”.
Vì vậy, một vấn đề đặt ra cho các hệ thống trích rút thông tin ngày nay là đáp
ứng được nhu cầu tìm kiếm “mềm dẻo” này của người sử dụng.
Bài toán đối sánh mẫu xấp xỉ tổng quát được phát biểu như sau:

11


Bài toán 1.4. Cho văn bản T độ dài n và xâu mẫu P độ dài m trên cùng một
bảng chữ A. Tìm các vị trí trong văn bản khớp với mẫu, cho phép nhiều nhất k lỗi.

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, kí hiệu là LCS(x, y). Độ dài dãy con chung
dài nhất của hai xâu x, y có thể được tính toán dựa trên khoảng cách Levenshtein
giữa x và y bởi công thức sau:
LevDistance(x,y) = m + n – 2length(LCS(x, y)).
1.4.3. Các tiếp cận giải bài toán đối sánh mẫu xấp xỉ
Các thuật toán đối sánh mẫu xấp xỉ hiện nay ra thành bốn loại.
1) Các thuật toán dựa trên quy hoạch động: Đây là tiếp cận xuất hiện đầu tiên
và đã được dùng để tính khoảng cách soạn thảo.
2) Các thuật toán sử dụng otomat tìm kiếm: Quá trình tìm kiếm sử dụng một
otomat đa định hữu hạn mà được xây dựng từ trước dựa trên thông tin của mẫu P và
số lỗi k. Đâ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 (bit–parallelism): Cách tiếp
cận này cho ra 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. Chỉ ra 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à BPM để tái tạo các thuật toán quy hoạch động.

13


4) Các thuật toán sử dụng cơ chế lọc: Ý tưởng của các thuật toán loại này là
cố gắng thu hẹp không gian tìm kiếm của bài toán bằng cách loại đi các văn bản mà

Khi đó cần phải bắt đầu đối sánh mẫu từ vị trí j - h +1 trên S (trường hợp xấu
nhất h = i - 1 trong thuật toán Brute - Force). Nếu tồn tại h > 0 sao cho h - 1 ký tự
đầu của mẫu khớp với h - 1 ký tự cuối của đoạn S(j - 1) hay có nghĩa đã khớp với
h - 1 ký tự cuối của P(i - 1) thì ta có thể bỏ qua h - 1 phép so sánh và tiếp tục so
sánh 2 ký tự Ph và Sj (hình 2.1). Do h phụ thuộc vào i nên ký hiệu h = next[i], i =
1,…,m.

Hình 2.1. Ý nghĩa của mảng next

Nếu Sj ≠ Ph thì phải tiếp tục lùi con trỏ trên mẫu. Để khắc phục nhược điểm
do tình huống này gây ra, cần cố gắng tìm h sao cho Ph có nhiều khả năng bằng Sj.
Vì Sj ≠ Pi nên cần tìm h thoả mãn Ph ≠ Pi .

15


Trong KMP, khi i > m ta được một xuất hiện của mẫu bắt đầu từ vị trí j - m
trên S. Để tìm xuất hiện tiếp theo, nếu bắt đầu đối sánh từ P1 và Sj thì có thể bỏ sót
mẫu khi có mẫu xuất hiện lồng nhau. Vì vậy, khi con trỏ trên S dừng ở vị trí j, cần
trượt mẫu đi một số vị trí sao cho h - 1 ký tự đầu của mẫu khớp với h - 1 ký tự
cuối của S(j - 1) hay chính là khớp với h - 1 ký tự cuối của P(m). Do đó cần mở
rộng mảng next với i = m + 1. (Hình 2.2).

Hình 2.2. Ý nghĩa của mảng next tại vị trí m + 1

Như vậy, với mỗi vị trí i trên P, i = 1..m + 1, cần xác định next [i] thoả mãn:
+ next[i] là số h lớn nhất sao cho h - 1 ký tự đầu của mẫu khớp với h - 1 ký tự
cuối của P(i- 1).
+ Pi ≠ Pnext [i]
(để có next[m + 1], tưởng tượng như đã bổ sung thêm ký tự # vào cuối P, với #

0

2

0

0

2

4

16


Ví dụ 2.2: Với P=abbaaba ta có bảng next như sau:
i

1

2

3

4

5

6


i: = i + 1; j: = j + 1;
if ( i < = m) and (Pi = P j) then next [i] := next [j]
else next [i] : = j;
end;
end;
Thuật toán 2.2. KMP tìm nhiều lần lặp mẫu proedure KMP();
{Tìm mọi vị trí xuất hiện xâu mẫu P độ dài m trong xâu đích S độ dài n, đồng thời
thống kê tần suất xuất hiện mẫu}
var i, j: Integer;
counter: Integer;
Begin
Initnext ();

17