ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG

NGÂN HOÀNG MỸ LINH

BÀI TOÁN ĐỐI SÁNH MẪU SỬ DỤNG
GIẢI THUẬT DI TRUYỀN

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN - 2015

Số hóa bởi Trung tâm Học liệu – ĐHTN




ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG

NGÂN HOÀNG MỸ LINH

BÀI TOÁN ĐỐI SÁNH MẪU SỬ DỤNG
GIẢI THUẬT DI TRUYỀN
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 60 48 01 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Ngƣời hƣớng dẫn khoa học: TS. VŨ MẠNH XUÂN


dỗ chúng tôi trong suốt quá trình học tập chƣơng trình cao học tại trƣờng.
Đặc biệt tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo TS Vũ Mạnh Xuân
đã quan tâm, định hƣớng và đƣa ra những góp ý, gợi ý, chỉnh sửa quý báu cho tôi
trong quá trình làm luận văn tốt nghiệp.
Cuối cùng, tôi xin chân thành cảm ơn các bạn bè đồng nghiệp, gia đình và
ngƣời thân đã quan tâm, giúp đỡ và chia sẻ với tôi trong suốt quá trình làm luận văn
tốt nghiệp.
Thái Nguyên, tháng 08 năm 2015

Ngân Hoàng Mỹ Linh

Số hóa bởi Trung tâm Học liệu – ĐHTN




iii

MỤC LỤC
MỞ ĐẦU .....................................................................................................................1
CHƢƠNG 1 MỘT SỐ THUẬT TOÁN ĐỐI SÁNH MẪU .......................................3
1.1. Giới thiệu về bài toán đối sánh mẫu.....................................................................3
1.2. Phát biểu bài toán .................................................................................................3
1.3. Một số thuật toán đối sánh mẫu cơ bản................................................................4
1.3.1. Thuật toán Brute Force......................................................................................4
1.3.2. Thuật toán Knuth-Morris-Pratt .........................................................................4
1.3.3. Thuật toán Automat hữu hạn.............................................................................5
1.3.4. Thuật toán Boyer-Moore ...................................................................................7
1.3.5. Thuật toán Karp-Rabin ....................................................................................10
1.3.6. Một số thuật toán khác ....................................................................................11

TÀI LIỆU THAM KHẢO .........................................................................................64

DANH MỤC THUẬT NGỮ, TỪ VIẾT TẮT, KÍ HIỆU
GA

Giải thuật di truyền

NST

Nhiễm sắc thể

Population

Quần thể

Pattern matching

Đối sánh mẫu

TSP

Bài toán ngƣời bán hàng

Số hóa bởi Trung tâm Học liệu – ĐHTN




v


1

MỞ ĐẦU
Hiện nay, cùng với sự phát triển không ngừng của ngành khoa học máy tính
chính là việc hệ thống thông tin đƣợc lƣu trữ ngày càng đồ sộ. Đối với một kho
thông tin lớn nhƣ vậy, việc ngƣời dùng muốn tra cứu, truy vấn dữ liệu cũng ngày
càng khó khăn hơn. Bên cạnh đó, khi lƣợng thông tin phát triển quá nhiều, việc tổ
chức, quản lí chúng để làm sao kiểm soát đƣợc việc bùng nổ thông tin cũng là một
trong những vấn đề cần quan tâm của các nhà quản lí. Hiện nay đã có rất nhiều công
cụ truy vấn có thể hỗ trợ cho ngƣời dùng phần nào trong việc tìm kiếm:
* Công cụ tìm kiếm của wikipedia: Chỉ tìm ra tên tựa bài của văn bản nào
trùng hợp với từ khóa.
* Công cụ tìm kiếm của phần mềm ứng dụng Microsoft word: Công cụ
FIND cho phép ngƣời dùng tìm kiếm cụm từ nội bên trong một hồ sơ, văn bản.
* Công cụ tìm kiếm của hệ điều hành Microsoft Windows và Adobe Reader:
Cả hai công cụ này cho phép tìm kiếm các hồ sơ có chứa từ khóa trong một hồ sơ,
một thƣ mục hay trong các ổ đĩa của máy tính.
Tuy nhiên, các công cụ trên vẫn tồn tại những hạn chế nhất định.Trong khi
đó, công việc tìm kiếm, truy vấn dữ liệu làm sao để nhanh chóng và hiệu quả vẫn
đang là một vấn đề cấp thiết đang đƣợc rất nhiều ngƣời dùng quan tâm. Các thông
tin đƣợc lƣu trữ trên máy tính tuy lớn nhƣng đa số đều đƣợc lƣu dƣới dạng văn bản,
và mặc dù có rất nhiều công cụ tìm kiếm nhƣng cơ chế chung của chúng vẫn là dựa
trên phƣơng pháp sử dụng chuỗi. Đối sánh mẫu (pattern matching) là một bài toán
quan trọng trong việc hỗ trợ tìm kiếm văn bản đƣợc áp dụng để tìm một xâu khớp
với mẫu trong văn bản hoặc tìm các văn bản có chứa mẫu.
Giải thuật di truyền (GA – Genetic Algorithms) là một kỹ thuật cơ bản của
tính toán mềm nhằm tìm kiếm giải pháp thích hợp cho các bài toán tối ƣu tổ hợp, nó
vận dụng các nguyên lý của tiến hóa nhƣ lai ghép, đột biến, chọn lọc. Ngày nay,

Số hóa bởi Trung tâm Học liệu – ĐHTN

CHƢƠNG 1
MỘT SỐ THUẬT TOÁN ĐỐI SÁNH MẪU
Chương này giới thiệu và phát biểu bài toán đối sánh mẫu, tìm hiểu một số
thuật toán đã và đang được sử dụng để giải bài toán đối sánh mẫu.
1.1. Giới thiệu về bài toán đối sánh mẫu
Trong khoa học máy tính, đối sánh mẫu là hành động kiểm tra xem một trình
tự các kí tự có hiện diện trong một xâu cho trƣớc hay không. Ngƣợc lại với nhận
dạng mẫu, đối sánh mẫu thƣờng có sự chính xác hơn. Dạng phổ biến nhất của bài
toán đối sánh mẫu là: Cho trƣớc nguồn tìm kiếm là một tập D các văn bản, 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) 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 mà chỉ cần “liên quan” tới q, nghĩa là 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 .[6]
1.2. Phát biểu bài toán
Đố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 q trên một văn bản S. Mẫu q và văn
bản S là các chuỗi có độ dài M và N (M ≤ N); q và S là các xâu ký tự trên cùng một
bảng chữ cái Σ có δ ký tự. Bài toán sánh mẫu tổng quát đƣợc phát biểu nhƣ sau:

Số hóa bởi Trung tâm Học liệu – ĐHTN



những ai yêu thích lập trình máy tính nói chung trên toàn thế giới. Thuật toán này
còn có tên là KMP, tức là lấy tên viết của ba ngƣời đồng phát minh ra nó, chữ “M”
là chỉ giáo sƣ J.H.Morris, cũng là một giáo sƣ rất nổi tiếng trong ngành khoa học
máy tính.

Số hóa bởi Trung tâm Học liệu – ĐHTN




5

Ý tƣởng chính của phƣơng pháp này nhƣ sau: Trong quá trình tìm kiếm vị trí
của mẫu P trong xâu gốc T, nếu tìm thấy một vị trí sai, ta chuyển sang vị trí tìm
kiếm tiếp theo và quá trình tìm kiếm này sẽ đƣợc tận dụng thông tin từ quá trình tìm
kiếm trƣớc để tránh việc phải xét lại các trƣờng hợp không cần thiết.
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, nó 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ự nê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


Với ví dụ ở trên ta có:
Nếu đang ở trạng thái 2 gặp ký tự A trên văn bản sẽ chuyển sang trạng thái 3.
Nếu đang ở trạng thái 6 gặp ký tự C trên văn bản sẽ chuyển sang trạng thái 2.
Trạng thái 8 là trạng thái cuối cùng, nếu đạt đƣợc trạng thái này có nghĩa là
đã tìm thấy một xuất hiện của mẫu trên văn bản.
Trạng thái 0 là trạng thái mặc định (các liên kết không đƣợc biểu thị đều chỉ
về trạng thái này), ví dụ ở nút 5 nếu gặp bất kỳ ký tự nào khác G thì đều chuyển về
trạng thái 0.
Số hóa bởi Trung tâm Học liệu – ĐHTN




7

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); thời gian và bộ nhớ để tạo ra hệ automat là
O(m* ) (tùy cách cài đặt).
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ác đặc điểm chính của nó:
-

Thực hiện việc so sánh từ phải sang trái.

-






8

Hình 1.2. Mis-match trong khi đang so sánh tại vị trí j

Khi đó, x[i+1...m-1] = y[j+i+1…j+m-1] = u và x[i] ≠ y[i+j]. Bây giờ ta đi xét
đối với từng trƣờng hợp, 2 hàm trên sẽ thực hiện việc di chuyển nhƣ thế nào:
-

Phép dịch chuyển good-suffix shift sẽ dịch cửa sổ sang bên phải cho
đến khi gặp 1 kí tự khác với x[i] trong trƣờng hợp đoạn u lại xuất hiện
trong x.

Hình 1.3. Good-suffix shift, trường hợp u lại xuất hiện trong x

-

Nếu đoạn u không xuất hiện lại trong x, mà chỉ có 1 phần cuối (suffix)
của u khớp với phần đầu (prefix) của x, thì ta sẽ dịch 1 đoạn sao cho
phần suffix dài nhất v của y[j+i+1…j+m-1] khớp với prefix của x.

Hình 1.4. Good-suffix shift, trường hợp chỉ có suffix của u xuất hiện trong x

-

Phép dịch chuyển bad-character shift sẽ khớp kí tự y[i+j] với 1 kí tự
(bên trái nhất) trong đoạn x[0…m-2].

ngƣợc lại.

Số hóa bởi Trung tâm Học liệu – ĐHTN




10

Bảng bmGs và bmBc đƣợc tính toán trong thời gian O(m+ ) trƣớc khi thực
hiện tìm kiếm và cần 1 không gian phụ là O(m+ ). Giai đoạn tìm kiếm có độ phức
tạp thời gian bậc 2 nhƣng lại chỉ có 3n phép so sánh khi tìm kiếm 1 chuỗi không có
chu kì. Đối với việc tìm kiếm trong một khối lƣợng lớn các chữ cái, thuật toán có
thể thực hiện với một tốc độ rất nhanh. Khi tìm kiếm chuỗi am-1 trong bn chuỗi, thuật
toán chỉ sử dụng O(m/n) phép so sánh, là chi phí thấp nhất của các thuật toán tìm
kiếm hiện đại có thể đạt đƣợc [2].
1.3.5. Thuật toán Karp-Rabin
Thuật toán mang tên hai nhà khoa học phát minh ra nó là Richard M.Karp
(sinh năm 1931,ngƣời Mỹ) và Michael O.Rabin (sinh năm 1931,ngƣời Đức). Tƣ
tƣởng chính của phƣơng pháp này là sử dụng phƣơng pháp băm (hashing). Tức là
mỗi một xâu sẽ đƣợc gán với một giá trị của hàm băm (hash function). Ví dụ, có
xâu “hello” đƣợc gán với giá trị bằng 5, và hai xâu đƣợc gọi là bằng nhau nếu giá trị
hàm băm của nó bằng nhau.Nhƣ vậy, thay vì việc phải đối sánh các xâu con của T
với mẫu P, ta chỉ cần so sánh giá trị hàm băm của chúng và đƣa ra kết luận.
Trong thuật toán này, hàm băm phải thỏa mãn một số tính chất nhƣ phải dễ
dàng tính đƣợc trên chuỗi, và đặc biệt công việc tính lại phải đơn giản để ít ảnh
hƣởng đến thời gian thực hiện của thuật toán. Chẳng hạn hàm băm đƣợc chọn ở đây
là: hash(w[i…i+m-1]) = h = (w[i]*dm-1 + w[i+1]*dm-2 + … w[i+m-1]*d0) mod q.
Việc tính lại hàm băm sau khi dịch cửa sổ đi một ký tự chỉ đơn giản nhƣ sau:
h = ((h – w[i]*dm-1)*d + w[i+m]

không làm giảm độ phức tạp lý thuyết mà dựa trên kinh nghiệm để có tốc độ tìm
kiếm nhanh hơn trong thực tế. Ngoài ra, một số thuật toán kết hợp quá trình tìm
kiếm của BM vào hệ thống Automat mong đạt kết quả tốt hơn.
Các thuật toán so sánh mẫu theo thứ tự đặc biệt:
-

Thuật toán Galil-Seiferas và Crochemore-Perrin chia mẫu thành hai đoạn,
đầu tiên kiểm tra đoạn ở bên phải rồi mới kiểm tra đoạn bên trái với chiều từ
trái sang phải.

-

Thuật toán Colussi và Galil-Giancarlo lại chia mẫu thành hai tập và tiến hành
tìm kiếm trên mỗi tập với một chiều khác nhau.

-

Thuật toán Optimal Mismatch và Maximal Shift sắp xếp thứ tự mẫu dựa vào
mật độ của ký tự và khoảng dịch đƣợc.

Số hóa bởi Trung tâm Học liệu – ĐHTN




12

-

Thuật toán Skip Search, KMP Skip Search và Alpha Skip Search dựa sự

GIỚI THIỆU VỀ GIẢI THUẬT DI TRUYỀN
Chương này giới thiệu tổng quan về giải thuật di truyền. Các toán tử của
giải thuật di truyền và những điểm khác biệt của giải thuật di truyền với các giải
thuật khác.[1],[3],[4],[5],[9]
2.1. Tổng quan chung về giải thuật di truyền (GA)
2.1.1. Giới thiệu
Lí thuyết về giải thuật di truyền trong những năm qua đã phát triển rất mạnh
và theo nhiều hƣớng tiếp cận khác nhau. Sở dĩ nhƣ vậy là do tính hiệu quả của giải
thuật này so với các giải thuật khác. Giải thuật di truyền đã thể hiện rõ tính ƣu việt
trong tìm kiếm tiến hoá và tính mềm dẻo trong khả năng thích nghi với yêu cầu của
bài toán đặt ra, đặc biệt đối với các bài toán khó, có không gian tìm kiếm lớn và có
nhiều ràng buộc phức tạp.
Giải thuật di truyền đƣợc J.H.Holland và các đồng nghiệp của ông tại trƣờng
đại học Michigan giới thiệu năm 1975, và đã có rất nhiều công trình nghiên cứu về
lí thuyết cũng nhƣ ứng dụng của nó đƣợc công bố trong những năm gần đây. GA
đƣợc ứng dụng trong nhiều lĩnh vực khác nhau nhƣ: Sinh học, khoa học cơ bản,
khoa học máy tính, trí tuệ nhân tạo.
Giải thuật di truyền là kỹ thuật phỏng theo quá trình thích nghi tiến hoá của
các quần thể sinh học dựa trên học thuyết Darwin. Cũng nhƣ các thuật toán tiến hoá
khác, GA đƣợc hình thành dựa trên một quan niệm đƣợc coi là một tiên đề phù hợp
với thực tế khách quan. Đó là quan niệm “quá trình tiến hoá tự nhiên là quá trình
hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu”. Quá trình tiến hoá thể
hiện tối ƣu ở chỗ thế hệ sau bao giờ cũng tốt hơn thế hệ trƣớc. Tƣ tƣởng của GA là
mô phỏng các hiện tƣợng tự nhiên: kế thừa và đấu tranh sinh tồn.

Số hóa bởi Trung tâm Học liệu – ĐHTN





thể có độ thích nghi càng cao thì càng có nhiều khả năng đƣợc chọn)
c. [Lai ghép] Với một xác suất lai ghép đƣợc chọn, lai ghép hai cá thể bố mẹ để tạo
ra một cá thể mới
d. [Đột biến] Với một xác suất đột biến đƣợc chọn, biến đổi cá thể mới
e. [Tạo lại quần thể mới]
4. [Chọn kết quả] Nếu điều kiện dừng đƣợc thỏa mãn thì thuật toán kết thúc và trả về
lời giải tốt nhất trong quần thể hiện tại.Nếu không, quay trở lại bƣớc [3].

2.1.2. Các vấn đề cơ bản của GA
2.1.2.1. Mã hoá cá thể
Trong giải thuật GA sử dụng một số thuật ngữ của di truyền học nhƣ: nhiễm
sắc thể (NST), quần thể (population), gen,… NST đƣợc tạo thành từ các gen (đƣợc
biểu diễn bằng một chuỗi tuyến tính). Mỗi gen mang một số đặc trƣng và có vị trí
nhất định trong NST. Mỗi NST sẽ đƣợc mã hoá để biểu diễn lời giải của bài toán.
Cách mã hoá NST đƣợc đánh giá là một trong hai yếu tố quyết định trong việc xây
dựng giải thuật GA.
a) Mã hoá nhị phân
Trong tất cả các phƣơng pháp mã hoá thì mã hoá nhị phân là phƣơng pháp
đơn giản và ra đời sớm nhất. Trong mã hoá nhị phân, mỗi NST là một chuỗi nhị
phân, mỗi bit trong nó có thể biểu diễn một đặc tính của lời giải.
Ví dụ: Hai NST 1 và 2 có độ dài 10:
NST 1: 1 0 1 0 0 1 0 1 0 0

Số hóa bởi Trung tâm Học liệu – ĐHTN

;

NST 2: 1 1 0 0 0 1 1 1 0 1




5.32

0.67

1.64

NST 2: (back)

(back)

(right)

(left)

Số hóa bởi Trung tâm Học liệu – ĐHTN




17

Mã hoá theo giá trị thƣờng dùng cho các bài toán đặc biệt. Trong cách mã
hoá này ta thƣờng phải phát triển các toán tử đột biến và lại ghép cho phù hợp với
từng bài toán.
2.1.2.2. Khởi tạo quần thể ban đầu
Quần thể là một tập hợp các cá thể cùng sống trong một môi trƣờng sống và
có chung một số đặc điểm nào đó. Trong GA, ta quan niệm “quần thể là tập các lời
giải của bài toán”.
Quần thể ban đầu ảnh hƣởng khá nhiều đến hiệu quả giải thuật, tuy nhiên

lọc trong GA chính là quá trình chọn các cá thể có độ thích nghi (cụ thể là giá trị
hàm mục tiêu) tốt hơn để đƣa vào thế hệ tiếp theo hoặc cho lai ghép, với mục đích
là sinh ra cá thể mới tốt hơn. Có nhiều cách lựa chọn nhƣng đều cùng một mục tiêu
là những cá thể tốt sẽ có khả năng đƣợc chọn cao hơn.
2.1.2.5. Lai ghép
Giống nhƣ trong sinh học, việc lai ghép giữa hai cá thể sẽ cho ra cá thể con
thừa hƣởng một phần từ cá thể cha và một phần từ cá thể mẹ. Mỗi toán tử lai ghép
sẽ có xác suất xảy ra tƣơng ứng của nó. Các nghiên cứu sinh học đã chỉ ra rằng
trong tự nhiên, xác suất xảy ra lai ghép thƣờng rất cao, khoảng 99,97%. Tuy nhiên,
trên thực tế, khi áp dụng vào các bài toán trên máy tính thì xác suất này thƣờng
không cao đến mức đó. Việc xác định xác suất lai ghép hoàn toàn phụ thuộc vào
vấn đế cần giải quyết.
2.1.2.6. Đột biến
Đột biến là một sự biến đổi tại một (hay một số) gen của NST ban đầu để tạo
ra một NST mới. Đột biến có xác suất xảy ra thấp hơn lai ghép rất nhiều. Đột biến
có thể tạo ra cá thể mới tốt hơn hoặc xấu hơn cá thể mẹ ban đầu. Tuy nhiên, trong
GA, ta luôn mong muốn tạo ra những phép đột biến cho phép cải thiện lời giải qua
từng thế hệ tiến hoá.
2.1.3. Sự khác biệt của GA với các giải thuật khác
Hoạt động của GA đơn giản là việc mô phỏng sự tiến hoá và chọn lọc tự
nhiên bằng máy tính bắt đầu từ một quần thể đƣợc khởi tạo ngẫu nhiên. Bên cạnh

Số hóa bởi Trung tâm Học liệu – ĐHTN