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

Đề tài: 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


Luận văn dài 76 trang

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