Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN

ĐỖ THỊ HẠNH TÌM KIẾM MỜ VÀ ỨNG DỤNG TÌM KIẾM THÔNG
TIN TRONG CÁC VĂN BẢN NÉN

Chuyên ngành: Khoa học máy tính
Mã số: 60 48 35 01

LUẬN VĂN THẠC SĨ
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 35 01

LUẬN VĂN THẠC SĨ
Người hướng dẫn: PGS.TS. ĐOÀN VĂN BAN Thái Nguyên - 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

LỜI CẢM ƠN
Em xin chân thành cảm ơn các thầy, cô khoa Công nghệ thông
tin trường Đại học Thái Nguyên đã tạo điều kiện giúp đỡ và truyền đạt
cho em những kiến thức về chuyên ngành và những kiến thức xã hội.
Đặc biệt, em xin bày tỏ lòng biết ơn sâu sắc đến PGS.TS. Đoàn
Văn Ban - Viện Khoa học Công nghệ Việt Nam. Thầy đã trực tiếp
hướng dẫn và giúp đỡ em hoàn thành luận văn. Mặc dù, trong quá

1.2. Hệ mờ ........................................................................................ 15
1.3. Ý tưởng chung của tiếp cận otomat mờ...................................... 15
1.4. Khái niệm otomat mờ ................................................................ 17
1.5. Một số thuật toán so mẫu ........................................................... 18
1.5.1. Thuật toán KMP ( Knuth- Morris- Pratt) ................................ 18
1.5.2. Thuật toán BM ( Boyer- Moor) ............................................... 22
1.6. Kết luận chương 1 ..................................................................... 26
Chương 2. BÀI TOÁN SO MẪU THEO CÁCH TIẾP CẬN
OTOMAT MỜ.................................................................................... 27
2.1. Bài toán so mẫu chính xác ......................................................... 27
2.1.1. Phát biểu bài toán ................................................................... 27
2.1.2. Độ mờ của mô hình ................................................................ 27
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4
2.1.3. Thuật toán KMP mờ ............................................................... 28
2.1.3.1. Otomat so mẫu ................................................................. 28
2.1.3.2. Tính đúng đắn của thuật toán ........................................... 29
2.1.3.3. Thuật toán ........................................................................ 29
2.1.3.4. So sánh KM P và thuật toán KMP mờ ............................. 32
2.1.4. Thuật toán KMP - BM mờ ...................................................... 33
2.1.4.1. Ý tưởng của thuật toán ..................................................... 33
2.1.4.2. Otomat mờ so mẫu ........................................................... 35
2.1.4.3. Thuật toán 2.4 .................................................................. 37
2.2. Bài toán so mẫu xấp xỉ............................................................... 38
2.2.1. Đặt vấn đề............................................................................... 38
2.2.2. Bài toán .................................................................................. 39
2.2.3. Độ tương tự dựa trên độ dài khúc con chung của hai xâu ........ 40
2.2.3.1. Phát biểu bài toán............................................................. 40

3.4. Kết luận chương 3 ..................................................................... 64
KẾT LUẬN ......................................................................................... 65
TÀI LIỆU THAM KHẢO .................................................................. 67

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Các ký hiệu
 Xâu rỗng
w
i
Ký tự thứ i của xâu w
w(f, d) Xâu con (hay khúc con) độ dài f của xâu w, kết
thúc ở vị trí d trên w
w1 ≤
s
w2 Xâu w1 là khúc đuôi của w2
w1 ≤
ls
w2 Xâu w1 là khúc đuôi dài nhất của w2
w(t) hoặc pref
t
(w) Khúc đầu độ dài t của xâu w
suf
t
(w) Khúc cuối độ dài t của xâu w
|A| Lực lượng của tập A


- Mức định lượng (chính xác)
- Mức định tính (không chính xác, bất định, mơ hồ, không
chắc chắn, nhập nhằng, không rõ ràng, mờ)
Tính thông minh trong quá trình xử lý thông tin thể hiện ở khả
năng xử lý thông tin định tính. Đây là điều mà thế hệ máy tính hiện nay
đang hướng 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.
Tìm kiếm thông tin thì bài toán đóng vai trò quan trọng là bài toán
so mẫu, với mẫu có thể ở bất kỳ 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 khác (ảnh, video, âm thanh, …). Trên thực tế có
rất nhiều ứng dụng tìm kiếm thông tin như: công cụ tìm kiếm của các hệ
điều hành, khai phá web trên Internet, ...
Để 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 chúng tôi chọn đề tài này cụ thể là tìm kiếm
văn bản text. Tìm kiếm văn bản text nếu như những văn bản có khối
lượng lớn thì có thể mất nhiều thời gian với những thuật toán kinh điển.
Vậy đặt ra vấn đề tìm kiếm văn bản nhưng ở dạng nén sẽ nhanh hơn.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2
Nên chúng tôi đi vào làm cụ thể là tìm kiếm mẫu trong văn bản nén.
Ngoài ra, văn bản nén cũng là văn bản mã hoá nhưng dung lượng giảm

- Luận văn cũng mong muốn nêu ra được một số hướng nghiên
cứu mở rộng về tìm kiếm mẫu theo hướng tiếp cận otomat mờ.
6. Phạm vi nghiên cứu
Luận văn tập trung nghiên cứu các kiến thức có liên quan, các cơ
sở lý thuyết: Hệ mờ, otomat mờ, các thuật toán tìm kiếm mẫu, các thuật
toán tìm kiếm mẫu theo cách tiếp cận otomat mờ.
7. Phương pháp nghiên cứu
Otomat mờ được xem là sự tổng quát hoá của otomat hữu hạn.
Trong đó tập trạng thái là các tập mờ, hàm chuyển trạng thái và trạng
thái kết thúc được biểu diễn qua các quan hệ mờ. Theo đánh giá của các
chuyên gia, các hệ hình thức otomat mờ là mô hình toán học thích hợp
với một số hệ thống quyết định, điều khiển, nhận dạng và đặc biệt được
dùng trong đoán nhận mẫu. Tận dụng những ưu điểm trên và sự kết hợp
với lý thuyết mờ, sử dụng một số hệ hình thức otomat mờ để giải bài
toán so xâu mẫu. Để thấy rõ được tiếp cận otomat mờ chúng tôi chọn
một bài toán cụ thể là tìm kiếm mẫu trong văn bản nén và mã hoá.
Trong phạm vi luận văn, bài toán có thể làm với các tệp dữ liệu
nén mà không cần giải nén toàn bộ. Ý tưởng cơ bản là đọc tuần tự trên
tệp nén và mở nén một số mã nén, lưu kết quả giải nén cục bộ vào vùng
đệm và áp dụng thuật toán theo tiếp cận mờ trên vùng đệm này.
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- Giới thiệu chung về vấn đề tìm kiếm văn bản, trọng tâm
là bài toán so xâu mẫu. Hướng tiếp cận của luận văn cho bài toán so
mẫu, chính xác và xấp xỉ, trên môi trường nén và mã hoá hoặc không sử
dụng một số hệ hình thức otomat mờ.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4

nhau như: các tiện ích của hệ điều hành, các hệ thống trích rút dữ liệu
(data retrieval system), trình soạn thảo văn bản (text editors), máy tìm
kiếm (search engine) trên internet, phân tích và tìm kiếm chuỗi gene
trong sinh vật học, xử lý ngôn ngữ tự nhiên, tìm kiếm text trong các hệ
cơ sở dữ liệu,…
Thời gian gần đây, vấn đề đối sánh chuỗi 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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 6
trích rút thông tin và các hệ thống sinh- tin học. Một lý do nữa, bởi 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 (gaps) và các biểu thức chính quy
(regular expresions). 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ừ đó, 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 hết sức thú vị đó là “tìm
kiếm xấp xỉ” (approximate matching, approximate searching).
Cho đến nay, đã có nhiều hướng tiếp cận giải các bài toán so mẫu
được đưa ra, từ những phương án rất lý thuyết đến các phương án rất
thực dụng. Hướng nghiên cứu lý thuyết đã nêu ra nhiều thuật toán quan
trọng, song lại chưa đạt hiệu quả cao trong thực hành, nếu không tận
dụng được những khả năng trong đặc điểm của kiến trúc máy tính. Hiện
nay, tiêu biểu cho những thuật toán mang tính chất thực hành theo hướng
nâng cao khả năng tận dụng kiến trúc máy tính là tiếp cận song song bit
(bit- parallelism) 1, 2, 3.
Có thể phân các loại thuật toán so mẫu theo 2 hướng. Thứ nhất là

, 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.
Thuật toán “thô” nhất và đã được sử dụng rộng rãi là Brute- Force.
Phương pháp này đơn giản chỉ là lần lượt bắt đầu từ vị trí trong S để đối
sánh với mẫu P. Mặc dù có tốc độ chậm, thời gian xấu nhất tỉ lệ với tích
m.n, song trong nhiều ứng dụng thực tế các chuỗi phát sinh ra thường có
thời gian xử lý thực sự luôn tỷ lệ với m + n. Ngoài ra, một ưu điểm khác
là nó thích hợp với cấu trúc của hầu hết các hệ máy tính.
Cho đến nay, rất nhiều thuật toán so đơn mẫu được đưa ra 4 5,
2, trong đó kinh điển nhất là KMP.
Có thể xem như có ba tiếp cận chung cho các thuật toán so mẫu,
phụ thuộc vào cách duyệt tìm mẫu trong văn bản. Việc đánh giá tốc độ
của các thuật toán dựa trên kích cỡ của mẫu P và bảng chữ A.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 8
Trong tiếp cận thứ nhất, lần lượt từng ký tự của văn bản S được đọc
và tại mỗi vị trí, sau khi đối sánh với một ký tự của mẫu sẽ cập nhật sự
thay đổi để nhận ra một khả năng xuất hiện mẫu. Hai thuật toán điển

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 4, có tốc độ cải thiện đáng kể khi số từ khoá nhiều và thuật
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 9
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
4, 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 [2]. 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 tìm kiếm hậu tố
(suffix search approach) và một kiểu hàm băm, được đánh giá là nhanh
trong thực hành.
Trong tiếp cận thứ ba đã có những mở rộng từ thuật toán BOM và
SBOM; tương tự với Shift- Or BNDM là Multiple BNDM 2.

1.1.2.3. Tìm mẫu mở rộng
Trong nhiều ứng dụng, tìm kiếm mẫu không chỉ đơn giản là dãy các
ký tự. Sau đây là một số mở rộng thường thấy trong các ứng dụng:
Mở rộng đơn giản nhất cho phép mẫu là một dãy các lớp hay các
tập ký tự, giả sử được đánh số thứ tự là 1,2,…,m. Bất kỳ ký tự nào trong
lớp thứ i cũng có thể được xem là ký tự thứ i của mẫu.
Mở rộng thứ hai là giới hạn khoảng trên độ dài: Một số vị trí trên

văn bản.
- Lỗi in ấn, sai lỗi chính tả, sử dụng dấu chấm sai,…
- Do 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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 11
Bài toán so mẫu xấp xỉ tổng quát được phát biểu như sau:
Bài toán 1.3.
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.

1.1.2.4.2. Các tiếp cận tìm kiếm xấp xỉ
Trong 2, tác giả chia các thuật toán tìm kiếm xấp xỉ hiện nay ra
thành 4 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 (Edit
Distance) (như trong 4).
2) Các thuật toán sử dụng otomat tìm kiếm: 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 (như
trong 9, 1). Đâ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 độ

k/m nhỏ; Multi BP xây dựng các NFA của tất cả các mẫu và sử dụng kết
quả này làm bộ lọc, đây là lựa chọn tốt nhất cho tỷ lệ k/m cỡ trung bình.
Một vài tiếp cận xấp xỉ cho bài toán tìm mẫu mở rộng và tìm biểu
thức chính qui có thể kể ra như: thuật toán dựa trên quy hoạch động cho
biểu thức chính qui; thuật toán sử dụng một otomat đa định hữu hạn cho
phép có “lỗi”, thuật toán song song bit dựa trên phương pháp của BPR, …

1.1.2.4.3. Độ tương tự giữa hai xâu
Để tìm kiếm xấp xỉ, cần sử dụng một hàm khoảng cách (distance
function) đo độ tương tự giữa hai xâu. Tương tự ở đây được hiểu là giữa
hai xâu ký tự có một vài sai khác ở những lỗi có thể nhận ra bằng mắt
thường, không xét về khía cạnh ngữ nghĩa (OCR- optical character
recognition errors), chẳng hạn “Việt Nam” và “Việt Nan” hay “Việtt
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 13
Nan”,… Có thể kể ra một số kỹ thuật phổ biến đo độ tương tự giữa hai
xâu: Xâu con chung dài nhất, dãy con chung dài nhất, khoảng cách soạn
thảo (Edit distance). Nhiều ứng dụng sử dụng các biến thể của các hàm
khoảng cách này.
1) Khoảng cách soạn thảo (Edit distance): 4, 7 Đối với hai xâu x,
y khoảng cách soạn thảo Edit distance (x,y) là số nhỏ nhất các phép sửa
đổi về mặt soạn thảo (editing transformations) để biến đổi xâu x thành
xâu y (việc tính toán khá phức tạp). Khoảng cách soạn thảo càng lớn thì
sự khác nhau giữa hai xâu càng nhiều (hay độ tương tự càng nhỏ) và
ngược lại. Khoảng cách soạn thảo thường để kiểm tra chính tả hay tiếng
nói. Tuỳ thuộc vào quy ước về các phép sửa đổi mà ta nhận được các
loại khoảng cách soạn thảo khác nhau, chẳng hạn như:
+ Khoảng cách Hamming: Phép sửa đổi chỉ là phép thay thế ký tự.

(full- compressed pattern matching hay còn gọi là compressed pattern
matching) và so mẫu trên miền nén (compressed- domain pattern
matching) 9. So mẫu nén thực hiện nén mẫu trước rồi đem đi tìm kiếm
trên văn bản nén (compressed text representation), còn so mẫu trên miền
nén sử dụng giải pháp nén từng phần của văn bản.
Nén dữ liệu text thực chất là một quá trình mã hoá, chuyển các
thông báo nguồn (trong bảng chữ nguồn A) thành các bản mã (trong bản
chữ mã B) và ngược lại là quá trình giải mã. Vì vậy thuật toán tìm kiếm
trên văn bản nén có thể áp dụng đối với văn bản mã hoá dạng khối ký tự.
Tuy nhiên, do yêu cầu bảo mật, đối với những văn bản mã hoá, cần có
những giải thuật tìm kiếm đảm bảo không bị rò rỉ thông tin ngay trong
quá trình tìm kiếm. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 15
1.2. Hệ mờ
Vấn đề cốt lõi quyết định khả năng xử lý thông tin là vấn đề của logic
mềm dẻo, trong đó logic đa trị là một ví dụ. Có thể nói rằng logic 2 trị:
đúng - sai (1 - 0) là logic hết sức cứng nhắc, không thể lý giải cho nhiều
sự việc của đời sống nói chung và của khoa học công nghệ nói riêng.
Định nghĩa 1.1:
Mọi sự vật, hiện tượng đều có tính đa cấu trúc đan xen, do đó tất
yếu có tính không rõ ràng, mập mờ, không chính xác..., bất định. Viên
gạch lý thuyết cơ sở để xây dựng nên thế giới không chính xác này có

Để giải bài toán so mẫu theo tiếp cận mờ, ta duyệt xâu đích S từ trái
sang phải và tại mỗi vị trí j, cần tính được ngay độ mờ xuất hiện mẫu P.
Một câu hỏi đặt ra: Giả sử đã biết độ mờ  của mẫu P tại vị trí j trên S,
làm cách nào để xác định được độ mờ ‟ tại vị trí tiếp theo? Ý tưởng để
trả lời câu hỏi này là: Bằng cách tiền xử lý mẫu P, ta hy vọng có thể tính
được ‟ theo công thức ‟= ( , S
j+1
). Điều này gợi ý cho ta việc sử
dụng một số hệ hình thức otomat mờ để tính độ mờ xuất hiện thông qua
hàm chuyển trạng thái  của otomat.
Ý tưởng chung của các thuật toán so mẫu theo tiếp cận otomat mờ
[11] như sau:
- Giai đoạn tiền xử lý mẫu P: Dựa vào thông tin trên mẫu P, xây
dựng otomat mờ so mẫu.
- Giai đoạn sánh mẫu: Duyệt xâu đích S từ trái sang phải, mỗi lần
một ký tự. Khởi đầu độ mờ là 0. Giả sử đã biết độ mờ tại vị trí j (j =
0,…, n- 1) trên S là . Khi đọc được ký tự S
j+1
, tính ngay được độ mờ tại
vị trí j + 1 trên S là ‟= ( , S
j+1
), trong đó  là hàm chuyển của otomat
mờ được xác định trong giai đoạn tiền xử lý mẫu.
Ưu điểm quan trọng nhất của thuật toán so mẫu theo tiếp cận otomat
mờ là:
- Không đòi hỏi lưu trữ toàn bộ S rồi mới so mẫu, do bản chất tuần
tự đọc từng ký tự trên S, nên có thể áp dụng trong các thuật toán hướng
online, đặc biệt là trên môi trường mạng, với không gian lưu trữ bộ đệm
cho S không lớn, tuỳ từng ứng dụng.
- Thông tin về mẫu được tiền xử lý và bao hàm trong cấu trúc của