[FONT=Times New Roman]. Đặt vấn đề

Ngày nay máy tính đã được sử dụng trong mọi lĩnh vực của đời sống,

vì vậy kho thông tin trong máy tính tăng trưởng không ngừng và thật khó

khăn cho công tác tìm kiếm (nhất là tìm kiếm trên các file văn bản). Hãng

Microsoft đã hỗ trợ tìm kiếm tự động bằng công cụ Search được tích hợp sẵn

trong hệ điều hành Windows, trong đó cho ta hai cách thức tìm kiếm file là:

tìm theo từ khoá tên file (All or part of the file name) – đưa ra các file có tên

chứa khoá tìm kiếm; và tìm theo từ khoá nội dung trong file (A word or

phrase in the file) – đưa ra các file Văn bản có chứa một từ hoặc cụm từ giống

với từ khoá. Mặc dù Search trong Windows hỗ trợ mạnh chức năng tìm kiếm

theo tên file, nhưng tìm theo nội dung trong file vẫn còn có những hạn chế

nhất định, chẳng hạn: Search chỉ đưa ra các file Văn bản có chứa chính xác từ

khoá tìm kiếm, như vậy sẽ rất khó khăn nếu người dùng không nhớ chính xác

từ khoá có trong nội dung Văn bản mà chỉ nhớ gần đúng với từ khoá, hơn nữa

công cụ Search không chỉ ra được cụm từ khoá tìm được nằm ở đâu trong văn

bản và tần suất xuất hiện của chúng, nên nếu cần người dùng lại một lần nữa

phải đi dò tìm bằng các công cụ tìm kiếm khác.

Vì lẽ đó bài toán tìm kiếm Văn bản là bài toán rất thiết thực đang được

nhiều người quan tâm, vấn đề cấp thiết đặt ra là giải quyết bài toán tìm kiếm

Văn bản sao cho hiệu quả, đáp ứng được nhu cầu của người sử dụng. Luận văn

này định hướng nghiên cứu sử dụng giải thuật di truyền tìm trong file Văn bản

các đoạn văn bản giống hoặc gần giống với mẫu (từ khoá) cần tìm kiếm.

Với mục tiêu đó, tôi lựa chọn đề tài nghiên cứu của luận văn là “Bài

toán tìm kiếm Văn bản sử dụng giải thuật di truyền.” Đây là hướng tiếp cận

khá mới đối với bài toán này, hy vọng rằng kết quả đạt được sẽ có hiệu quả

đáng kể so với các phương pháp tìm kiếm khác.

2. Mục đích của luận văn

Mục đích của luận văn là: nghiên cứu các phương pháp tìm kiếm văn

bản và tìm cách ứng dụng giải thuật di truyền để giải quyết bài toán này, trên

cơ sở đó Xây dựng phần mềm ứng dụng tìm kiếm Văn bản một cách hiệu quả

và thiết thực.

3. Nội dung của luận văn

Đề tài tập trung vào bài toán tìm kiếm Văn bản theo hướng tiếp cận sau:

Tìm các vị trí trong Văn bản có xuất hiện chuỗi Văn bản giống hoặc gần giống

với chuỗi Văn bản mẫu (xuất hiện gần giống trong trường hợp Văn bản tìm

kiếm không chứa chuỗi Văn bản mẫu). Trên cơ sở đó, nội dung của luận văn

gồm bốn chương sau phần Mở đầu:

- Chương 1: Nghiên cứu khái quát về các kỹ thuật tìm kiếm văn bản.

- Chương 2: Tìm hiểu giải thuật di truyền, chú trọng đến các kỹ thuật có

liên quan đến bài toán tìm kiếm.

- Chương 3: Xây dựng và phát biểu bài toán, đề xuất phương pháp sử

dụng giải thuật di truyền trong tìm kiếm văn bản.

Chương 4: Kết quả thử nghiệm và Phát triển phần mềm ứng dụng.

4. Phƣơng pháp nghiên cứu

Nghiên cứu tài liệu, đề xuất giải pháp và lập trình thử nghiệm.

Luận văn đã bước đầu đề xuất phương pháp ứng dụng giải thuật di

truyền vào giải quyết bài toán tìm kiếm văn bản, các chương trình thử nghiệm

đã minh chứng hướng tiếp cận là đúng đắn và có hiệu quả. Đặc biệt chương

trình đã chỉ ra được các vị trí xuất hiện đoạn Văn bản giống Văn bản mẫu hoặc

gần giống với Văn bản mẫu (trong trường hợp Văn bản không chứa Văn bản

mẫu) cần tìm trong thời gian cho phép. Hiện nay chúng tôi đang trong quá

trình Phát triển phần mềm ứng dụng dựa vào các kết quả nghiên cứu này.

MỤC LỤC

Trang

Trang phụ bìa

Lời cam đoan

Mục lục .................................................. .................................................. .... i

Danh mục các thuật ngữ .................................................. ............................. iv

Danh mục các hình vẽ, bảng biểu .................................................. ............... v

MỞ ĐẦU:........................................... .................................................. ....... 1

1. ĐẶT VẤN ĐỀ .................................................. .................................. 1

2. MỤC ĐÍCH CỦA LUẬN VĂN .................................................. ............ 2

3. NỘI DUNG CỦA LUẬN VĂN .................................................. .............. 2

4. PHƯƠNG PHÁP NGHIÊN CỨU .................................................. .......... 2

NỘI DUNG .................................................. ...............................................

CHƯƠNG 1. MỘT SỐ KỸ THUẬT TÌM KIẾM Văn bản ...................... 3

1.1. Bài toán tìm kiếm Văn bản .................................................. ................... 3

1.2. Các thuật toán............................................. ........................................... 4

1.2.1. Thuật toán Brute Force .................................................. ..................... 4

1.2.2. Thuật toán Knuth-Morris-Pratt .................................................. ......... 5

1.2.3. Thuật toán Deterministic Finite Automaton (máy automat hữu hạn)... 7

1.2.4. Thuật toán Boyer-Moore .................................................. .................. 10

1.2.5. Thuật toán Karp-Rabin .................................................. ..................... 15

1.2.6. Các thuật toán khác .................................................. .......................... 17

CHƯƠNG 2. GIỚI THIỆU VỀ GIẢI THUẬT DI TRUYỀN ....................... 20

2.1. Tổng quan về giải thuật di truyền .................................................. ........ 20

2.1.1. Giới thiệu .................................................. ......................................... 20

2.1.2. Sự khác biệt của giải thuật di truyền so với các giải thuật khác........... 21

2.1.3. Tính chất quan trọng của giải thuật di truyền ...................................... 21

2.2. Giải thuật di truyền cổ điển .................................................. ................. 22

2.2.1. Giới thiệu .................................................. ......................................... 22

2.2.2. Các toán tử di truyền .................................................. ........................ 24

2.2.2.1. Toán tử chọn lọc .................................................. ............................ 24

2.2.2.2. Toán tử lai ghép .................................................. ............................. 25

2.2.2.3. Toán tử đột biến............................................ ................................... 26

2.2.3. Các bước quan trọng trong việc áp dụng giải thuật di truyền cổ điển .. 26

2.2.4. Ví dụ .................................................. ................................................ 27

CHƯƠNG 3. SỬ DỤNG GIẢI THUẬT DI TRUYỀN ĐỂ TÌM KIẾM

Văn bản .................................................. ........................... 33

3.1. Yêu cầu đặt ra cho bài toán tìm kiếm văn bản........................................ 33

3.2. Xây dựng hàm tìm kiếm Văn bản .................................................. ......... 34

3.3. Phát biểu bài toán tìm kiếm Văn bản theo hướng tiếp cận di truyền ....... 35

3.4. Tìm độ dài xâu con chung lớn nhất bằng quy hoạch động ..................... 38

3.5. Áp dụng giải thuật di truyền .................................................. ................ 39

3.5.1. Biểu diễn nhiễm sắc thể .................................................. .................... 39

3.5.2. Khởi tạo quần thể .................................................. ............................. 40

3.5.3. Hàm mục tiêu .................................................. ................................... 40

3.5.4. Các toán tử di truyền .................................................. ........................ 41

3.5.5. Các tham số .................................................. ...................................... 42

3.5.6. Chi phí thời gian .................................................. ............................... 42

CHƯƠNG 4. KẾT QUẢ THỰC NGHIỆM VÀ Phát triển PHẦN

MỀM ỨNG DỤNG .................................................. ............. 44

4.1. Các kết quả thử nghiệm .................................................. ....................... 44

4.1.1. Kết quả thử nghiệm tìm kiếm tuyến tính ............................................. 44

4.1.1.1. Tìm kiếm tuyến tính bằng so khớp chuỗi ......................................... 44

4.1.1.2. Tìm kiếm tuyến tính sử dụng hàm quy hoạch động .......................... 45

4.1.2. Kết quả thử nghiệm tìm kiếm bằng giải thuật di truyền ...................... 46

4.2. Phát triển phần mềm ứng dụng .................................................. ............ 50

KẾT LUẬN VÀ ĐỀ NGHỊ .................................................. ...................... 51

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

PHỤ LỤC............................................. .................................................. ..... 54