ĐẠ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ả
1
Đào Thị Dung
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
2
Đào Thị Dung
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
3.2.1. Tập CSDL sử dụng: .................................................................................... 48
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
4
TÀI LIỆU THAM KHẢO ............................................................................................. 52
Danh mục các ký hiệu và chữ viết tắt
Từ viết tắt Từ đầy đủ
Aho-Corasick AC
Backward-Dawg-Matching BDH
Backward-OracleMatching BOM
Deterministic Finite Automaton DFA
Franek-Jennings-Smyth FJS
Multi – phase Dynamic Hash MDH
Quick Search QS
Knuth – Morris – Pratt KMP
Boyer-Moore BM
5
Random Access Memory RAM
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
6
Bảng 3.8 : Bảng thống kê kết quả số 5 .......................................................................... 39
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
7
Hình 3.3 : Giao diện chƣơng trình tìm kiếm theo từ đầy đủ ......................................... 42
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.
8
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:
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
9
thử nghiệm và đánh giá kết quả thuật toán.
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
10
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ự
đá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;
11
- Các thuật toán Boyer-Moore Horspool [9] sử dụng xác suất, có thể quét các ký
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<=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.
12
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 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
12
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
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])
14
*( kmpNext + j) = *( kmpNext + i);
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
15
1.2.3.3. Thuật toán tìm kiếm dựa trên thừa số
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ử
16
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
hệ thống thực tế. Các thuật toán tìm kiếm chuỗi đƣợc áp dụng cho nhiều ứng dụng và
trong nhiều lĩnh vực khác nhau của khoa học máy tính nhƣ :
- Máy tìm kiếm : Máy tìm kiếm là công cụ đƣợc xây dựng trên nền tảng web
cho phép ngƣời dùng tìm kiếm nội dung của các trang web trên Internet. Bạn có thể
tìm thầy bất kỳ thông tin nào bằng cách gõ các cụm từ hoặc từ tìm kiếm. Máy tìm
kiếm sẽ dò quyét nội dung tất cả các trang web trên Internet và cập nhật nội dung văn
bản text vào cơ sở dữ liệu khổng lồ của mình mà ngƣời dùng có thể khai thác sau đó.
Máy tìm kiếm sẽ trả về một danh sách kết quả các trang web liên quan đến cụm từ mà
bạn gõ. Đề làm việc này các máy tìm kiếm thƣờng gửi các web crawler, web spider
hay web robot ví dụ : googlebot của Google, Yahoo slurp của Yahoo đến các trang
đánh chỉ số. Các bọ tìm kiếm này sẽ truy cập phân tích và gửi nội dung về các máy tìm
kiếm. Máy tìm kiếm sắp xếp các trang Web dựa vào nội dung HTML của trang . Có
thể kể đến một số công cụ tìm kiếm phổ biến sau:
Google Search
Yahoo Search
Live Search của Microsoft
Ask Sear
Máy tìm kiếm đƣợc tạo thành bởi 3 yếu tố chính : Spider, Index, Query.
Spider:
Tìm kiếm, ghé thăm những website mới để lập chỉ mục, đƣa website vào danh
mục của nó. Các spider rất quan tâm đến các đƣờng liên kết, do thông qua các đƣờng
liên kết này, nó có thể tiếp tục đến các trang web khác.
Index:
Thu nhận tất cả thông tin mà các spider mang về và dùng thuật toán để lập chỉ
mục tất cả dữ liệu này theo từng từ, cụm từ. Việc lập chỉ mục này sẽ giúp các bộ máy
tìm kiếm nhanh chóng tìm ra và tiếp cận nguồn dữ liệu khổng lồ mà nó lƣu giữ. Ngoài
việc lập chỉ mục, các phần mềm index còn sử dụng nhiều thuật toán khác nhau để phân
tích, đánh giá các trang web và ấn định thứ hạng cho chúng. Nhờ vào đó bộ máy tìm
kiếm đánh giá tầm quan trọng của mỗi trang web đối với ngƣời dùng đang tìm kiếm.
Query:
Là giao diện mà ngƣời dùng nhìn khi sử dụng bộ máy tìm kiếm. Nó bao gồm ô
17
để gõ từ khóa và ra lệnh tìm kiếm. Máy tìm kiếm sẽ đƣa ra những trang web phù hợp,
liên quan đến từ khóa của bạn. Tuy vậy, thực chất thì phần mềm query không trực tiếp
tìm kiếm các trang web, nó chỉ lấy ra các dữ liệu đã đƣợc phần mềm index lƣu trữ,
đánh giá và sắp xếp.
Tóm lại máy tìm kiếm là tập hợp, phân tích và sắp xếp các trang web. Bạn chỉ
việc gõ từ hoặc cụm từ cần tìm và ra lệnh tìm kiếm, các Search Engine sẽ đƣa ra danh
sách kết quả phù hợp với yêu cầu của bạn.
- Trình soạn thảo văn bản: Chức năng search trong các trình soạn thảo văn bản
và Web browser
- Sinh học phân tử: tìm kiếm sự tƣơng đồng các chuỗi trình tự, đo lƣờng sự
giống nhau giữa các chuỗi trình tự. Các trình tự là các chuỗi DNA, RNA hoặc các
trình tự amino acid (protein). Là cách thức so sánh giữa 2 hay nhiều trình tự dựa trên
việc so sánh một chuỗi các ký tự của trình tự để tìm ra điểm tƣơng đồng, giống nhau
giữa các trình tự. Dựa trên phƣơng pháp, ngƣời ta chia thành 2 loại tìm kiếm
Phép tìm kiếm theo hƣớng toàn cục : đƣợc áp dụng trên toàn bộ chuỗi trình tự.
Thƣờng đƣợc sử dụng khi các trình tự so sánh có kích thƣớc gần tƣơng đƣơng và
các trình tự này có độ tƣơng đồng cao.
Phép tìm kiếm theo hƣớng cục bộ : đƣợc áp dụng trên một phần của chuỗi trình tự.
Thƣờng đƣợc sử dụng khi các trình tự có độ dài lớn, độ tƣơng đồng không cao
hoặc khi các trình tự có kích thƣớc khác biệt lớn.
- Trong an ninh mạng: tìm kiếm 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.3. Tóm tắt chƣơng
Tìm kiếm chuỗi là một kỹ thuật đóng vai trò quan trong việc xử lý văn bản.
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 phổ biến nhất để lƣu trữ và trao đổi thông tin.
Chƣơng 1 trình bày tổng quan về tìm kiếm chuỗi con và các ứng dụng của tìm
kiếm chuỗi. Ứng dụng của tìm kiếm chuỗi đƣợc sử dụng trong nhiều lĩnh vực nhƣ
trong máy tìm kiếm, trình soạn thảo văn bản, trình duyệt Web, sinh học phân tử và
trong phát hiện đột nhập mạng.
Chƣơng 2 của luận văn chúng ta đi sâu nghiên cứu về các thuật toán tìm kiếm
18
chuỗi thông qua đó so sánh và đánh giá hiệu năng của từng thuật toán.
CHƢƠNG 2. CÁC THUẬT TOÁN TÌM KIẾM CHUỖI CON
2.1. Các thuật toán tìm kiếm chuỗi con thông dụng
2.1.1. Thuật toán Brute Force
2.1.1.1. Ý tƣởng:
Thuật toán này thử kiểm tra tất cả các vị trí trên văn bản từ 1 cho đến
. Sau mỗi lần thử, mẫu đƣợc dịch sang bên phải một ký tự cho đến khi kiểm tra hết
văn bản
2.1.1.2. Phát biểu bài toán
- Các thuật toán brute force không đòi hỏi có giai đoạn tiền xử lý và không gian liên
tục.
Void BF (char *x, int m, char *y, int n) {
int i , j ;
/* Searching */
for ( j=0 ; j <= n-m ; ++j) {
for ( i =0; i < m && x[i] == y[i+ j] ; ++i) ;
if ( i >= m)
OUTPUT (j);
}
}
- Thuật toán:
2.1.1.3. Đánh giá thuật toán:
Trƣờng hợp xấu nhất là tìm đến hết chuỗi T mà không thấy. Khi đó với
vị trí tìm kiếm, ta phải so sánh m ký tự của chuỗi P với các ký tự tƣơng
ứng của chuỗi T. Số lần so sánh: . Thông thƣờng m rất nhỏ
so với n nên ta có thể coi . Nhƣ vậy đ ộ phức tạp thuật toán này là
.
2.1.1.4. Ví dụ:
First attempt G C A T C G C A G A G A G T A T A C A G T A C G
1 2 3 4
19
G C A G A G A G
19
Second attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Third attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Fourth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Fifth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Sixth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1 2 3 4 5 6 7 8
G C A G A G A G
Seventh attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
20
G C A G A G A G
Eighth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Ninth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1 2
G C A G A G A G
Tenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Eleventh attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1 2
G C A G A G A G
Twelfth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Thirteenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1 2
21
G C A G A G A G
Fourteenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Fifteenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Sixteenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Seventeenth attempt
2.1. G C A T C G C A G A G A G T A T A C A G T A C G
2. 1 Thu
G C A G A G A G ật
toá
n Karp-Rabin
2.1.2.1. Ý tƣởng :
Thuật toán Rabin - Karp là thuật tìm chuỗi con do Michael O. Rabin và Richard
M. Karp tạo ra năm 1987. Thuật toán này dùng hàm hash (hàm băm) để tìm chuỗi con.
#define REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))
void KR(char *x, int m, char *y, int n) {
int d, hx, hy, i, j;
/* Preprocessing */
/* computes d = 2^(m-1) with the left-shift operator */
for (d = i = 1; i < m; ++i)
d = (d<<1);
22
2.1.2.2. Thuật toán :
for(hy = hx = i = 0; i < m; ++i)
hx = ((hx<<1) + x[i]);
hy = ((hy<<1) + y[i]);
}
/* Searching */
j = 0;
while (j <= n-m) {
if (hx == hy && memcmp(x, y + j, m) == 0)
OUTPUT(j);
hy = REHASH(y[j], y[j + m], hy);
++j;
}
}
2.1.2.3. Đánh giá thuật toán:
Với văn bản độ dài n và chuỗi con cần tìm độ dài m thì độ phức tạp trung bình
và tốt nhất là , xấu nhất là .
2.1.2.4. Ví dụ :
Hash (GCAGAGAG) = 17597
First attempt
G C A T C G C A G A G A G T A T A C A G T A C G
G C A G A G A G
Second attempt
G C A T C G C A G A G A G T A T A C A G T A C G
G C A G A G A G
Third attempt
G C A T C G C A G A G A G T A T A C A G T A C G
23
G C A G A G A G
23
Fourth attemp
G C A T C G C A G A G A G T A T A C A G T A C G
G C A G A G A G
Fifth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
G C A G A G A G
Sixth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1 2 3 4 5 6 7 8
G C A G A G A G
Seventh attempt
G C A T C G C A G A G A G T A T A C A G T A C G
G C A G A G A G
Eighth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
G C A G A G A G
Ninth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
24
G C A G A G A G
Tenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
G C A G A G A G
Eleventh attempt
G C A T C G C A G A G A G T A T A C A G T A C G
G C A G A G A G
Twelfth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
G C A G A G A G
hash(y[11 .. 18]) = 17723
Thirteenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
G C A G A G A G
hash(y[12 .. 19]) = 18877
Fourteenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
G C A G A G A G
hash(y[13 .. 20]) = 19662
Fifteenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
G C A G A G A G
hash(y[14 .. 21]) = 17885
Sixteenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
G C A G A G A G
25
hash(y[15 .. 22]) = 19197
Seventeenth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
G C A G A G A G
hash(y[16 .. 23]) = 16961
2.1.3. Thuật toán Knuth – Morris – Pratt
2.1.3.1. Ý tƣởng :
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
void preKmp(char *x, int m, int kmpNext[]) {
int i, j;
i = 0;
j = kmpNext[0] = -1;
while (i < m) {
while (j > -1 && x[i] != x[j])
j = kmpNext[j];
i++;
j++;
if (x[i] == x[j])
kmpNext[i] = kmpNext[j];
else
kmpNext[i] = j;
}
}
void KMP(char *x, int m, char *y, int n) {
int i, j, kmpNext[XSIZE];
/* Preprocessing */
preKmp(x, m, kmpNext);
/* Searching */
i = j = 0; while (j < n) {
while (i > -1 && x[i] != y[j])
26
2.1.3.2. Thuật toán :
i = kmpNext[i];
i++;
j++;
if (i >= m) {
OUTPUT(j - i);
i = kmpNext[i];
}
}
2.1.3.3. Đánh giá thuật toán:
Thuật toán thực hiện so sánh từ trái qua phải, độ phức tạp về thời gian trong
giai đoạn tiền xử lý là O(m), độ phức tạp thời gian trong giai đoạn tìm mẫu
là O(m+n).
2.1.3.4. Ví dụ :
Xét chuỗi : y: GCATCGCAGAGAGTATACAGTACG
Chuỗi mẫu x : GCAGAGAG
+ Giai đoạn tiền xử lý: Bảng kmpNext
i 0 1 2 3 4 5 6 7 8
x[i] G C A G A G A G
0 0 -1 1 -1 1 -1 1 kmpNext[i] -1
Bảng 2.1: Bảng kmpNext
+ Các bƣớc của thuật toán :
First attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1 2 3 4
G C A G A G A G
Shift by: 4 (i-kmpNext[i]=3- -1)
Second attempt
G C A T C G C A G A G A G T A T A C A G T A C G
27
1
G C A G A G A G
27
Shift by: 1 (i-kmpNext[i]=0- -1)
Third attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1 2 3 4 5 6 7 8
G C A G A G A G
Shift by: 7 (i-kmpNext[i]=8-1)
Fourth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Shift by: 1 (i-kmpNext[i]=1-0)
Fifth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Shift by: 1 (i-kmpNext[i]=0- -1)
Sixth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Shift by: 1 (i-kmpNext[i]=0- -1)
Seventh attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
28
Shift by: 1 (i-kmpNext[i]=0- -1)
Eighth attempt
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
Shift by: 1 (i-kmpNext[i]=0- -1)
2.1.4. Thuật toán Boyer – Moore
2.1.4.1. Ý tƣởng :
Thuật toán Boyer-Moore [1] đƣợc coi là thuật toán hiệu quả nhất trong vấn đề
tìm kiếm chuỗi (string-matching) trong các ứng dụng thƣờng gặp.
+ Các biến thể của nó thƣờng đƣợc dùng trong các bộ soạn thảo cho các lệnh
nhƣ <
+ Thuật toán sẽ quét các ký tự của mẫu (pattern) từ phải sang trái bắt đầu ở
phần tử cuối cùng. Trong trƣờng hợp mis-match (hoặc là trƣờng hợp đã tìm đƣợc 1
đoạn khớp với mẫu), nó sẽ dùng 2 hàm đƣợc tính toán trƣớc để dịch cửa sổ sang bên
phải. Hai hàm dịch chuyển này đƣợc gọi là good-suffix shift (còn đƣợc biết với cái tên
phép dịch chuyển khớp) và bad-character shift (còn đƣợc biết với cái tên phép dịch
chuyển xuất hiện). Đối với mẫu ta dùng 1 biến chỉ số i chạy từ cuối về
đầu, đối với chuỗi ta dùng 1 biến j để chốt ở phía đầu.
G/s rằng trong quá trình so sánh ta gặp 1 mis-match tai vị trí của mẫu và
trong khi đang thử khớp tại vị trí j.
Hình 2.1: mis-match trong khi đang so sánh tại vị trí j
Khi đó, và . Bây
giờ ta đi xét xem đối với từng trƣờng hợp, 2 hàm trên sẽ thực hiện việc dịch chuyển
Phép dịch chuyển good-suffix shift sẽ dịch cửa sổ sang bên phải cho đến khi gặp
nhƣ thế nào:
29
1 ký tự khác với x[i] trong trƣờng hợp đoạn u lại xuất hiện trong x.
Nếu đoạn u không xuất hiện lại trong x, mà chỉ có 1 phần cuối (suffix) của u
Hình 2.2 : good-suffix shift, trƣờng hợp u lại xuất hiện trong x
khớp với phần đầu (prefix) của x, thì ta sẽ dịch 1 đoạn sao cho phần suffix dài
nhất v của
khớp với prefix của x.
Phép dịch chuyển bad-character shift sẽ khớp kí tự với 1 ký tự (bên
Hình 2.3: good-suffix shift, trƣờng hợp chỉ suffix của u xuất hiện trong x
phải nhất) trong đoạn
Hình 2.4 : bad-character shift
Nếu không xuất hiện trong x, ta thấy ngay rằng không có xuất hiện
nào của x trong y mà lại chứa chấp , do đó ta có thể đặt cửa sổ ngay sau
30
, tức là .
Thuật toán Boyer-Moore sẽ chọn đoạn dịch chuyển dài nhất trong 2 hàm dịch
chuyển good-suffix shift và bad-character shift. Hai hàm này đƣợc định nghĩa nhƣ sau:
30
Hàm
good-suffix shift đƣợc lƣu trong bảng bmGs có kích thƣớc m+1. Ta định nghĩa 2
điều kiện sau:
Cs(i, s): với mỗi k mà i < k < m, s ≥ k hoặc và
1. Co(i, s): nếu s
Khi đó, với 0≤ i và chúng ta định nghĩa bmGs[0] là độ dài chu kỳ của x. Việc tính toán bảng bmGs sử dụng 1 bảng suff định nghĩa nhƣ sau: với , { } Hàm bad-character shift đƣợc lƣu trong bảng bmBc có kích thƣớc σ. Cho c trong { nếu c xuất hiện trong x, m ngƣợc lại. void preBmBc(char *x, int m, int bmBc[]) { int i; for (i = 0; i < ASIZE; ++i) bmBc[i] = m; for (i = 0; i < m - 1; ++i) bmBc[x[i]] = m - i - 1; } void suffixes(char *x, int m, int *suff) { int f, g, i; suff[m - 1] = m; g = m - 1; for (i = m - 2; i >= 0; --i) { if (i > g && suff[i + m - 1 - f] < i - g) suff[i] = suff[i + m - 1 - f]; else { if (i < g) g = i; f = i; while (g >= 0 && x[g] == x[g + m - 1 - f]) --g; suff[i] = f - g; } } } 31 2.1.4.2. Thuật toán : void preBmGs(char *x, int m, int bmGs[]) { int i, j, suff[XSIZE]; suffixes(x, m, suff); for (i = 0; i < m; ++i) bmGs[i] = m; j = 0; for (i = m - 1; i >= 0; --i) if (suff[i] == i + 1) for (; j < m - 1 - i; ++j) if (bmGs[j] == m) bmGs[j] = m - 1 - i; for (i = 0; i <= m - 2; ++i) bmGs[m - 1 - suff[i]] = m - 1 - i; } void BM(char *x, int m, char *y, int n) { int i, j, bmGs[XSIZE], bmBc[ASIZE]; /* Preprocessing */ preBmGs(x, m, bmGs); preBmBc(x, m, bmBc); /* Searching */ j = 0; while (j <= n - m) { for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i); if (i < 0) { OUTPUT(j); j += bmGs[0]; } else j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i); } } Thực hiện việc so sánh từ phải sang trái. Giai đoạn tiền xử lý (preprocessing) có độ phức tạp thời gian và không gian là 2.1.4.3. Đánh giá thuật toán : Giai đoạn tìm kiếm có độ phức tạp . 32 . So sánh tối đa 3n ký tự trong trƣờng hợp xấu nhất đối với mẫu không có chu 4 Độ phức tạp ⁄ trong trƣờng hợp tốt nhất. 2.1.4.4. Ví dụ: - Giai đoạn tiền xử lý : Bảng bmBc[c] và bảng bmGs[i] A C G T c bmBc[c] 1 6 2 8 Bảng 2.2 : Bảng bmBc[c] i 0 1 2 3 4 5 6 7 X[i] G C A G A G A G Suff[i] 1 0 0 2 0 4 0 8 bmGs[i] 7 7 7 2 7 4 7 1 Bảng 2.3 : Bảng bmGs[i] - Các bƣớc của giải thuật : First attempt G C A T C G C A G A G A G T A T A C A G T A C G 1 G C A G A G A G Shift by: 1 (bmGs[7]=bmBc[A]-8+8) Second attempt G C A T C G C A G A G A G T A T A C A G T A C G 3 2 1 G C A G A G A G Shift by: 4 (bmGs[5]=bmBc[C]-8+6 Third attempt G C A T C G C A G A G A G T A T A C A G T A C G 8 7 6 5 4 3 2 1 G C A G A G A G 33 Shift by: 7 (bmGs[0]) Fourth attempt G C A T C G C A G A G A G T A T A C A G T A C G 3 2 1 G C A G A G A G Shift by: 4 (bmGs[5]=bmBc[C]-8+6) Fifth attempt G C A T C G C A G A G A G T A T A C A G T A C G 2 1 G C A G A G A G Shift by: 7 (bmGs[6]) 2.2. So sánh các thuật toán tìm kiếm chuỗi Độ Tên thuật Độ phức tạp STT Thứ tự so sánh phức Đặc điểm chính toán tiền xử lý tạp Brute-Force Không theo thứ Không có giai O(mn) Dịch chuyển từng 1 tự nhất định đoạn tiền xử lý kí tự Karp-Rabin Từ trái qua phải O(m) O(mn) Sử dụng hàm băm 2 Knuth-Morris- Từ trái qua phải O(m) O(m+n) Dựa vào chính Pratts pattern để tính bƣớc dịch tiếp. Tăng khả 3 năng thực thi, giảm độ trễ và thời gian đối sánh. Boyer-Moore Từ phải sang O(m) O(mn) Sử dụng hai hàm trái dịch chuyển là hậu tố tốt – good suffix 4 và ký tự tồi – bad character. 34 Bảng 2.4: Bảng so sánh các thuật toán tìm kiếm 2.3. Tóm tắt chƣơng Trong chƣơng 2, luận văn nghiên cứu về các thuật toán tìm kiếm chuỗi thông dụng thƣờng dùng. Mỗi thuật toán có sự khác nhau về tiền xử lý từ đó có các phƣơng pháp khác nhau về bƣớc dịch chuyển của pattern trong văn bản. Thuật toán Brute – Fore và Rabin – Karp có độ dịch chuyển pattern trong văn bản là giống nhau. Tuy nhiên, thuật toán Rabin – Karp sử dụng hàm băm (hash) để chuyển thuật toán về so sánh mảng số nguyên tránh đƣợc việc so sánh những chuỗi văn bản dài. Thuật toán KMP và Boyer – Moore dựa vào chuỗi mẫu để quyết định bƣớc dịch chuyển tiếp theo của chuỗi mẫu trên văn bản. Tuy nhiên, thuật toán Boyer – Moore phức tạp hơn vì sử dụng 2 hàm good-suffix và bad-character shift đƣợc tính toán trƣớc để dịch chuyển chuỗi mẫu trên văn bản Chƣơng 3 luận văn sẽ cài đặt thử nghiệm các thuật toán để đánh giá, so sánh 35 thời gian chạy của từng thuật toán và cài đặt thử nghiệm ứng dụng. CHƢƠNG 3. KẾT QUẢ THỰC NGHIỆM VÀ ỨNG DỤNG 3.1. Thực nghiệm - Mục đích của thực nghiệm: Đánh giá và so sánh hiệu năng thời gian chạy của 4 thuật toán tìm kiếm chuỗi. - Thời gian thực hiện giải thuật phụ thuộc: Kích thƣớc dữ liệu: dữ liệu càng lớn thì thời gian xử lý càng chậm. Nếu gọi n là kích thƣớc dữ liệu thì thời gian thực hiện của một giải thuật có thể biểu diễn là một hàm của n: T(n) Phần cứng máy tính Ngôn ngữ, chƣơng trình dịch ngôn ngữ Chính vì vậy trong phần thực nghiệm của chƣơng 3 đã sử dụng 2 tập CSDL là từ điển có kích thƣớc mục từ ngắn và từ điển có kích thƣớc mục từ dài để đánh giá độ phức tạp của các thuật toán bằng ngôn ngữ C++ trên nền hệ điều hành Windows và hệ điều hành Linux. Sau đây tôi xin đƣợc trình bày cụ thể hơn về môi trƣờng cũng nhƣ cách thức thực hiện thực nghiệm 3.1.1. Môi trƣờng thực nghiệm 3.1.1.1. Cấu hình phần cứng: STT Tên Thông số 1 Intel(R) Core(TM) i7-3632 QM CPU @ 2.20GHz CPU 2 RAM 8.00 GB 3 Hệ điều hành Win 10 Bảng 3.1: Cấu hình phần cứng Windows STT Tên Thông số 1 CPU Intel Xeon 2 GHz 2 RAM 2.00 GB 3 Hệ điều hành Win 10 Bảng 3.2 : Cấu hình phần cứng Linux 3.1.1.2. Cấu hình phần mềm STT Tên Nguồn 1 Microsof Visual Studio https://www.visualstudio.com/ 36 Bảng 3.3: Cấu hình phần mềm 3.1.2. Chƣơng trình thực nghiệm 3.1.2.1. Đối với HĐH Linux Thống kê kết quả chạy với từ điển dài: - Tổng danh mục từ điển: 479777 - Tổng độ dài từ điển: 42376210 ký tự - Trung bình độ dài các danh mục: 88.32 ký tự - Tổng số query: 10000 - Tổng độ dài query :66445 ký tự - Độ dài trung bình query: 6.64 kí tự - Kết quả thu đƣợc: STT Thuật toán Tổng thời gian chạy Thời gian chạy trung bình 1 query (giây) (mili giây) Brute - Force 343.62 1 34.362 Karp - Rabin 340.89 2 34.089 Knuth – Morris - Prat 1247 .98 3 124.798 Boyer - Moore 1191.23 4 119.123 glibc strstr 344.93 5 34.493 Bảng 3.4: Bảng thống kê kết quả số 1 Thống kê kết quả chạy đƣợc với từ điển ngắn (Số query:10000) - Tổng danh mục từ điển: 479777 - Tổng độ dài từ điển: 4953604 ký tự - Trung bình độ dài các danh mục: 10.32 ký tự - Tổng số query: 10000 - Tổng độ dài query: 66445 ký tự - Độ dài trung bình query: 6.64 kí tự - Kết quả thu đƣợc: STT Thuật toán Tổng thời gian chạy Thời gian chạy trung bình 1 query (giây) (mili giây) Brute - Force 178.56 1 17.856 Karp - Rabin 178.05 2 17.805 Knuth – Morris - Prat 607.23 3 60.723 37 Boyer - Moore 895.11 4 89.511 5 glibc strstr 178.16 17.816 Bảng 3.5: Bảng thống kê kết quả số 2 Thống kê kết quả chạy đƣợc với từ điển ngắn (Số query:50000) - Tổng danh mục từ điển: 479777 - Tổng độ dài từ điển: 4953604 ký tự - Trung bình độ dài các danh mục: 10.32 ký tự - Tổng số query: 50000 - Tổng độ dài query: 334620 ký tự - Độ dài trung bình query: 6.69 kí tự - Kết quả thu đƣợc: STT Thuật toán Tổng thời gian chạy Thời gian chạy trung bình 1 query (giây) (mili giây) 1 Brute - Force 887.85 17.757 2 Karp - Rabin 886.73 17.735 3 Knuth – Morris - Prat 1247.98 24.96 4 Boyer - Moore 4506.3 90.126 5 glibc strstr 870.82 17.42 Bảng 3.6: Bảng thống kê kết quả số 3 3.1.2.2. Đối với HĐH Windows Thống kê kết quả chạy đƣợc với từ điển ngắn (Số query:10000) - Tổng danh mục từ điển: 479777 - Tổng độ dài từ điển: 4953604 ký tự - Trung bình độ dài các danh mục: 10.32 ký tự - Tổng số query: 10000 - Tổng độ dài query: 66445 ký tự - Độ dài trung bình query: 6.64 kí tự - Kết quả thu đƣợc: STT Thuật toán Tổng thời gian chạy Thời gian chạy (giây) trung bình 1 query (mili giây) 1 Brute - Force 142 14.2 38 2 Karp - Rabin 141 14.1 3 Knuth – Morris - Prat 661 66.1 4 Boyer - Moore 618 61.8 5 glibc strstr 174 17.4 Bảng 3.7: Bảng thống kê kết quả số 4 Thống kê kết quả chạy đƣợc với từ điển ngắn (Số query:50000) - Tổng danh mục từ điển: 479777 - Tổng độ dài từ điển: 4953604 ký tự - Trung bình độ dài các danh mục: 10.32 ký tự - Tổng số query: 50000 - Tổng độ dài query: 334620 ký tự - Độ dài trung bình query: 6.69 kí tự - Kết quả thu đƣợc: STT Thuật toán Tổng thời gian chạy Thời gian chạy (giây) trung bình 1 query (mili giây) 1 Brute - Force 732 73.2 2 Karp - Rabin 725 72.5 3 Knuth – Morris - Prat 3336 333.6 4 Boyer - Moore 3131 313.1 5 glibc strstr 875 87.5 Bảng 3.8 : Bảng thống kê kết quả số 5 3.1.3. Đánh giá kết quả thực nghiệm - Theo lý thuyết độ phức tạp của 4 thuật toán lần lƣợt là : Brute Force: O(m*n) Karp-Rabin: Tồi nhất: O(m*n), tốt nhất O(m+n) Knuth – Morris – Pratt: O(m+n) Boyer – Moore: Tồi nhất: O(m*n), tốt nhất O(n/m) Nhƣ vậy, theo lý thuyết thì thuật toán Boyer – Moore là thuật toán tìm kiếm nhanh nhất, thuật toán Brute – Force là thuật toán tìm kiếm tồi nhất nhƣng theo kết quả thực nghiệm thì thuật toán Brute – Force lại cho kết quả thời gian gần nhƣ là nhanh nhất. Sự chênh lệch giữa lý thuyết và thực nghiệm là vì m, n là độ dài xâu mẫu cần tìm và 39 độ dài xâu văn bản. Nếu m, n ở đây lớn thì sẽ có ý nghĩa với các thuật toán tìm kiếm. Nhƣng đầu vào thực nghiệm, độ dài chuỗi văn bản và độ dài xâu mẫu rất nhỏ nên độ chênh lệch nhau nhiều trong khi đó thuật toán Boyer-Moore phải thực hiện 2 hàm preBmGS và preBmBc lại chiếm nhiều thời gian hơn cả quá trình Searching vì vậy mà thuật toán Boyer – Moore cho kết quả thời gian nhiều nhất. - Trong phần thực nghiệm tôi có cài thêm hàm strstr – một hàm tìm kiếm có sẵn của thƣ viện string.h để so sánh kết quả tìm kiếm của các thuật toán. Qua kết quả thực nghiệm ta thấy rằng kết quả tìm kiếm từ hàm có sẵn strstr cho kết quả tƣơng đối nhanh 3.2. Chƣơng trình ứng dụng : Mục đích: Viết một ứng dụng smartdictionary – từ điển viết tắt: Trong đó có mục tìm kiếm theo từ viết tắt và tìm kiếm theo từ đầy đủ. Khi ngƣời dùng nhớ cụm từ viết tắt và muốn tra cụm từ đầy đủ thì gõ các ký tự vào bên trƣờng Abbriviation, mỗi khi 1 ký tự đƣợc gõ vào thì giải thuật tìm kiếm xâu con đƣợc áp dụng để lọc ra các từ chứa chuỗi con đƣợc nhập vào, và tên đầy đủ của các cụm từ tƣơng ứng cũng đƣợc liệt kê ra ở trƣờng Full name. Trong trƣờng hợp ngƣời dùng chỉ nhớ đƣợc một số từ trong tên đầy đủ và tra ngƣợc lại từ viết tắt là gì thì có thể gõ một phần tên trong trƣờng Full name, khi đó giải thuật tìm kiếm chuỗi con đƣợc áp dụng để lọc ra các tên đầy đủ chứa chuỗi con đƣợc nhập vào cùng các từ viết tắt tƣơng ứng ở bên trƣờng Abbriviation. Ý nghĩa: Áp dụng đƣợc thuật toán tìm kiếm vào trong thực tế 3.2.1. Tập CSDL sử dụng: - Sử dụng tập dữ liệu trích lấy trong www.abbreviation.com - Tạo ra 2 tập CSDL : + Tập CSDL viết tắt 39 + Tập CSDL viết đầy đủ 3.2.2. Giao diện chƣơng trình: + Giao diện chính: Hình 3.1 : Giao diện chƣơng trình + Giao diện tìm kiếm theo từ viết tắt 41 Hình 3.2: Giao diện chƣơng trình tìm kiếm theo từ viết tắt + Giao diện tìm kiếm theo từ đầy đủ: Hình 3.3 : Giao diện chƣơng trình tìm kiếm theo từ đầy đủ 3.3. Tóm tắt chƣơng Trong chƣơng 3 đã trình bày về thực nghiệm so sánh thời gian chạy của một số thuật toán tìm kiếm chuỗi (string matching) trên các hệ điều hành, và các tập dữ liệu cũng nhƣ số lƣợng query khác nhau. Để đánh giá độ phức tạp về thời gian tôi đã triển khai cài đặt các thuật toán Brute-Force, , thuật toán Karp-Rabin, thuật toán Knuth- Morris-Pratt, thuật toán Boyer-Moore trên ngôn ngữ C++. Điều kiện thực nghiệm kiểm chứng trên máy tính với hệ điều hành Win 10, RAM 8G, CPU Intel(R) Core(TM) i7-3632 QM CPU @ 2.20GHz Đồng thời cài đặt chƣơng trình demo ví dụ về một ứng dụng smartdictionary – 42 từ điển viết tắt áp dụng thuật toán tìm kiếm chuỗi để giải quyết bài toán Đánh giá kết quả đề tài : Nội dung luận văn đạt đƣợc một số kết quả nghiên cứu đạt đƣợc sau đây: Các kiến thức cơ bản về bài toán tìm kiếm chuỗi con, các hƣớng tiếp cận Trình bày một số thuật toán tìm kiếm chuỗi Cài đặt thực nghiệm thuật toán từ đó so sánh đánh giá hiệu năng của các thuật toán tìm kiếm chuỗi con trên các môi trƣờng và các tập dữ liệu khác nhau. Cài đặt ứng dụng thuật toán tìm kiếm chuỗi con vào thực tế. Hạn chế : Chƣơng trình thử nghiệm còn đơn giản. Hƣớng phát triển trong tƣơng lai: Với những kết quả đã đạt đƣợc, tôi xin đề xuất một số công việc tiếp theo trong thời gian tới nhƣ sau: Tiếp tục xử lý những vấn đề còn tồn tại trong chƣơng trình thử nghiệm đã cài đặt nhƣ: + Xây dựng giao diện chƣơng trình thân thiện và dễ sử dụng hơn. + Tiếp tục nghiên cứu và phát triển các ứng dụng khác sử dụng các thuật toán 43 tìm kiếm từ điển nhƣ tìm kiếm trong danh bạ điện thoại. TÀI LIỆU THAM KHẢO [1] Christian Charras, Therry Lecroq, T, Handbook of Exact String Matching Algorithms, King's College Publications, 2004. [2] Simone Faro, Thierry Lecroq. The exact online string matching problem A review of the most recent results. [3] Knuth et al. 1977, Algorithms and Theory of Computation Handbook [4] Maxime Crochemore, Thierry Lecroq, Pattern matching and text compression algorithms, King's College Publications, 2004. [5] R. Boyer and J. Moore. A Fast String Searching Algorithm, Commun. ACM, 1977,pages 762-772. [6] Beate Commentz – Walter , A String Matching Algorithm Fast on the Average Extended Abstract, 1979 [7] S. Faro and T. Lecroq . Efficient Variants of the Backward-Oracle- Matching Algorithm . Proceedings of the Prague Stringology Conference 2008, pp.146—160 [8] Gusfield, D., 1997, Algorithms on strings, trees, and sequences: Computer Science and Computational Biology, Cambridge University Press. [9] R. N. Horspool (1980). "Practical fast searching in strings". Software - Practice & Experience [10] Jan Holub1, William F.Smyth, and Shu Wang, Hybrid Pattern – Matching Algorithms on Indeterminate Strings [11] STEPHEN, G.A., 1994, String Searching Algorithms, World Scientific. [12] SEDGEWICK, R., 1988, Algorithms in C, Chapter 19, Addison-Wesley [13] LECROQ, T., 1995, Experimental results on string matching algorithms, Software - Practice & Experience [14] CROCHEMORE, M., LECROQ, T., 1996, Pattern matching and text compression algorithms, in CRC Computer Science and Engineering Handbook, A. Tucker ed., Chapter 8, pp 162-202, CRC Press Inc., Boca Raton, FL. [15] CROCHEMORE, M., HANCART, C., 1999, Pattern Matching in Strings, in Algorithms and Theory of Computation Handbook, M.J. Atallah ed., Chapter 11, pp 44 11-1--11-28 [16] GONNET, G.H., BAEZA-YATES, R.A., 1991. Handbook of Algorithms and Data Structures in Pascal and C, 2nd Edition, Chapter 7, pp. 251-288, Addison-Wesley Publishing Company. [17] GOODRICH, M.T., TAMASSIA, R., 1998, Data Structures and Algorithms in JAVA, Chapter 11, pp 441-467, John Wiley & Sons. [18] Zongwei Zhou, Yibo Xue, Junda Liu, Wei Zhang, Jun Li, A high speed multi – 45 phase Dynamic Hash String Matching Algorithm for Large – Scale Pattern Set.KẾT LUẬN
Publishing Company.
