Luận văn 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

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN ĐỖ THỊ HẠNH 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 Chuyên ngành: Khoa học máy tính Mã số: 60 48 35 01 LUẬN VĂN THẠC SĨ Người hướng dẫn: PGS.TS. ĐOÀN VĂN BAN Thái Nguyên - 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN ĐỖ THỊ HẠNH 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 Chuyên ngành: Khoa học máy tính Mã số: 60 48 35 01 LUẬN VĂN THẠC SĨ Người hướng dẫn: PGS.TS. ĐOÀN VĂN BAN Thái Nguyên - 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên LỜI CẢM ƠN Em xin chân thành cảm ơn các thầy, cô khoa Công nghệ thông tin trường Đại học Thái Nguyên đã tạo điều kiện giúp đỡ và truyền đạt cho em những kiến thức về chuyên ngành và những kiến thức xã hội. Đặc biệt, em xin bày tỏ lòng biết ơn sâu sắc đến PGS.TS. Đoàn Văn Ban - Viện Khoa học Công nghệ Việt Nam. Thầy đã trực tiếp hướng dẫn và giúp đỡ em hoàn thành luận văn. Mặc dù, trong quá trình làm luận văn em đã gặp nhiều khó khăn nhưng thầy luôn động viên, chia sẻ, đó là nguồn động lực lớn giúp em vượt qua. Thầy chính là tấm gương cho em trong công tác giảng dạy, nghiên cứu khoa học, cũng như trong cuộc sống. Em xin cảm ơn thầy. Em không quên sự động viên, khích lệ của gia đình, bạn bè và những người thân đã giúp đỡ em vượt qua mọi khó khăn để em hoàn thành khoá học. Em xin chân thành cảm ơn! Thái Nguyên, tháng 11 năm 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyê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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Các ký hiệu  Xâu rỗng wi Ký tự thứ i của xâu w w(f, d) Xâu con (hay khúc con) độ dài f của xâu w, kết thúc ở vị trí d trên w w1 ≤ s w2 Xâu w1 là khúc đuôi của w2 w1 ≤ ls w2 Xâu w1 là khúc đuôi dài nhất của w2 w(t) hoặc preft(w) Khúc đầu độ dài t của xâu w suft(w) Khúc cuối độ dài t của xâu w |A| Lực lượng của tập A Các chữ viết tắt NFA Otomat đa định hữu hạn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên DANH MỤC CÁC HÌNH VẼ Hình 1.1. Ý nghĩa của mảng next ......................................................... 19 Hình 1.2. Ý nghĩa của mảng next tại vị trí m + 1 .................................. 19 Hình 2.1. Dịch chuyển con trỏ trên mẫu ............................................... 32 Hình 2.2. Ý tưởng chung của thuật toán KMP-BM mờ ........................ 35 Hình 2.3. Một ví dụ với các khối độ dài t = 3 ....................................... 44 Hình 2.4. Tập mờ mô tả độ gần tựa ngữ nghĩa của mẫu P so với xâu đích S................................................................. 45 Hình 3.1. Phương pháp so mẫu trên miền nén có sử dụng otomat mờ .. 48 Hình 3.2. Phương pháp so mẫu không giải mã ..................................... 49 Hình 3.3. Queue trước (a) và sau (b) khi thực hiện thủ tục Decompress 52 Hình 3.4. Queue trước (a) và sau (b) bước nhảy n2‟ ............................. 53 Hình 3.5. Đồ thị xây dựng khái niệm tích đàn hồi ................................ 56 Hình 3.6. Đồ thị xác định mã đàn hồi ................................................... 58 Hình 2.7. Quá trình mã hóa hai tầng ..................................................... 64 Hình 2.8. Quá trình giải mã hai tầng ..................................................... 64 Hình 2.9. Quá trình tìm kiếm mẫu trên văn bản mã hóa hai tầng .......... 64 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1 MỞ ĐẦU 1. Lý do chọn đề tài Bộ não của con người có thể xử lý thông tin ở hai mức: - Mức định lượng (chính xác) - Mức định tính (không chính xác, bất định, mơ hồ, không chắc chắn, nhập nhằng, không rõ ràng, mờ) Tính thông minh trong quá trình xử lý thông tin thể hiện ở khả năng xử lý thông tin định tính. Đây là điều mà thế hệ máy tính hiện nay đang hướng tới. Máy tính ngày nay đã được sử dụng trong hầu hết các lĩnh vực và đã góp phần quan trọng vào việc thúc đẩy sự phát triển kinh tế, xã hội, khoa học kỹ thuật, … Máy tính ra đời nhằm phục vụ cho những mục đích nhất định của con người. Với tất cả sự xử lý của máy tính để lấy thông tin hữu ích và trong quá trình xử lí đó một vấn đề đặc biệt quan trọng là tìm kiếm thông tin với khối lượng lớn, độ chính xác cao, thời gian nhanh nhất. Tìm kiếm thông tin thì bài toán đóng vai trò quan trọng là bài toán so mẫu, với mẫu có thể ở bất kỳ kiểu dữ liệu nào, từ văn bản đến các loại dữ liệu đa phương tiện khác (ảnh, video, âm thanh, …). Trên thực tế có rất nhiều ứng dụng tìm kiếm thông tin như: công cụ tìm kiếm của các hệ điều hành, khai phá web trên Internet, ... Để tìm kiếm thông tin thì cần phải xem thông tin đó lưu trữ dưới dạng dữ liệu nào? Dữ liệu được lưu trữ dưới nhiều dạng, song phổ biến nhất vẫn là dạng text nên chúng tôi chọn đề tài này cụ thể là tìm kiếm văn bản text. Tìm kiếm văn bản text nếu như những văn bản có khối lượng lớn thì có thể mất nhiều thời gian với những thuật toán kinh điển. Vậy đặt ra vấn đề tìm kiếm văn bản nhưng ở dạng nén sẽ nhanh hơn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 Nên chúng tôi đi vào làm cụ thể là tìm kiếm mẫu trong văn bản nén. Ngoài ra, văn bản nén cũng là văn bản mã hoá nhưng dung lượng giảm nhiều so với văn bản nguồn nên chúng tôi đi nghiên cứu mở rộng thêm văn bản mã hoá. Trong các bài toán tìm kiếm, để tìm kiếm nhanh đáp ứng được nhu cầu và không chỉ tìm kiếm cứng nhắc trong với từ khoá đưa ra. Người dùng mong muốn có thể tìm được cả những thông tin liên quan gợi ý cho người dùng. Vậy bài toán đó thì việc tìm kiếm theo hệ mờ là rất cần thiết. Vì vậy cần phải xây dựng các thuật toán mềm dẻo cho phép phát huy được sức mạnh của tìm kiếm mờ và đặc biệt cho phép sử dụng được nguồn tri thức giàu tính chuyên gia trong những tính huống tìm kiếm phức tạp. 2. Mục đích nghiên cứu Luận văn tập trung nghiên cứu về tiếp cận otomat mờ và xây dựng một số giải thuật tiếp cận otomat mờ để tìm kiếm mẫu của văn bản nén. 3. Đối tượng nghiên cứu - Tìm hiểu về otomát mờ. - Tìm hiểu về văn bản nén và mã hoá. - Cách so mẫu theo hướng tiếp cận otomát mờ. 4. Giả thuyết khoa học Nếu chúng ta sử dụng tiếp cận otomát mờ thì chúng ta không những tìm kiếm được những thông tin chính xác mong muốn mà còn tìm kiếm được những thông tin liên quan trong thời gian nhanh nhất, đáp ứng nhu cầu người dùng. 5. Nhiệm vụ nghiên cứu - Nghiên cứu về otomat mờ. - Nghiên cứu về nén và mã hoá. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3 - Đưa ra các thuật toán tìm kiếm, các kết quả nghiên cứu trên. - Luận văn cũng mong muốn nêu ra được một số hướng nghiên cứu mở rộng về tìm kiếm mẫu theo hướng tiếp cận otomat mờ. 6. Phạm vi nghiên cứu Luận văn tập trung nghiên cứu các kiến thức có liên quan, các cơ sở lý thuyết: Hệ mờ, otomat mờ, các thuật toán tìm kiếm mẫu, các thuật toán tìm kiếm mẫu theo cách tiếp cận otomat mờ. 7. Phương pháp nghiên cứu Otomat mờ được xem là sự tổng quát hoá của otomat hữu hạn. Trong đó tập trạng thái là các tập mờ, hàm chuyển trạng thái và trạng thái kết thúc được biểu diễn qua các quan hệ mờ. Theo đánh giá của các chuyên gia, các hệ hình thức otomat mờ là mô hình toán học thích hợp với một số hệ thống quyết định, điều khiển, nhận dạng và đặc biệt được dùng trong đoán nhận mẫu. Tận dụng những ưu điểm trên và sự kết hợp với lý thuyết mờ, sử dụng một số hệ hình thức otomat mờ để giải bài toán so xâu mẫu. Để thấy rõ được tiếp cận otomat mờ chúng tôi chọn một bài toán cụ thể là tìm kiếm mẫu trong văn bản nén và mã hoá. Trong phạm vi luận văn, bài toán có thể làm với các tệp dữ liệu nén mà không cần giải nén toàn bộ. Ý tưởng cơ bản là đọc tuần tự trên tệp nén và mở nén một số mã nén, lưu kết quả giải nén cục bộ vào vùng đệm và áp dụng thuật toán theo tiếp cận mờ trên vùng đệm này. Nội dung luận văn gồm có phần mở đầu, 3 chương, phần kết luận, tài liệu tham khảo và phụ lục. Chương 1- Giới thiệu chung về vấn đề tìm kiếm văn bản, trọng tâm là bài toán so xâu mẫu. Hướng tiếp cận của luận văn cho bài toán so mẫu, chính xác và xấp xỉ, trên môi trường nén và mã hoá hoặc không sử dụng một số hệ hình thức otomat mờ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4 Chương 2 - Đưa ra ví dụ về bài toán so mẫu xấp xỉ và chính xác.... Chương 3- Giới thiệu một số thuật toán tìm kiếm mẫu trên môi trường văn bản nén và mã hoá. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5 Chương 1. TÌM KIẾM MẪU TRONG VĂN BẢN THEO CÁCH TIẾP CẬN OTOMAT MỜ 1.1. Tổng quan về tìm kiếm mẫu trên văn bản 1.1.1 Giới thiệu chung về vấn đề tìm kiếm văn bản Kiểu văn bản (Text) là dạng biểu diễn dữ liệu hay gặp nhất trong các hệ thống thông tin. Tìm kiếm văn bản (text searching) là vấn đề chủ yếu thuộc lĩnh vực quản lý văn bản. Một dạng cơ bản và tổng quát hơn là tìm kiếm chuỗi (hay xâu) (String searching) hay đối sánh chuỗi (string matching). Khái niệm “chuỗi” ở đây khá rộng, có thể là chuỗi văn bản gồm một dãy các chữ, số và ký tự đặc biệt, có thể là chuỗi nhị phân hay chuỗi gene,… Tìm kiếm chuỗi là bài toán tìm ra một mẫu (pattern) với một số đặc tính nào đó trong chuỗi các ký hiệu cho trước, vì thế bài toán này còn được gọi là so xâu mẫu hay có thể gọi ngắn gọn là so mẫu (string pattren matching). Dạng đơn giản nhất là tìm sự xuất hiện một xâu cho trước trong một chuỗi (còn gọi là xâu đích). Thực ra, đây là một trong những bài toán kinh điển nhất và phổ dụng nhất của khoa học máy tính, bởi hầu hết các ứng dụng đều có sự đối sánh chuỗi ở một dạng nào đó. Các phương pháp tìm kiếm văn bản và tìm kiếm chuỗi chính là cốt lõi trong rất nhiều loại phần mềm khác nhau như: các tiện ích của hệ điều hành, các hệ thống trích rút dữ liệu (data retrieval system), trình soạn thảo văn bản (text editors), máy tìm kiếm (search engine) trên internet, phân tích và tìm kiếm chuỗi gene trong sinh vật học, xử lý ngôn ngữ tự nhiên, tìm kiếm text trong các hệ cơ sở dữ liệu,… Thời gian gần đây, vấn đề đối sánh chuỗi càng trở nên quan trọng và được quan tâm nhiều do sự tăng trưởng nhanh chóng của các hệ thống Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 6 trích rút thông tin và các hệ thống sinh- tin học. Một lý do nữa, bởi con người ngày nay không chỉ đối mặt với một lượng thông tin khổng lồ mà còn đòi hỏi những yêu cầu tìm kiếm ngày càng phức tạp. Các mẫu đưa vào không chỉ đơn thuần là một xâu ký tự mà còn có thể chứa các ký tự thay thế (wild card), các khoảng trống (gaps) và các biểu thức chính quy (regular expresions). Sự “tìm thấy” không đơn giản là xuất hiện chính xác mẫu mà còn cho phép có “một ít sai khác” giữa mẫu và xuất hiện của nó trong văn bản. Từ đó, bên cạnh vấn đề kinh điển là “tìm kiếm chính xác”, nảy sinh một hướng nghiên cứu hết sức thú vị đó là “tìm kiếm xấp xỉ” (approximate matching, approximate searching). Cho đến nay, đã có nhiều hướng tiếp cận giải các bài toán so mẫu được đưa ra, từ những phương án rất lý thuyết đến các phương án rất thực dụng. Hướng nghiên cứu lý thuyết đã nêu ra nhiều thuật toán quan trọng, song lại chưa đạt hiệu quả cao trong thực hành, nếu không tận dụng được những khả năng trong đặc điểm của kiến trúc máy tính. Hiện nay, tiêu biểu cho những thuật toán mang tính chất thực hành theo hướng nâng cao khả năng tận dụng kiến trúc máy tính là tiếp cận song song bit (bit- parallelism) 1, 2, 3. Có thể phân các loại thuật toán so mẫu theo 2 hướng. Thứ nhất là các thuật toán trực tuyến (on-line), trong đó chỉ mẫu được tiền xử lý (thường sử dụng otomat hoặc dựa trên các đặc tính kết hợp trên xâu), còn văn bản thì không. Thứ hai là giải pháp tiền xử lý văn bản theo cách xây dựng một cấu trúc dữ liệu trên văn bản (lập chỉ mục). Nhiều ứng dụng cần sử dụng giải pháp này mặc dù đã có những thuật toán trực tuyến nhanh bởi chúng cần phải điều khiển một lượng văn bản quá lớn nên không có thuật toán trực tuyến nào có thể thực hiện một cách hiệu quả. Tìm kiếm trên chỉ mục thực ra cũng dựa trên tìm kiếm on-line. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 7 1.1.2. Các dạng tìm kiếm và các kết quả nghiên cứu Phân loại các thuật toán tìm kiếm dựa trên các đặc tính của mẫu ta có các dạng: tìm đơn mẫu, tìm đa mẫu (mẫu là tập các xâu), tìm mẫu mở rộng (extended strings), tìm biểu thức chính qui (regular expressions) với hai hướng tiếp cận là tìm kiếm chính xác và xấp xỉ. Nội dung của luận văn chỉ tập trung giải quyết vấn đề để tìm đơn mẫu, chính xác và xấp xỉ. 1.1.2.1. Tìm đơn mẫu Bài toán 1.1: Cho xâu mẫu P dộ dài m, P = P1 P2… Pm , và xâu độ dài n, S = S1 S 2… Sn (S thường dài, là một văn bản) trên cùng một bảng chữ A. Tìm tất cả các xuất hiện của xâu P trong S. Trong các thuật toán so mẫu thường sử dụng các khái niệm: Khúc đầu, khúc cuối, khúc con hay xâu con của một xâu, được định nghĩa như sau: Cho 3 xâu x, y, z. Ta nói x là khúc đầu (prefix) của xâu xy, là khúc cuối (suffix) của xâu yx và là khúc con hay xâu con (factor) của xâu yxz. Thuật toán “thô” nhất và đã được sử dụng rộng rãi là Brute- Force. Phương pháp này đơn giản chỉ là lần lượt bắt đầu từ vị trí trong S để đối sánh với mẫu P. Mặc dù có tốc độ chậm, thời gian xấu nhất tỉ lệ với tích m.n, song trong nhiều ứng dụng thực tế các chuỗi phát sinh ra thường có thời gian xử lý thực sự luôn tỷ lệ với m + n. Ngoài ra, một ưu điểm khác là nó thích hợp với cấu trúc của hầu hết các hệ máy tính. Cho đến nay, rất nhiều thuật toán so đơn mẫu được đưa ra 4 5, 2, trong đó kinh điển nhất là KMP. Có thể xem như có ba tiếp cận chung cho các thuật toán so mẫu, phụ thuộc vào cách duyệt tìm mẫu trong văn bản. Việc đánh giá tốc độ của các thuật toán dựa trên kích cỡ của mẫu P và bảng chữ A. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 8 Trong tiếp cận thứ nhất, lần lượt từng ký tự của văn bản S được đọc và tại mỗi vị trí, sau khi đối sánh với một ký tự của mẫu sẽ cập nhật sự thay đổi để nhận ra một khả năng xuất hiện mẫu. Hai thuật toán điển hình theo tiếp cận này là KMP và Shift - Or. Tiếp cận thứ hai sử dụng một “cửa sổ trượt” trên xâu S và tìm kiếm mẫu trong cửa sổ này. Tại mỗi vị trí trong cửa sổ, cần tìm một khúc cuối của cửa sổ mà là khúc cuối của xâu mẫu P. Thuật toán BM là một điển hình cho tiếp cận này và một biến thể đơn giản hoá của nó là Horspool. Tiếp cận thứ ba mới xuất hiện gần đây cho ra đời các thuật toán hiệu quả về thực hành đối với mẫu P đủ dài. Cũng tương tự như tiếp cận thứ hai, song tại mỗi thời điểm sẽ tìm khúc cuối dài nhất của cửa sổ mà là khúc con của mẫu. Thuật toán đầu tiên theo tiếp cận này là BDM và khi P đủ ngắn, một phiên bản đơn giản hơn, hiệu quả hơn là BNDM. Với những mẫu dài, thuật toán BOM được đánh giá là nhanh nhất 2. 1.1.2.2. Tìm đa mẫu Bài toán 1.2: Cho một mẫu P gồm tập các từ khoá w1, w2,….,w k và xâu vào S = S1S2…Sn trên cùng bảng chữ A. Tìm sự xuất hiện của các từ khoá wi trong S. Một cách đơn giản để tìm nhiều từ khoá trong một xâu đích là sử dụng thuật toán so đơn mẫu nhanh nhất đối với mỗi từ khoá. Rõ ràng phương pháp này không hiệu quả khi số lượng từ khoá lớn. Cả ba tiếp cận tìm đơn mẫu ở trên đều được mở rộng cho tìm đa mẫu. Hai điển hình theo tiếp cận thứ nhất là thuật toán nổi tiếng Aho- Corasisk 4, có tốc độ cải thiện đáng kể khi số từ khoá nhiều và thuật Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 9 toán Multiple Shift- And, được sử dụng hiệu quả khi tổng độ dài của mẫu P rất nhỏ 2. Theo tiếp cận thứ hai có thuật toán nổi tiếng Commentz - Walter 4, trong đó kết hợp ý tưởng của Boyer - Moore và Aho- Corasisk , nhanh về lý thuyết, song lại không hiệu quả trong thực hành [2]. Một mở rộng của thuật toán Horspool là Set Horspool. Cuối cùng là thuật toán Wu-Manber, một phương pháp pha trộn giữa tiếp cận tìm kiếm hậu tố (suffix search approach) và một kiểu hàm băm, được đánh giá là nhanh trong thực hành. Trong tiếp cận thứ ba đã có những mở rộng từ thuật toán BOM và SBOM; tương tự với Shift- Or BNDM là Multiple BNDM 2. 1.1.2.3. Tìm mẫu mở rộng Trong nhiều ứng dụng, tìm kiếm mẫu không chỉ đơn giản là dãy các ký tự. Sau đây là một số mở rộng thường thấy trong các ứng dụng: Mở rộng đơn giản nhất cho phép mẫu là một dãy các lớp hay các tập ký tự, giả sử được đánh số thứ tự là 1,2,…,m. Bất kỳ ký tự nào trong lớp thứ i cũng có thể được xem là ký tự thứ i của mẫu. Mở rộng thứ hai là giới hạn khoảng trên độ dài: Một số vị trí trên mẫu được ấn định để khớp với một dãy văn bản nào đó có độ dài nằm trong một khoảng xác định trước. Điều này thường được sử dụng trong các ứng dụng sinh- tin học, chẳng hạn tìm mẫu PROSITE. Mở rộng thứ ba sử dụng các ký tự tùy chọn và ký tự lặp. Trong xuất hiện của mẫu trên văn bản, các ký tự tuỳ chọn có thể có hoặc không có, còn các ký tự lặp có thể có một hoặc lặp nhiều lần. Các vấn đề nảy sinh từ ba hướng mở rộng trên và những kết hợp từ ba hướng này được giải quyết bằng cách điều chỉnh lại thuật toán Shift - Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 10 Or và BNDM, trong đó có sử dụng cơ chế song song bit để mô phỏng otomat đa định, cho phép tìm tất cả các xuất hiện của mẫu. 1.1.2.4. Tìm kiếm xấp xỉ 1.1.2.4.1. Phát biểu bài toán Tìm kiếm xấp xỉ là bài toán tìm sự xuất hiện của một mẫu trong văn bản, trong đó sự “khớp” giữa mẫu và xuất hiện của nó có thể chấp nhận k “lỗi” (k là một giới hạn cho trước). Có thể kể ra một vài kiểu “lỗi”, như những lỗi đánh máy hay lỗi chính tả trong hệ thống trích rút thông tin, những sự biến đổi chuỗi gen hay các lỗi đo đạc trong sinh- tin học và những lỗi truyền dữ liệu trong các hệ thống xử lý tín hiệu,… Vì trong các hệ thống tin học khó có thể tránh được các “lỗi” nên vấn đề tìm kiếm xấp xỉ càng trở nên quan trọng. Đặc biệt, khi sử dụng các hệ thống trích rút thông tin, người dùng ngày nay còn đòi hỏi cả những kết quả gần giống hoặc có được kết quả phù hợp trả về nếu có sự sai sót trong mẫu hay văn bản. Trong trường hợp này “lỗi” có thể do nhiều nguyên nhân khác nhau, có thể kể ra như sau: - Câu truy vấn sai chính tả, xâu tìm kiếm không đúng cú pháp so với văn bản. - Lỗi in ấn, sai lỗi chính tả, sử dụng dấu chấm sai,… - Do sự biến đổi hình thái từ trong một số ngôn ngữ. - Dữ liệu đưa vào cơ sở dữ liệu không chính xác, thường xảy ra với tên người, địa chỉ… - Thông tin người tìm đưa vào không chính xác, chỉ “đại loại”. Vì vậy, một vấn đề đặt ra cho các hệ thống trích rút thông tin ngày nay là đáp ứng được nhu cầu tìm kiếm “mềm dẻo” này của người sử dụng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 11 Bài toán so mẫu xấp xỉ tổng quát được phát biểu như sau: Bài toán 1.3. Cho văn bản T độ dài n và xâu mẫu P độ dài m trên cùng một bảng chữ A. Tìm các vị trí trong văn bản khớp với mẫu, cho phép nhiều nhất k lỗi. 1.1.2.4.2. Các tiếp cận tìm kiếm xấp xỉ Trong 2, tác giả chia các thuật toán tìm kiếm xấp xỉ hiện nay ra thành 4 loại. 1) Các thuật toán dựa trên quy hoạch động: Đây là tiếp cận xuất hiện đầu tiên và đã được dùng để tính khoảng cách soạn thảo (Edit Distance) (như trong 4). 2) Các thuật toán sử dụng otomat tìm kiếm: Trước tiên xây dựng một hàm của mẫu P và số lỗi k, sau đó tạo otomat đa định hữu hạn (như trong 9, 1). Đây là hướng tiếp cận được quan tâm nhiều vì có độ phức tạp thời gian trong trường hợp xấu nhất là O(n) (tuy nhiên đòi hỏi độ phức tạp không gian lớn hơn). 3) Các thuật toán sử dụng cơ chế song song bit (bit- parallelism): cách tiếp cận này cho ra rất nhiều thuật toán hiệu quả nhờ khai thác bản chất song song của các phép toán bit trên một từ máy trong bộ vi xử lý. Nói chung song song bit được dùng để song song hoá các kỹ thuật khác, như tạo otomat đa định, lập ma trận quy hoạch động. Nói chung kỹ thuật này làm việc khá tốt với mẫu ngắn và tăng tốc đáng kể so với những cài đặt không tận dụng khả năng song song của thanh ghi. Trong 2 các tác giả cũng chỉ ra một số thuật toán dùng cơ chế song song bit là BPR và BPD để tái tạo một otomat đa định hữu hạn và BDM để tái tạo các thuật toán quy hoạch động. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 12 4) Các thuật toán sử dụng cơ chế lọc: Cố gắng thu hẹp không gian tìm kiếm của bài toán bằng cách loại đi các văn bản mà chắc chắn không chứa một đoạn nào “khớp” với mẫu. Nói chung, phương pháp này đạt được bằng cách áp dụng kỹ thuật so mẫu chính xác cho các mẫu nhỏ của mẫu. Hai thuật toán hiệu quả nhất theo tiếp cận này là PEX và ABNDM 2. Trong PEX, mẫu được chia thành k + 1 đoạn và sắp xếp để tìm kiếm đa mẫu trên các đoạn này, vì ít nhất một đoạn phải có mặt trong một xuất hiện bất kỳ. Thuật toán ABNDM là một mở rộng của thuật toán BNDM, trong đó tái tạo otomat đa định hữu hạn cho tìm kiếm xấp xỉ. Nói chung, các thuật toán sử dụng cơ chế lọc làm việc tốt hơn tỷ lệ k/m nhỏ. Đối với trường hợp tỷ lệ k/m lớn, các thuật toán sử dụng cơ chế song song bit được đánh giá tốt hơn. Đối với bài toán tìm kiếm đa mẫu cũng đã có một số phát triển theo hướng xấp xỉ. Thuật toán MultiHash chỉ làm việc với k = 1 song rất hiệu quả khi số lượng mẫu lớn; MultiPEX là thuật toán hiệu quả nhất khi tỷ lệ k/m nhỏ; Multi BP xây dựng các NFA của tất cả các mẫu và sử dụng kết quả này làm bộ lọc, đây là lựa chọn tốt nhất cho tỷ lệ k/m cỡ trung bình. Một vài tiếp cận xấp xỉ cho bài toán tìm mẫu mở rộng và tìm biểu thức chính qui có thể kể ra như: thuật toán dựa trên quy hoạch động cho biểu thức chính qui; thuật toán sử dụng một otomat đa định hữu hạn cho phép có “lỗi”, thuật toán song song bit dựa trên phương pháp của BPR, … 1.1.2.4.3. Độ tương tự giữa hai xâu Để tìm kiếm xấp xỉ, cần sử dụng một hàm khoảng cách (distance function) đo độ tương tự giữa hai xâu. Tương tự ở đây được hiểu là giữa hai xâu ký tự có một vài sai khác ở những lỗi có thể nhận ra bằng mắt thường, không xét về khía cạnh ngữ nghĩa (OCR- optical character recognition errors), chẳng hạn “Việt Nam” và “Việt Nan” hay “Việtt Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 13 Nan”,… Có thể kể ra một số kỹ thuật phổ biến đo độ tương tự giữa hai xâu: Xâu con chung dài nhất, dãy con chung dài nhất, khoảng cách soạn thảo (Edit distance). Nhiều ứng dụng sử dụng các biến thể của các hàm khoảng cách này. 1) Khoảng cách soạn thảo (Edit distance): 4, 7 Đối với hai xâu x, y khoảng cách soạn thảo Edit distance (x,y) là số nhỏ nhất các phép sửa đổi về mặt soạn thảo (editing transformations) để biến đổi xâu x thành xâu y (việc tính toán khá phức tạp). Khoảng cách soạn thảo càng lớn thì sự khác nhau giữa hai xâu càng nhiều (hay độ tương tự càng nhỏ) và ngược lại. Khoảng cách soạn thảo thường để kiểm tra chính tả hay tiếng nói. Tuỳ thuộc vào quy ước về các phép sửa đổi mà ta nhận được các loại khoảng cách soạn thảo khác nhau, chẳng hạn như: + Khoảng cách Hamming: Phép sửa đổi chỉ là phép thay thế ký tự. + Khoảng cách Levenshtein: Phép sửa đổi bao gồm: Chèn, xoá, và thay thế ký tự. + Khoảng cách Damerau 3: Phép sửa đổi bao gồm: Chèn, xoá, thay thế và hoán vị liền kề của các ký tự. 2) Xâu con chung dài nhất (hay khúc con chung dài nhất): Một xâu w là xâu con hay khúc con (substring or factor) của xâu x nếu x = uwv (u, v có thê rỗng). Xâu w là khúc con chung của hai xâu x, y nếu w đồng thời là khúc con của x và y. Khúc con chung dài nhất của hai xâu x và y, ký hiệu LCF (x,y), là một khúc con có độ dài lớn nhất. 3) Dãy con chung dài nhất 4, 6: Một dãy con của xâu x là một dãy các ký tự có được bằng cách xoá đi không, một hoặc nhiều ký tự từ x. Dãy con chung của hai xâu x, y là một dãy con của cả hai xâu x và y. Dãy con chung của x và y có độ dài lớn nhất được gọi là dãy con chung Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 14 dài nhất LCS (x,y). Có thể dùng độ dài dãy con chung của hai xâu x, y để tính khoảng cách Levenstein giữa x và y theo công thức: LevDistance (x,y) = m + n - 2 length(LCS( x,y)) 1.1.3. Tìm kiếm trong văn bản nén và mã hoá Để giảm sự dư thừa trong lưu trữ và truyền dữ liệu, một giải pháp được sử dụng là nén dữ liệu. Quá trình nén làm cho các tệp chiếm ít không gian lưu trữ hơn, giảm được thời gian và chi phí truyền thông nhưng lại làm mất đi phần lớn cấu trúc của dữ liệu, dẫn đến khó khăn trong việc tìm kiếm và trích rút thông tin. Cách đơn giản nhất song rất tốn thời gian (và khó khả thi với những văn bản quá lớn) là giải nén toàn bộ rồi tiến hành tìm kiếm bằng một thuật toán so mẫu kinh điển. Hiện nay, đã có nhiều giải pháp tốt hơn theo hai hướng chính là: so mẫu nén (full- compressed pattern matching hay còn gọi là compressed pattern matching) và so mẫu trên miền nén (compressed- domain pattern matching) 9. So mẫu nén thực hiện nén mẫu trước rồi đem đi tìm kiếm trên văn bản nén (compressed text representation), còn so mẫu trên miền nén sử dụng giải pháp nén từng phần của văn bản. Nén dữ liệu text thực chất là một quá trình mã hoá, chuyển các thông báo nguồn (trong bảng chữ nguồn A) thành các bản mã (trong bản chữ mã B) và ngược lại là quá trình giải mã. Vì vậy thuật toán tìm kiếm trên văn bản nén có thể áp dụng đối với văn bản mã hoá dạng khối ký tự. Tuy nhiên, do yêu cầu bảo mật, đối với những văn bản mã hoá, cần có những giải thuật tìm kiếm đảm bảo không bị rò rỉ thông tin ngay trong quá trình tìm kiếm. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 15 1.2. Hệ mờ Vấn đề cốt lõi quyết định khả năng xử lý thông tin là vấn đề của logic mềm dẻo, trong đó logic đa trị là một ví dụ. Có thể nói rằng logic 2 trị: đúng - sai (1 - 0) là logic hết sức cứng nhắc, không thể lý giải cho nhiều sự việc của đời sống nói chung và của khoa học công nghệ nói riêng. Định nghĩa 1.1: Mọi sự vật, hiện tượng đều có tính đa cấu trúc đan xen, do đó tất yếu có tính không rõ ràng, mập mờ, không chính xác..., bất định. Viên gạch lý thuyết cơ sở để xây dựng nên thế giới không chính xác này có thể chọn là tập mờ và được xác định như sau: Giả sử X là tập nền (vũ trụ) và là tập rõ; A là tập con trên X; µA()là hàm của x biểu thị mức độ thuộc về tập A, thì A được gọi là tập mờ khi và chỉ khi:   1,0:)(,))(,(  XxXxxxA AA  Trong đó µA() được gọi là hàm thuộc của tập mờ 1.3. Ý tưởng chung của tiếp cận otomat mờ Khi tìm kiếm chính xác sự xuất hiện của mẫu P trong văn bản T, câu trả lời sẽ là “có” hoặc “không”. Cách nhìn mờ cho phép trả về kết quả là "độ mờ xuất hiện mẫu" (một cách hiểu nôm na là “mức độ xuất hiện” hay “mức độ khớp” của mẫu P trong T). Tuỳ thuộc vào nhu cầu hay quan niệm trong hệ thống tìm kiếm mà có thể đưa ra định nghĩa chính xác về “độ mờ xuất hiện mẫu” cho từng trường hợp cụ thể. Một cách tự nhiên, cách nhìn theo quan điểm hệ mờ về sự xuất hiện mẫu cũng đáp ứng được nhu cầu tìm kiếm mẫu xấp xỉ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 16 Để giải bài toán so mẫu theo tiếp cận mờ, ta duyệt xâu đích S từ trái sang phải và tại mỗi vị trí j, cần tính được ngay độ mờ xuất hiện mẫu P. Một câu hỏi đặt ra: Giả sử đã biết độ mờ  của mẫu P tại vị trí j trên S, làm cách nào để xác định được độ mờ ‟ tại vị trí tiếp theo? Ý tưởng để trả lời câu hỏi này là: Bằng cách tiền xử lý mẫu P, ta hy vọng có thể tính được ‟ theo công thức ‟= ( , Sj+1 ). Điều này gợi ý cho ta việc sử dụng một số hệ hình thức otomat mờ để tính độ mờ xuất hiện thông qua hàm chuyển trạng thái  của otomat. Ý tưởng chung của các thuật toán so mẫu theo tiếp cận otomat mờ [11] như sau: - Giai đoạn tiền xử lý mẫu P: Dựa vào thông tin trên mẫu P, xây dựng otomat mờ so mẫu. - Giai đoạn sánh mẫu: Duyệt xâu đích S từ trái sang phải, mỗi lần một ký tự. Khởi đầu độ mờ là 0. Giả sử đã biết độ mờ tại vị trí j (j = 0,…, n- 1) trên S là . Khi đọc được ký tự Sj+1, tính ngay được độ mờ tại vị trí j + 1 trên S là ‟= ( , Sj+1), trong đó  là hàm chuyển của otomat mờ được xác định trong giai đoạn tiền xử lý mẫu. Ưu điểm quan trọng nhất của thuật toán so mẫu theo tiếp cận otomat mờ là: - Không đòi hỏi lưu trữ toàn bộ S rồi mới so mẫu, do bản chất tuần tự đọc từng ký tự trên S, nên có thể áp dụng trong các thuật toán hướng online, đặc biệt là trên môi trường mạng, với không gian lưu trữ bộ đệm cho S không lớn, tuỳ từng ứng dụng. - Thông tin về mẫu được tiền xử lý và bao hàm trong cấu trúc của otomat mờ tương ứng nên: + Luôn phản ánh được thông tin về sự xuất hiện mẫu mỗi khi duyệt đến một vị trí bất kỳ trên xâu đích S. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 17 + Khi cần tìm kiếm mẫu P trong nhiều xâu S, chỉ cần dùng chung một otomat mờ so mẫu được xây dựng từ mẫu P. Điều này đặc biệt hữư ích khi tìm kiếm trong cơ sở dữ liệu. 1.4. Khái niệm otomat mờ Một số nghiên cứu về otomat mờ có thể xem trong 9, …. Mô hình otomat mờ dạng tổng quát có mỗi trạng thái mờ là một tập con mờ trên tập nền X = 1, …, n (X hữu hạn), có hàm thuộc mở rộng là f: X  R. Ta có thể biểu diễn f dưới dạng vector rõ (f(1), f(2),…,f(n)). Như vậy, trạng thái mờ được xem như là một véctor n chiều toạ độ thực. Tuỳ theo từng ứng dụng cụ thể mà có thể xem f(i)  0,1 hay f(i)  N hay f(i)  R,…. Định nghĩa 1.2. Một otomat mờ tổng quát là bộ A(P) = (A, Q, qo, , F), trong đó: + Bảng chữ vào A = A0 t , trong đó mỗi chữ là một xâu gồm t ký tự trên bảng chữ cơ sở A0. + Q là tập hữu hạn các trạng thái mờ có dạng q = (v1, v2,….vk) trên tập nền X = 1,…, k với giá trị mờ nguyên + q0  Q là trạng thái khởi đầu + F là tập các trạng thái kết thúc + Hàm chuyển : Q × A  Q Hàm chuyển có thể được mở rộng trong đó tín hiệu tác động là một xâu thuộc A*: (q, wa) = ((q, w),a), w  A*, a  A. Số thành phần trong trạng thái mờ và tập giá trị mờ phụ thuộc vào quan điểm về “độ mờ xuất hiện mẫu” và nhu cầu tìm kiếm trong từng bài toán cụ thể. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 18 Để thuận lợi cho việc trình bày sau này, quy định một số ký hiệu như sau: Với w, w1, w2 là các xâu ký tự, + wi là ký tự thứ i của xâu w + w(f,d) là xâu con (hay khúc con) độ dài f của xâu w, kết thúc ở vị trí d trên w. + w1  s w2 nếu w1 là khúc đuôi của w2 + w1  ls w2 nếu w1 là khúc đuôi dài nhất của w2 + Với w = w1, w2….wm, 0  t  m w(t) hoặc preft(w) là khúc đầu độ dài t của w, w(t) = w1 w2….wt Suft(w) là khúc cuối độ dài t cuả w, Suft(w) = wm - t+1 w m-t+2....wm Quy ước pref0(w) = suf0(w) =  ( là xâu rỗng) + Với a là một ký tự, w = w1w2…wm, ký hiệu wa = w1w2…wma 1.5. Một số thuật toán so mẫu 1.5.1. Thuật toán KMP ( Knuth- Morris- Pratt) Thuật toán KMP được trình bày chi tiết trong 4, 5, 14 nội dung như sau: Duyệt từ trái sang phải trên S và P, mỗi lần một ký tự. Gọi con trỏ trên P là i, con trỏ trên S là j. Giả sử đã xuất hiện khúc đầu độ dài i - 1 của mẫu P và việc khớp mẫu thất bại tại vị trí j trên S, có nghĩa: P1P2…Pi -1  Sj - i + 1Sj - i + 2…S j - 1 và Pi  Sj Khi đó cần phải bắt đầu đối sánh mẫu từ vị trí j - h +1 trên S (trường hợp xấu nhất h = i - 1 trong thuật toán Brute - Force). Nếu tồn tại h > 0 sao cho h - 1 ký tự đầu của mẫu khớp với h - 1 ký tự cuối của đoạn S(j - 1) hay có nghĩa đã khớp với h - 1 ký tự cuối của P(i - 1) thì ta có thể bỏ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 19 h=next[i] S P P i j m m +1 j h=next[m+1] P S P qua h - 1 phép so sánh và tiếp tục so sánh 2 ký tự Ph và Sj (hình 1.1). Do h phụ thuộc vào i nên ký hiệu h = nexti, i = 1,…,m. ? Hình 1.1. Ý nghĩa của mảng next Nếu Sj  Ph thì phải tiếp tục lùi con trỏ trên mẫu. Để khắc phục nhược điểm do tình huống này gây ra, cần cố gắng tìm h sao cho Ph có nhiều khả năng bằng Sj. Vì Sj  Pi nên cần tìm h thoả mãn Ph  Pi . Trong KMP, khi i > m ta được một xuất hiện của mẫu bắt đầu từ vị trí j - m trên S. Để tìm xuất hiện tiếp theo, nếu bắt đầu đối sánh từ P1 và Sj thì có thể bỏ sót mẫu khi có mẫu xuất hiện lồng nhau. Vì vậy, khi con trỏ trên S dừng ở vị trí j, cần trượt mẫu đi một số vị trí sao cho h - 1 ký tự đầu của mẫu khớp với h - 1 ký tự cuối của S(j - 1) hay chính là khớp với h - 1 ký tự cuối của P(m). Do đó cần mở rộng mảng next với i = m + 1. (Hình 1.2). Hình 1.2. Ý nghĩa của mảng next tại vị trí m + 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 20 Như vậy, với mỗi vị trí i trên P, i = 1..m + 1, cần xác định next i thoả mãn: + nexti là số h lớn nhất sao cho h - 1 ký tự đầu của mẫu khớp với h - 1 ký tự cuối của P(i- 1). + Pi  Pnext i (để có nextm + 1, tưởng tượng như đã bổ sung thêm ký tự  vào cuối P, với  là một ký tự không xuất hiện trong P). Ví dụ 1.1. Với P = aababaab ta có bảng next như sau: i 1 2 3 4 5 6 7 8 9 next[i] 0 0 2 0 2 0 0 2 4 Thuật toán 1.1. Xây dựng mảng next procedure Initnext(); var i, j: Integer; begin i: = 1; j: = next 1: = 0; while i< = m do begin while j > 0 and Pi  P j do j: = next j; i: = i + 1; j: = j + 1; if ( i < = m) and (Pi = P j) then next i := next j else next i : = j; end; end; Thuật toán 1.2. KMP tìm nhiều lần lặp mẫu proedure KMP(); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21  Tìm mọi vị trí xuất hiện xâu mẫu P độ dài m trong xâu đích S độ dài n, đồng thời thống kê tần suất xuất hiện mẫu var i, j: Integer; counter: Integer; begin Initnext (); i:= 1; j:= 1; counter: = 0; repeat while i < = m and j < = n do begin while (i > 0) and (Sj  Pi) do i: = next i; i: = i + 1; j = j + 1; end; if( i > m) then begin Ghi nhận vị trí xuất hiện mẫu là j - m; counter: =counter + 1; end; i: = next m + 1; until j > n; Ghi nhận counter; end; Độ phức tạp của thuật toán 4, 5 - Pha tiền xử lý mẫu: Độ phức tạp thời gian và không gian để xây dựng bảng next là O(m). - Pha tìm kiếm: Thời gian xấu nhất là O(m+n). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 22 1.5.2. Thuật toán BM ( Boyer- Moor) Một tiếp cận phổ biến trong các thuật toán so đơn mẫu là duyệt tuần tự qua tất cả các ký tự trên xâu vào S, mỗi lần một ký tự. Nhưng trong thuật toán BM, có thể có những bước nhẩy xa trên S được thực hiện, nhờ vậy BM được đánh giá là thuật toán nhanh nhất về thực hành, đây là lựa chọn hiệu quả cho những ứng dụng thông thường như các trình soạn thảo văn bản. Ý tưởng cơ bản của thuật toán là sử dụng một “Cửa sổ trượt” như sau: “Cửa sổ” thực ra là một khúc độ dài m trên xâu vào S (m là độ dài của mẫu P) được đối sánh với mẫu tại một thời điểm nào đó. Mỗi lần đối sánh mẫu P với một cửa sổ trên S bằng cách so sánh từng ký tự từ phải sang trái. Khi gặp ký tự không khớp, cửa sổ trượt sang phải qua một đoạn trên S (tương ứng với việc dịch mẫu P sang phải). Trường hợp tốt nhất khi sự không khớp xảy ra tại vị trí Pm và ký tự không khớp là Sk lại không phải là một ký tự trong mẫu P, lúc đó có thể an toàn trượt cửa sổ sang phải qua m vị trí trên S và bắt đầu quá trình tìm kiếm mới bởi việc so sánh Pm và Sk+ m. Giả sử tại một thời điểm đang xét cửa sổ Sk - m+ 1Sk - m + 2 .... Sk và bắt đầu so sánh Pmvới Sk. (1) Giả sử Pm  Sk có hai khả năng: a) Nếu vị trí xuất hiện phải nhất của ký tự Sk trong P là m - g, ta có thể dịch mẫu P sang phải g vị trí sao cho Pm-g dóng thẳng với Sk rồi bắt đầu lại quá trình đối sánh bởi phép so sánh Pm và S k+ g b) Nếu ký tự Sk không có mặt trong P, ta có thể dịch mẫu P sang phải m vị trí. Đây là bước dịch chuyển xa nhất có thể mà vẫn không bỏ sót sự xuất hiện nào của mẫu. (2) Giả sử m - i ký tự cuối của mẫu P đã khớp với m - i ký tự cuối của S(k). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 23 Nếu i = 0, ta đã tìm được một xuất hiện của mẫu P. Ngược lại, nếu i > 0 và Pi  Sk -m+i, xét hai khả năng: a) Nếu vị trí xuất hiện trái nhất của ký tự Sk -m+i trong P là i - g, khi đó mẫu P được dịch sang phải g vị trí sao cho Pi-g dóng thẳng với Sk-m+i và sẽ bắt đầu quá trình đối sánh mới, bắt đầu từ Pm so với Sk+g. Nếu Pi-g nằm bên phải của Pi (khi g < 0) thì mẫu P chỉ dịch sang phải 1 vị trí. b) Giả sử sufi(P) là một xâu con của Pi+1-gPi+2-g....Pm-gvà Pi-g  Pi (nếu có nhiều xuất hiện như vậy của sufi(P) thì chọn vị trí phải nhất). Khi đó sẽ dịch mẫu P sang phải một đoạn dài hơn so với trường hợp (2a) sao cho khúc Pi+1-gPi+2-g....Pm-g dóng thẳng với khúc Sk-m+i+1Sk-m+i+2...Sk và bắt đầu quá trình đối sánh mới từ Pm so với Sk+g. Như vậy, khi Pi  Sj, mẫu P sẽ dịch sang phải đi một số vị trí. Thuật toán sử dụng hai bảng d1và d2 để tính toán bước địch chuyển này. Bảng d1 bao hàm trường hợp (1) và (2a): Với mỗi ký tự c, d1c là số i lớn nhất sao cho c = Pi hoặc dc = m nếu c không xuất hiện trong mẫu P. Bảng d2 bao hàm trường hợp (2b): Với mỗi i, 1 i  m, d2i được xác định là: d2i = ming + m - i| g  1 và (g  i hoặc Pi-g  Pi) và ((g  k hoặc Pk-g = Pk) với i  k  m) Có nhiều cách tính toán bảng d2 được đưa ra. Thuật toán 1.3. tính bảng dịch chuyển d2 là của Knuth, có sự sửa đổi của Mehlhorn. Trong thuật toán 1.3 sử dụng hàm f có tính chất f[m] = m+1 và với 1  j < m, fj = mini j < i < m và Pi+1Pi+2....Pm = Pj+1Pj+2....Pm+j-i. Thuật toán 1.3. Tính bảng dịch chuyển d2 procedure computed 2(); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 24 begin for i: = 1 to m do d2i : = 2 *m- i; j := m; k: = m+ 1; while j > 0 do begin fj: = k; while k <= m and Pj  Pi do begin d2k:= mind2k, m- j ; k: = fk]; end; j := j - 1; k := k - 1; end; for i: = 1 to k do d2i : = mind2i, m +k - i j: = fk; while k < = m do begin while k <=j do begin d2k := mind2k, j-k + m  k := k + 1; end; j: = fj; end; end; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25 Thuật toán 1.4. Thuật toán BM tìm sự xuất hiện của mẫu P trong xâu vào S procedure BM(); var i, j: integer; counter: integer; begin j:= m; counter: = 0; while j <= n do begin i: = m; while i >0 and Sj  Pi do begin i: = i - 1; j: = j - 1; end; if i: = 0 then begin Ghi nhận một lần xuất hiện mẫu tại vị trí j + 1; counter: = counter + 1; j := j + m + 1; end; else j: =j+ maxd1Sj, d2i; end; Ghi nhận counter; end; Độ phức tạp của thuật toán 4, 5 Độ phức tạp thời gian là O(m + n) và độ phức tạp không gian là O(m). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26 1.6. Kết luận chương 1 Chương này đã trình bày tổng quan về vấn đề tìm kíêm văn bản, phát biểu và tổng kết các hướng nghiên cứu cho các dạng bài toán tìm kiếm. Nội dung của luận văn tập trung giải quyết bài toán so đơn mẫu, chính xác, xấp xỉ theo hướng tiếp cận sử dụng một số hệ hình thức otomat mờ. Ý nghĩa của tiếp cận này cũng như mô hình otomat mờ tổng quát được giới thiệu ở mục 1.2. Cuối cùng là hai thuật toán kinh điển nổi tiềng cho bài toán so đơn mẫu chính xác là KMP và BM được trình bày. Việc tính toán bảng next trong KMP và ý tưởng về bước dịch chuyển xa trong BM là nguồn gốc cho 2 thuật toán so đơn mẫu chính xác, xấp xỉ theo tiếp cận mờ sẽ được đưa ra ở chương 2. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 Chương 2. BÀI TOÁN SO MẪU THEO CÁCH TIẾP CẬN OTOMAT MỜ 2.1. Bài toán so mẫu chính xác 2.1.1. Phát biểu bài toán Cho xâu mẫu P độ dài m (P = P1P2 ... Pm) và xâu đích S độ dài n (S = S1S2 ... Sn) trên cùng bảng chữ A. Tìm tất cả các vị trí xuất hiện của mẫu P trong xâu S. Từ việc giải bài toán trên dễ dàng thống kê được tần suất xuất hiện mẫu P trong một văn bản. 2.1.2. Độ mờ của mô hình Bài toán đặt ra ở đây là tìm kiếm chính xác mẫu, nhiều lần lặp mẫu. Độ mờ là một giá trị nguyên thuộc khoảng [0,...,m] cho biết độ dài của khúc đầu dài nhất của mẫu P đã xuất hiện trên S. Đây cũng có thể xem như một mô hình “lỗi”, rất phù hợp với tìm kiếm xấp xỉ khúc đầu trong các từ điển lớn. Định nghĩa 2.1. Cho xâu mẫu P độ dài m và xâu đích S độ dài n. Độ mờ xuất hiện mẫu P trên S tại vị trí j là giá trị nguyên   0 thoả mãn: -  = 0 nếu Sj  P1 -  là số lớn nhất sao cho P1P2 ...P = Sj-+1Sj-+2..... Sj Trong các thuật toán so mẫu theo tiếp cận mờ ở đây, mỗi khi đọc được một kí tự Sj sẽ cho biết ngay độ mờ xuất hiện mẫu. Giả sử đã biết độ mờ tại vị trí j là , khi đọc được ký tự Sj+1 = a, độ mờ mới sẽ được xác định như một hàm kiến thiết của cặp (,a). Gọi AP là tập các kí tự có trong mẫu P, # là một kí tự đại diện cho các kí tự thuộc A nhưng không xuất hiện trong P. Khi đó độ mờ được xác định thông qua hàm TFuzz: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 TFuzz: {0,1, ...,m} × (AP  #)  {0,1, ...,m} (,a)  ‟ = TFuzz (,a)  gọi là độ mờ cũ, ‟ gọi là độ mờ mới khi gặp kí tự a. Hàm TFuzz được xây dựng dựa vào bảng next như trong thuật toán KMP tìm nhiều lần lặp mẫu đã trình bày ở Mục 1.5.1. Dựa vào Định nghĩa 1.3, bằng phương pháp quy nạp, ta nhận được ngay kết quả sau: Bổ đề 2.1. Giả sử độ mờ xuất hiện mẫu P tại vị trí Sj là , khi đó độ mờ mới ’ tại Sj+1 được xác định bởi một hàm ’ = TFuzz (, Sj+1), với TFuzz được xác định như sau: + TFuzz (0, ) =      1 1 ,1 ,0 Px Px + TFuzz (i, #) = 0, i = 0..m i+1, nếu  = Pi+1    mi xiTFuzz ..1 , j, j  i và j là số lớn nhất sao cho P1P2...Pj-1 = Pi-j+2Pi-j+3...Pi và Pj = , nếu   {Pi+1, #} Việc xác định j dựa vào bảng next và một vòng lặp. 2.1.3. Thuật toán KMP mờ 2.1.3.1. Otomat so mẫu Do ý nghĩa của độ mờ là độ dài khúc đầu dài nhất của mẫu P đã xuất hiện trên S nên otomat sẽ có tập trạng thái là tập số nguyên {0, 1,..., m}. Hoạt động của otomat mờ so mẫu sẽ như sau: - Khởi đầu con trỏ trên S là j = 0. Tại đó chưa xuất hiện khúc đầu nào của mẫu nên trạng thái khởi đầu của otomat là q0 = 0. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 - Duyệt S, mỗi lần một kí tự, bắt đầu từ S1. Giả sử trạng thái của otomat là q thì khi đọc được kí tự Sj, trạng thái mới (ứng với vị trí j trên S) sẽ là q‟ = (q,Sj) ( là hàm chuyển của otomat). - Tại vị trí j trên S, nếu trạng thái của otomat là q, có nghĩa khúc đầu dài nhất xuất hiện trên S của P có độ dài q. Nếu q = m, báo hiệu một lần xuất hiện mẫu, bắt đầu từ vị trí j -m+1. Mô hình otomat mờ cần được xây dựng một cách thích hợp để đáp ứng được yêu cầu sánh mẫu như trên. Định nghĩa 2.2. Otomat mờ so mẫu là bộ A(P) = (A, Q, q0, , F) trong đó: + Bảng chữ vào A = AP  {#} + Tập trạng thái Q = {0,1,...,m} + Trạng thái khởi đầu q0 = 0 + Trạng thái kết thúc F = m. + Hàm chuyển : Q  A  Q (q,a) = TFuzz (q,a), với hàm TFuzz được xác định như trong Bổ đề 2.1. 2.1.3.2. Tính đúng đắn của thuật toán Định lý 1.1. Cho xâu mẫu P độ dài m. A(P) là otomat mờ được xác định theo định nghĩa 2.2. Giả sử q = (q0, w), w  A * . Nếu q = F thì P là khúc cuối của w. Chứng minh. Dựa vào Bổ đề 2.1. và định nghĩa 2.2., tiến hành quy nạp theo độ dài của từ w, dễ dàng nhận được điều phải chứng minh. 2.1.3.3. Thuật toán Khi cài đặt thuật toán cần lưu ý lựa chọn cấu trúc dữ liệu phù hợp để có thể truy nhập nhanh chóng trong bảng TFuzz. Gọi A[0..k] là mảng lưu giữ bảng chữ A của otomat, trong đó k là số kí tự phân biệt trong mẫu P. Màng được sắp theo chiều tăng của các kí Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 tự và A[k] = „#‟. Để thuận tiện khi truy nhập đến các chữ cái trong A, có thể sử dụng mảng index xác định vị trí của chữ trong bảng. i, nếu c = A [i] index [c] = k, nếu c  {A[0], A[1], ...A[k-1]} TFuzz là mảng [0..m, 0..k], trong đó TFuzz [i, j] là độ mờ mới khi độ mờ i gặp kí tự x có index [] = j. Khi đó chi tiết thuật toán tạo lập bảng TFuzz và tìm kiếm dựa vào bảng TFuzz sẽ như sau: Thuật toán 2.1. Tạo lập TFuzz procedure initTFuzz() var i, j, t: integer; begin for i: = 0 to m do TFuzz [i,m]:=0; for j: = 0 to k do TFuzz [0, j] := 0; TFuzz [0, index [P1]]:=1; for i: = 0 to m do for t: = 0 to k-1 do begin if i = m then j:= next [i+1] elsse j:=i+1; while (j > 0) and (Pj  A([t]) do j:=next [j]; TFuzz [i, index [A[t]]:= j; end; end; Thuật toán 2.2. Tìm kiếm mẫu dựa vào bảng TFuzz procedure FPM(); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31 var j, counter: integer; fuz: array [1..50] of integer; {* độ mờ*} begin j :=1; counter :=0; fuz[0] = 0; while (còn đọc được Sj) do begin fuz [j] = TFuzz [fuz[j-1], index [Sj]]; if fuz [j] = m then begin counter :=counter+1; Ghi nhận vị trí j-m+1; end; end; {while} Ghi nhận counter; if counter = 0 then Ghi nhận vị trí 0; end; Ví dụ 2.1. Với mẫu P = aababaab, A = {a, b, #}, AP = {a,b}. Bảng TFuzz được tính toán dựa trên mảng next (ví dụ 1.1, Mục 1.5.1) cho kết quả như sau: A Q a b # 0 1 0 0 1 2 0 0 2 0 3 0 3 4 0 0 4 2 5 0 5 6 0 0 6 7 0 0 7 2 8 0 8 4 0 0 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32 Quá trình so mẫu trên dòng dữ liệu S = aabaababaababaababaab sẽ như sau: j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 S a a b a a b a b a a b a b a a b a b a a b j 1 2 3 4 2 3 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 ghi nhận ghi nhận ghi nhận 11-8+1=4 168+1=9 21-8+1=14 2.1.3.4. So sánh KM P và thuật toán KMP mờ Hình 2.1. Dịch chuyển con trỏ trên mẫu Giả sử đã xuất hiện khúc đầu độ dài i-1 của P trên S, tính tới vị trí j, có nghĩa đã có P(i - 1) = sufi - 1(S(j - 1)) hay độ mờ tại vị trí j - 1 là j-i = i - 1. Xét ký tự Sj, có thể xảy ra hai khả năng: + Trường hợp 1: Sj = Pi (hay độ mờ tại vị trí j là j = i) Tăng i, j lên 1. Với trường hợp này tốc độ thao tác của thuật toán KMP như trong tiếp cận mờ. + Trường hợp 2: Sj  Pi (hay độ mờ tại vị trí j là j  i) Trong KMP, con trỏ j trên S giữ nguyên, chỉ dịch chuyển con trỏ trên mẫu (dùng lệnh i:= next[i] (Hình 2.1). Vì vậy phải mất thời gian dịch chuyển theo bảng next, thậm chí nhiều lần. Ví dụ như: ? next [i] P P S i i j-i = i - 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33 Với P = aababaab, sử dụng bảng next (ví dụ 1.1, mục 1.5) để tìm sự xuất hiện của mẫu trong dòng ký tự S như sau: S = a a c ... j = 3 P = a a b a b a a b i = 3 dịch lần thứ nhất a a b a b a a b i = next[i] = 2 dịch lần thứ 2 a a b a b a a b i = next[i] = 0 Ta thấy có 2 lần dùng i:= next[i] và 2 lần so sánh Sj và Pi (i khác nhau). Nói chung có thể xảy ra nhiều lần dùng next trong khi con trỏ trên S vẫn giữ nguyên. Điều này làm chậm đáng kể so với tiếp cận mờ: mỗi lần nhận một ký tự Sj là một lần điều chỉnh giá trị mờ theo otomat: j = TFuzz (j-1, Sj). Lệnh này thực hiện rất nhanh nếu TFuzz được biểu diễn dưới dạng một mảng và được tính toán cẩn thận trước theo thông tin trên mẫu P. Kết quả sau so sánh tốc độ thực hiện việc tìm sự xuất hiện mẫu P trong tệp dữ liệu lớn S theo hai thuật toán KMP và tiếp cận mờ trên máy PC IBM tốc độ 233MHz. Mẫu P Kích thước tệp S TKMP TFuzzy-KMP 1) aababcab 1400 KB 17% s 11% s 2) MDSVF6V 140.000 KB 35 s 30 s 3) bacabccaa 1200 KB 16% s 10% s 4) S068FAB50 140.000 KB 37 s 30 s 2.1.4. Thuật toán KMP - BM mờ 2.1.4.1. Ý tưởng của thuật toán Trong thuật toán Boyer - Moore (BM), các ký tự trên mẫu P được duyệt từ phải sang trái, bắt đầu từ Pm. Tại thời điểm gặp ký tự không trùng khớp, chẳng hạn Pi = a còn Sj = b, khi đó sẽ quyết định dịch con trỏ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34 trên mẫu. Phép dịch chuyển ứng với mỗi ký tự trên P, nếu sự không trùng khớp xảy ra ở đó, được xác định trong bước tiền xử lý mẫu P. Trong thuật toán “ký tự không khớp” này của BM, có một trường hợp cho phép dịch chuyển tốt nhất (xa nhất) là khi ký tự b không xuất hiện trong mẫu P. Từ chi tiết này, kết hợp với kiểu sánh mẫu như trong KMP, ta sẽ có một “thuật toán theo tiếp cận mờ tổng quát kiểu KMP và BM”, trong đó độ mờ vẫn được tính toán dựa trên hàm TFuzz, đồng thời sẽ có những bước nhảy dài trên xâu đích, đem lại hiệu quả tìm kiếm cao. Ý tưởng của thuật toán này là [11]: gọi ptr là con trỏ trên xâu đích S (khởi đầu ptr = 0 và độ mờ tại đó bằng 0 báo hiệu chưa tìm thấy mẫu). Mỗi lần xét một khối w gồm m + 1 ký tự liên tục trên S, bắt đầu từ vị trí ptr, ta gọi khối này là “khối ký tự quan sát” và ký hiệu wi là ký tự thứ i trong w (với w1 = Sptr). Dựa trên bảng TFuzz, tính độ mờ xuất hiện mẫu khi gặp ký tự w1 (hay chính là Sptr), ký hiệu độ mờ này là n1, đồng thời xác định bước nhảy tiếp theo để từ đó sẽ xét khối ký tự w mới, ký hiệu bước nhảy là n2. Nếu n1 là độ mờ tại Sptr thì có nghĩa sufn1(S(ptr)) = P(n1) (Hình 2.2). Xảy ra các khả năng sau: + Nếu n1 = m, chứng tỏ đã xuất hiện mẫu bắt đầu từ vị trí ptr - m + 1 trên S. Để không bỏ sót sự xuất hiện lồng nhau của mẫu, đặt n2 = 1. + Nếu n1 lớn hơn độ mờ tại vị trí được xét trước vị trí ptr, có nghĩa đang có hy vọng tìm thấy mẫu nên n2 = 1. + Trong các trường hợp còn lại của n1, chỉ mới xuất hiện khúc đầu P(n1) khớp với khúc cuối độ dài n1 của S(ptr). Nếu việc khớp mẫu thành công với khối ký tự quan sát w, thì ký tự Pm sẽ khớp với ký tự Sptr+m-n1 (hay w1+m-n1). Do đó, nếu Sptr+m-n1 không phải là một ký tự xuất hiện trong P thì có thể thực hiện bước nhảy xa để đọc w mới bắt đầu từ vị trí ptr+m- n1+1 trên S mà vẫn đảm bảo không bỏ sót sự xuất hiện nào của mẫu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35 Hình 2.2. Ý tưởng chung của thuật toán KMP-BM mờ 2.1.4.2. Otomat mờ so mẫu Định nghĩa 2.3. Cho P là xâu mẫu độ dài m trên bảng chữ A. Ap là bảng các ký tự xuất hiện trong P. Otomat mờ so mẫu là A(P) = (Ak, Q, q0, F, ), trong đó: + A k là bảng chữ vào, mỗi chữ là một xâu ký tự độ dài k trên A, k=m+1 + Q là tập hữu hạn các trạng thái, Q = {q=(n1,n2)| n1, n2  N, 0  n1  m, 1  n2  k}  n1 gọi là độ mờ tại vị trí đang xét  n2 gọi là bước nhảy tiếp theo vị trí đang xét + q0 là trạng thái khởi đầu, q0 = (0,1) + F là trạng thái kết thúc, F = (m,1) + Hàm chuyển : Q × Ak  Qs (q, w)  q‟ = (q, w) Với q = (n1, n2) thì q‟ = (n1‟, n2‟) được xác định như sau:  Nếu n2 > 1 thì đặt n1 = 0  Tính n1‟ = TFuzz (n1, w1)  Nếu n1‟ = m hoặc n1‟ > n1 thì n2‟ = 1, ngược lại (n1‟ < m và n1‟  n1) thì xét: Nếu w1+m-n1‟  Ap thì n2‟ = 1, ngược lại n2‟=1+m-n1‟ ptr P(n1) ptr+m-n1 1+m-n1 m+1 S Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36 Hoạt động của otomat mờ so mẫu như sau: Cho mẫu P độ dài m và xâu đích S độ dài n trên bảng chữ A. A(P) là otomat được xác định theo định nghĩa 2.3. Ta sẽ dùng otomat A(P) để đoán nhận tất cả các vị trí xuất hiện mẫu P trong xâu S và tổng số lần xuất hiện mẫu. Thuật toán cơ bản dựa trên otomat được mô tả như sau: Thuật toán 2.3. Ta dùng các ký hiệu: + j là con trỏ quan sát trên S + q.n1, q.n2 là hai thành phần của trạng thái q + w là khối ký tự quan sát bắt đầu từ vị trí j trên xâu đích S, giả sử đã bổ sung thêm m ký tự # vào cuối S. + qold là trạng thái của otomat tại vị trí trước khi đọc w + q là trạng thái otomat sau khi tác động w, q = (qold, w) + Counter là biến đếm số lần xuất hiện mẫu. Bước 1: Khởi tạo j: = 0; counter := 0; qold.n1 :=0; qold.n2 :=1; Bước 2: While j  n do j: = j + qold.n2 Đọc khối ký tự quan sát w; {w1 Sj} {Tính q = (qold, w)} if qold.n2 > 1 then qold.n1:= 0; endif; q.n1: = TFuzz (qold.n1, w1); q.n2: = 1; if q.n1= m then Ghi nhận vị trí xuất hiện mẫu là j - m + 1; Counter: = counter + 1; else if q.n1 < m and q.n1 < qold.n1 then Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 37 if w1+m-q.n1  Ap then q.n2: = 1+m-q.n1; endif; endif; endif; qold := q; endwhile; 2.1.4.3. Thuật toán 2.4 procedure GFSearching (); {tìm kiếm mẫu dựa trên định nghĩa 2.3} var apr: array [1..N] of integer; counter, j, n1, n2, n1’, n2’: integer; begin j:= 0; n1:= 0; n2 := 1; while j <= n do begin j := j + n2; if n2 > 1 then n1:= 0; n1’ := TFuzz [n1, index [S[j]]]; n2’: = 1; if n1’ = m then begin counter := counter + 1; apr[counter]:= j - m + 1; end else if n1’ < m and n1’ <= n1 then begin if j + m - n1’ > n then return; if index [S[j + m - n1’]] = k then n2’ : = 1 + m - n1’; end; n1:=n1’; n2: = n2’; end; end; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 38 2.2. Bài toán so mẫu xấp xỉ 2.2.1. Đặt vấn đề Để tìm kiếm xấp xỉ, cần sử dụng một hàm khoảng cách (distance function) đo độ tương tự giữa hai xâu. Tương tự ở đây được hiểu là giữa hai xâu kí tự có một vài sai khác ở những lỗi có thể nhận ra bằng mắt thường, không xét về khía cạnh ngữ nghĩa (OCR - optical character recognition errors), chẳng hạn “Việt Nam” và “Việt Nan” hay “Việtt Nan”,... Có thể kể ra một số kỹ thuật phổ biến đo độ tương tự giữa hai xâu: xâu con chung dài nhất, dãy con chung dài nhất, khoảng cách soạn thảo (Edit Distance). Các kỹ thuật trên chủ yếu chỉ hiệu quả khi có những sai khác về mặt chính tả: có sự bổ sung, xoá hay thay thế một số kí tự. Trong nhiều tình huống, những kỹ thuật này chưa đáp ứng đầy đủ yêu cầu thực tế, như khi cần tìm kiếm theo tên người nước ngoài (chẳng hạn “christian Charras” và “Charas C”), khi có sự sai khác do biến đổi hình thái từ, cấu trúc câu (“approximate searching” và “search approximately”), một số trường hợp thứ tự ghép từ khác nhau nhưng mang ngữ nghĩa giống nhau (“toán logic” và “logic toán”) hoặc do thứ tự sai song vẫn hiểu được đúng nghĩa (“toán giải tích” và “giải tích toán”,...). Phương pháp xác định độ tương tự giữa hai xâu kí tự theo “độ gần tựa ngữ nghĩa” được đề xuất trong luận văn sẽ đáp ứng nhu cầu tìm kiếm như trên. Xét một tình huống khác. Khi ứng dụng trong thực tế, mỗi từ theo nghĩa thông thường có thể xem là một kí tự hình thức. Chẳng hạn câu “bạn Minh giỏi Toán” được xem là một „xâu‟ gồm 4 „kí tự‟, có thể hình thức hoá là P = derq và S là “Ở trường tôi bạn Minh được đánh giá là một trong những sinh viên học Toán giỏi nhất", hình thức hoá là S = abcdefghiklmnopqrs. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 39 Tính độ tương tự giữa hai xâu bằng các kĩ thuật trên được kết quả như sau: + Độ dài dãy con chung dài nhất: 3, độ tương tự có thể xem là 3/18 + Độ dài xâu con chung dài nhất: 2, độ tương tự có thể xem là 2/18 + Khoảng cách Levenshtein: 14. + Khoảng cách Hamming: 18 (đúng bằng độ dài xâu S). Độ tương tự giữa hai xâu kí tự P và S theo những độ đo kinh điển kể trên là rất nhỏ, mặc dù hai xâu rất gần nhau về mặt ngữ nghĩa. Để đáp ứng nhu cầu tìm kiếm trong những tình huống như trên, một mô hình lỗi phản ánh độ tương tự giữa hai xâu kí tự là “Độ bảo toàn thứ tự xuất hiện các kí tự” được đề xuất. Do độ tương tự xác định theo hai cách này phản ánh được độ gần gũi ngữ nghĩa giữa hai xâu, xét về mặt thống kê, nên được gọi là “độ tương tự tựa ngữ nghĩa”. Một mô hình lỗi kinh điển là dựa vào độ dài khúc con chung dài nhất song với cách tiếp cận otomat mờ được đề xuất ở đây sẽ đem lại một thuật toán nhanh, đặc biệt hiệu quả khi cần so mẫu P với rất nhiều xâu S. 2.2.2. Bài toán Bài toán được phát biểu: Cho xâu nguồn P độ dài m và xâu đích S độ dài n. Xác định dộ tương tự giữa hai xâu P và S. Bài toán này có thể coi là cốt lõi để cài đặt tính năng tìm kiếm xấp xỉ tựa ngữ nghĩa trong cơ sở dữ liệu và trong các hệ thống trích rút văn bản. Trường hợp S là một dòng dữ liệu văn bản (trong các máy tìm kiếm của hệ thống khai phá text, khai phá web,...), xâu mẫu P thường ngắn còn xâu đích S dài hơn rất nhiều so với P nên để phản ánh ngữ nghĩa được tốt cần phải chặt khúc dòng dữ liệu S và sánh từng khúc với P Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 40 (chẳng hạn, việc ngắt câu có thể xem là một cách chặt khúc). Khi đó độ tương tự sẽ được tổng hợp từ các kết quả so sánh P và các khúc của S. Khi áp dụng trong các hệ thống xử lý văn bản, rất hay gặp những lỗi nhỏ về mặt chính tả (như: “Việt Nam” và “Việt Nan”, “vật lý” và “vật lí” ...) hoặc do dùng các từ đồng nghĩa hay có nghĩa tương tự nhau (như „yêu‟ và „thích‟, „mê‟,...) do sự biến đổi về hình thái từ (trong một số ngôn ngữ: Anh, Pháp, ... “approximate” và “aproximately”). Để đáp ứng nhu cầu tìm kiếm được tốt hơn, có thể dùng các thuật toán tìm kiếm xấp xỉ nhưng tính tới độ tương tự của các kí tự, về mặt chính tả hoặc về mặt ngữ nghĩa. Khi đó khái niệm “xuất hiện” hay “thuộc xâu P” của một kí tự c được hiểu như sau: - Sử dụng một hàm đo độ tương tự với ngưỡng mờ  nào đó do người sử dụng chọn. - Tìm kí tự hình thức trong P có độ tương tự cao nhất so với c và nằm ở bên trái nhất. - Nếu độ tương tự đó lớn hơn ngưỡng  thì coi như c chính là kí tự tương ứng trên P, nếu không thì coi như c không xuất hiện trên P. 2.2.3. Độ tương tự dựa trên độ dài khúc con chung của hai xâu 2.2.3.1. Phát biểu bài toán Bài toán: Cho xâu mẫu P = P1P2 ...Pm (độ dài m) và xâu đích S = S1S2 ... Sn (đo độ dài n) trên bảng chữ A. Tìm khúc con chung dài nhất giữa hai xâu P và S. Bài toán có thể hiểu là tìm khúc con dài nhất của P xuất hiện trên S. Để giải quyết bài toán, trước hết ta đưa vào một số ký hiệu. Cho bảng chữ A, với mỗi xâu u = u1u2...uk, ui A: + prefm(u) = u1u2..um (hay gọn hơn là u(m), là khúc đầu gồm m chữ của u. + sufm(u) = uk-m+1uk-m+2...uk là khúc cuối gồm m chữ của u. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 41 + Quy ước pref0(u) = suf0(u) =  (từ rỗng) + Với hai số tự nhiên f, d, ||u||  d  f  0, đặt u(f,d) = suff(prefd(u)) là khúc cuối độ dài f của một khúc đầu gồm d kí tự của u. Quy ước u(0,d) = . + Với mỗi xâu y là khúc con của u, đặt lid(y,u) = (|y|, Min {dN| f  0: u(f,d) = y}). + Cho hai xâu u, v, kí hiệu lfact(v, u) là khúc cuối y dài nhất của v mà y là khúc con nào đó của u, độ dài của xâu y như vậy được ký hiệu là lfuz(v, u). Ví dụ 2.2. Cho u = drabcgaba, pref6(u) = drabcg, suf2(drabcg) = cg, do vậy u(2,6) = cg, lid(ab, u) = (2,4) vì ab là khúc con trái nhất của u kết thúc tại vị trí 4 trên u và ab có độ dài 2. Cho v = ghbacabc, lfact(v,u) = abc, lfuz (v,u) = 3, lfact (u,v) = ba, lfuz(u,v) = 2. Với xâu P độ dài m đã cho, trên các cặp số (f,d), với m  d  f  0, xác định một quan hệ tương đương như sau: (f,d) tương đương với (f‟,d‟) nếu P(f,d) = P(f‟,d‟) (khi đó hiển nhiên f = f‟). Lớp tương đương của một cặp (f,d) được kí hiệu là [f,d]. Cặp số (f,d) được gọi là có nghĩa (với P) nếu (f,d) là cặp có d nhỏ nhất trong lớp, nghĩa là có khúc con y của P sao cho lid(y,P) = (f,d). Ví dụ 2.3. Cho u = drabcgaba, các cặp (2,4), (2,8) tương đương vì u (2,4) = u(2,8) = ab, cặp (f,d) = (2,8) là không có nghĩa vì y = ab có vị trí kết thúc trái nhất trên u là ở vị trí 4, không phải ở vị trí 8 mặc dù u (2,8) = y = ab. Phương pháp giải quyết Độ mờ xuất hiện mẫu P tại vị trí j trên S là lfuz(S(j),P) (chính là độ dài khúc cuối dài nhất w của S(j) mà w là khúc con nào đó của P). Bản chất thuật toán cần được xây dựng là: duyệt S từ trái sang phải, ở vị trí thứ j, sau khi đọc được kí tự Sj, cho biết ngay cặp giá trị (f,d) có nghĩa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 42 của P, sao cho P(f,d) = lfact (S(j), P), do đó f = lfuz (S(j), P). Sử dụng biến LenMax để đánh dấu độ dài của khúc con dài nhất tìm được, tính tới vị trí j trên S. Sau khi duyệt xong S, LenMax cho biết độ dài khúc con chung dài nhất của P và S. Thuật toán 2.4 (Mục 2.2.3) được xây dựng dựa trên một mô hình otomat mờ sẽ đáp ứng được yêu cầu trên. Để xây dựng thuật toán chi tiết, sau đây ta sẽ xét hai hệ hình thức otomat, hệ hình thức thứ nhất đóng vai trò bổ trợ nhằm giúp thể hiện bản chất của hệ thức sau. 2.2.3.2. Otomat so mẫu Định nghĩa 2.4. Otomat trạng thái các khúc con của P có: + Bảng chữ vào A = Ap {#}, Ap gồm các ký tự xuất hiện trong mẫu P và ký tự #  Ap đại diện cho các ký tự không có mặt trong P, + Tập trạng thái là tập tất cả các khúc con của P, mỗi trạng thái là một khúc con của P (bao gồm cả xâu rỗng), + Với mỗi chữ a, mỗi khúc con u của P, hàm chuyển T cho bởi: T(u,a):= lfact(ua,P) Ta mở rộng tác động cho xâu w=a1a2...ak tuỳ ý T(u,w):= T(..T(T(T(u,a1),a2),a3),...ak), quy ước T(u, ) = u. Ví dụ 2.4. P = bcgabcdbabed T(ab, c) = abc, T(ab, e) = abe, T(ab, z) = , T(ab, zebcd) = bcd. Dựa vào các tính chất đã được chứng minh trong [11], chúng ta có thuật toán sau: Thuật toán 2.5. Tìm khúc con chung dài nhất giữa hai sâu Vào: Mẫu P độ dài m; xâu đích S độ dài n Dựa vào thông tin trên P, đã xây dựng otomat mờ so mẫu với hàm chuyển TFuzz. Ra: Khúc con chung dài nhất giữa P và S Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 43 + LenMax: độ dài của khúc con chung dài nhất + LF_P: vị trí (kết thúc) xuất hiện trên P + LF_S: vị trí (kết thúc) xuất hiện trên S Phương pháp (f,d) := (0,0); f_max := 0; LenMax := 0; LF_P := 0, LF_S := 0; for j:=1 to n do (f’,d’) := TFuzz((f,d),Sj); (f,d):= (f’,d’); if f > f_max then f_max := f else {đã tìm được một khúc con dài nhất của P độ dài f_max và là khúc cuối của S(j)} if LenMax < f_max then LenMax := f_max; LF_P := d; LF_S := j; endif; f_max := f; endif; endfor; Return(LF_P, LF_S, LenMax); 2.2.4. Độ gần tựa ngữ nghĩa 2.2.4.1. Ý tưởng về độ gần Độ gần của xâu S so với xâu P được xác định thông qua số khúc con của P xuất hiện trong S. Bài toán: Cho xâu kí tự P (xâu nguồn hay mẫu) độ dài m (P = P1P2..Pm) và S (xâu đích) độ dài n (S = S1S2...Sn). Hãy xác định độ gần tựa ngữ nghĩa của S so với P. Độ gần ở đây được hiểu là giá trị thực nằm trong khoảng [1,0] thoả mãn: + độ gần càng lớn nếu số khúc con của P xuất hiện trong S càng nhiều Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 44 + độ gần bằng 1 nếu xâu P xuất hiện trong S + độ gần bằng 0 nếu không có một phần nào của P xuất hiện trong S. 2.2.4.2. Thuật toán sơ bộ tính độ gần 2.2.4.2.1. Ý tưởng Hình 2.3. Một ví dụ với các khối độ dài t = 3 - Gọi PiPi+1...Pi+t-1 là một khối độ dài t của mẫu P và kí hiệu khối này là (t,i). - Lần lượt xét tất cả các khối độ dài t, t = 1,2,..,m, và kiểm tra xem khối đó có xuất hiện trong S hay không (xem Hình 2.3). - Tính hàm giá H(S, P) =   m t tk 1 * , trong đó k là số khối độ dài t có xuất hiện trong xâu đích S. - Gọi M là giá trị cực đại của hàm giá (khi S = P), M = H(P, P) =     m 1t t*1tm (2.1). - Độ gần của s so với P là tỷ số H/M 2.2.4.2.2. Thuật toán chi tiết Thuật toán 2.6. Tính độ gần tựa ngữ nghĩa của xâu S độ dài n so với mẫu P độ dài m. {Tính độ gần tối đa M = Hmax = H(P, P)} (3,1) (3,3) (3,5) (3,2) (3,4) P (3,2) (3,1) S (3,5) (3,1) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 45 M= H(P,P) =     m 1t t*1tm ; {Xây dựng hàm giả H(P, S) H:=0; for t:=1 to m do for i:=1 to m - t + 1 do if (khối (t, i) xuất hiện trong S) then H:=H + t; (2.2) {Tính độ gần của S so với P} F := H/M; 2.2.4.3. Giải thích độ mờ của mô hình Giá trị mờ P(S) = H/M cho biết độ gần tựa ngữ nghĩa của P trong S. Tập nền X là tập rõ bao gồm tập tất cả các xâu S trong cơ sở dữ liệu. Khi P(S) = 1 nghĩa là có mẫu P trong S hay toàn bộ thông tin của P được phản ánh trong S. Khi P(S) = 0 thì không có bất kỳ một phần nào của mẫu P trong S (xem Hình 2.4). Hình 2.4. Tập mờ mô tả độ gần tựa ngữ nghĩa của mẫu P so với xâu đích S Độ phức tạp khi so sánh mỗi khối (t,i) của mẫu được cắt với S có thể sử dụng thuật toán theo tiếp cận mờ xác định nhiều lần lặp mẫu (xem S1 S S2 S3 độ gần 1,0 0,8 0,4 0,0 0(S) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 46 mục 2.1.3), cỡ là n, chưa tính khâu tiền xử lý cho cấu trúc bảng chuyển của otomat. Số khối được xét với mọi t là: m+(m-1) + ... + 1 = m(m+1)/2. Vì mẫu đưa vào thường ngắn từ 3 đến 30 ký tự nên giá trị này có thể coi là hằng số C. Do đó độ phức tạp thời gian của thuật toán là T = n.m(m+1)/2+Tpt, với Tpr là thời gian tiền xử lý để tính m(m+1)/2 cấu trúc otomat. Thời gian tiền xử lý này là hằng số và không lớn nếu so với n = |S| (rất lớn) nên xem độ phức tạp của thuật toán là O(n). Nhưng nếu S nhỏ và tìm nhiều lần trên nhiều S khác nhau, mỗi S là giá trị trên trường text của bản ghi trong cơ sở dữ liệu, mà phải bắt đầu lại quá trình tìm mẫu thì quá là con số không nhỏ: cỡ k.T, với k là số bản ghi cần duyệt. 2.3. Kết luận chương 2 Chương này trình bày hai bài toán so mẫu xấp xỉ và chính xác theo tiếp cận otomat mờ. Bài toán so mẫu xấp xỉ và chính xác trình bày hệ hình thức cụ thể của otomat mờ tổng quát đã giới thiệu ở Mục 1.2. Hệ hình thức otomat thứ nhất có trạng thái mờ là một số tự nhiên (chính là một vectơ gồm 1 thành phần), làm cơ sở cho thuật toán so mẫu KMP mờ. Thuật toán này có thể xem như một tiếp cận mới cho thuật toán kinh điển KMP - tiếp cận otomat mờ. Hình thức thứ hai có trạng thái mờ là một bộ gồm hai thành phần, làm cơ sở cho thuật toán so mẫu KMP - BM mờ, với ý tưởng có bước dịch chuyển xa trên xâu đích S như trong thuật toán BM. Quan niệm về “độ mờ xuất hiện mẫu” trong cả hai thuật toán này đều là độ dài khúc đầu dài nhất của mẫu P đã xuất hiện trên xâu đích S, tính tới vị trí đang xét. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 47 Chương 3. TÌM KIẾM MẪU TRONG VĂN BẢN NÉN VÀ MÃ HOÁ 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á Khi tìm kiếm trên văn bản nén hoặc mã hoá, bài toán bơ bản đặt ra như sau: Cho mẫu P là một xâu độ dài m (P = P1,P2,...Pm) trên bảng chữ A. Xâu vào S được nén hoặc mã hoá thành xâu Y = Y1Y2...Yn trên bảng chữ B bằng một phương pháp nén (hoặc mã hoá) đã biết trước. Tìm tất cả các xuất hiện của mẫu P trên Y. Đối với những văn bản nén, mặc dù đem lại hiệu quả rõ rệt về mặt lưu trữ, quản lý, tổ chức và chuyển tải, song lại làm mất đi phần lớn cấu trúc của dữ liệu, dẫn đến khó khăn cho việc tìm kiếm và trích rút thông tin. Cách đơn giản nhất rất tốn thời gian (và khó khả thi với những văn bản quá lớn) là giải nén toàn bộ rồi tiến hành tìm kiếm bằng một thuật toán so mẫu kinh điển. Hiện nay đã có nhiều giải pháp tốt hơn cho phép tìm kiếm trực tiếp trên dữ liệu nén mà không cần giải nén hoặc chỉ giải nén một phần. Tìm kiếm không giải nén được gọi là so mẫu nén (full- compressed pattern matching hay còn gọi là compressed pattern matching), trong đó mẫu được nén rồi đem so với văn bản nén. Tuy nhiên phương pháp này nhiều khi không khả thi, đặc biệt là với những thuật toán nén có sử dụng các biểu diễn khác nhau cho cùng một xâu con, tuỳ thuộc vào ngữ cảnh của xâu con đó. Một kỹ thuật khác là so mẫu trên miền nén (compressed-domain pattern matching), trong đó sử dụng biện pháp giải nén bộ phận trên văn bản, nhờ đó mà tránh được một số hạn chế của phương pháp so mẫu nén mà vẫn đảm bảo không phải giải nén toàn bộ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 48 Hình 3.1. Phương pháp so mẫu trên miền nén có sử dụng otomat mờ Cải tiến từ thuật toán so mẫu KMP - BM mờ được giới thiệu ở Chương 1, một thuật toán theo kiểu so mẫu trên miền nén được đưa ra. Giải pháp này phù hợp với những văn bản đã được nén bằng bất kỳ phương pháp nén nào mà có giải nén là một khối kí tự. Ưu điểm quan trọng của việc sử dụng thuật toán KMP-BM mờ trên dữ liệu giải nén cục bộ so với các thuật toán kinh điển (như KMP, BM,...) là không cần lưu lại bất kỳ kí tự nào mà đã duyệt qua, đồng thời có tốc độ nhanh nhờ những bước dịch chuyển xa trên khối dữ liệu tìm kiếm, song việc cài đặt lại đơn giản. Ý tưởng chung của các thuật toán so mẫu trên miền nén có sử dụng tiếp cận otomat mờ được mô tả trong Hình 3.1. Văn bản nén Vùng đệm Otomat so mẫu Mẫu P Tiền xử lý Độ mờ xuất hiện mẫu P Giải nén cục bộ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 49 Hình 3.2. Phương pháp so mẫu không giải mã Nén dữ liệu text thực chất là một quá trình mã hóa, vì vậy thuật toán tìm kiếm trên văn bản nén có thể áp dụng đối với văn bản mã hóa dạng khối kí tự. Tuy nhiên, đối với các văn bản mã hóa, yêu cầu về tính bảo mật là rất quan trọng. Mặc dù dữ liệu giải nén cục bộ chỉ được lưu giữ một thời gian ngắn trên bộ nhớ trong, song không thể chắc chắn đây không là một sơ hở để lộ thông tin. Để nâng cao tính bảo mật, tránh rò rỉ thông tin ngay trong quá trình tìm kiếm, ý tưởng tìm kiếm xâu mẫu trong văn bản mã hóa mà không cần giải mã cục bộ được đưa ra. Phương pháp này được gọi là so mẫu không giải mã. Khả năng này có được chính là nhờ sử dụng tiếp cận otomat cho quá trình tìm kiếm. Hình 3.2 mô tả ý tưởng chung của các phương pháp so mẫu không giải mã. Trong Mục Tiền xử lý Mẫu P Nếu được 1 từ mã Đọc một ký tự thuộc bản mã Văn bản mã hoá Otomat đoán nhận một từ mã Otomat so mẫu Đọc một ký tự thuộc bản mã Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 50 3.2.3.3 sẽ trình bày một ứng dụng cụ thể kiểu so mẫu không giải mã, áp dụng trên văn bản mã hóa bởi mã đàn hồi (đây là một dạng mã dựa trên tích đàn hồi được giới thiệu trong [HN]). Với tiếp cận otomat mờ, các thuật toán tìm kiếm chính xác trên văn bản nén và mã hóa được trình bày ở đây có thể dễ dàng chuyển đổi sang tìm kiếm gần đúng bằng cách sử dụng những otomat so mẫu xấp xỉ đã giới thiệu ở trên. 3.2. Tìm kiếm trên văn bản nén 3.2.1. Các mô hình nén văn bản Nén dữ liệu là một lĩnh vực của lý thuyết thông tin mà mục đích chính là làm giảm thiểu khối lượng dữ liệu được lưu trữ và trao đổi. Nén dữ liệu text thực chất là một quá trình mã hóa, chuyển các thông báo nguồn (trong bảng chữ nguồn A) thành các bản mã (trong bảng chữ mã B) và ngược lại là quá trình giải mã. Các dạng mã hóa có thể là block - block, block - variable, variable - block và variable - variable , trong đó block - block là các thông báo nguồn và các bản mã đều có thể thay đổi. Một cách phân loại khác chỉ ra 2 phương pháp nén là tĩnh và động. Trong phương pháp tĩnh, ánh xạ từ tập thông báo nguồn đến tập từ mã được xác định trước khi bắt đầu quá trình chuyển đổi nên với một thông báo cho trước thì tất cả các lần xuất hiện của nó đều tương ứng với một bản mã. Với phương pháp động, ánh xạ từ tập thông báo đến tập bản mã thay đổi theo thời gian. Cho đến nay đã có nhiều thuật toán nén dữ liệu text được đưa ra [15], như nén Hufman, LZ, LZW,... 3.2.2. Thuật toán tìm kiếm trên dữ liệu nén dạng text Thuật toán theo tiếp cận mờ đã nêu ở mục 2.2 có thể áp dụng trên các tệp dữ liệu nén mà không cần giải nén toàn bộ. Ý tưởng cơ bản là đọc tuần tự trên tệp nén và mở nén một số mã nén, lưu kết quả giải nén Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 51 cục bộ vào vùng đệm và áp dụng thuật toán theo tiếp cận mờ trên vùng đệm này. Khi đó một số vấn đề đặt ra là: (i) Vùng đệm phải có độ dài đáp ứng được yêu cầu: - Luôn có thể đọc được một khối kí tự w độ dài m+1 (với m là độ dài xâu mẫu). - Kích thước phải đủ lớn để vùng đệm không bị tràn khi gặp trường hợp một mã nén tương ứng với một đoạn văn bản dài (chẳng hạn như trong thuật toán Run - length, giải nén mã nén a256 sẽ được 256 kí tự a liên tiếp). (ii) Truy xuất đến các phần tử trên vùng đệm nhanh, thuận tiện. Để đáp ứng yêu cầu (i), ta đưa ra hai điều kiện cho vùng đệm: - Điều kiện dưới: Dữ liệu trên vùng đệm phải có > m+1 kí tự (nếu chưa đọc hết văn bản). - Điều kiện trên: Dữ liệu trên vùng đệm phải có độ dài nhỏ hơn hoặc bằng kích thước của vùng đệm, trong đó kích thước của vùng đệm bằng độ dài tối đa khi giải nén của một mã nén cộng với m+1. Ở đây ta cần xem như độ dài tối đa của một mã nén khi giải nén đã được xác định cụ thể trong từng phương pháp giải nén khác nhau. Để đáp ứng yêu cầu (ii) ta sử dụng cấu trúc dữ liệu dạng hàng đợi vòng tròn (circular queue) dựa trên vùng đệm là một mảng kí tự như sau: buffer: array[1...bur_len] of char; trong đó buf_len = max_encode_len+m-1, với max_encode_len là độ dài tối đa khi mở nén của một mã nén. Hàng đợi vòng tròn trên vùng đệm được xác định bởi 2 con trỏ: F trỏ vào đầu lấy ra một phần tử trong queue, B trỏ vào đầu đưa một phần tử vào hàng đợi. Độ dài của hàng đợi (ký hiệu là len_queue) bằng số phần tử trên hàng đợi, cụ thể được tính theo công thức sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 52 len_queue =      FB,1FBlen_buf)1BF_(len_buf FB,1FB Hoạt động của queue Phép định vị con trỏ T trên hàng đợi sau bước nhảy qua k phần tử được xác định theo chiều kim đồng hồ bởi công thức: Tk =      len_bufkT,len_bufkT len_fbukT,kT Khi vùng đệm không thỏa mãn điều kiện dưới, cần phải bổ sung thêm một đoạn dữ liệu giải nén. Ta đặt giả thiết là từng phương pháp giải nén đều có thể xây dựng được thủ tục Decompress (buffer, B, len_queue) theo yêu cầu sau: (Hình 3.3) + Đọc một số mã nén, giải nén và lưu vào buffer bắt đầu từ vị trí b 1 + Kết thúc thủ tục, B trỏ vào kí tự cuối cùng được ghi vào buffer + Kết thúc thủ tục thì vùng đệm thỏa mãn điều kiện trên và dưới, có nghĩa m+1 < len_queue  buf_len. Nếu đã đọc hết văn bản mà điều kiện dưới vẫn chưa được đáp ứng thì chấp nhận len_queue  m+1. Hình 3.3. Queue trước (a) và sau (b) khi thực hiện thủ tục Decompress B Decompress B F len_queue len_queue m+1 (a) (b) m+1 F Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 53 Ở đây ta chỉ xét loại hình thức giải nén mà một mã nén cho ra một khối kí tự (như Hufman, LZ, LZW...). Với những giải thuật nén mà dữ liệu giải nén không ở dạng khối kí tự thì chỉ cần thay đổi nguyên tắc họat động của thủ tục Decompress. Có thể tăng thêm cơ chế quản lý buffer nếu dữ liệu là mảng các bit thì phải có con trỏ quản lý tới bit. Thuật toán 3.1. Vào: Mẫu P độ dài m, dòng dữ liệu S ở dạng nén, AP là bảng các kí tự xuất hiện trong mẫu P. Ra: - Mảng apr lưu vị trí xuất hiện của mẫu trên văn bản sau khi mở nén. - Counter lưu số lần xuất hiện mẫu P. Hình 3.4. Queue trước (a) và sau (b) bước nhảy n2‟ Phương pháp : (Hình 3.4) Begin F := 0; B := 0; lenqueue := 0; counter := 0; j := 0; n1 := 0; n2 := 1; repeat F := F  n2; j := j + n2; if len_queue <= m +1 then B F len_queue m+1 (a) B len_queue (b) F new = F old  n2‟ F old m+1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 54 Decompress (buffer, B, len_queue); if n2 > 1 then n1 := 0; n1’ := TFuzz (n1, buffer [F]); n2’ := 1; if n1’ = m then begin counter: =counter + 1; apr [counterr]:=j - m+1; end else if n1’ < m and n1’ < n1 then begin t:=F (m-n1’) if t > B then return; if buffer[t]  Ap then n2’:= 1 + m - n1’; end; len_queue := len_queue - n2’; n1:=n1’; n2:= n2’; until len_queue <= 0; End. Khả năng mở rộng của phương pháp Trong từng giải thuật nén và giải nén cụ thể, với những cấu trúc cụ thể, chẳng hạn dạng cây (Hufman, LZW) ta có thể dựa trên giải thuật trên, cải biên để xây dựng các giải thuật sử dụng một danh sách của vài con trỏ, trỏ vào những điểm thích hợp trên cây để tận dụng ngay cấu trúc cây trực tiếp, thay cho việc cần một hàng đợi thực sự, nhằm tăng hiệu quả của chương trình. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 55 3.3. Tìm kiếm trên văn bản mã hóa 3.3.1. Tìm kiếm trên văn bản mã hóa dạng khối kí tự Nén dữ liệu text thực chất là một quá trình mã hóa, vì vậy thuật toán tìm kiếm trên văn bản nén có thể áp dụng đối với văn bản mã hóa dạng khối kí tự, trong đó thủ tục giải nén Decompress được thay thế bằng thủ tục giải mã. 3.3.2. Mã đàn hồi Trong mã thông thường, tích hai từ là phép đặt 2 từ cạnh nhau và tập X là mã nếu một từ bất kỳ có sự phân tích thành tích của các từ mã trong X thì sự phân tích đó là duy nhất. Đã có nhiều phương pháp mở rộng khái niệm tích sử dụng kỹ thuật khác nhau để từ đó đề xuất xây dựng các lớp mã mới. Một trong những hướng nghiên cứu mở rộng trong lý thuyết mã là sử dụng các yếu tố điều khiển để đề xuất tích mới của các từ mã, nhằm xây dựng các lớp mã mới. Những hình thức mã mới như mã zigzag, mã điều khiển theo tích trộn đã được nhiều tác giả trên thế giới nghiên cứu, còn mã đàn hồi (spring product) được giới thiệu lần đầu tiên trong [16]. Ở đây ta giới hạn xem xét các ngôn ngữ xây dựng từ bảng chữ nhị phân B = {0,1} có độ dài như nhau, X  Bk = [0,1}k. Ý tưởng xây dựng tích đàn hồi là trong quá trình mã hóa, tích của các từ không ghép như tích thông thường mà có thể “co lại” hoặc “kéo dãn”. Ta sẽ sử dụng đồ thị để xây dựng khái niệm tích đàn hồi (được gọi là đồ thị xác định mã đàn hồi). Mỗi phần tử b = b1b2,...,bk  B k được mô tả bằng 1 đỉnh có tên tương ứng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 56 Từ mỗi đỉnh b = b1b2,...,bk có 2 cung đi ra đến 2 đỉnh c, d được xác định như sau: + Cung từ đỉnh b = b1b2,...,bk đến đỉnh c = b2...bk1 sẽ có nhãn 1 + Cung từ đỉnh b = b1b2,...,bk đến đỉnh d = b2...bk0 sẽ có nhãn 0 Ví dụ 3.1. Với k = 3, ta có đồ thị mô tả cho B3 = {0,1}3 như sau (Hình 3.5) Hình 3.5. Đồ thị xây dựng khái niệm tích đàn hồi Với việc sử dụng biểu diễn bằng đồ thị như trên, có thể định nghĩa tích đàn hồi của hai từ x,y B như sau. Định nghĩa 3.1. Cho ngôn ngữ X  Bk = {0,1}k, hai từ x, y  X, mà hai đỉnh tương ứng trong đồ thị của Bk là xB, yB. Tích đàn hôi của x, y kí hiệu x.py là một đường đi p từ xB đến yB không qua các đỉnh trung gian thuộc X: xB yB. 111 011 110 101 001 010 000 100 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 57 Chú ý rằng qua cách thể hiện bằng đồ thị ở trên, có thể có nhiều đường đi p: XB yB, tức là có thể có nhiều phương án mã hóa khác nhau (mã hóa đa trị). Một cách quy nạp ta định nghĩa: x1.px2.p....pxn = (x1.px2.p....pxn-1).p.xn Từ khái niệm tích đàn hồi, khái niệm mã đàn hồi được xây dựng như sau. Ví dụ 3.2. Cho X = {000,010,110,101] và ánh xạ mã a000, b010, c 110, d 101 ab được mã bởi 00(0)10 với tính chất “co lại” thay vì như tích ghép là 000010. Có thể thấy 00010 phân tích duy nhất thành các từ trong X. Tuy nhiên nếu mã ab bởi 000101 theo kiểu tích ghép thì giải mã theo kiểu tích đàn hồi sẽ không duy nhất, chẳng hạn. 000101 = (000)(101) = ad = (000) (010) (101) = abd. Để tránh tình huống này, khi mã hóa ad ta sẽ “kéo dãn” thành 0001101, khi đó 0001101 được giải mã thành (000)(001)(011)(101) = 000.00001.0101110101( sự phân tích là duy nhất qua các từ a, d trong X). Định nghĩa 3.2. Cho ngôn ngữ X  Bk = {0,1}k, X là mã tích đàn hồi nếu một từ bất kỳ được phân tích theo tích đàn hồi bởi các từ trong X thì sự phân tích đó là duy nhất. Ví dụ 3.3. Cho B 3, ngôn ngữ X ={000,010, 101, 111}. Giả sử có ánh xạ mã: a  000, b 010, c 111, d 1010 Tích ab được mã hóa bởi đường đi từ đỉnh 000 đến đỉnh 010 qua đỉnh 001: ab 00010. Tích abd được mã hóa bởi đường đi từ đỉnh 000 qua 001, 010 đến 101: abd 000101. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 58 Việc giải mã được tiến hành bằng việc duyệt theo con đường xác định bởi các nhãn. Chẳng hạn 000101 được giải mã như sau: + Từ đỉnh 000 = a theo nhãn 1: đến đỉnh 001. + Tiếp tục theo nhãn 0 đến đỉnh 010 = b, + Cuối cùng theo nhãn 1 đến đỉnh 101 = d. Kết quả được từ abd. Hình 3.6. Đồ thị xác định mã đàn hồi Mệnh đề 3.1. Cho ngôn ngữ X  Bk. X là mã đàn hồi khi và chỉ khi với mọi cặp đỉnh x, y  X, tồn tại ít nhất một đường đi từ x tới y không qua bất kỳ đỉnh trung gian nào khác thuộc X. 3.3.3. Tìm kiếm trên văn bản mã hóa bởi mã đàn hồi 3.3.3.1. Ý tưởng chung Giải pháp - Xây dựng otomat đoán nhận mã của một ký tự 111 011 110 101 001 010 000 100 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 59 - Kết hợp với otomat tìm kiếm theo mẫu tiếp cận mờ xác định độ mờ xuất hiện mẫu. Khi độ mờ này bằng độ dài mẫu, báo hiệu một lần xuất hiện mẫu. Yêu cầu: - Thuật toán tìm chính xác sự xuất hiện mẫu, không bỏ sót. - Không giải mã cục bộ mà vẫn thống kê được tần suất xuất hiện mẫu, mặc dù phương pháp mã hóa đàn hồi là đa trị. 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 3.3.3.2.1. Bài toán Giả sử: A là bảng chữ rõ; B là bảng chữ mã Hàm mã E: A  Bk Để thuận tiện cho việc trình bày, không mất tính tổng quát, có thể giả sử A = {a,b,c,d]=, b = {0,1}, k = 1, hàm mã hóa theo phương pháp mã đàn hồi xác định như sau (xem đồ thị Hình 3.4.): A a b c d E(A) 000 010 101 111 Xác định hàm bin: {0,...,2k} Bk, bin(i) cho xâu nhị phân của i. Bài toán đặt ra là: Cho xâu mẫu P = P1P2...Pm trên bảng chữ A. Xâu đích S được mã hóa thành Y = Y1Y2...Yn theo phương pháp mã đàn hồi. Thống kê tần suất xuất hiện mẫu P trong xâu mã hóa Y. 3.3.3.2.2. Mô tả phương pháp - Đổi sánh các kí tự đã mã hóa của mẫu P với xâu đích Y - Dùng otomat A0 tìm kiếm mẫu rõ để tìm vị trí đầu tiên gặp mã E(P1) của kí tự đầu của mẫu P; Otomat A1 đoán nhận mã; Otomat A2 đoán nhận độ mờ xuất hiện mẫu rõ P. Mỗi giá trị trạng thái ra của otomat A1 nếu là trạng thái kết thì sẽ là trạng thái vào của otomat A2. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 60 3.3.3.2.3. Chi tiết hóa các otomat trong thuật toán Otomat A1 đoán nhận mã A1(P) = (1, Q1,Q10, Q1F, 1), trong đó: 1 = {0,1}: bảng chữ vào Q1 = {0,1, ..., 2 k -1}: là tập trạng thái Q10: là tập trạng thái khởi đầu Q1F là tập trạng thái kết Q10 = Q1F = bin -1 (E(A)) = (A), với hàm  = bin-1.E Hàm chuyển 1 được xây dựng theo đồ thị xác định mã đàn hồi (xem Hình 3.6) Ví dụ 3.5: Với hàm mã hóa ở Mục (a), ta có : Q = {0,1,..,7}; Q10 = Q1F = {0,2,5,7} Hàm chuyển 1 được xây dựng là: A Q 0 1 0 0 1 1 2 3 2 4 5 3 6 7 4 0 1 5 2 3 6 4 5 7 6 7 Otomat A2 đoán nhận độ mờ xuất hiện mẫu rõ P Otomat A2 có quan hệ đẳng cấp với otomat mờ A(P) = (A,Q,q0,,F) tìm kiếm mẫu rõ (xem Định nghĩa 1.4, Mục 1.6.3.1); Bảng chữ vào là 2 = (AP){#}; Hàm chuyển là 2‟. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 61 Ví dụ 3.6. Với mẫu P = ababa, hàm chuyển 2‟ như sau: 2 Q 0 2 # 0 1 0 0 1 1 2 0 2 3 0 0 3 1 4 0 4 5 0 0 5 1 4 0 3.3.3.2.4. Thuật toán tìm kiếm mẫu dựa trên otomat Vào: Xâu mẫu rõ P, xâu mã Y = Y1Y2...Yn Ra: counter đếm số lần xuất hiện mẫu P + Giả sử đã xây dựng ba otomat A0, A1, A2 + Biến q ghi giá trị trạng thái của otomat A1 đoán nhận mã. Nếu q là một trạng thái kết, báo hiệu đoán nhận được mã của một ký tự trong bảng chữ A. + Biến f ghi giá trị độ mờ xuất hiện mẫu rõ P + Hàm AoSeek(P1,j) tìm vị trí (kết thúc) trên xâu mã hóa Y đọc được ký tự P1 lần đầu tiên, kể từ vị trí j trở đi. Phương pháp counter:= 0; j:=1; f:=0; j: = AoSeek(P1,j); {P1 là ký tự đầu tiên trng mẫu} if j = 0 then return (0); j:=J+1; f:=1; q = (P1); while j 0 do q:= 1(q,Yj); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 62 if q Q1F then f:=2(f,q); if f=m then counter:=counter+1; endif; endif; j:=j+1; andwhile; until j>=n; return (counter); Ví dụ 3.7. Với mẫu P=ababa, xâu đích S=aacdababab được mã hóa thành Y a b b b b Y = 0000110111000100011001001100010 a c a a b a Quá trình duyệt trên Y để thống kê tần suất xuất hiện mẫu P như sau: Khởi đầu 1 1 0 0 j Yj AoSeek(P1,j) q=1(q,Yj) f=2‟(f,q) counter 1 1 0 1 4 0 0 1 5 1 1 6 1 3 7 0 6 8 1 5 0 13 0 1 14 1 1 15 0 2 2 16 0 4 17 0 0 3 18 1 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 63 19 1 3 20 0 6 21 0 4 22 1 1 23 0 2 4 24 0 4 25 1 1 26 1 3 27 0 6 28 0 4 29 0 0 5 1 30 1 1 31 0 2 4 3.3.4. Tìm kiếm trên văn bản mã hóa hai tầng Trong một hệ thống bảo vệ dữ liệu cá nhân, việc sử dụng mã hóa đàn hồi và giải thuật so mẫu không giải mã sẽ đáp ứng tốt nhu cầu bảo mật mà vẫn có thể tìm thấy thông tin cần thiết. Tuy nhiên, để nâng cao mức độ bảo mật, tùy thuộc các nhu cầu ứng dụng và sử dụng được các sản phẩm mã hóa dữ liệu chất lượng cao sẵn có, phần này tác giả đưa ra giải pháp mã hóa hai tầng. Giả sử C1 là hàm mã hóa theo mã đàn hồi với hàm giải mã D1, C2 là hàm mã hóa hoặc hàm nén theo một giải thuật nào đó (như các hệ mã đối xứng AES, IDEA, SEFER; các hệ mã công khai RSA [16] [17]; nén Huffman, LXW,... [15], có hàm giải mã là D2. Quá trình mã hóa hai tầng được mô tả trong Hình 3.7 và Hình 3.8 là quá trình giải mã. Khi đó, giải thuật tìm kiếm mẫu trong văn bản mã hóa bởi mã hai tầng được thể hiện qua sơ đồ Hình 2.9. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 64 Bản rõ X C1 Y1 = C1(X) C2 Bản mã Y = C2(C1(X)) Hình 2.7. Quá trình mã hóa hai tầng Bản rõ X= D1(D2(Y)) D1 Y1 = D2(Y) D2 Bản mã Y Hình 2.8. Quá trình giải mã hai tầng Hình 2.9. Quá trình tìm kiếm mẫu trên văn bản mã hóa hai tầng 3.4. Kết luận chương 3 Chương này đã trình bày các kết quả của luận văn về vấn đề tìm kiếm mẫu trên môi trường văn bản nén và mã hóa, bao gồm: - Giới thiệu sơ đồ tìm kiếm tổng quát - Trình bày một thuật toán theo kiểu so mẫu miền nén, được cải tiến từ thuật toán KMP-BM (xem mục 2.4), để áp dụng cho văn bản nén dạng khối kí tự. Với những giải thuật nén mà dữ liệu giải nén không ở dạng khối kí tự, có thể cải biên thuật toán này bằng cách thay đổi nguyên tắc họat động của thủ tục giải nén. Giải mã Y bởi D2 Y: Văn bản mã hóa hai tầng Y1: Văn bản mã hóa bởi C1 Đọc 1 ký tự thuộc bản mã Otomat đoán nhận một từ mã Nếu được 1 từ mã Otomat so mẫu Độ mờ xuất hiện mẫu P Tiền xử lý Mẫu P Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 65 KẾT LUẬN Luận văn đã tìm hiểu về otomat mờ, một số thuật toán tìm kiếm và đã giới thiệu hai bài toán so mẫu xấp xỉ - chính xác. Trình bày những thuật toán so mẫu của hai bài toán trên đều dựa vào độ tương tự giữa hai xâu theo một mô hình "lỗi" kinh điển. Ngoài ra, luận văn trình bày thuật toán so mẫu cho văn bản nén và mã hoá dạng text thu được những kết quả dưới. Các kết quả đạt được của luận văn:  Trình bày được tổng quan về tìm kiếm mẫu trên văn bản, từ đó đưa ra các dạng tìm kiếm mẫu.  Giới thiệu hệ mờ, ý tưởng chung của tiếp cận otomat mờ. Sau đó đưa ra một số thuật toán so mẫu như KMP, BM.  Trình bày thuật toán so mẫu chính xác và xấp xỉ theo tiếp cận otomat mờ và thuật toán tìm kiếm mẫu trong văn bản nén và mã hoá. Một số hạn chế của luận văn:  Chưa cài đặt được chương trình tìm kiếm mẫu trong văn bản nén và mã hoá.  Thuật toán đưa ra còn chưa tối ưu.  Trình bày luận văn còn lủng củng. Hướng nghiên cứu tiếp theo:  Cài đặt chương trình tìm kiếm mẫu trong văn bản nén, mã hoá và ứng dụng trong các chương trình tìm kiếm thông tin.  Giới thiệu thuật toán tối ưu hơn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 66 Do thời gian và khả năng có hạn, luận văn còn thiếu sót nhiều, em rất mong nhận được sự góp ý, chỉ dẫn thêm của các Thầy Cô, bạn bè để em có thể xây dựng được ứng dụng hoàn thiện hơn. Một lần nữa em xin chân thành cảm ơn Thầy hướng dẫn PGS.TS. Đoàn Văn Ban, các Thầy Cô trong khoa đã tạo mọi điều kiện thuận lợi để em có thể hoàn thành luận văn đúng thời hạn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 67 TÀI LIỆU THAM KHẢO Tiếng Anh [1]. Gonzalo Navarro, Mathieu Raffinot (2000), Fast and Flexible String Matching by Combining Bit - Parallelism and Suffix Automata, ACM Journal of Experimental Algorithmics (JEA). [2]. Gonzalo Navarro, Mathieu Raffinot (2002), Flexible Pattern Matching in Strings, Cambridge University Press, ISBN 0-521-81307-7. [3]. Heikki Hyyro (2002), A Bit - Vector Algorithm for Computing Levenshtein and Damerau Edit Distances, Proceedings of the Prague Stringology Conference '02, pp. 44-54. [4]. Aho A.V.(1992), Algorithms for finding patterns in strings, Chapter 5 of Jan Van Leeuwen (ed.), Handbook of Theoretical Computer Science "Algorithms and Complexity", The MIT Press, pp. 255-300. [5]. Christian Charras, Thierry Lecroq (2000), Handbook of Exact Stringmatching Algorithms. Tiếng Việt [6]. Phan Trung Huy và Nguyễn Quý Khang (2002), "A New Algorithm For LCS Problem", Kỷ yếu Hội nghị Toán học Toàn quốc 9/2002. [7]. Robert Sedgewick (1994), Cẩm nang thuật toán, Tập 1: Các thuật toán thông dụng, NXB Khoa học và Kỹ thuật, tr. 324 - 351. [8]. Vũ Thành Nam, Phan Trung Huy, Nguyễn Thị Thanh Huyền (2005), Mã tích đàn hồi và tìm kiếm trên văn bản mã hoá sử dụng thuật toán so mẫu theo tiếp cận mờ, Báo cáo khoa học tại Hội nghị Ứng dụng toán học toàn quốc lần 2, Hà Nội, 12/2005. [9]. Nguyễn Thị Thanh Huyền (2006), Luận án Tìm kiếm mờ, phân cụm mờ và ứng dụng trên mạng tại trường Đại học Bách khoa Hà Nội.