ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
ĐÀO THỊ DUNG
TÌM HIỂU MỘT SỐ GIẢI THUẬT TÌM KIẾM
CHUỖI CON VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Hà Nội – 2016
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
ĐÀO THỊ DUNG
TÌM HIỂU MỘT SỐ GIẢI THUẬT TÌM KIẾM
CHUỖI CON VÀ ỨNG DỤNG
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60480104
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. NGUYỄN TRÍ THÀNH
Hà Nội – 2016
1
LỜI CẢM ƠN
Sau thời gian nghiên cứu, làm việc khẩn trƣơng và đƣợc sự hƣớng dẫn tận tình
giúp đỡ của thầy giáo PGS.TS Nguyễn Trí Thành, luận văn với đề tài “ Tìm hiểu
một số giải thuật tìm kiếm chuỗi con và ứng dụng” đã đƣợc hoàn thành.
Tác giả xin bày tỏ lòng biết ơn sâu sắc tới:
Thầy giáo hƣớng dẫn PGS.TS Nguyễn Trí Thành đã tận tình chỉ dẫn, giúp đỡ
tác giả hoàn thành luận văn.
Các thầy cô giáo Trƣờng Đại học công nghệ và một số đồng nghiệp, đã quan tâm
động viên, giúp đỡ tác giả trong suốt quá trình học tập để hoàn thành luận văn này.
Mặc dù đã cố gắng hết sức, song do điều kiện thời gian và kinh nghiệm thực tế của
bản thân còn ít, cho nên đề tài không thể tránh khỏi thiếu sót. Vì vậy, tác giả mong nhận
đƣợc sự đóng góp ý kiến của các thầy giáo, cô giáo và các bạn bè đồng nghiệp.
Tôi xin chân thành cảm ơn!
Hà Nội, ngày 10 tháng 03 năm 2016
Tác giả
Đào Thị Dung
2
LỜI CAM ĐOAN
Tên tôi là: Đào Thị Dung
Sinh ngày 30 tháng 12 năm 1989
Học viên lớp cao học khoá 20 HTTT - Trƣờng đại học công nghệ - ĐHQGHN
Hiện đang công tác tại : Trƣờng THPT DTNT Tỉnh Vĩnh Phúc
Xin cam đoan luận văn “ Tìm hiểu một số giải thuật tìm kiếm chuỗi con và
ứng dụng” do thầy giáo PGS.TS Nguyễn Trí Thành hƣớng dẫn là công trình nghiên
cứu của riêng tôi. Tất cả các tài liệu tham khảo đều có nguồn gốc, xuất xứ rõ ràng.
Tác giả xin cam đoan tất cả những nội dung trong luận văn đúng nhƣ nội dung
trong đề cƣơng và yêu cầu của thầy giáo hƣớng dẫn. Nếu có vấn đề gì trong nội dung
của luận văn tác giả xin hoàn toàn chịu trách nhiệm với lời cam đoan của mình.
Hà Nội, ngày 10 tháng 03 năm 2016
Học viên
Đào Thị Dung
3
MỤC LỤC
LỜI CẢM ƠN .................................................................................................................. 1
LỜI CAM ĐOAN ............................................................................................................ 2
MỤC LỤC ....................................................................................................................... 3
Danh mục các ký hiệu và chữ viết tắt .............................................................................. 5
Danh mục các bảng.......................................................................................................... 6
Danh mục hình ảnh .......................................................................................................... 7
MỞ ĐẦU ......................................................................................................................... 8
CHƢƠNG 1. TỔNG QUAN VỀ TÌM KIẾM CHUỖI CON ........................................ 13
1.1. Lịch sử về tìm kiếm chuỗi con ......................................................................... 13
1.1.1. Thuật toán trƣớc những năm 2000 ............................................................... 13
1.1.2. Thuật toán sau năm 2000 .............................................................................. 14
1.2. Tìm kiếm chuỗi con ......................................................................................... 15
1.2.1. Khái niệm về tìm kiếm chuỗi con ................................................................. 15
1.2.2. Các cách tiếp cận: ......................................................................................... 16
1.2.3. Các dạng tìm kiếm chuỗi .............................................................................. 16
1.2.4. Ứng dụng của tìm kiếm chuỗi ...................................................................... 20
1.3. Tóm tắt chƣơng ................................................................................................... 18
CHƢƠNG 2. CÁC THUẬT TOÁN TÌM KIẾM CHUỖI CON ................................... 19
2.1. Các thuật toán tìm kiếm chuỗi con thông dụng .................................................. 19
2.1.1. Thuật toán Brute Force ................................................................................. 19
2.1.2. Thuật toán Karp-Rabin ................................................................................. 27
2.1.3. Thuật toán Knuth – Morris – Pratt ............................................................... 32
2.1.4. Thuật toán Boyer – Moore ........................................................................... 29
2.2. So sánh các thuật toán tìm kiếm chuỗi ............................................................... 42
2.3. Tóm tắt chƣơng ................................................................................................. 43
CHƢƠNG 3. KẾT QUẢ THỰC NGHIỆM VÀ ỨNG DỤNG ..................................... 36
3.1. Thực nghiệm ....................................................................................................... 36
3.1.1. Môi trƣờng thực nghiệm .............................................................................. 36
3.1.2. Đánh giá kết quả thực nghiệm ..................................................................... 39
3.2. Chƣơng trình ứng dụng : ..................................................................................... 40
3.2.1. Tập CSDL sử dụng: .................................................................................... 48
