Luận văn Thạc sĩ Công nghệ thông tin: Tìm hiểu một số giải thuật tìm kiếm chuỗi con và ứng dụng

Chia sẻ: Tomjerry001 | Ngày: | Loại File: PDF | Số trang:53

Thêm vào BST

Báo xấu

37
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung nghiên cứu của đề tài bao gồm 3 chương sau: Chương 1: Tổng quan về tìm kiếm chuỗi con: Nghiên cứu tổng quan về tìm kiếm chuỗi con và ứng dụng của tìm kiếm chuỗi con trong thực tế. Chương 2: Các thuật toán tìm kiếm chuỗi con : Nghiên cứu các thuật toán tìm kiếm chuỗi con kèm theo đánh giá, so sánh giữa các thuật toán tìm kiếm chuỗi con. Chương 3: Kết quả thực nghiệm và ứng dụng tìm kiếm chuỗi con trong xâu gói tin và cài đặt thử nghiệm: Sử dụng các thuật toán tìm kiếm chuỗi con. Từ đó cài đặt thử nghiệm và đánh giá kết quả thuật toán.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: Tìm hiểu một số giải thuật tìm kiếm chuỗi con và ứng dụng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ ĐÀO THỊ DUNG TÌM HIỂU MỘT SỐ GIẢI THUẬT TÌM KIẾM CHUỖI CON VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội – 2016
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ ĐÀO THỊ DUNG TÌM HIỂU MỘT SỐ GIẢI THUẬT TÌM KIẾM CHUỖI CON VÀ ỨNG DỤNG Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. NGUYỄN TRÍ THÀNH Hà Nội – 2016
LỜI CẢM ƠN Sau thời gian nghiên cứu, làm việc khẩn trƣơng và đƣợc sự hƣớng dẫn tận tình giúp đỡ của thầy giáo PGS.TS Nguyễn Trí Thành, luận văn với đề tài “ Tìm hiểu một số giải thuật tìm kiếm chuỗi con và ứng dụng” đã đƣợc hoàn thành. Tác giả xin bày tỏ lòng biết ơn sâu sắc tới: Thầy giáo hƣớng dẫn PGS.TS Nguyễn Trí Thành đã tận tình chỉ dẫn, giúp đỡ tác giả hoàn thành luận văn. Các thầy cô giáo Trƣờng Đại học công nghệ và một số đồng nghiệp, đã quan tâm động viên, giúp đỡ tác giả trong suốt quá trình học tập để hoàn thành luận văn này. Mặc dù đã cố gắng hết sức, song do điều kiện thời gian và kinh nghiệm thực tế của bản thân còn ít, cho nên đề tài không thể tránh khỏi thiếu sót. Vì vậy, tác giả mong nhận đƣợc sự đóng góp ý kiến của các thầy giáo, cô giáo và các bạn bè đồng nghiệp. Tôi xin chân thành cảm ơn! Hà Nội, ngày 10 tháng 03 năm 2016 Tác giả Đào Thị Dung 1
LỜI CAM ĐOAN Tên tôi là: Đào Thị Dung Sinh ngày 30 tháng 12 năm 1989 Học viên lớp cao học khoá 20 HTTT - Trƣờng đại học công nghệ - ĐHQGHN Hiện đang công tác tại : Trƣờng THPT DTNT Tỉnh Vĩnh Phúc Xin cam đoan luận văn “ Tìm hiểu một số giải thuật tìm kiếm chuỗi con và ứng dụng” do thầy giáo PGS.TS Nguyễn Trí Thành hƣớng dẫn là công trình nghiên cứu của riêng tôi. Tất cả các tài liệu tham khảo đều có nguồn gốc, xuất xứ rõ ràng. Tác giả xin cam đoan tất cả những nội dung trong luận văn đúng nhƣ nội dung trong đề cƣơng và yêu cầu của thầy giáo hƣớng dẫn. Nếu có vấn đề gì trong nội dung của luận văn tác giả xin hoàn toàn chịu trách nhiệm với lời cam đoan của mình. Hà Nội, ngày 10 tháng 03 năm 2016 Học viên Đào Thị Dung 2
MỤC LỤC LỜI CẢM ƠN ..................................................................................................................1 LỜI CAM ĐOAN ............................................................................................................2 MỤC LỤC .......................................................................................................................3 Danh mục các ký hiệu và chữ viết tắt ..............................................................................5 Danh mục các bảng..........................................................................................................6 Danh mục hình ảnh ..........................................................................................................7 MỞ ĐẦU .........................................................................................................................8 CHƢƠNG 1. TỔNG QUAN VỀ TÌM KIẾM CHUỖI CON ........................................13 1.1. Lịch sử về tìm kiếm chuỗi con ......................................................................... 13 1.1.1. Thuật toán trƣớc những năm 2000 ...............................................................13 1.1.2. Thuật toán sau năm 2000 ..............................................................................14 1.2. Tìm kiếm chuỗi con ......................................................................................... 15 1.2.1. Khái niệm về tìm kiếm chuỗi con .................................................................15 1.2.2. Các cách tiếp cận: .........................................................................................16 1.2.3. Các dạng tìm kiếm chuỗi ..............................................................................16 1.2.4. Ứng dụng của tìm kiếm chuỗi ......................................................................20 1.3. Tóm tắt chƣơng ................................................................................................... 18 CHƢƠNG 2. CÁC THUẬT TOÁN TÌM KIẾM CHUỖI CON ...................................19 2.1. Các thuật toán tìm kiếm chuỗi con thông dụng .................................................. 19 2.1.1. Thuật toán Brute Force.................................................................................19 2.1.2. Thuật toán Karp-Rabin .................................................................................27 2.1.3. Thuật toán Knuth – Morris – Pratt ...............................................................32 2.1.4. Thuật toán Boyer – Moore ...........................................................................29 2.2. So sánh các thuật toán tìm kiếm chuỗi ............................................................... 42 2.3. Tóm tắt chƣơng ................................................................................................. 43 CHƢƠNG 3. KẾT QUẢ THỰC NGHIỆM VÀ ỨNG DỤNG .....................................36 3.1. Thực nghiệm ....................................................................................................... 36 3.1.1. Môi trƣờng thực nghiệm ..............................................................................36 3.1.2. Đánh giá kết quả thực nghiệm .....................................................................39 3.2. Chƣơng trình ứng dụng :..................................................................................... 40 3.2.1. Tập CSDL sử dụng: ....................................................................................48 3
3.3. Tóm tắt chƣơng ................................................................................................... 50 KẾT LUẬN ...................................................................................................................52 Đánh giá kết quả đề tài : ............................................................................................ 51 Hạn chế : .................................................................................................................... 51 Hƣớng phát triển trong tƣơng lai: .............................................................................. 51 TÀI LIỆU THAM KHẢO .............................................................................................52 4
Danh mục các ký hiệu và chữ viết tắt Từ viết tắt Từ đầy đủ AC Aho-Corasick BDH Backward-Dawg-Matching BOM Backward-OracleMatching DFA Deterministic Finite Automaton FJS Franek-Jennings-Smyth MDH Multi – phase Dynamic Hash QS Quick Search KMP Knuth – Morris – Pratt BM Boyer-Moore RAM Random Access Memory 5
Danh mục các bảng Bảng 1.1: Phân loại các dạng tìm kiếm chuỗi ............................................................... 18 Bảng 2.1: Bảng kmpNext .............................................................................................. 27 Bảng 2.2 : Bảng bmBc[c] .............................................................................................. 33 Bảng 2.3 : Bảng bmGs[i] ............................................................................................... 33 Bảng 2.4: Bảng so sánh các thuật toán tìm kiếm........................................................... 42 Bảng 3.1: Cấu hình phần cứng Windows ...................................................................... 36 Bảng 3.2 : Cấu hình phần cứng Linux ........................................................................... 36 Bảng 3.3: Cấu hình phần mềm ...................................................................................... 36 Bảng 3.4: Bảng thống kê kết quả số 1 ........................................................................... 37 Bảng 3.5: Bảng thống kê kết quả số 2 ........................................................................... 38 Bảng 3.6: Bảng thống kê kết quả số 3 ........................................................................... 38 Bảng 3.7: Bảng thống kê kết quả số 4 ........................................................................... 39 Bảng 3.8 : Bảng thống kê kết quả số 5 .......................................................................... 39 6
Danh mục hình ảnh Hình 2.1: mis-match trong khi đang so sánh tại vị trí j ................................................. 29 Hình 2.2 : good-suffix shift, trƣờng hợp u lại xuất hiện trong x ................................... 37 Hình 2.3: good-suffix shift, trƣờng hợp chỉ suffix của u xuất hiện trong x .................. 37 Hình 2.4 : bad-character shift ........................................................................................ 37 Hình 3.1 : Giao diện chƣơng trình ................................................................................. 41 Hình 3.2: Giao diện chƣơng trình tìm kiếm theo từ viết tắt .......................................... 41 Hình 3.3 : Giao diện chƣơng trình tìm kiếm theo từ đầy đủ ......................................... 42 7
MỞ ĐẦU 1. Lý do chọn đề tài: Cùng với sự phát triển của công nghệ thông tin, số lƣợng các tài liệu điện tử cũng đƣợc tăng lên đáng kể. 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. Để 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. Bài toán tìm kiếm xâu kí tự (string searching, hay đôi khi gọi là đối sánh xâu - string matching) là một trong những bài toán cơ bản và quan trọng trong các thuật toán xử lý về xâu ký tự hay xử lý văn bản (text processing). Đây là thuật toán xử lý xâu văn bản quan trọng và có nhiều ứng dụng trong thực tế. Có rất nhiều thuật toán tìm kiếm xâu kí tự ví dụ nhƣ thuật toán Brute Force, thuật toán Knuth - Morris- Pratt, thuật toán DFA (Deterministic Finite Automaton - máy automat hữu hạn), thuật toán Karp - Rabin,... Luận văn này nghiên cứu thuật toán tìm kiếm chuỗi con và ứng dụng chúng vào hệ thống tìm kiếm văn bản. 2. Hƣớng nghiên cứu : - Nghiên cứu và cài đặt thử nghiệm 4 thuật toán : thuật toán Brute Force, thuật toán Knuth - Morris- Pratt, thuật toán Karp – Rabin, thuật toán Boyer – Moore - Đánh giá hiệu năng của 4 thuật toán. - Xây dựng chƣơng trình ứng dụng : từ điển viết tắt smartDictionary. 3. Nội dung chính : 8
Luận văn đƣợc chia làm 3 chƣơng với nội dung nhƣ sau: 8
Chƣơng 1 : Tổng quan về tìm kiếm chuỗi con: Nghiên cứu tổng quan về tìm kiếm chuỗi con và ứng dụng của tìm kiếm chuỗi con trong thực tế. Chƣơng 2 : Các thuật toán tìm kiếm chuỗi con : Nghiên cứu các thuật toán tìm kiếm chuỗi con kèm theo đánh giá, so sánh giữa các thuật toán tìm kiếm chuỗi con Chƣơng 3 : Kết quả thực nghiệm và ứng dụng tìm kiếm chuỗi con trong xâu gói tin và cài đặt thử nghiệm: Sử dụng các thuật toán tìm kiếm chuỗi con. Từ đó cài đặt thử nghiệm và đánh giá kết quả thuật toán. 9
CHƢƠNG 1. TỔNG QUAN VỀ TÌM KIẾM CHUỖI CON Bài toán tìm kiếm xâu ký tự (string searching, hay đôi khi gọi là đối sánh xâu - string matching) là một trong những bài toán cơ bản và quan trọng trong các thuật toán xử lý về xâu ký tự hay xử lý văn bản (text processing). 1.1. Lịch sử về tìm kiếm chuỗi con 1.1.1. Thuật toán trƣớc những năm 2000 Thuật toán dựa trên so sánh : Hầu hết các thuật toán dựa trên so sánh thể hiện trong thời gian này bằng cách cải thiện hoặc kết hợp các ý tƣởng của thuật toán công bố trƣớc đây. Một trong những thuật toán đầu tiên để giải quyết vấn đề chuỗi kết hợp trong thời gian tuyến tính là do Knuth, Morris và Pratt [3]. Ý tƣởng chính của phƣơng pháp này nhƣ sau : trong quá trình tìm kiếm vị trí của mẫu P trong xâu gốc T, nếu tìm thấy một vị trí sai ta chuyển sang vị trí tìm kiếm tiếp theo và quá trình tìm kiếm sau này sẽ đƣợc tận dụng thông tin từ quá trình tìm kiếm trƣớc để không phải xét các trƣờng hợp không cần thiết. Việc tìm kiếm đƣợc thực hiện bằng cách duyệt văn bản từ trái sang bên phải và với mỗi vị trí văn bản j, nhớ lại những tiền tố dài nhất của mô hình đó cũng là một hậu tố của . Thuật toán Boyer-Moor có sự thay đổi bằng cách duyệt mô hình p từ phải sang trái và khi phát hiện sự khác nhau đầu tiên thuật toán sẽ tiến hành dịch cửa sổ : Cách thứ 1: Dịch sao cho những phần đã so sánh trong lần trƣớc khớp với những phần giống nó trong lần sau. Cách thứ 2: Coi ký tự đầu tiên không khớp trên văn bản là b=T[j+i-1] ta sẽ dịch sao cho có một ký tự giống b trên xâu mẫu khớp vào vị trí đó (nếu có nhiều vị trí xuất hiện b trên xâu mẫu chọn vị trí phải nhất) Thuật toán dựa trên Ô – tô – mát tất định: Trong thuật toán này, quá trình tìm kiếm đƣợc đƣa về một quá trình biến đổi trạng thái automat. Hệ thống automat trong thuật toán DFA sẽ đƣợc xây dựng dựa trên xâu mẫu. Mỗi trạng thái (nút) của automat sẽ đại diện cho số ký tự đang khớp của mẫu với văn bản. Các ký tự của văn bản sẽ làm thay đổi các trạng thái. Và khi đạt đƣợc trạng cuối cùng có nghĩa là đã tìm đƣợc một vị trí xuất hiện ở mẫu. Thuật toán này có phần giống thuật toán Knuth-Morris-Pratt trong việc nhảy về trạng thái trƣớc khi gặp một ký tự không khớp, nhƣng thuật toán DFA có sự 10
đánh giá chính xác hơn vì việc xác định vị trí nhảy dựa trên ký tự không khớp của văn bản (trong khi thuật toán KMP lùi về chỉ dựa trên vị trí không khớp). Việc xây dựng hệ automat khá đơn giản khi đƣợc cài đặt trên ma trận kề. Khi đó thuật toán có thời gian xử lý là O(n) và thời gian để tạo ra hệ automat là O(m*n) (tùy cách cài đặt). Nhƣng ta nhận thấy rằng trong DFA chỉ có nhiều nhất M cung thuận và M cung nghịch, vì vậy việc lƣu trữ các cung không cần thiết phải lƣu trên ma trận kề mà có thể dùng cấu trúc danh sách kề Forward Star để lƣu trữ. Nhƣ vậy thời gian chuẩn bị và lƣợng bộ nhớ chỉ là O(m). Tuy nhiên thời gian tìm kiếm có thể tăng lên một chút so với cách lƣu ma trận kề. Thuật toán song song theo bit: Bit-song song là một kỹ thuật đƣợc giới thiệu trong Domolki 1968 [2], và sau đó xem xét lại trong Baeza-Yates và Gonnet năm 1992; Wu và Manber 1992. Bit-song song là một kỹ thuật sử dụng tính chất hoạt động song song bên trong máy tính, cho phép cắt giảm số lƣợng các hoạt động mà một thuật toán thực hiện bởi một yếu tố lên đến W, nơi ω là số bit trong từ máy tính. Bit-song song là đặc biệt thích hợp cho các mô phỏng hiệu quả của máy tự động không đơn định. Các thuật toán đƣợc xem xét trong phần này làm cho việc sử dụng các hoạt động trên bit, tức là hoạt động dựa trên một hoặc nhiều vectơ bit ở cấp độ bit riêng lẻ của họ. Trên các kiến trúc hiện đại, hoạt động trên bit có tốc độ giống nhƣ ngoài nhƣng nhanh hơn đáng kể so với phép nhân và phép chia. 1.1.2. Thuật toán sau năm 2000 Thuật toán dựa trên so sánh: + Các biến thể của thuật toán Boyer – Moore: - Các thuật toán AKC, một biến thể của thuật toán Apostolico-Giancarlo [8] nhớ lại tất cả các hậu tố của mô hình đƣợc tìm thấy trong các văn bản và tính những thay đổi cho phù hợp ở phần cuối của mỗi lần so sánh. - Thuật toán Fast- Search Family dựa trên thực tế rằng ở cuối mỗi lần so sánh đƣợc tính toán với các quy tắc bad-character khi so sánh kí tự đầu tiên là không phù hợp và sự thay đổi đƣợc tính bằng cách sử dụng quy tắc hậu tố tốt - Thuật toán SSABS và TVSBS, quét các kí tự đầu tiên ngoài cùng bên phải của mô hình, sau đó tận cùng bên trái và cuối cùng các kí tự còn lại của mô hình; - Các thuật toán Boyer-Moore Horspool [9] sử dụng xác suất, có thể quét các ký 11
tự của mô hình theo tần số . - Các thuật toán FJS [10], thuật toán kết hợp giữa thuật toán KMP và QS; - Các thuật toán 2Block, theo dõi tất cả các ký tự tƣơng ứng trƣớc đó trong cửa sổ hiện tại và không để di chuyển vị trí đọc vô điều kiện đến cuối của mô hình khi không phù hợp xảy ra. +Two Windows: Trong phần này chúng tôi trình bày một thuật toán chuỗi kết hợp gần đây, tên là Two-Sliding-Windows, dựa trên so sánh kí tự và trong đó sử dụng hai cửa sổ văn bản trong khi tìm kiếm cho tất cả các lần xuất hiện của các mẫu. Nó quét song song các phần bên trái và phần bên phải của văn bản và sử dụng một quy luật thay đổi của thuật toán Berry-Ravindran [1]. + Hàm băm và g-gram: Thuật toán dựa trên Ô – tô – mát tất định: + Biến thể của thuật toán BOM: Thuật toán song song theo bit: 1.2. Tìm kiếm chuỗi con Mặc dù dữ liệu đƣợc ghi nhớ trong nhiều cách khác nhau nhƣng văn bản vẫn là hình thức chính để lƣu trữ thông tin. Điều này đặc biệt rõ ràng trong ngôn ngữ văn học, nơi dữ liệu đƣợc cấu tạo từ các văn thể rất lớn và từ điển. Điều này đƣợc áp dụng phân tử sinh học nơi mà một số lƣợng lớn các dữ liệu đƣợc lƣu trữ trong các tập tin tuyến tính. Ví dụ các phân tử sinh học biểu diễn các trình tự nucleotide hoặc các axit amin. 1.2.1. Khái niệm về tìm kiếm chuỗi con Tìm kiếm chuỗi là việc so sánh một hoặc một vài chuỗi (thƣờng đƣợc gọi là mẫu hay pattern) với văn bản để tìm nơi và số lần xuất hiện của chuỗi đó trong văn bản. Tìm một (hoặc nhiều) vị trí xuất hiện cuả một xâu ký tự (mẫu tìm kiếm - pattern) ở trong một xâu ký tự lớn hơn hay trong một đoạn văn bản nào đó , m
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 tìm kiếm 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 { } hay có thể là tập các ký tự DNA trong sinh học { } . - Đầu vào : Xâu mẫu Xâu tìm kiếm - Đầu ra : Tất cả vị trí xuất hiện của P trong T 1.2.2. Các cách tiếp cận: - Có 4 cách tiếp cận chính để làm tăng tốc độ thuật toán :  Classical Algorthms : Thuật toán cổ điển chủ yếu dựa vào phép so sánh giữa các ký tự - Ví dụ : Thuật toán Quick Search, Brute Force,…  Suffix Automata Algorthms : Thuật toán máy tự động hậu tố 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 Pattern - Ví dụ : Thuật toán Knuth – Morris – Pratt  Bit-Parallelism Algorithms : Thuật toán Bit song song 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. - Ví dụ : Thuật toán Shift – Or  Hashing Algorithms : Thuật toán băm sử dụng kỹ thuật hàm băm, tránh việc so sánh các ký tự có độ phức tạp bậc 2 Ví dụ : Thuật toán Karp – Rabin - Các thuật toán đối sánh chuỗi thƣờng có 2 bƣớc xử lý sau: - Bƣớc tiền xử lý (Preprocessing Phase) : + Xử lý Pattern + Khởi tạo cấu trúc dữ liệu. - Bƣớc tìm kiếm (Searching Phase) : Tìm kiếm Pattern trong Text 1.2.3. Các dạng tìm kiếm chuỗi Phân loại các thuật toán tìm kiếm chuỗi dựa trên các đặc tính của mẫu ta có các dạng : tìm kiếm đơn mẫu, tìm kiếm đa mẫu, tìm kiếm mẫu mở rộng 12
13
Cơ sở Tiếp cận đơn mẫu Tiếp cận đa mẫu Tiền tố KMP AC ACMS, CIAC,. (Prefix) (Knuth-Morris-Pratt) (Aho-Corasick) Hậu tố BM (Boyer-Moore) CW (Suffix) (Commentz & Walter) BMH SBMH (Boyer-Moore Horspool) WM Factor BDH SBDM (Backward-Dawg-Matching) BOM SBOM (Backward-Oracle Matching) Bảng 1.1: Phân loại các dạng tìm kiếm chuỗi 1.2.3.1. Thuật toán tìm kiếm dựa trên tiền tố Knuth, Morris và Pratt đƣa ra thuật toán KMP tìm kiếm dựa trên tiền tố bằng cách không so sánh mẫu với lần lƣợt từng vị trí trong văn bản nhƣ trong thuật toán Brute-Force mà có thể dịch chuyển mẫu sang phải văn bản một số vị trí do sử dụng những thông tin của những lần dịch chuyển trƣớc cho lần dịch chuyển sau. Thuật toán KMP đã cải tiến thời gian thực hiện vì đã giảm đƣợc số phép so sánh dựa trên các mẫu đƣợc tiền xử lý để tìm ra các mẫu con từ đó xây dựng mảng Next để xác định ký tự tiếp theo trong mẫu đƣợc kiểm tra trên mô hình Thuật toán tính mảng Next: int* InitNext(char *p,int m) { int i,j,*kmpNext; i = -1; j = 0; *kmpNext = -1; while (j < m ) { while (i > -1)&&( p[i] != p[j]) i = *(kmpNext + i); i++; j++; if (p[i]== p[j]) *( kmpNext + j) = *( kmpNext + i); 14
else *( kmpNext + j) = i;} return kmpNext; } Thuật toán KMP chỉ áp dụng trên các tập mẫu đơn, để mở rộng trên các tập mẫu khác ta sử dụng cải tiến của thuật toán KMP, là thuật toán AC (Aho- Corasick). Thuật toán AC cho tập đa mẫu sử dụng mô hình otomat hữu hạn (S,Q,I,T,F). Trong đó : Q là tập hữu hạn các trạng thái, I là trạng thái bắt đầu, T là tập các trạng thái kết thúc, F là hàm dịch chuyển. Trong otomat có thể là đơn định DFA hoặc không đơn định NFA. Việc tìm kiếm trên DFA nhanh hơn quá trình tìm kiếm NFA. Thuật toán DFA gồm 2 bƣớc: bƣớc tiền xử lý, mô hình DFA đƣợc xây dựng trên thuật toán AC, việc tìm tìm trong DFA sẽ tìm các cột có giá trị bằng 0 trong ma trận. Chuyển ma trận thành Aho-Corasick DFA bằng cách dịch các nút trạng thái thành các nút ký tự, với mỗi nút ký tự có n mục trạng thái tiếp theo ứng với tất cả các trạng thái. Tiếp theo các cột đƣợc tìm kiếm có giá trị bằng 0 trên các dòng sẽ đƣợc trộn lại thành một dòng. 1.2.3.2. Thuật toán tìm kiếm dựa trên hậu tố Thuật toán Boyer – Moore đƣợc đƣa ra năm 1977 [5] để kiểm tra các ký tự của mẫu từ phải sang trái. Khi xuất hiện sự khác nhau ta sẽ tiến hành dịch mẫu sang phải văn bản một số vị trí. Thuật toán có 2 cách dịch chuyển mẫu là Good suffix và Bad - Character. Good -suffix: gần giống trong thuật toán KMP, ta dịch mẫu sang phải văn bản sao cho tại vị trí mới có đoạn u trên mẫu P khớp với đoạn u trên văn bản T và ký tự c trên mẫu P ngay trƣớc u phải khác a. Ta chọn đoạn dịch ngắn nhất. Nếu không có cả đoạn u trong P, ta chọn sao cho phần đuôi dài nhất của u xuất hiện ở đầu mẫu P. Bad-character: xuất hiện sự khác nhau giữa mẫu P và văn bản T: , ta sẽ dịch sao cho có một ký tự giống b trên mẫu khớp vào vị trí đó, nếu có nhiều vị trí xuất hiện b trên mẫu ta chọn vị trí bên phải nhất. Nếu không có ký tự b nào trong mẫu ta sẽ dịch sao cho ký tự trái nhất của mẫu vào vị trí ngay sau ký tự để đảm bảo sự ăn khớp. Hai hƣớng tiếp cận sẽ tạo ra 2 giá trị dịch chuyển khác nhau, từ đó sẽ lựa chọn giá trị lớn hơn làm giá trị dịch chuyển. Các thuật toán cải tiến của BM : BMH (BM-Horspool) đƣa ra năm 1980 dùng cho tập đơn mẫu. CW (Commentz & Walter) đƣa ra năm 1979 [6] , SBMH năm 2002 và YBHK năm 2003, WM (Wu & Manner) năm 1994 dùng cho tập đa mẫu 1.2.3.3. Thuật toán tìm kiếm dựa trên thừa số 15
Thuật toán BDH (Backward Dawg Matching) đƣợc xây dựng để tìm kiếm vị trí xuất hiện các ký tự trong mẫu dựa trên thừa số thực bằng cách xây dựng bảng mặt nạ mẫu, các vị trí xuất hiện bit 1 trong bảng tƣơng ứng với vị trí ký tự đó xuất hiện trong mẫu. Việc tìm thừa số đƣợc thực hiện bằng cách thực hiện phép toán AND. Nếu kết quả phép AND trả lại một chuỗi toàn các bit 0 thì mẫu đó không xuất hiện trong chuỗi. Thuật toán BDH nhanh chóng tìm ra việc có hay không xuất hiện các mẫu con của mẫu ban đầu trong văn bản T, từ đó dễ dàng loại bỏ mẫu và dịch chuyển nhanh trong văn bản. Cải tiến của BDM trên tập đơn mẫu là BOM (Backward Oracle Matching) [7], thuật toán BOM có thể thực thi tìm kiếm rất nhanh trên một tập mẫu lớn với số lƣợng các ký tự nhỏ. Trong giai đoạn tiền xử lý độ phức tạp về thời gian và không gian là O(m), độ phức tạp về thời gian tìm kiếm là O(m*n) nhƣng lại cho kết qủa tối ƣu trong trƣờng hợp trung bình. Các cải tiến của BDH và BOM dùng cho tập đa mẫu theo hƣớng tiếp cận thừa số là SBDM và SBOM 1.2.3.4. Thuật toán tìm kiếm dựa trên hàm băm Thuật toán này đƣợc mở rộng từ thuật toán WM. Các mục trong bảng HASH và PREFIX có mối quan hệ một-một, thuật toán MDH [18] sử dụng hai bảng nén HASH, bảng các mẫu so khớp khả dĩ PMT (Possible matching patterns) kết hợp với bảng SHIFT. Bảng HASH đầu tiên giống bảng HASH ở trên và bảng HASH thứ hai, MDH băm lại giá trị trong bảng SHIFT và lƣu chúng trong bảng PTM. Trong giai đoạn tìm kiếm, kích thƣớc B của cửa sổ sẽ đƣợc trƣợt từ trái sang phải. Với mỗi cửa sổ ký tự có kích thƣớc B, tính toán hàm băm và kiểm tra các mục liên quan trong bảng SHIFT. Nếu giá trị của SHIFT là 0 thì di chuyển cửa sổ sang phải. Ngƣợc lại, băm các ký tự trong cửa sổ lần nữa sử dụng hàm băm thứ hai, bây giờ sử dụng giá trị băm mới để định danh sách mục trong bảng PMT. Bƣớc cuối cùng, cần xác minh tất cả các mẫu thích hợp khả dĩ đƣợc liên kết trong các mục và di chuyển cửa sổ văn bản sang phải để khởi động lại thủ tục một lần nữa. 1.2.4. Ứng dụng của tìm kiếm chuỗi Tìm kiếm chuỗi (string matching) là một lĩnh vực quan trọng trong lĩnh vực xử lý văn bản. Các thuật toán tìm kiếm chuỗi đƣợc xem là thành phần cơ sở để cài đặt các 16