Thạc Sĩ 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

MỤC LỤC
MỞ ĐẦU . 1
Chương 1. TÌM KIẾM MẪU TRONG VĂN BẢN THEO CÁCH
TIẾP CẬN OTOMAT MỜ 5
1.1. Tổng quan về tìm kiếm mẫu trên văn bản 5
1.1.1 Giới thiệu chung về vấn đề tìm kiếm văn bản 5
1.1.2. Các dạng tìm kiếm và các kết quả nghiên cứu 7
1.1.2.1. Tìm đơn mẫu . 7
1.1.2.2. Tìm đa mẫu 8
1.1.2.3. Tìm mẫu mở rộng 9
1.1.2.4. Tìm kiếm xấp xỉ . 10
1.1.2.4.1. Phát biểu bài toán . 10
1.1.2.4.2. Các tiếp cận tìm kiếm xấp xỉ . 11
1.1.2.4.3. Độ tương tự giữa hai xâu 12
1.1.3. Tìm kiếm trong văn bản nén và mã hoá 14
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
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
2.2.3.2. Otomat so mẫu . 42
2.2.4. Độ gần tựa ngữ nghĩa 43
2.2.4.1. Ý tưởng về độ gần . 43
2.2.4.2. Thuật toán sơ bộ tính độ gần 44
2.2.4.2.1. Ý tưởng . 44
2.2.4.2.2. Thuật toán chi tiết . 44
2.2.4.3. Giải thích độ mờ của mô hình 45
2.3. Kết luận chương 2 . 46
Chương 3. TÌM KIẾM MẪU TRONG VĂN BẢN NÉN VÀ MÃ
HOÁ 47
3.1. Tiếp cận tìm kiếm tổng quát trên văn bản nén và mã hoá . 47
3.2. Tìm kiếm trên văn bản nén 50
3.2.1. Các mô hình nén văn bản 50
3.2.2. Thuật toán tìm kiếm trên dữ liệu nén dạng text . 50
3.3. Tìm kiếm trên văn bản mã hóa . 55
3.3.1. Tìm kiếm trên văn bản mã hóa dạng khối kí tự . 55
3.3.2. Mã đàn hồi 55
3.3.3. Tìm kiếm trên văn bản mã hóa bởi mã đàn hồi . 58
3.3.3.1. Ý tưởng chung . 58
3.3.3.2. Phương pháp đánh giá độ mờ xuất hiện mẫu trên văn bản
mã hóa 59
3.3.3.2.1. Bài toán 59
3.3.3.2.2. Mô tả phương pháp . 59
3.3.3.2.3. Chi tiết hóa các otomat trong thuật toán . 60
3.3.3.2.4. Thuật toán tìm kiếm mẫu dựa trên otomat . 61
3.3.4. Tìm kiếm trên văn bản mã hóa hai tầng 63
3.4. Kết luận chương 3 . 64
KẾT LUẬN . 65
TÀI LIỆU THAM KHẢO 67