Tài liệu Nghiên cứu thuật toán knuth-morris-pratt và ứng dụng

  • Số trang: 76 |
  • Loại file: PDF |
  • Lượt xem: 41 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 27125 tài liệu

Mô tả:

-1- ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG ĐỖ QUỲNH ANH NGHIÊN CỨU THUẬT TOÁN KNUTH-MORRIS-PRATT VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS: ĐỖ TRUNG TUẤN Thái Nguyên – 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ -2- MỤC LỤC MỤC LỤC .......................................................................................................................1 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ..................................................5 DANH MỤC CÁC HÌNH VẼ VÀ CÁC BẢNG ............................................................ 6 MỞ ĐẦU ......................................................................................................................... 7 CHƢƠNG 1. SO KHỚP CHUỖI ..................................................................................10 1.1. Khái niệm so khớp chuỗi ...................................................................................10 1.2. Lịch sử phát triển................................................................................................ 11 1.3. Các cách tiếp cận ................................................................................................ 12 1.4. Ứng dụng của so khớp chuỗi..............................................................................12 1.5. Các dạng so khớp chuỗi .....................................................................................13 1.5.1. So khớp đơn mẫu ........................................................................................ 13 1.5.2. So khớp đa mẫu........................................................................................... 14 1.5.3. So mẫu mở rộng .......................................................................................... 15 1.5.4. So khớp chính xác ....................................................................................... 16 1.5.5. So khớp xấp xỉ ............................................................................................ 17 1.5.5.1. Phát biểu bài toán ................................................................................17 1.5.5.2. Các tiếp cận so khớp xấp xỉ .................................................................18 1.5.5.3. Độ tƣơng tự giữa hai xâu .....................................................................19 1.5. Một số thuật toán so mẫu ...................................................................................20 1.5.1. Thuật toán Brute Force ...............................................................................20 1.5.2. Thuật toán Karp-Rabin ...............................................................................21 1.5.3. Thuật toán BM ( Boyer- Moor) ..................................................................24 1.5.4. Các thuật toán khác .....................................................................................27 1.6. Khớp chuỗi với otomat hữu hạn .........................................................................28 1.6.1. Otomat hữu hạn ........................................................................................... 28 1.6.1.1. Ôtômát hữu hạn đơn định DFA ........................................................... 29 1.6.1.2. Ôtômát hữu hạn không đơn định NFA ................................................33 1.6.2. Otomat khớp chuỗi......................................................................................36 1.6.2.1. Giới thiệu ............................................................................................. 36 1.6.2.2. Thuật toán xây dựng Otomat so khớp chuỗi .......................................38 1.7. Kết luận chƣơng .................................................................................................40 CHƢƠNG 2. THUẬT TOÁN SO KHỚP CHUỖI KNUTH-MORRIS-PRATT..........41 2.1. Thuật toán KMP .................................................................................................41 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ -32.1.1. Giới thiệu thuật toán ...................................................................................41 2.1.2. Bảng so sánh một phần ...............................................................................45 2.1.3. Độ phức tạp của thuật toán KMP ................................................................ 47 2.2. Thuật toán KMP mờ ........................................................................................... 48 2.2.1. Otomat so mẫu ............................................................................................ 48 2.2.2. Thuật toán ...................................................................................................49 2.2.2.1 Thuật toán tạo lập TFuzz ......................................................................49 2.2.2.2. Thuật toán tìm kiếm mẫu dựa vào bảng TFuzz ...................................51 2.2.3. So sánh KMP và thuật toán KMP mờ ......................................................... 52 2.3. Thuật toán KMP - BM mờ .................................................................................53 2.3.1. Ý tƣởng của thuật toán ................................................................................53 2.4.2. Otomat mờ so mẫu ......................................................................................55 2.3.2.1. Giới thiệu ............................................................................................. 55 2.3.2.2. Hoạt động của otomat mờ so mẫu ....................................................... 55 2.3.3. Thuật toán tìm kiếm ....................................................................................56 2.4. Kết luận chƣơng .................................................................................................57 CHƢƠNG 3. ỨNG DỤNG THUẬT TOÁN KMP TRONG TÌM KIẾM THÔNG TIN TRÊN VĂN BẢN..........................................................................................................58 3.1. Bài toán tìm kiếm mẫu trên văn bản ..................................................................58 3.1.1. Tìm kiếm mẫu ............................................................................................. 58 3.1.2. Tìm kiếm thông tin......................................................................................59 3.1.2.1 Giới thiệu .............................................................................................. 59 3.1.2.2 Các mô hình tìm kiếm thông tin thƣờng sử dụng .................................61 3.2. Mã nguồn mở Lucene ........................................................................................ 64 3.2.1. Giới thiệu ....................................................................................................64 3.2.2. Các bƣớc sử dụng Lucene ...........................................................................66 3.3. Ứng dụng tìm kiếm thông tin trên văn bản ........................................................ 67 3.4. Cài đặt chƣơng trình thử nghiệm .......................................................................68 3.4.1. Giải pháp, công nghệ sử dụng.....................................................................68 3.4.2. Nội dung chƣơng trình ................................................................................68 3.4.3. Kết quả thực nghiệm ...................................................................................71 3.4.3.1. Giao diện chính của chƣơng trình ....................................................... 72 3.4.3.2. Kết quả thử nghiệm của chƣơng trình khi tìm kiếm với từ khóa “Văn bản” ...................................................................................................................72 3.5. Kết luận chƣơng 3 .............................................................................................. 73 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ -4KẾT LUẬN ...................................................................................................................74 TÀI LIỆU THAM KHẢO ............................................................................................. 76 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ -5- DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT BM Thuật toán Boyer - Moore DFA Deterministic Finite Automata - Ôtômát hữu hạn đơn định DOC Document FA Finite Automata - Ôtômát hữu hạn HTML HyperText Markup Language IDF Inverse document frequency - Tần suất tài liệu ngƣợc KMP KNUTH-MORRIS-PRATT LAN Local area network NFA Nondeterministic Finite Automata - Ôtômát hữu hạn không đơn định TF Term frequency - Tần suất từ Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ -6- DANH MỤC CÁC HÌNH VẼ VÀ CÁC BẢNG Hình 1.1. Sơ đồ chuyển của một DFA ................................................................ 30 Hình 1.2. Mô tả một DFA ................................................................................... 31 Bảng 1.1. Ví dụ hàm chuyển δ của DFA ............................................................ 32 Hình 1.3. Sơ đồ của một NFA ............................................................................. 34 Hình 1.4. Di chuyển chuỗi .................................................................................. 35 Bảng 1.2. Ví dụ hàm chuyển trạng thái δ của NFA ............................................ 35 Hình1.5. Ví dụ so khớp chuỗi ............................................................................. 37 Hình 1.6. Ví dụ otomat so khớp chuỗi ................................................................ 38 Bảng 2.1. Bảng so sánh một phần ....................................................................... 46 Bảng 2.2. Thí dụ khác ......................................................................................... 46 Bảng 2.3. Trƣờng hợp mẫu xấu nhất với thuật toán KMP.................................. 47 Bảng 2.4. Bảng next ............................................................................................ 51 Bảng 2.5. Bảng TFuzz ......................................................................................... 51 Bảng 2.6. Minh họa thí dụ ................................................................................... 52 Hình 2.1. Dịch chuyển con trỏ trên mẫu ............................................................. 52 Bảng 2.7. Kết quả tìm sự xuất hiện mẫu P trong tệp S theo KMP và tiếp cận mờ ............................................................................................................................. 53 Hình 2.2. Ý tƣởng chung của thuật toán KMP-BM mờ ...................................... 55 Hình 3.1. Mô hình biểu diễn và so sánh thông tin .............................................. 60 Hình 3.2. Mô hình không gian vec tơ ................................................................. 62 Bảng 3.1. Tính điểm số ....................................................................................... 64 Hình 3.3. Mô hình đánh chỉ mục của Lucene ..................................................... 65 Hình 3.4. Mô hình ứng dụng tìm kiếm thông tin văn bản .................................. 68 Hình 3.5. Giao diện chính của chƣơng trình ....................................................... 72 Hình 3.6. Kết quả tìm kiếm của chƣơng trình..................................................... 73 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ -7- MỞ ĐẦU 1. Lý do chọn đề 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. Cùng với sự phổ biến của công nghệ thông tin, số lƣợng các tài liệu điện tử cũng gia tăng từng ngày. Đến nay, số lƣợng các tài liệu đƣợc lƣu trữ lên đến hàng tỷ trang. Trong khi đó, nhu cầu khai thác trong kho tài liệu khổng lồ này để tìm kiếm những thông tin cần thiết đang là nhu cầu thƣờng ngày và thiết thực của ngƣời sử dụng. Tuy nhiên, một trong những khó khăn con ngƣời gặp phải trong việc khai thác thông tin là khả năng tìm chính xác thông tin họ cần trong kho tài liệu. Để trợ giúp công việc này, các hệ thống tìm kiếm đã lần lƣợt đƣợc phát triển nhằm phục vụ cho nhu cầu tìm kiếm của ngƣời sử dụng. Những hệ thống tìm kiếm bắt đầu phát triển và đƣa vào ứng dụng, phổ biến là các hệ thống tìm kiếm theo từ khóa. Nhiều hệ thống hoạt động hiệu quả trên Internet nhƣ Google, Bing, Yahoo!… Tuy nhiên, phần lớn các công cụ tìm kiếm này là những sản phẩm thƣơng mại và mã nguồn đƣợc giữ bí mật. Hoặc các hệ thống tìm kiếm trên máy cá nhân nhƣ Windows Search, Google Desktop… đã đáp ứng phần nào nhu cầu của ngƣời sử dụng, miễn phí cho cá nhân, tuy nhiên cũng chỉ đáp ứng đƣợc trên phạm vi nhỏ và mới chỉ dừng lại ở mức độ tìm kiếm từ khóa theo tiêu đề và phần tóm tắt. Có một cách tiếp cận hiệu quả để giải quyết vấn đề này là thực hiện việc Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ -8- so khớp và tìm kiếm toàn văn. Một trong những thuật toán so khớp chuỗi kinh điển là thuật toán KMP. Có thể nói, KPM là một thuật toán mới mẻ ít đƣợc sử dụng tại Việt Nam trong việc quản lý, lƣu trữ và xử lý lƣợng dữ liệu lớn nhƣng rất hiệu quả và chính xác. Dựa trên hƣớng tiếp cận đó và sự hƣớng dẫn của giáo viên, tôi mạnh dạn nhận đề tài “So khớp chuỗi và thuật toán Knuth-MorrisPratt”. 2. Đối tƣợng và phạm vi nghiên cứu Các khái niệm so khớp chuỗi. Các khái niệm thuật toán so khớp chuỗi KMP. Một số ứng dụng trong thuật toán KMP. 3. Hƣớng nghiên cứu của đề tài Nghiên cứu tìm kiếm Knuth–Morris–Pratt và ứng dụng trong việc tìm kiếm thông tin trên văn bản. Nghiên cứu giải pháp công nghệ cài đặt chƣơng trình thử nghiệm. 4. Những nội dung chính Luận văn đƣợc trình bày trong 3 chƣơng, có phần mở đầu, phần kết luận, phần mục lục, phần tài liệu tham khảo. Luận văn đƣợc chia làm ba chƣơng với nội dung cơ bản nhƣ sau: Chƣơng 1: Trình bày khái niệm về so khớp chuỗi, các hƣớng tiếp cận, các dạng so khớp và một số thuật toán so mẫu. Chƣơng 2: Trình bày về thuật toán KMP, thuật toán KMP mờ và thuật toán KMP-BM mờ. Chƣơng 3: Trình bày về bài toán tìm kiếm thông tin trên văn bản và tiến hành cài đặt thử nghiệm chƣơng trình. 5. Phƣơng pháp nghiên cứu Tổng hợp các tài liệu đã đƣợc công bố về thuật toán tìm kiếm thông tin, Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ -9- khai phá dữ liệu, đặc biệt các kết quả nghiên cứu liên quan đến thuật toán tìm kiếm thông tin. Thực nghiệm thuật toán tìm kiếm KMP với dữ liệu mẫu. Nhận xét, đánh giá kết quả thử nghiệm. 6. Ý nghĩa khoa học của đề tài Luận văn nghiên cứu kỹ thuật, thuật toán tìm kiếm thông tin là cơ sở hỗ trợ cho công tác dự báo, lập kế hoạch, quy hoạch, phân tích dữ liệu quản lý, chuyên môn, nghiệp vụ. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ - 10 - CHƢƠNG 1. SO KHỚP CHUỖI 1.1. Khái niệm so khớp chuỗi So khớp chuỗi là một kỹ thuật đóng vai trò nền tảng trong lĩnh vực xử lý văn bản. Hầu nhƣ tất cả các trình soạn thoải và xử lý văn bản đều cần phải có một cơ chế để so khớp các chuỗi trong tài liệu hiện tại. Việc tích hợp các thuật toán so khớp chuỗi là một trong những khâu cơ bản đƣợc sử dụng trong việc triển khai phần mềm và đƣợc thực hiện trên hầu hết các hệ điều hành. Mặc dù hiện nay dữ liệu đƣợc lƣu trữ dƣới nhiều hình thức khác nhau, nhƣng văn bản vẫn là hình thức chủ yếu để lƣu trữ và trao đổi thông tin. Trong nhiều lĩnh vực nhƣ so khớp, trích chọn thông tin, tin sinh học…, một lƣợng lớn dữ liệu thƣờng đƣợc lƣu trữ trong các tập tin tuyến tính. Hơn nữa khối lƣợng dữ liệu thu thập đƣợc tăng lên rất nhanh nên đòi hỏi phải có các thuật toán xử lý và so khớp dữ liệu văn bản hiệu quả So khớp chuỗi là việc so sánh một hoặc nhiều chuỗi (thƣờng đƣợc gọi là mẫu hoặc Pattern) với văn bản để tìm vị trí và số lần xuất hiện của chuỗi đó trong văn bản. Ta hình thức hoá bài toán so khớp chuỗi nhƣ sau: coi văn bản là một mảng T[1..n] có chiều dài n và khuôn mẫu là một mảng P[1..m] có chiều dài m; các thành phần của T và P là các ký tự đƣợc rút từ một bảng chữ cái hữu hạn ∑. Ví dụ, ta có thể có ∑ = {0,1} hoặc ∑ ={a,b,....,z}. Các mảng ký tự P và T thƣờng đƣợc gọi là các chuỗi ký tự. Ta nói rằng một chuỗi w là tiền tố (hậu tố) của một chuỗi x, ký hiệu là w ⊂ x (w ⊃ x), nếu x = wy (x = yw), với y là một chuỗi nào đó. Để ngắn gọn, ta kí hiệu Pk để thể hiện tiền tố k - ký tự P[1..k] của khuôn mẫu P[1..m]. Ta nói rằng khuôn mẫu P xảy ra với khoá chuyển s trong văn bản T (hoặc, theo tƣơng đƣơng, nói rằng khuôn mẫu P xảy ra bắt đầu tại vị trí s + i trong văn bản T) nếu 0 ≤ s ≤ n-m và T[s + 1..s + m] = P[1..m] (nghĩa là, nếu T[s+j] = P[j], với 1 ≤ j ≤ m). Bài toán so khớp chuỗi là bài toán tìm tất cả các Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ - 11 - khoá chuyển hợp lệ với nó một khuôn mẫu P đã cho xảy ra trong một văn bản T đã cho. Ví dụ: khuôn mẫu P = abaa xuất hiện một lần trong văn bản T = abcabaabcabac, tại khoá chuyển s = 3. Với bài toán này, rõ ràng ta có một cách làm đơn giản là tìm tất cả các khoá chuyển hợp lệ dùng một vòng lặp kiểm tra điều kiện P[1..m] = T[s+1..s+m] với n - m + 1 giá trị có thể của s. 1.2. Lịch sử phát triển Trong năm 1970, S.A. Cook đã chứng minh một kết quả lý thuyết giúp suy ra sự tồn tại của một thuật toán để giải bài toán so khớp mẫu có thời gian tỷ lệ với (M+N) trong trƣờng hợp xấu nhất. D.E.Knuth và V.R.Pratt đã kiên trì theo đuổi kiến trúc mà Cook đã dùng để chứng minh cho định lý của ông và nhận đƣợc một thuật toán tƣơng đối đơn giản. Đồng thời J.H.Morris cũng khám phá ra thuật toán này. Knuth, Morris, Pratt đã không giới thiệu thuật này của họ cho đến năm 1976, và trong thời gian này R.S.Boyer và J.S.Moore đã khám phá ra một thuật toán nhanh hơn nhiều. Tháng 6 – 1975, Alfred V. Aho và Margret J. Corasick đã giới thiệu thuật toán so khớp chuỗi đa mẫu Aho Corasick trong tài liệu “Communications of the ACM 18”. Năm 1980, Nigel Horspool đã giới thiệu thuật toán so khớp chuỗi tƣơng tự thuật toán KMP, nhƣng đảo ngƣợc thứ tự so sánh trong tài liệu Software Practice & Experience, 10(6):501-506. Tháng 3 - 1987, R.M.Karp và M.O.Rabin đã giới thiệu thuật toán đơn giản gần nhƣ thuật toán Brute Force có thời gian thực thi tỉ lệ với m+n trong tài liệu IBM J. Res develop – vol 31 no.2. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ - 12 - 1.3. Các cách tiếp cận Có 4 cách tiếp cận chính của các thuật toán so khớp chuỗi: Thuật toán cổ điển: là các thuật toán chủ yếu dựa vào sự so sánh giữa các ký tự. Các thuật toán điển hình bao gồm Brute Force, Naïve,… Thuật toán máy tự động hậu tố: là các thuật toán sử dụng cấu trúc dữ liệu hậu tố tự động để nhận ra tất cả các hậu tố của mẫu. Các thuật toán điển hình bao gồm Knuth – Morris – Pratt, Boyer – Moore, Horspool,… Thuật toán bit song song: là các thuật toán khai thác bản chất song song của các dữ liệu bit để thực hiện các thao tác cùng lúc. Các thuật toán điển hình bao gồm Shift – Or, … Thuật toán băm: là các thuật toán sử dụng kỹ thuật băm, tránh việc so sánh các ký tự có độ phức tạp bậc 2. Các thuật toán điển hình bao gồm Karp – Rabin. Độ phức tạp tính toán: Trên thực tế có nhiều loại ký tự khác nhau nhƣ: binary, DNA, Alphabet, numeric… và mỗi loại ký tự có độ phức tạp khác nhau. Độ phức tạp tính toán tỉ lệ thuận với chiều dài của mẫu, chiều dài của vănbản và độ lớn của tập các ký tự. Các thuật toán so khớp chuỗi thƣờng đƣợc thực hiện theo 2 bƣớc xử lý sau: Bƣớc tiền xử lý: bao gồm xử lý mẫu và Khởi tạo cấu trúc dữ liệu. Bƣớc so khớp: thực hiện việc so khớp mẫu trong văn bản. 1.4. Ứng dụng của so khớp chuỗi So khớp chuỗi là một trong những bài toán cơ bản của ngành Tin học. So Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ - 13 - khớp chuỗi đƣợc sử dụng rộng rãi trong nhiều ứng dụng và lĩnh vực khác nhau nhƣ: Chức năng search trong các trình soạn thảo văn bản và web browser. Các công cụ so khớp nhƣ: Google Search, Yahoo Search,…. Sinh học phân tử nhƣ trong so khớp các mẫu trong DNA, protein,…. So khớp cơ sở dữ liệu. Trong nhiễu kênh với cho phép chấp nhận đƣợc. Trong so khớp mẫu hoặc vết của tấn công, đột nhập và các phần mềm độc hại. Trong lĩnh vực an toàn mạng và an toàn thông tin…. 1.5. Các dạng so khớp chuỗi Phân loại các thuật toán so khớp dựa trên các đặc tính của mẫu ta có các dạng: so khớp đơn mẫu, so khớp đa mẫu (mẫu là tập các xâu), so khớp mẫu mở rộng, so khớp biểu thức chính qui với hai hƣớng tiếp cận là so khớp chính xác và xấp xỉ. 1.5.1. So khớp đơn mẫu 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. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ - 14 - 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, 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. 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à so khớp 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 1.5.2. So khớp đa mẫu Cho một mẫu P gồm tập các từ khoá w1, w2,….,w Số hóa bởi Trung tâm Học liệu k và xâu vào S = http://www.lrc-tnu.edu.vn/ - 15 - 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, có tốc độ cải thiện đáng kể khi số từ khoá nhiều và thuật 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, 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. 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 so khớp 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. 1.5.3. So mẫu mở rộng Trong nhiều ứng dụng, so khớp 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. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ - 16 - 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 - 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.5.4. So khớp chính xác Tìm một (hoặc nhiều) vị trí xuất hiện chính xác cuả một xâu ký tự P[1..m] (mẫu so khớp - pattern) ở trong một xâu ký tự lớn hơn hay trong một đoạn văn bản nào đó T[1..n], m<=n. Ví dụ: ta có thể tìm thấy vị trí của xâu “abc” trong xâu “abcababc” là 1 và 6. Phát biểu hình thức bài toán nhƣ sau: gọi Σ là một tập hữu hạn (finite set) các ký tự. Thông thƣờng, các ký tự của cả mẫu so khớp và đoạn văn bản gốc đều nằm trong Σ. Tập Σ tùy từng ứng dụng cụ thể có thể là bảng chữ cái tiếng Anh từ A đến Z thông thƣờng, cũng có thể là một tập nhị phân chỉ gồm hai phần tử 0 và 1 (Σ = {0,1}) hay có thể là tập các ký tự DNA trong sinh học (Σ = {A,C,G,T}). Phƣơng pháp đơn giản nhất là lần lƣợt xét từng vị trí i trong xâu ký tự gốc từ 1 đến n-m+1, so sánh T[i…(i+m-1)] với P[1..m] bằng cách xét từng cặp ký tự một và đƣa ra kết quả so khớp. Ngƣời ta còn gọi phƣơng pháp này là cách tiếp cận ngây thơ (Naïve string search). Dƣới đây là thủ tục đặc tả của phƣơng pháp này: NAÏVE_STRING_MATCHER (T, P) 1. n ← length [T] 2. m ← length [P] 3. for s ← 1 to n-m+1 do 4. j ← 1 5. while j ≤ m and T[s + j] = P[j] do 6. j ← j +1 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ - 17 7. If j > m then 8. return s // s là vị trí tìm được 9. return false. // không có vị trí nào thỏa mãn Độ phức tạp trung bình của thuật toán là O(n+m), nhƣng trong trƣờng hợp xấu nhất độ phức tạp là O(n.m), ví dụ nhƣ so khớp mẫu “”aaaab” trong xâu “aaaaaaaaab”. 1.5.5. So khớp xấp xỉ 1.5.5.1. Phát biểu bài toán So mẫu 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 đề so khớp 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 so khớp 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”. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ - 18 - 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 so khớp “mềm dẻo” này của ngƣời sử dụng. Bài toán so mẫu xấp xỉ tổng quát đƣợc phát biểu nhƣ sau: 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.5.5.2. Các tiếp cận so khớp xấp xỉ Thuật toán so khớp xấp xỉ hiện nay chia 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. 2) Các thuật toán sử dụng otomat so khớp: 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. Đâ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: 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. 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. 4) Các thuật toán sử dụng cơ chế lọc: Cố gắng thu hẹp không gian so khớp 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 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ - 19 - 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. Trong PEX, mẫu đƣợc chia thành k + 1 đoạn và sắp xếp để so khớp đ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 so khớp 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 so khớp đ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.5.5.3. Độ tương tự giữa hai xâu Để so khớp xấp xỉ, cần sử dụng một hàm khoảng cách đ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. 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: Đố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 để biến đổi Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ - 20 - 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: 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: 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 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.5. Một số thuật toán so mẫu 1.5.1. Thuật toán Brute Force Thuật toán Brute Force thử kiểm tra tất cả các vị trí trên văn bản từ 1 cho đến n-m+1. Sau mỗi lần thử thuật toán brute force dịch mẫu sang phải một ký tự Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
- Xem thêm -