Bài toán tìm kiếm văn bản sử dụng giải thuật di truyền

[magtarita]

Download Luận văn Bài toán tìm kiếm văn bản sử dụng giải thuật di truyền

Download miễn phí Luận văn Bài toán tìm kiếm văn bản sử dụng giải thuật di truyền

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


http://cloud.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2013-10-26-luan_van_bai_toan_tim_kiem_van_ban_su_dung_giai_th.GT1E7IdxOM.swf /tai-lieu/de-tai-ung-dung-tren-liketly-42345/
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung:

1
1 1 1 0 1 1 0 1 0 1 0 1
0 0 1 0 1 0 1 1 1 1 0 1
1 1 1 1 1 0 0 0 1 0 1 0
1 1 1 1 1 0 1 1 1 1 0 1
1 3170 0.1364
2 915 0.1818
3 2524 0.1364
4 1242 0.2727
5 3647 0.0909
6 376 0.1818
7 2573 0.2273
8 12 0.2273
9 2162 0.1364
10 2619 0.1364
11 467 0.1364
12 2185 0.0909
13 2050 0.1364
14 208 0.2273
15 3621 0.0000
16 2731 0.4091
17 3797 0.1818
18 701 0.1818
19 3978 0.0909
20 4029 0.1364
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 1 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
1 0 1 0 1 0 1 0 1 1 1 0
- KHỞI TẠO: Gia tri tot nhat = 0.409 ca the thu 16 tai vi tri 2731 trong van ban
- KẾT THÚC: Gia tri tot nhat = 1.000 ca the thu 1 tai vi tri 2734 trong van ban
- Thời gian thực hiện (%second): 33
Test 5:
KHỞI TẠO Cá thể Vị trí Hàm mục tiêu KẾT THÚC
1 0 1 1 1 0 0 1 0 1 1 0
1 1 0 0 1 0 1 1 1 1 1 0
0 0 0 0 1 0 0 0 1 1 0 1
0 1 1 0 1 0 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 0 1 1
1 0 0 0 0 1 1 1 0 1 0 1
1 0 1 1 0 1 1 0 1 0 0 0
1 2966 0.0455
2 3262 0.0000
3 141 0.1818
4 1666 0.1818
5 4091 0.1818
6 2165 0.1364
7 2920 0.1364
0 0 1 1 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 1 1 0 0 0
0 0 1 1 0 0 0 1 0 1 0 0
0 0 1 1 0 0 0 1 0 1 0 0
0 1 1 1 0 0 0 1 0 0 0 0
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
55
0 1 1 0 1 1 0 1 1 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 1 1 0 1 0
1 0 0 0 1 1 1 1 1 0 1 0
1 0 1 0 1 0 0 1 1 0 0 1
1 1 1 0 1 0 0 0 1 0 1 1
1 0 0 1 0 1 1 0 1 1 1 1
0 1 0 1 0 1 1 0 1 1 0 1
1 1 1 0 0 1 1 1 0 1 1 1
0 0 1 1 1 1 1 0 1 0 1 0
0 0 1 1 1 1 1 0 1 0 0 1
0 0 1 1 1 0 0 1 0 0 0 0
0 0 0 0 1 0 0 1 0 1 1 0
8 1752 0.0909
9 768 0.2273
10 2202 0.2727
11 2298 0.2273
12 2713 0.1364
13 3723 0.1364
14 2415 0.1818
15 1389 0.0000
16 3703 0.2273
17 1002 0.0000
18 1001 0.0000
19 912 0.2727
20 150 0.1818
1 0 1 1 0 0 1 1 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 1 1 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0
- KHỞI TẠO: Gia tri tot nhat = 0.273 ca the thu 10 tai vi tri 2202 trong van ban
- KẾT THÚC: Gia tri tot nhat = 0.318 ca the thu 1 tai vi tri 784 trong van ban
- Thời gian thực hiện (%second): 38
Test 10:
KHỞI TẠO Cá thể Vị trí Hàm mục tiêu KẾT THÚC
1 1 0 0 1 0 1 0 0 1 0 0
1 0 1 0 0 1 1 1 1 0 0 0
0 0 1 1 0 1 0 0 0 0 1 0
1 0 0 0 0 1 1 1 1 0 1 0
1 1 0 1 1 1 1 1 0 0 0 0
1 1 1 1 1 0 0 1 1 0 0 0
1 1 0 0 0 1 0 1 0 0 1 0
1 0 0 1 1 1 1 0 0 1 0 0
0 1 1 1 0 1 0 0 1 0 0 0
0 0 0 0 1 1 0 0 0 1 1 1
0 1 1 1 1 0 0 0 0 0 1 1
0 0 1 0 0 0 1 0 0 1 1 0
0 0 0 1 0 0 1 1 1 1 1 1
1 1 0 0 1 0 1 0 0 0 0 0
0 1 1 0 0 1 0 1 0 1 0 1
0 1 1 0 0 1 0 1 0 0 1 1
0 1 0 0 0 1 1 0 0 0 0 1
1 0 1 1 1 1 1 0 1 1 1 1
1 0 1 1 0 1 0 1 0 0 1 1
1 0 1 0 0 1 0 0 1 1 0 1
1 3236 0.0455
2 2680 0.2273
3 834 0.3182
4 2170 0.1818
5 3568 0.0000
6 3992 0.1364
7 3154 0.0000
8 2532 0.1818
9 1864 0.2273
10 199 0.1818
11 1923 0.1818
12 550 0.2727
13 319 0.0455
14 3232 0.0455
15 1621 0.1364
16 1619 0.1364
17 1121 0.3182
18 3055 0.1818
19 2899 0.0455
20 2637 0.1364
0 1 0 0 0 1 0 0 1 0 0 1
0 1 0 0 0 1 0 0 1 0 0 0
0 1 0 0 0 1 0 0 1 0 0 0
0 1 0 0 0 1 0 0 1 0 0 1
0 1 0 0 0 1 0 0 1 0 0 0
0 1 0 0 0 1 0 0 1 0 0 0
0 1 0 0 0 1 0 0 1 0 0 0
0 1 0 0 0 1 0 0 1 0 0 0
0 1 0 0 0 1 0 0 1 0 0 0
0 1 0 0 0 1 0 0 1 0 0 0
0 1 0 0 0 1 0 0 1 0 0 0
0 1 0 0 0 1 0 0 1 0 0 0
0 1 0 0 0 1 0 0 1 0 0 0
0 1 0 0 0 1 0 0 1 0 0 1
0 1 0 0 0 1 0 0 1 0 0 1
0 1 0 0 0 1 0 0 1 0 0 0
0 1 0 0 0 1 0 0 1 0 0 0
0 1 0 0 0 1 0 0 1 0 0 0
0 1 0 0 0 1 0 0 1 0 0 0
0 1 0 0 0 1 0 0 1 0 0 0
- KHỞI TẠO: Gia tri tot nhat = 0.318 ca the thu 3 tai vi tri 834 trong van ban
- KẾT THÚC: Gia tri tot nhat = 0.500 ca the thu 2 tai vi tri 1096 trong van ban
- Thời gian thực hiện (%second): 33
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
56
Test 15:
KHỞI TẠO Cá thể Vị trí Hàm mục tiêu KẾT THÚC
0 0 1 1 1 0 1 1 1 0 0 1
0 1 0 0 1 1 1 0 1 1 1 0
0 0 1 1 0 0 0 0 0 1 1 1
1 0 1 1 0 0 0 0 1 0 1 1
1 1 0 1 0 0 0 1 0 1 1 0
0 1 1 0 1 0 1 0 1 0 1 1
0 0 1 0 0 1 1 1 1 1 1 1
0 1 0 0 0 1 0 1 1 0 1 0
0 1 1 0 0 1 1 1 1 0 1 1
1 0 0 0 1 1 1 1 1 0 1 1
1 1 0 0 0 1 1 0 0 0 1 1
1 0 0 0 1 1 1 0 0 1 0 1
1 1 0 1 1 0 0 0 0 0 0 1
0 0 1 0 0 0 0 1 1 1 0 1
0 0 0 1 0 1 1 0 0 0 0 0
1 0 1 1 1 1 1 1 0 0 0 0
0 1 0 1 0 0 0 1 0 1 0 1
1 1 0 0 0 1 1 0 1 0 0 1
1 0 0 1 1 1 1 1 0 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0
1 953 0.3636
2 1262 0.2727
3 775 0.1364
4 2827 0.2273
5 3350 0.0000
6 1707 0.1818
7 639 0.1818
8 1114 0.4545
9 1659 0.2727
10 2299 0.1818
11 3171 0.0909
12 2277 0.1818
13 3457 0.1818
14 541 0.1818
15 352 0.0909
16 3056 0.2273
17 1301 0.2727
18 3177 0.0455
19 2544 0.1364
20 36 0.2727
0 0 0 0 0 1 1 1 1 1 1 1
0 1 0 0 0 1 0 1 1 1 0 1
0 1 0 0 0 1 0 1 1 1 0 1
0 1 0 0 0 1 0 1 1 1 0 1
0 1 0 0 0 1 0 1 1 1 1 0
0 1 0 0 0 1 1 1 1 1 0 1
0 1 0 0 0 1 0 1 1 1 0 0
0 1 0 0 0 1 0 1 1 1 0 1
0 1 0 0 0 1 0 1 1 1 0 1
0 1 0 0 0 1 1 1 1 1 0 1
0 1 0 0 0 1 0 1 1 1 1 0
0 1 0 0 0 1 0 1 1 1 0 1
0 1 1 0 0 1 0 1 1 1 0 1
0 1 0 0 0 1 0 1 1 1 0 1
0 1 0 0 0 1 0 1 1 1 0 1
0 1 0 0 0 1 0 1 0 1 0 1
0 1 0 0 0 1 0 1 1 1 0 1
0 1 0 0 0 1 0 1 1 1 1 0
0 1 0 0 0 1 0 1 1 1 0 1
0 1 0 0 0 1 0 1 1 1 0 1
- KHỞI TẠO: Gia tri tot nhat = 0.455 ca the thu 8 tai vi tri 1114 trong van ban
- KẾT THÚC: Gia tri tot nhat = 1.000 ca the thu 2 tai vi tri 1117 trong van ban
- Thời gian thực hiện (%second): 43
Test 20:
KHỞI TẠO Cá thể Vị trí Hàm mục tiêu KẾT THÚC
1 1 0 1 1 1 1 0 1 1 1 1
0 1 1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 0 1 1 1 1 0
0 1 1 1 0 1 0 0 1 1 0 0
0 0 0 0 1 1 0 1 1 0 1 0
1 0 0 1 0 0 1 1 0 1 1 1
1 1 0 1 1 0 0 0 1 1 0 0
0 0 1 0 1 0 1 1 1 0 0 0
1 0 1 0 0 0 1 1 1 0 1 1
1 0 0 1 0 1 1 0 1 0 1 1
1 0 1 0 0 0 0 1 1 0 1 0
1 1 0 1 0 0 1 1 0 0 0 1
0 0 0 1 0 1 1 1 0 1 0 0
0 1 1 0 0 0 0 1 1 1 0 0
0 1 0 0 1 0 0 1 1 1 1 0
0 0 1 0 1 0 0 0 1 0 1 1
1 3567 0.0000
2 2044 0.1364
3 2014 0.0455
4 1868 0.1818
5 218 0.2273
6 2359 0.2273
7 3468 0.0000
8 696 0.1818
9 2619 0.1364
10 2411 0.1818
11 2586 0.1818
12 3377 0.1364
13 372 0.2273
14 1564 0.1364
15 1182 0.1364
16 651 0.1818
1 0 1 1 0 1 1 1 1 0 0 1
1 0 1 0 0 1 1 1 1 0 0 1
1 0 1 0 0 1 1 1 1 0 0 1
1 0 1 0 0 1 1 1 1 0 0 1
1 0 1 0 0 1 1 1 1 0 0 1
1 0 1 1 0 1 1 1 1 0 0 1
1 0 1 0 0 1 1 1 1 0 0 1
1 0 1 0 0 1 1 1 1 0 0 1
1 0 1 0 0 1 1 1 1 0 0 1
1 0 1 0 0 1 1 1 1 0 0 1
1 1 1 0 0 1 1 1 1 0 0 1
1 0 1 0 0 1 1 1 1 0 0 1
1 0 1 0 0 1 1 1 1 0 0 1
1 0 1 0 0 1 1 1 1 0 0 1
1 0 1 0 0 1 1 1 1 0 0 1
1 0 1 0 0 1 1 1 1 0 0 1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
57
0 1 0 0 1 1 1 0 0 0 0 0
1 0 0 1 1 0 0 1 1 0 1 1
0 1 1 1 0 1 0 0 0 1 0 0
0 0 0 1 0 0 0 0 1 1 1 0
17 1248 0.2273
18 2459 0.1364
19 1860 0.1818
20 270 0.0909
1 0 1 0 0 1 1 1 1 0 0 1
1 0 1 0 0 1 1 1 1 0 0 1
1 0 1 0 0 1 1 1 1 0 0 1
1 0 1 0 0 1 1 1 1 0 0 1
- KHỞI TẠO: Gia tri tot nhat = 0.227 ca the thu 5 tai vi tri 218 trong van ban
- KẾT THÚC: Gia tri tot nhat = 0.364 ca the thu 2 tai vi tri 2681 trong van ban
- Thời gian thực hiện (%second): 32
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
58
Phụ lục 2: Kết quả chi tiết xuất hiện vượt ngưỡng (với ngưỡng = 0.8)
Xem kết quả chi tiết của 5 lần xuất hiện vượt ngưỡng (với ngưỡng =
0.8) trong bảng 4.6.
TheHe Max CaThe ViTri(trong van ban)
KT 0.636 18 10
1 0.818 1 8
2 0.818 9 8
3 0.818 3 8
4 0.818 6 8
5 0.818 1 8
6 0.909 12 7
7 0.909 4 7
8 0.909 1 7
9 0.909 1 7
10 0.909 1 7
11 0.909 2 7
12 0.909 1 7
13 0.909 1 7
14 0.909 1 7
15 0.909 2 7
16 0.909 1 7
17 0.909 1 7
18 0.909 1 7
19 1.000 13 6
20 1.000 13 6
21 1.000 17 6
22 1.000 7 6
23 0.909 1 7
24 0.909 1 7
25 1.000 2 6
26 1.000 5 6
27 0.909...

 

Tags: code tìm kiếm văn bản bằng thuật di truyền, tìm kiếm văn bản áp dụng thuật toán di truyền