ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN&TRUYỀN THÔNG Nguyễn Thị Phương Thảo
MỘT HỌ THUẬT TOÁN ĐỐI SÁNH MẪU CHÍNH XÁC NHANH
SSABS - TVSBS - FQS VÀ THỰC NGHIỆM
Chuyên ngành: Khoa học máy tính
Mã số: 60. 48. 01. 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 Hà Quang Thụy
Thái Nguyên - 2015
i
LỜI CAM ĐOAN
Tôi xin cam đoan:
Những nội dung trong luận văn này là do tôi thực hiện dưới sự hướng dẫn
trực tiếp của thầy giáo hướng dẫn PGS TS. Hà Quang Thụy.
Mọi tham khảo trong luận văn đều được trích dẫn rõ ràng tác giả, tên công
trình, thời gian, địa điểm công bố.
Tôi xin cam đoan luận văn không phải là sản phẩm sao chép của bất kỳ tài
liệu khoa học nào.
Học viên
Nguyễn Thị Phương Thảo
ii
LỜI CẢM ƠN
Đầu tiên tôi xin gửi lời cảm ơn sâu sắc nhất tới PGS. TS Hà Quang Thụy
người hướng dẫn khoa học, đã tận tình chỉ bảo, giúp đỡ tôi thực hiện luận văn. Tôi
cũng xin lời lời cám ơn trân thành tới PGS. TS. Nguyễn Trí Thành và các anh chị
em Phòng Thí nghiệm Khoa học dữ liệu và Công nghệ Tri thức, Trường Đại học
Công nghệ, Đại học Quốc gia Hà Nội đã giúp đỡ và tạo điều kiện hỗ trợ tôi.
Tôi xin cảm ơn các thầy cô trường Đại học Công nghệ thông tin và Truyền
thông - Đại học Thái Nguyên đã giảng dạy và truyền đạt kiến thức cho tôi.
Tôi xin trân thành cảm ơn Ban giám hiệu trường Cao đẳng nghề Phú Thọ và
các đồng nghiệp trong khoa Công nghệ thông tin đã tạo mọi điều kiện giúp đỡ tôi
hoàn thành nhiệm vụ học tập.
Cuối cùng, tôi xin cảm ơn những người thân và các bạn bè chia sẻ, giúp đỡ
tôi hoàn thành luận văn này.
Mặc dù đã hết sức cố gắng hoàn thành luận văn với tất cả sự nỗ lực của bản
thân, nhưng luận văn vẫn còn những thiếu sót. Kính mong nhận được những ý kiến
đóng góp của quý Thầy, Cô và bạn bè đồng nghiệp.
Tôi xin chân thành cảm ơn!
Việt Trì, ngày 10 tháng 09 năm 2015
Nguyễn Thị Phương Thảo
iii
MỤC LỤC
LỜI CAM ĐOAN ............................................................................................................. i LỜI CẢM ƠN ................................................................................................................. ii MỤC LỤC ..................................................................................................................... iii DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT .................................................... v DANH MỤC CÁC BẢNG ............................................................................................. vi DANH MỤC CÁC HÌNH VẼ ....................................................................................... vii MỞ ĐẦU ........................................................................................................................ 1 CHƯƠNG 1. GIỚI THIỆU CHUNG VỀ THUẬT TOÁN SÁNH MẪU.......................... 3 1.1. Bài toán sánh mẫu và phân loại ............................................................................ 3
1.1.1. Bài toán sánh mẫu .......................................................................................... 3
1.1.2. Phân loại bài toán sánh mẫu ........................................................................... 3 1.2. Một số ứng dụng của bài toán sánh mẫu ............................................................... 5 1.3. Một số thuật toán sánh mẫu truyền thống ............................................................. 5
1.3.1. Thuật toán Boyer–Moore ............................................................................... 6
1.3.2. Thuật toán Quick Search ................................................................................ 9 1.4. Khái quát về các thuật toán sánh mẫu chính xác ................................................. 10 1.5. Kết luận chương 1 .............................................................................................. 11
CHƯƠNG 2: HỌ THUẬT TOÁN SÁNH MẪU CHÍNH XÁC NHANH SSABS - TVSBS – FQS ............................................................................................................... 13 2.1. Giới thiệu về các biến thể của thuật toán Quick Search ....................................... 13 2.2. Thuật toán đối sánh mẫu nhanh SSABS ............................................................. 13
2.2.1. Giới thiệu ..................................................................................................... 13
2.2.2. Thuật toán .................................................................................................... 14 2.3. Thuật toán TVSBS ............................................................................................. 19
2.3.1. Giới thiệu ..................................................................................................... 19
2.3.2. Thuật toán .................................................................................................... 19
2.3.3. Ví dụ ............................................................................................................ 21 2.4. Thuật toán Faster Quick Search .......................................................................... 24
2.4.1. Giới thiệu ..................................................................................................... 24
2.4.2. Thuật toán .................................................................................................... 24
2.4.3. Ví dụ ............................................................................................................ 29 2.5. Kết luận chương 2 .............................................................................................. 32
iv
CHƯƠNG 3: CHƯƠNG TRÌNH THỰC NGHIỆM HỌ THUẬT TOÁN ĐỐI SÁNH MẪU CHÍNH XÁC NHANH VỚI BỘ CÔNG CỤ SMART ............................. 33 3.1. Giới thiệu ........................................................................................................... 33 3.2. Bộ công cụ Smart ............................................................................................... 33
3.2.1. Các thành phần chính trong bộ công cụ SMART .......................................... 33
3.2.2. Sử dụng bộ công cụ Smart ........................................................................... 43 3.3. Bộ trung gian PUTTY ........................................................................................ 44 3.4. Kết quả thực nghiệm và nhận xét ........................................................................ 45
3.4.1. Thực nghiệm đánh giá hiệu năng hai thuật toán SSABS và TVSBS ............. 45
3.4.2. Thực nghiệm về kết quả sánh mẫu của hai thuật toán SSABS và TVSBS ..... 49 3.5. Kết luận chương 3 .............................................................................................. 51 KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU TIẾP THEO ............................................... 53 TÀI LIỆU THAM KHẢO ............................................................................................. 54
PHỤ LỤC
v
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
MP70 Morris-Pratt
BM Boyer-Moore
CLRS01 CLRS01
BDM CR94
ACR99 Bakward-Oracle
BDM BNDM
QS Quick Search
KMP Knuth-Morris-Pratt
brBc Berry-Ravindran
vi
DANH MỤC CÁC BẢNG
Bảng 2.1. Các giá trị dịch chuyển cho = 4 được đưa ra bởi hàm brBc ............ 22
Bảng 2.2. Các hàng ES, next và shift cho một mẫu ví dụ ................................... 30
Bảng 3.1. Danh sách tất cả các thuật toán sánh xâu từ năm 1970 trên SMART . 34
Bảng 3.2. Bộ các kho ngữ liệu thử nghiệm ........................................................ 38
Bảng 3.3. Bảng kết quả thử nghiệm 1 ................................................................ 46
vii
DANH MỤC CÁC HÌNH VẼ
Hình 3.1. Đăng nhập bằng bộ trung gian PUTTY .............................................. 45
Hình 3.2. Kết quả thực nghiệm 1 ....................................................................... 46
Hình 3.3. Kết quả thực nghiệm 2 tìm mẫu trong chuỗi ...................................... 50
Hình 3.4. Kết quả thực nghiệm 2 tìm mẫu trong file ......................................... 51
1
MỞ ĐẦU
Đối sánh xâu chính xác (exac string matching, sau đây gọi tắt là “sánh xâu chính xác”), còn được gọi là sánh mẫu chính xác (exac pattern matching) là bài toán tìm ra tất cả sự xuất hiện của một xâu p cho trước trong một văn bản t, trong đó p, t đều là các xâu văn bản theo một bảng chữ cái; p được gọi là “mẫu” (pattern) còn t là được gọi là “văn bản đích” (target text) [3, 8]. Một ví dụ gần gũi là cho một truy vấn p và một trang web t, kiểm tra xem p có xuất hiện trong nội dung của t hay không.
Theo Simone Faro và Thierry Lecroq [8], trong 40 năm gần đây, đối sánh xâu là một trong những bài toán được nghiên cứu rộng rãi nhất trong khoa học máy tính, chủ yếu vì các ứng dụng trực tiếp của nó cho rất nhiều lĩnh vực khác nhau như xử lý văn bản - hình ảnh - tín hiệu (text, image and signal processing), phân tích và nhận dạng giọng nói (speech analysis and recognition), truy hồi thông tin (information retrieval), nén dữ liệu (data compression), sinh học và hóa học tính toán (computational biology and chemistry). Bài toán sánh xâu chính xác trực tuyến (onlineexac string matching) nhận được sự quan tâm rất lớn của cộng đồng nghiên cứu. Trong thập kỷ 2001-2010, hơn 50 thuật toán mới được đưa ra, mở rộng thêm số lượng khoảng 40 thuật toán đã có từ trước năm 2000 [2]. Hệ thống các thuật toán này đã được phân tích, đánh giá công phu [5, 6, 7].
Theo Simone Faro và Thierry Lecroq, nhóm các thuật toán sánh mẫu nhanh có nguồn gốc từ thuật toán QS [9] đã chứng tỏ được lợi thế, đặc biệt khi mẫu đối sánh có độ dài ngắn. Chính vì lý do đó, luận văn này định hướng nghiên cứu một số thuật toán sánh mẫu chính xác nhanh có nguồn gốc từ thuật toán QS, tập trung vào họ thuật toán SSABS [8] – TVSBS [4] - FQS [3] do các thuật toán này đã tỏ ra ưu việt trong bài toán sánh mẫu ngắn. Họ thuật toán này là ở nhánh thuật toán khác với các thuật toán trong [1], hơn nữa, thuật toán FQS là mới được công bố vào năm 2014.
Nội dung chủ yếu của luận văn là nghiên cứu, phân tích chi tiết các thuật toán sánh mẫu SSABS – TVSBS - FQS, khai thác công cụ [11] để tiến hành thực nghiệm. Nội dung chính của luận văn gồm phần mở đầu, bốn chương nội dung, phần kết luận. Nội dung của bốn chương nội dung được giới thiệu sơ bộ như sau:
Chương 1. Giới thiệu chung về thuật toán sánh mẫu trình bày các khái niệm và đặc trưng của bài toán sánh mẫu, các ứng dụng của sánh mẫu, khái quát về các thuật toán sánh mẫu chính xác nhanh.
2
Chương 2. Họ thuật toán sánh mẫu chính xác nhanh SSABS -TVSBS- FQS giới thiệu về một lớp thuật toán sánh mẫu chính xác nhanh, trình bày và phân tích họ thuật toán SSABS-TVSBS- FQS. Đồng thời, các bước tiến hóa và hiệu suất của ba thuật toán này cũng được giới thiệu.
Chương 3. Chương trình thực nghiệm họ thuật toán đối sánh mẫu chính xác nhanh với bộ công cụ Smart.
Phần kết luận tổng kết các kết quả chính cũng như các hạn chế của luận văn, đồng thời, ý tưởng về các nghiên cứu tiếp theo cũng được giới thiệu.
3
CHƯƠNG 1. GIỚI THIỆU CHUNG VỀ THUẬT TOÁN SÁNH MẪU
1.1. Bài toán sánh mẫu và phân loại
1.1.1. Bài toán sánh mẫu
Theo Simone Faro và Thierry Lecroq [6, 7, 8], bài toán sánh mẫu được phát biểu như sau “Cho một bảng chữ cái S cỡ s, một văn bản T với độ dài n và một mẫu p với độ dài m, bài toán sánh mẫu là việc tìm ra tất cả các lần xuất hiện của mẫu p trong văn bản T đã cho’’.
Như đã được giới thiệu, do được ứng dụng trực tiếp trong rất nhiều lĩnh vực như xử lý văn bản, hình ảnh và tín hiệu, phân tích giọng nói và nhận dạng, truy hồi thông tin, nén dữ liệu, sinh học tính toán và hóa học tính toán cho nên bài toán sánh mẫu được nghiên cứu rộng rãi trong khoa học máy tính. Từ năm 1970 tới nay đã có hơn 80 thuật toán sánh mẫu đã được đề xuất và hơn 50% các thuật toán này đã được đưa ra trong 10 năm qua [6, 7, 8].
Thời gian gần đây, bài toán sánh mẫu càng trở nên quan trọng và được quan tâm nhiều do sự tăng trưởng nhanh chóng của các hệ thống truy hồi thông tin (information retrieval) và các hệ thống tin - sinh học (bioinformatics). Một lý do nữa, con người ngày nay không chỉ đối mặt với một lượng tài nguyên thông tin khổng lồ mà còn đòi hỏi những yêu cầu tìm kiếm ngày càng phức tạp. Các mẫu đưa vào không chỉ đơn thuần là một xâu ký tự mà còn có thể chứa các ký tự thay thế, các khoảng trống và các biểu thức chính quy. Sự “tìm thấy” không đơn giản là chỉ ra sự xuất hiện chính xác mẫu trong văn bản mà còn cho phép “một xấp xỉ” giữa mẫu và sự xuất hiện của nó trong văn bản. Từ đó, bên cạnh vấn đề kinh điển là “tìm kiếm chính xác”, nảy sinh một hướng nghiên cứu là "sánh mẫu xấp xỉ/tìm kiếm xấp xỉ” (approximate pattern match/search) v.v.
1.1.2. Phân loại bài toán sánh mẫu
1.1.2.1. Sánh mẫu chính xác và sánh mẫu xấp xỉ
Phát biểu về bài toán sánh mẫu được trình bày trong mục trên đây [5] thực chất là phát biểu cho bài toán sánh mẫu chính xác. Với bài toán sánh mẫu chính xác, việc tìm ra tất cả các lần xuất hiện của chuỗi mẫu có thể được thi hành bằng một lần quét duy nhất, diễn ra với nhiều lần thử trên các đoạn khác nhau của văn bản đích T. Trong mỗi lần thử, chương trình sẽ kiểm tra sự giống nhau giữa mẫu với cửa sổ hiện thời. Độ phức tạp của thuật toán tìm tất cả các lần xuất hiện của P trong T là O (mn).
4
Trong bài toán tìm kiếm văn bản trên tập văn bản T, bài toán sánh mẫu được thực hiện đối với mọi cặp gồm mẫu (truy vấn) q và mọi văn bản tT. Trong trường hợp độ dài n của t rất lớn và số lượng văn bản trong T rất nhiều (|T|>>1) thì thời gian tìm kiếm văn bản phù hợp với câu hỏi q sẽ là rất tốn kém. Chính vì lý do đó, nghiên cứu đề x`uất các thuật toán sánh mẫu mới, cải tiến các thuật toán sánh mẫu sẵn có để nâng cao tốc độ sánh mẫu luôn là một chủ đề nghiên cứu được cộng đồng hết sức quan tâm.
Thực tiễn cũng tồn tại nhiều tình huống tìm kiếm xấp xỉ trong đó cho phép có sự "sai khác không đáng kể" giữa mẫu P và xâu con S' của xâu S. Cũng chính vì lý do đó, bài toán sánh mẫu xấp xỉ (Approximate Pattern Matching) được đặt ra, trong đó, hãy tìm ra một (hay tất cả) các xâu con S' của xâu S mà S' "sai khác không đáng kể" với mẫu P [11]. Tồn tại một số tiêu chí cho độ đo "sai khác không đáng kể", chẳng hạn như số lượng ký tự cùng vị trí trong hai xâu S' và P là khác nhau chiếm tỷ lệ rất nhỏ so với độ dài m của xâu P.
Thông thường, các thuật toán sánh mẫu làm việc với mẫu có độ dài ngắn (m30), tuy nhiên trong thực tiễn, bài toán sánh mẫu có độ dài mẫu lên tới con số hàng chục ngàn. Người ta gọi các bài toán sánh mẫu với mẫu dài như vậy là bài toán sánh mẫu "nặng" để phân biệt với bài toán sánh mẫu "nhẹ" mà độ dài mẫu không quá 30. Thực tiễn cũng chỉ ra rằng hầu hết các ứng dụng của sánh mẫu là sánh mẫu nhẹ.
1.1.2.2. Sánh mẫu trực tuyến và sánh mẫu ngoại tuyến
Sánh mẫu ngoại tuyến (offline pattern matching) là trường hợp bài toán sánh mẫu khi mà cả mẫu P và văn bản T đã có sẵn. Một trường hợp đặc biệt chính là cả mẫu P và văn bản T đã có trong bộ nhớ. Trong sánh mẫu ngoại tuyến, việc tiền xử lý dữ liệu đối với P và T có thể được tiến hành từ trước để tạo điều kiện tạo nên các cơ chế phù hợp (bao gồm các cấu trúc dữ liệu bổ sung thích hợp) để tăng tốc độ quá trình sánh mẫu. Thông tin cơ bản như độ dài của P và T được coi như một thông tin tiên liệu về quá trình sánh mẫu.
Sánh mẫu trực tuyến (online pattern matching) là trường hợp bài toán sánh mẫu khi mà văn bản T chưa được biết toàn bộ, chẳng hạn như trường hợp tiến hành sánh một mẫu P đã cho với một văn bản T đang được đọc từ Internet. Tiền xử lý dữ liệu không cho phép tiền xử lý dữ liệu, khi đó nhiều thông tin liên quan chưa thể biết, chẳng hạn như độ dài của văn bản T.
5
1.2. Một số ứng dụng của bài toán sánh mẫu
Bài toán sánh mẫu không chỉ được ứng dụng trong miền xử lý văn bản (text processing) mà còn được ứng dụng trong nhiều miền ứng dụng khác, chẳng hạn như, xử lý hình ảnh và tín hiệu (image and signal processing), phân tích và tổng hợp tiếng nói (speech analysis and recognition), nén dữ liệu (data compression), truy hồi thông tin (informationretrieval), sinh học và hóa học tính toán (computational biology and chemistry) [5, 6, 7].
Trên thực tế có rất nhiều ứng dụng sánh mẫu như: cơ chế sánh mẫu của hệ điều hành (chẳng hạn, lệnh grep, fgrep ... tìm kiếm một file theo tên file trong hệ điều hành UNIX), cơ chế kiểm tra một file có bị nhiễm virus hay không (sánh mẫu “xâu đặc tả virus” với nội dung file), máy tìm kiếm (search engine) trên Internet tìm kiếm các trang web có chứa mẫu p là cụm từ khóa tìm kiếm, xác định mẫu gene bệnh xuất hiện trong đoạn gene của người (các xâu văn bản trong bảng chữ cái gồm bốn chữ cái A, C, G, T) ...
1.3. Một số thuật toán sánh mẫu truyền thống
Tất cả các thuật toán sánh mẫu truyền thống đều quét văn bản T với sự trợ giúp của một cửa sổ có độ dài tương đương với độ dài của mẫu, trong đó, cửa sổ là một chuỗi m ký tự liên tiếp trên văn bản. Trong mỗi lần kiểm tra, chương trình sẽ xem xét sự giống nhau giữa mẫu với cửa sổ hiện thời, nếu kết quả đúng thì ghi nhận một lần xuất hiện của mẫu trong xâu. Sau đó, cửa sổ sẽ được dịch sang bên phải trên văn bản cho lần kiểm tra tiếp theo.
Trong mỗi lần xem xét, quá trình được bắt đầu từ việc so sánh lần lượt từng phần tử từ trái sang phải của cửa sổ với phần tử tương ứng của mẫu. Nếu xuất hiện một sự không phù hợp có thể dừng việc xem xét cửa sổ hiện thời với mẫu, nếu ngược lại thì quá trình được tiếp tục cho tới phần tử cuối cùng trong cửa sổ. Các thuật toán sánh mẫu là khác nhau ở trật tự so sánh ký tự trên mẫu và khoảng cách mà cửa sổ được di chuyển trên văn bản sau mỗi lần kiểm tra.
Nhiều thuật toán sánh mẫu đã được đề xuất mà mỗi thuật toán có những ưu, nhược điểm tùy theo độ dài mẫu, sự thiết lập chu kỳ và bảng chữ cái. Simone Faro và Thierry Lecroq [6] đã trình bày một phân tích đánh giá 85 thuật toán sánh mẫu chính xác, đưa ra mười lớp tình huống sánh mẫu chính xác và tương ứng là 10 thuật toán điển hình cho từng tình huống bài toán sánh mẫu.
Các thuật toán sánh mẫu chính xác được phát triển dựa trên một số thuật toán sánh mẫu truyền thống mà điển hình là các Boyer–Moore và Quick Search như giới thiệu dưới đây.
6
1.3.1. Thuật toán Boyer–Moore
Boyer–Moore (BM) là một thuật toán tìm kiếm xâu hiệu quả được Boyer và Moore đưa ra vào năm 1977 [6, 8]. Thuật toán BM được xếp là loại thuật toán đo lường đạt chuẩn trong tài liệu về sánh xâu chính xác kể từ khi nó được giới thiệu. Thuật toán BM xử lý trước mẫu P và sử dụng thông tin thu thập được trong suốt bước tiền xử lý để bỏ qua các khối văn bản trong khi đối sánh, kết quả đạt được nhanh hơn rất nhiều thuật toán sánh xâu khác. Nhìn chung, thuật toán BM chạy nhanh hơn khi chiều dài của mẫu tăng lên.
Đầu tiên, BM xử lý trước mẫu P để xây dựng hàng dịch chuyển xuất hiện (được viết tắt là bad_shift) với độ dài |Σ|, được xác định bằng việc sử dụng công thức:
bad_shift() = min (m-1-k: {0 k Sau đó, BM sử dụng quy tắc ký tự xuất hiện. Quy tắc này quy định rằng một
khi xuất hiện lỗi đối sánh, thuật toán nhảy tới vị trí tiếp theo, được xác định bằng
hàng bad_shift mà không cần thực hiện những so sánh theo thuật toán Brute Force. BM cũng sử dụng quy tắc dịch chuyển khớp, BM bắt đầu so sánh giữa văn
bản T và mẫu P từ phải sang trái. Khi có một lỗi đối sánh xảy ra trong P [i] ≠ T [j +
i] với 0 < i < m và 0 < j < n, dịch chuyển khớp của mẫu P[i+1,…,m-1] đối sánh
văn bản T[i+j+1,…,j+m-1]; dịch chuyển khớp của mẫu P[i+1,…,m-1] được gọi là
phép dịch chuyển khớp tốt. Thuật toán tính toán hàng dịch chuyển tốt có độ dài
m+1 xác định vị trí nhảy kế tiếp bằng việc sử dụng khoảng cách dịch chuyển tối đa
có thể từ cấu trúc của mẫu. Giá trị dịch chuyển tổng thể sau đó được xác định bằng
việc lựa chọn khoảng cách dài hơn giữa cả hai hàng dịch chuyển khớp và dịch
chuyển xuất hiện. Thuật toán cổ điển Quick Search và biến thể cải tiến của các tác
giả đều không sử dụng quy tắc dịch chuyển khớp; Do đó, phương trình hàng dịch
chuyển khớp tương ứng không hiển thị ở đây. Thuật toán gốc BM có thời gian chạy
trong trường hợp xấu nhất là O(mn) và thời gian chạy thực trong trường hợp tốt nhất
là O(n/m). Nhìn chung, nó có hiệu suất rất tốt và có những chỉnh sửa đổi đơn giản
để đạt được thời gian tổng thể trong trường hợp xấu nhất trong giới hạn: O(n + m + |Σ|). Trong thuật toán này có hai cách 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. 7 Trong lần thử tại vị trí j, khi so sánh đến ký tự i trên mẫu thì phát hiện ra sự
khác nhau giữa ký tự x[i]=a của mẫu và ký tự y[i+j]=b của văn bản, lúc đó
x[i+1..m-1]=y[i+j+1..j+m-1]=u và y[i+j-1]=b và x[i]y[i+j] khi đó thuật toán sẽ
dịch cửa sổ sao cho đoạn u=y[i+j+1..j+m-1] giống với một đoạn mới trên mẫu
(trong các phép dịch ta chọn phép dịch nhỏ nhất) b u y x a u shift x c u Dịch sao cho u xuất hiện lại và c ≠ a Nếu không có một đoạn nguyên vẹn của u xuất hiện lại trong x, ta sẽ chọn sao cho phần đôi dài nhất của u xuất hiện trở lại ở đầu mẫu. y b u x a u shift x u Dịch để một phần đôi của u xuất hiện lại trên x Cách thứ 2: Coi ký tự đầu tiên không khớp trên văn bản là b=y[i+j] 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 ta chọn vị trí phải nhất). y b u a u x shift x b không chứa b Dịch để ký tự b ăn khớp với văn bản. 8 Nếu không có ký tự b nào xuất hiện trên mẫu ta sẽ dịch cửa sổ sao cho ký tự trái nhất của cửa sổ vào vị trí ngay sau ký tự y[i+j-1]=b để đảm bảo sự ăn khớp. y u b x u a shift x không chứa b Dịch khi b không xuất hiện trong x Trong hai cách dịch chuyển, thuật toán sẽ chọn cách dịch có lợi nhất. Trong cài đặt ta dùng mảng bmGs để lưu cách dịch 1, mảng bmBc để lưu phép dịch
thứ 2 (ký tự không khớp). Việc tính toán mảng bmBc thực sự không có gì nhiều để
bàn. nếu c xuất hiện trong x bmBc[c]= ngược lại (1.2) Nhưng việc tính trước mảng bmGs khá phức tạp, ta không tính trực tiếp mảng này mà tính gián tiếp thông qua mảng suff. suff[i]=max{k | x[i-k+1..i]=x[m-k..m-1]} Các mảng bmGs và bmBc có thể được tính toán trước trong thời gian tỉ lệ
với O(m+). Thời gian tìm kiếm (độ phức tạp tính toán) của thuật toán Boyer-
Moore là O(m*n). Tuy nhiên với những bản chữ cái lớn thuật toán thực hiện rất
nhanh. Trong trường hợp tốt chi phí thuật toán có thể xuống đến O(n/m) là chi phí
thấp nhất của các thuật toán tìm kiếm hiện đại có thể đạt được. Thuật toán Boyer-Moore có thể đạt tới chi phí O(n/m) là nhờ có cách dịch
thứ 2 “ký tự không khớp”. Cách chuyển cửa sổ khi gặp “ký tự không khớp” cài đặt
vừa đơn giản lại rất hiệu quả trong các bảng chữ cái lớn nên có nhiều thuật toán
khác cũng đã lợi dụng các quét mẫu từ phải sang trái để sử dụng cách dịch này. Tuy nhiên chi phí thuật toán của Boyer-Moore là O(m*n) vì cách dịch thứ
nhất của thuật toán này không phân tích triệt để các thông tin của những lần thử
trước, những đoạn đã so sánh rồi vẫn có thể bị so sánh lại. Có một vài thuật toán đã 9 cải tiến cách dịch này để đưa đến chi phí tính toán của thuật toán Boyer-Moore là
tuyến tính. 1.3.2. Thuật toán Quick Search Thuật toán Quick Search (QS) là một sự đơn giản hóa của thuật toán Boyer-
Moore mà không theo quy tắc dịch chuyển khớp. QS xử lý trước mẫu P sử dụng
một hàng bad_shift đã qua sửa đổi (được gọi là qbad_shift) của độ dài |Σ| trong độ
phức hợp thời gian của Θ(m + |Σ|). Sự sửa đổi hàng bad_shift của QS được xác
định như sau: qbad_shift(σ) = min (m-k: {0 k m-1 p[m k 1] = σ, σ} {m+1}) Các bước tiền xử lý của thuật toán QS được thể hiện trong Thuật toán 1.
Trong Thuật toán 1, hàng qsBc là hàng ký tự dịch chuyển xuất hiện Quick Search,
được khởi tạo giá trị m từ Hàng 1 tới Hàng 3. Hàng 4-6 thực hiện Biểu thức (1.2).
Ví dụ, trong trường hợp P = “GCAGTCAG” với m = 8 và Σ = {A, C, G, T}. Mỗi
yếu tố trong hàng bad_shiftqsBc[A, C, G, T] được khởi tạo đến 8. Sau khi thực hiện
lệnh forloop từ Hàng 4 đến Hàng 6, ta có hàng bad_shift là qsBc[A, C, G, T] =
[2,3,1,4]. Thuật toán 1: Tiền xử lý của Thuật toán Quick search PREQS(P, m) 1 for i ← 0 to |Σ|-1
2 qsBc[i] ← m
3 end for
4 for i ← 0 to m − 1
5 qsBc[P[i]] ← m − i
6 end for
7 return qsBC[] Trong Thuật toán 1, Dòng 1-3 chạy trong |Σ| các bước; Dòng 4-6 chạy trong m các bước. Do vậy, tổng thời gian tiền xử lý là O(m + |Σ|). Thuật toán 2 thể hiện thuật toán Quick Search. Trước tiên, quy trình tiền xử
lý được gọi là preQs, để tính toán hàng dịch chuyển xuất hiện. Từ Hàng 3-9 sử dụng
whileloop để so sánh văn bản T và mẫu P. Hàng 4 so sánh P[0, ..., m − 1] và T[j, ...,
j + m − 1], trong đó 0 ≤ j ≤ n − m. Khi lỗi đối sánh xảy ra, thuật toán QS chuyển
sang một vị trí mới được quyết định bởi ký tự xuất hiện trong T, bằng việc sử dụng
giá trị dịch chuyển thích hợp cho biểu tượng, đó là T[j + m] Thuật toán 2: Thuật toán Quick search 10 QS(P, m, T, n, |Σ|)
1 shift ← preQS(P,m)
2 j ← 0
3 while (j ≤ n − m)
4 Compare P[0, ..., m − 1] and T[j, ..., j + m − 1]
5 if all matched then do
6 output j
7 end if
8 j ← j + shift[T[j + m]]
9 end while Giai đoạn tìm kiếm của QS có độ phức tạp thời gian trong trường hợp xấu
nhất là O(mn). Trong mỗi thời gian, khoảng cách dịch chuyển được duy trì và ký tự
xuất hiện được tìm thấy trong so sánh cuối cùng của P[0] tới văn bản phù hợp (QS
bắt đầu so sánh từ phải sang trái). Ví dụ: Nếu T = Anvà P = BAm-1, trong trường hợp này, khoảng cách dịch
chuyển qsBc[A] = 1. Đó là, khi mỗi ký tự xấu xuất hiện, khoảng cách dịch chuyển
sẽ là 1. Thêm vào đó, ký tự xuất hiện này được tìm thấy trong so sánh cuối cùng của
P[0] với vị trí văn bản tương ứng, bởi vì so sánh của QS thực hiện từ phải sang trái.
Tuy nhiên, trường hợp cực xấu này hiếm xảy ra. Giống như BM, nhìn chung QS có
hiệu suất thực tiễn rất tốt. 1.4. Khái quát về các thuật toán sánh mẫu chính xác Theo Simone Faro và Thierry Lecroq [7], bài toán sánh xâu chính xác bao
gồm việc tìm ra tất cả những lần xuất hiện của một mẫu đối sánh (p) trong một văn
bản (t). Đây là một vấn đề đã được nghiên cứu nhiều trong khoa học máy tính, chủ
yếu do nó có những ứng dụng trực tiếp đến nhiều mặt như xử lý văn bản, hình ảnh
và tín hiệu, phân tích giọng nói và nhận dạng, truy vấn thông tin, nén dữ liệu, sinh
học tính toán và hóa học tính toán. Trong suốt thập kỷ qua (2001-2010) có hơn 50 thuật toán mới được đưa ra để
áp dụng cho vấn đề này, mở rộng thêm số lượng thuật toán đã có (khoảng 40 thuật
toán) được trình bày trước năm 2000. Các tác giả sẽ xem xét những thuật toán đối
sánh chuỗi hiệu quả nhất được trình bày trong thập kỷ qua để đưa ra một cách hệ
thống trong số hàng chục bài đã xuất bản trong lĩnh vực này. Các tác giả thực hiện so sánh 85 thuật toán đối sánh chuỗi chính xác với 12
văn bản thuộc về những loại khác nhau. Các tác giả chia các mẫu đối sánh làm 4
loại theo chiều dài m: rất ngắn (m4), ngắn (4 < m 32), dài (32 < m 256) và rất 11 dài (m > 256). Các tác giả tiến hành theo cùng một cách như vậy đối với việc chia
mẫu đối sánh theo khổ chữ cái s: rất nhỏ (s<4), nhỏ (4 s<32), rộng (32 s < 128)
và rất rộng (s>128). Theo các kết quả thử nghiệm, các tác giả kết luận rằng các
thuật toán sau đạt hiệu quả nhất trong các tình huống sau đây: - SA: các mẫu đối sánh rất ngắn và bảng chữ cái rất nhỏ. - TVSBS: các mẫu đối sánh rất ngắn và bảng chữ cái nhỏ, và các mẫu đối sánh dài và bảng chữ cái rộng. - FJS: các mẫu rất ngắn và bảng chữ cái rộng và rất rộng. - EBOM: các mẫu ngắn và bảng chữ cái rộng và rất rộng. - SBNDM-BMH và BMH-SBNDM: mẫu ngắn và bảng chữ cái rất rộng. - HASHq: các mẫu rộng, ngắn và bảng chữ cái nhỏ. - FSBNDM: các mẫu dài và bảng chữ cái rộng và rất rộng. - SBNDMq : các mẫu dài và bảng chữ cái nhỏ. - LBNDM : các mẫu rất dài và bảng chữ cái rất rộng. - SSEF [7]: các mẫu rất dài. Nhưng trong số các thuật toán này chỉ có một thuật toán là SA được thiết kế
trong suốt thập kỷ qua, 4 thuật toán khác được dựa trên sự so sánh các kí tự, một
thuật toán dựa trên automata trong khi 6 thuật toán còn lại là những thuật toán bit
song song. Để giảm thiểu các công việc phát triển các thuật toán đối sánh chuỗi chính
xác, các tác giả phát triển một công cụ thông minh (công cụ nghiên cứu các thuật
toán đối sánh chuỗi, tham khảo tại http://www.dmi.unict.it/~faro/smart/) cung cấp
khung tiêu chuẩn cho các nhà nghiên cứu trong đối sánh chuỗi. Nó giúp cho người
sử dụng kiểm tra, thiết kế, đánh giá và hiểu được các giải pháp hiện có để giải
quyết vấn đề đối sánh chuỗi chính xác. Hơn nữa nó cung cấp bổ sung hầu hết tất cả
các thuật toán đối sánh chuỗi và một dữ liệu vùng đệm văn bản mở rộng. 1.5. Kết luận chương 1 Chương 1 trình bày các nghiên cứu về các bài toán sánh mẫu. Bài toán sánh
mẫu có thể chia làm 2 loại là: sánh mẫu chính xác và sánh mẫu xấp xỉ; hoặc sánh
mẫu trực tuyến và sánh mẫu ngoại tuyến. Trong đó, bài toán sánh xâu chính xác bao
gồm việc tìm ra tất cả những lần xuất hiện của một mẫu đối sánh (p) trong một văn
bản (t). Đây là một trong những bài toán được nghiên cứu rộng rãi nhất trong khoa
học máy tính, chủ yếu vì các ứng dụng trực tiếp của nó cho rất nhiều lĩnh vực khác 12 nhau như xử lý văn bản - hình ảnh - tín hiệu (text, image and signal processing),
phân tích và nhận dạng giọng nói (speech analysis and recognition), truy hồi thông
tin (information retrieval), nén dữ liệu (data compression), sinh học và hóa học tính
toán (computational biology and chemistry). Chương này tập trung nghiên cứu và trình bày các thuật toán sánh mẫu truyền thống là thuật toán Boyer - Moore và thuật toán QuickSearch. 13 2.1. Giới thiệu về các biến thể của thuật toán Quick Search Trong [7], Simone Faro và Thierry Lecroq cung cấp một khái quát về các
thuật toán sánh mẫu được phát triển dựa trên thuật toán Quick Search. Một số thuật
toán điển hình như sau: - Thuật toán SSABS được công bố năm 2004 [8] là một kết hợp chiến lược
chuyển dịch của thuật toán QS và chiến lược kiểm thử nghiệm của thuật toán Raita.
Thuật toán TVSBS được công bố năm 2006 [4] là phiên bản cải tiến của SSABS.
Hai thuật toán này có độ phức tạp thời gian trong trường hợp xấu nhất là O(nm) với
n, m tương ứng là kích thước của mẫu và xâu văn bản. - Thuật toán Franek-Jennings-Smyth được công bố năm 2007 là một thuật
toán kết hợp đơn giản các trường hợp độ phức tạp thời gian tồi nhất của thuật toán
Knuth-Morris-Pratt với các hành vi trung bình tốt hơn của thuật toán QS. - Thuật toán Forward BOM (Forward-Backward-Oracle-Matching) được
công bố năm 2008 là một thuật toán kết hợp các ý tưởng tiến bộ của thuật toán
Extended-BOM và thuật toán QS. Luận văn này tập trung vào một nhóm thuật toán biến thể của thuật toán
Quick Search mà được kiểm định là có lợi thế khi mẫu ngắn với bảng chữ nhỏ hoặc
mẫu dài với bảng chữ lớn [6] với đại diện là thuật toán TVSBS. Các mục dưới đây
trình bày lần lượt ba thuật toán thuộc nhóm này là SSABS (Sheik-Sumit-Anindya-
Balakrishnan-Seka) [8], TVSBS (Thathoo-Virmani-Sai-Balakrishnan-Sekar) [4] và
FQS (faster quick search) [3]. 2.2. Thuật toán đối sánh mẫu nhanh SSABS 2.2.1. Giới thiệu Thuật toán SSABS được S. S. Sheik và cộng sự công bố vào năm 2004 [8]
và được đặt tên theo tên năm tác giả S. S. Sheik - Sumit K. Aggarwal - Anindya
Poddar - N. Balakrishnan - K. Sekar. Theo S. S. Sheik và cộng sự, hầu hết các thuật toán sánh mẫu nổi tiếng làm
việc theo hai giai đoạn: giai đoạn tiền xử lý và giai đoạn tìm kiếm. Trong giai đoạn
tiền xử lý, các thuật toán này xử lý mẫu và sử dụng thông tin này trong giai đoạn
tìm kiếm để giảm thiểu tổng số lượng so sánh ký tự và do đó giảm thời gian thực
hiện tổng thể. Hiệu quả của một thuật toán chủ yếu phụ thuộc vào giai đoạn tìm
kiếm. Mục tiêu chính của các thuật toán đối sánh mẫu là để giảm thiểu số lượng so 14 sánh ký tự giữa mẫu và văn bản nhằm làm tăng hiệu quả tổng thể. Sự cải tiến trong
hiệu quả của một tìm kiếm có thể đạt được bằng cách thay đổi trật tự các ký tự được
so sánh mỗi lần thử nghiệm và bằng việc lựa chọn yếu tố dịch chuyển cho phép
bước nhảy của một số ký tự được xác định trước trong văn bản sau mỗi lần thử
nghiệm. Các thuật toán đối sánh mẫu quét văn bản với sự hỗ trợ của một cửa sổ, có
kích thước tương đương với độ dài của mẫu. Bước đầu tiên là gắn kết các phần cuối
cùng bên trái của cửa sổ và văn bản, sau đó so sánh với các ký tự tương ứng của cửa
sổ và mẫu. Sau mỗi một đối sánh hoặc lỗi đối sánh của mẫu, cửa sổ văn bản được
dịch chuyển sang bên phải. Vấn đề đặt ra ra là có bao nhiêu ký tự được yêu cầu dịch
chuyển cửa sổ trên văn bản. Các giá trị dịch chuyển này dựa trên phương pháp luận
được sử dụng bởi các thuật toán khác nhau. Quy trình đó được lặp đi lặp lại cho tới
khi phần cuối cùng bên phải của cửa sổ nằm trong phần cuối cùng bên phải của văn
bản. 2.2.2. Thuật toán Trật tự các so sánh được thực hiện bằng việc so sánh ký tự cuối cùng của cửa
sổ và mẫu, sau khi đối sánh, thuật toán tiếp tục so sánh ký tự đầu tiên của cửa sổ và
mẫu. Như vậy, một sự tương đồng ban đầu có thể được thiết lập giữa mẫu và cửa
sổ, các ký tự còn lại được so sánh từ phải qua trái cho tới khi đối sánh hoàn toàn
hoặc lỗi đối sánh xảy ra. Sau mỗi lần thử nghiệm, bước nhảy của cửa sổ đạt được
bằng giá trị dịch chuyển qsBc đối với ký tự được đặt ở vị trí liền kề với cửa sổ. Do sự phụ thuộc của các ký tự lân cận mạnh hơn so với các ký tự khác nên
cần so sánh ký tự cuối cùng trước tiên và ký tự đầu tiên thứ hai sau đó tiếp tục so
sánh các ký tự theo trình tự từ phải sang trái của mẫu và cửa sổ. Vì vậy, sẽ tốt hơn
nếu tạm dừng việc so sánh các ký tự lân cận nhau. Xác xuất việc đánh giá một đối
sánh chính xác giữa mẫu với cửa sổ được tăng lên với một lượng tối thiểu so sánh
bằng cách kết hợp sự tương đồng ban đầu. Thêm vào đó, sự tối đa hóa bước nhảy
cho cửa sổ giúp giảm thiểu số lượng so sánh ký tự với ký tự và làm tăng hiệu suất. Giai đoạn tiền xử lý: Giai đoạn này được thực hiện bằng việc sử dụng hàm dịch chuyển qsBc đối
với tất cả các ký tự trong bảng chữ cái được thiết lập. Một bảng được hình thành với
cỡ σ, chứa ký tự và giá trị bước nhảy tương ứng của nó. Giá trị qsBc cho một bảng
chữ cái cụ thể được xác định như vị trí của ký tự trong mẫu từ phải sang trái, nếu
điều đó không diễn ra trong mẫu thì giá trị sẽ bằng (m+1). Giá trị bước nhảy cho
mỗi ký tự được lưu trữ trong bảng qsBc được sử dụng trong giai đoạn tìm kiếm.
Trong giai đoạn tìm kiếm, sau mỗi lần thử, bước nhảy của cửa sổ được tính toán 15 bằng việc đạt được giá trị dịch chuyển của ký tự ngay sau cửa sổ. Giá trị bước nhảy
tối đa đối với cửa sổ được nhận ra khi ký tự (ký tự ngay sau cửa sổ) không có mặt ở
trong mẫu. Xác suất của một ký tự xuất hiện trong mẫu ít hơn khi cỡ bảng chữ cái
lớn điều đó giúp cho việc đạt được bước nhảy tối đa của cửa sổ. Trong thuật toán
này ta xem xét hàm dịch chuyển qsBC của Quick-search vì những lí do sau: (1) Giá trị qsBc thường được xác định ≥ 1, do đó nó có thể làm việc một cách
độc lập và ra một thuật toán nhanh. Mặt khác, bmBc đôi khi mang lại giá trị dịch
chuyển ≤ 0 và trong các trường hợp như vậy nó không được sử dụng một cách độc
lập. Do vậy, nó phải làm việc cùng với bmGs (dịch chuyển khớp của Boyer-Moore)
để tính toán bước nhảy của cửa sổ. (2) qsBC = bmBC, trừ các ký tự cuối cùng trong mẫu. Do đó, qsBc luôn luôn có giá trị dịch chuyển nhiều hơn bmBc trong thực tế. (3) qsBc không phụ thuộc vào trật tự các so sánh giữa mẫu và cửa sổ. Vì
qsBc được xác định liên quan tới một ký tự nằm ngoài phạm vi so sánh hiện tại của
mẫu. Giai đoạn tìm kiếm: Bước 1 và bước 2 của giai đoạn này giải quyết trật tự so sánh ký tự với ký tự giữa cửa sổ và mẫu. Bước 1: Để tìm ra sự tương đồng ban đầu giữa mẫu và cửa sổ, trước tiên, ký
tự cuối cùng của mẫu và cửa sổ được so sánh, trong trường hợp có đối sánh, ký tự
đầu tiên của mẫu và ký tự tương ứng trong cửa sổ được so sánh. Nếu những ký tự
này đối sánh, thuật toán đi vào bước tiếp theo, nếu không nó sẽ đi tới bước cuối
cùng. Bước 2: Sau khi tạo một sự tương đồng ban đầu giữa cửa sổ và mẫu, các ký
tự còn lại được so sánh theo trật tự từ phải sang trái cho đến khi một lỗi đối sánh
xảy ra hoặc tất cả các ký tự (m – 2) đối sánh. Nếu tất cả các ký tự đối sánh, thuật
toán hiển thị vị trí tương ứng (j) của cửa sổ trên văn bản. Sau đó thuật toán đi vào
bước cuối cùng. Bước 3: Trong bước này, sự tính toán khoảng cách mà cửa sổ được dịch
chuyển được tính toán sử dụng qsBc, đã được tạo ra trong suốt giai đoạn tiền xử lý,
đối với ký tự đầu tiên ngay sau cửa sổ. Quy trình này lặp lại cho tới khi cửa sổ đạt được vị trí ngoài (n - m +1). Phân tích thuật toán: 16 Trong giai đoạn tiền xử lý: Thời gian tính toán của của thuật toán là O(m + σ) và độ
phức tạp không gian là O(σ). Trong giai đoạn tìm kiếm: Trong trường hợp tốt nhất độ phức tạp thời gian là
O([(n/(m + 1))]) . Các ký tự không xảy ra trong mẫu có giá trị dịch chuyển (m+1)
được xác định bởi qsBc được tính toán trong suốt giai đoạn tiền xử lý. Việc xem xét
trường hợp tốt nhất là các ký tự trong mẫu hoàn toàn khác so với các ký tự trong
văn bản, đối sánh m ký tự của mẫu trong văn bản thu được giá trị dịch chuyển
(m+1) tại mỗi lần thử nghiệm và do đó độ phức tạp thời gian là O([(n/(m + 1))]). Trong trường hợp xấu nhất độ phức tạp thời gian là O(m(n-m+1)). Thực tế
tất cả các ký tự trong văn bản được đối sánh không hơn m thời gian, tổng số các so
sánh ký tự đối với n ký tự của văn bản không thể nhiều hơn m(n+1); Sự dịch
chuyển bằng 1 và các ký tự được đối sánh trong mỗi lần thử nghiệm. Điều này được
nhận ra khi các ký tự trong mẫu tương đồng chính xác với các ký tự trong văn bản. Độ phức tạp thời gian trung bình không thể được xác định một cách chính
xác vì nó chủ yếu phụ thuộc vào cỡ bảng chữ cái và xác xuất lần xuất hiện của mỗi
ký tự riêng lẻ trong văn bản. 2.2.3. Ví dụ Gene người bao gồm 37490 trình tự gene (NCBI site, U.S.A., ftp://ftp.ncbi. nih.gov/genomes/H_sapiens/protein/). tự trình Toàn bộ theo định dạng FASTA: >gi|4504279|ref| NP_002098.1|H3histone,family3A[Homosapiens]MARTKQTARKSTGGKAPRK
QLATKAARKSAPSTGGVKKPHRYRPGTVALREIRRYQKSTELLIRKLPFQR
LVREIAQDFKTDLRFQSAAIGALQEASEAYLVGLFEDTNLCAIHAKRVTIMPKDI
QLARRIRGERA Phần trình tự được xem xét để chạy thử MARTKQTARKSTGGKAPRKQLATKAARKSAPSTGGVKKPHRYRPGTV T=MARTKQTARKSTGGKAPRKQLATKAARKSAPSTGGVKKPHRYRPGTV P=KAPRKQL n=47 m=7 Giai đoạn tiền xử lý A A C D E F G H I K L M N P Q R S T V W Y qsBc[a] 6 8 8 8 8 8 8 8 3 1 8 8 5 2 4 8 8 8 8 8 17 Một bảng được thành lập với cỡ σ, lưu trữ ký tự và giá trị bước nhảy tương ứng của nó. Giai đoạn tìm kiếm. Thử nghiệm đầu tiên : MARTKQTARKSTGGKAPRKQLATKAARKSAPSTGGVKKPHRYRPGTV 1 KAPRKQL shift = qsBc[A] =6 Trước tiên, các ký tự cuối cùng của mẫu và cửa sổ được so sánh. Trong
trường hợp lỗi đối sánh, cửa sổ di chuyển dựa trên giá trị dịch chuyển xuất hiện
qsBc y[j+m]. Lần thử thứ hai : MARTKQTARKSTGGKAPRKQLATKAARKSAPSTGGVKKPHRYRPGTV 1 KAPRKQL shift = qsBc[G] =8 Tại đây một lần nữa, so sánh các ký tự cuối cùng của mẫu và văn bản được
thực hiện, và trong khi có lỗi đối sánh, cửa sổ được dịch chuyển dựa trên giá trị
dịch chuyển y[j+m]. Lần thử thứ ba : MARTKQTARKSTGGKAPRKQLATKAARKSAPSTGGVKKPHRYRPGTV 2 7 65 4 31 KAPRKQL shift = qsBc[A] = 6 Trong trường hợp này, mẫu được đưa ra đối sánh với văn bản và so sánh
được thực hiện như sau: Trước tiên, ký tự cuối cùng của mẫu và cửa sổ được so
sánh, sau đó đến ký tự đầu tiên, tiếp theo là các ký tự còn lại theo trình tự từ phải
sang trái. Sau đó cửa sổ được di chuyển dựa trên giá trị dịch chuyển y[j+m]. 18 Thử nghiệm thứ 4: MARTKQTARKSTGGKAPRKQLATKAARKSAPSTGGVKKPHRYRPGTV 1 KAPRKQL shift = qsBc[K] = 3 Trong lần này, lỗi đối sánh xảy ra giữa các ký tự cuối cùng của mẫu và văn bản. Do đó, cửa sổ được dịch chuyển dựa trên giá trị dịch chuyển như trên. Thử nghiệm thứ 5 : MARTKQTARKSTGGKAPRKQLATKAARKSAPSTGGVKKPHRYRPGTV 1 KAPRKQL shift = qsBc[P] = 5 Lần này cũng như vậy, lỗi đối sánh xảy ra, cửa sổ được di chuyển dựa trên giá trị dịch chuyển như trên. Thử nghiệm thứ 6 : MARTKQTARKSTGGKAPRKQLATKAARKSAPSTGGVKKPHRYRPGTV 1 KAPRKQL shift =qsBc[V] = 8 Tại đây một lần nữa, so sánh các ký tự cuối cùng của mẫu và văn bản không thành, do đó cửa sổ được dịch chuyển dựa trên giá trị dịch chuyển. Thử nghiệm thứ 7 : MARTKQTARKSTGGKAPRKQLATKAARKSAPSTGGVKKPHRYRPGTV 1 KAPRKQL Tổng số lần thử nghiệm: 7 Tổng số ký tự được so sánh : 13 19 Như đã chỉ ra ở trên, so sánh ký tự với ký tự không thành. Giá trị dịch
chuyển được tính toán, nhưng cửa sổ không dịch chuyển, vì nó đi ra ngoài điểm
cuối cùng bên phải của văn bản. 2.3. Thuật toán TVSBS 2.3.1. Giới thiệu Thuật toán TVSBS được Rahul Thathoo và cộng sự công bố vào năm 2006
[4] và được đặt tên theo tên năm tác giả Rahul Thathoo, Ashish Virmani, S. Sai
Lakshmi, N. Balakrishnan, K. Sekar. Thuật toán TVSBS là sự kết nối của thuật toán
SSABS và Berry-Ravindran. Hiệu suất của thuật toán mới đã được cải thiện bằng
việc sử dụng chuyển mạch bảng ký tự Berry-Ravindran, số lượng các so sánh ký tự ít
hơn. Hiệu quả của thuật toán nằm trong 2 giai đoạn: giai đoạn tiền xử lý và giai
đoạn tìm kiếm. Các ký tự trong mẫu được xử lý trước trong giai đoạn tiền xử lý và
thông tin này được sử dụng trong giai đoạn tìm kiếm để giảm tổng số lần so sánh ký
tự, từ đó giảm thiểu tổng số thời gian thực hiện. Giai đoạn tìm kiếm được thiết lập
bằng cách thay đổi trật tự so sánh các ký tự trong mỗi lần thử nghiệm và bằng cách
chọn một giá trị dịch chuyển tối ưu cho phép một bước nhảy tối đa trên văn bản. Sự khác nhau giữa các thuật toán chủ yếu do quy trình dịch chuyển và tốc độ
dịch chuyển khi một lỗi đối sánh được phát hiện. Giai đoạn tiền xử lý sử dụng thuật
toán Berry-Ravindran và giai đoạn tìm kiếm sử dụng thuật toán SSABS là tốt nhất. 2.3.2. Thuật toán Hàm dịch chuyển xuất hiện brBc (Berry-Ravindran) hiệu quả trong giai
đoạn tiền xử lý. Giai đoạn tìm kiếm của thuật toán này tương tự như thuật toán
SSABS. Trật tự so sánh được thực hiện bằng việc so sánh ký tự cuối cùng của cửa
sổ và mẫu đến khi chúng có sự đối sánh, sau đó thuật toán so sánh ký tự đầu tiên
của cửa sổ và mẫu. Điều này cũng thiết lập sự tương đồng ban đầu giữa mẫu và
cửa sổ. Các ký tự còn lại sau đó được so sánh từ phải sang trái cho tới khi đối sánh
hoàn tất hoặc một lỗi đối sánh xảy ra. Sau mỗi lần như vậy, việc bỏ qua cửa sổ đạt
được bằng giá trị dịch chuyển brBc cho 2 ký tự liên tiếp ngay cạnh cửa sổ. Hàm
brBc được khai thác để đạt được sự dịch chuyển cực đại và giảm thiểu số lượng so
sánh ký tự. Các yếu tố này được chọn lọc giúp cải thiện đáng kể hiệu suất thuật
toán. Giai đoạn tiền xử lý: Giai đoạn này được thực hiện bằng việc sử dụng hàm brBc, đối với tất cả
các ký tự trong bảng chữ cái được thiết lập. Thuật toán xem xét 2 ký tự liên tiếp 20 xuất hiện ngay sau cửa sổ, tại đó qsBc sử dụng 1 ký tự duy nhất ngay sau cửa sổ.
Giai đoạn tiền xử lý của thuật toán bao gồm trong việc tính toán mỗi cặp ký tự
(a,b) với a, bcũng như với sự xuất hiện ngoài cùng bên phải của ab trong
mẫu. Giá trị dịch chuyển brBc được xác định: 1
1im if
if ]1m[P
]1i[P]i[P
a
ab brBc ]b,a[ min 1m
if ]0[P b 2m
(2.1)
Trường hợp khác Giá trị dịch chuyển tính toán bởi hàm brBc được lưu trữ trong mảng một
chiều thay vì mảng hai chiều và thời gian thực hiện ít hơn trong suốt giai đoạn tìm
kiếm. Chỉ số của mảng một chiều được tính toán bằng các phép toán thao tác trên
bit. Điều này giảm thời gian thực hiện để có giá trị dịch chuyển brBc và thời gian
truy cập bộ nhớ. Bước nhảy của cửa sổ được tìm bằng cách lấy giá trị trị dịch chuyển của 2 ký
tự liên tiếp ngay sau cửa sổ. Giá trị bước nhảy tối đa của cửa sổ đạt được khi cả hai
ký tự này không xuất hiện trong mẫu. Xác xuất của một ký tự trong mẫu xuất hiện
trong bảng chữ cái nhỏ hơn khi cỡ bảng chữ cái lớn và nó giúp đạt được bước nhảy
cực đại của cửa sổ. Thuật toán TVSBS, sử dụng hàm brBc hiệu quả hơn hàm qsBc và bmBc vì những lý do sau: Trong qsBc, giá trị dịch chuyển đi kèm với mỗi ký tự liền kề cửa sổ, được
gọi là a, dựa trên sự xuất hiện ngoài cùng bên phải của ký tự này. Tuy nhiên, brBc
tính toán giá trị dịch chuyển dựa trên sự xuất hiện của 2 ký tự liên tiếp ngoài cùng
bên phải, được gọi là ab, tại đó b là ký tự kế tiếp a trong mẫu, ngoài cửa sổ. Xác
xuất xuất hiện của ab ngoài cùng bên phải trong mẫu nhỏ hơn xác xuất xuất hiện
của a. Do đó, brBc thường cung cấp sự dịch chuyển tốt hơn so với qsBc. Giá trị brBc ≥ 1, do đó nó độc lập thực hiện thuật toán nhanh, trong khi đó một
số trường hợp giá trị bmBc ≤ 0 yêu cầu sử dụng bmGs (phép dịch chuyển khớp
Boyer-Moore) để tính toán bước nhảy của cửa sổ. Giai đoạn tìm kiếm: Giai đoạn 1 và 2 giải quyết trật tự các so sánh ký tự giữa cửa sổ và mẫu. 21 Giai đoạn 1: Giai đoạn tìm kiếm bắt đầu với việc so sánh ký tự cuối cùng
của mẫu với ký tự cuối cùng của cửa sổ. Nếu có đối sánh, ký tự đầu tiên của mẫu sẽ
được so sánh với ký tự đầu tiên của cửa sổ. Nếu tất cả ký tự này đối sánh, thuật toán
di chuyển tới bước tiếp theo, bỏ qua giai đoạn 2 và đến giai đoạn 3. Giai đoạn 2: Trong bước này, so sánh tuần tự thực hiện từ ký tự thứ nhất đến
thứ hai cho đến khi nào đối sánh hoàn thành hoặc lỗi đối sánh xảy ra. Nếu toàn bộ
ký tự đối sánh, vị trí tương ứng của cửa sổ trên văn bản được hiển thị và thuật toán
bước vào giai đoạn thứ 3. Trong trường hợp có lỗi đối sánh, thuật toán sẽ chuyển tới
bước tiếp theo. Giai đoạn 3: Đây là bước bao gồm việc phục hồi giá trị dịch chuyển tương
ứng với 2 ký tự (đặt ngay sau cửa sổ) từ mảng một chiều đã được tạo ra trong suốt
giai đoạn tiền xử lý. Cửa sổ được dịch chuyển từ trái sang phải dựa trên giá trị dịch
chuyển này. Tất cả 3 bước này trong giai đoạn tìm kiếm được lặp lại cho tới khi cửa sổ đạt được vị trí ngoài n-m+1. Phân tích thuật toán: Trong giai đoạn tiền xử lý độ phức tạp thời gian của thuật toán là O(+k*) và độ phức tạp không gian là O(+k*). Trường hợp tốt nhất xảy ra khi tất cả các ký tự trong mẫu hoàn toàn khác so
với ký tự trong văn bản, giá trị dịch chuyển brBc là (m+2). Do vậy độ phức tạp thời
gian là O([n/(m+2)]). Trường hợp xấu nhất xảy ra khi tất cả các ký tự được đối sánh trong mỗi lần
thử. Tất cả ký tự của văn bản được đối sánh không nhiều hơn m lần, tổng số so sánh
ký tự cho n ký tự của văn bản không vượt quá m(n-m+1). Do đó, độ phức tạp thời
gian là O(m(n–m+1)). 2.3.3. Ví dụ Cho văn bản T có độ dài n và mẫu P có độ dài m. Trong đó: T =ATCTAACATCATAACCCTAATTGGCAGAGAGAGAATCAATCGAATCA P = GCAGAGAG n = 47, m = 8 Giai đoạn tiền xử lý: Hàm brBc đưa ra các giá trị dịch chuyển cho = 4 được chỉ ra
trong bảng 2.1: Bảng 2.1. Các giá trị dịch chuyển cho = 4 được đưa ra bởi hàm brBc 22 C brBC A G T * 10 A 10 2 10 10 10 C 7 9 10 10 1 G 1 1 1 1 10 T 10 9 10 10 10 * 10 9 10 10 Giá trị dịch chuyển được lưu trong mảng một chiều ở vị trí của hàng 2 chiều
được tính toán sử dụng hàm brBc. Hàm được sử dụng để tính toán chỉ số của mảng
là [F(a, b) = ((a<< 5) ^ b)] . AA AG GAGTTC 2145 …. 2151 …. 2209 …. 2228 …. 2755 …. … ….. 10 2 1 1 10 Giai đoạn tìm kiếm-Thử nghiệm đầu tiên: ATCTAACATCATAACCCTAATTGGCAGAGAGAGAATCAATCGAATCA 1 GCAGAGAG Shift=brBc[T][C] = 10. Trong lần thử đầu tiên, các ký tự cuối cùng của mẫu và cửa sổ được so sánh.
Khi có một lỗi đối sánh, cửa sổ được dịch chuyển dựa trên giá trị dịch chuyển brBc
tương ứng với (T,C), bằng 10. Lần thử thứ hai: ATCTAACATCATAACCCTAATTGGCAGAGAGAGAATCAATCGAATCA 1 GCAGAGAG shift = brBc[A][A] = 10. 23 Một lần nữa, so sánh các ký tự cuối cùng của mẫu và mẫu dẫn tới một lỗi đối sánh, do đó cửa sổ được dịch chuyển tới 10. Lần thứ thứ ba: ATCTAACATCATAACCCTAATTGGCAGAGAGAGAATCAATCGAATCA 1 GCAGAGAG shift = brBc[G][A] = 1. Lần này, lối đối sánh cũng xảy ra giữa các ký tự cuối cùng của mẫu và cửa sổ. Do đó, cửa sổ được dịch chuyển bằng 1. Lần thứ tư: ATCTAACATCATAACCCTAATTGGCAGAGAGAGAATCAATCGAATCA 2 1 GCAGAGAG shift = brBc[A][G] = 2. Lần này so sánh các ký tự cuối cùng của mẫu và cửa sổ được thực hiện đối
sánh. Do đó, ký tự đầu tiên của mẫu và cửa sổ được so sánh nhưng diễn ra lỗi đối
sánh, cửa sổ được dịch chuyển bằng 2. Lần thứ năm: ATCTAACATCATAACCCTAATTGGCAGAGAGAGAATCAATCGAATCA 2 8 7 6 5 43 1 GCAGAGAG shift = brBc[A][G] = 2 Trong trường hợp này, mẫu đưa ra hoàn toàn đối sánh với cửa sổ và so sánh
được thực hiện theo: Thứ nhất, các ký tự cuối cùng của mẫu và cửa sổ được so sánh,
sau đó đến ký tự đầu tiên và tiếp theo từ phải sang trái. Sau đó cửa sổ di chuyển dựa
trên giá trị dịch chuyển của (y[j + m], y[j + m + 1]), có giá trị bằng 2. Lần thứ sáu: ATCTAACATCATAACCCTAATTGGCAGAGAGAGAATCAATCGAATCA 2 1 GCAGAGAG 24 shift = brBc[A][A] = 10 Một lần nữa, so sánh các ký tự cuối cùng của mẫu và cửa sổ dẫn tới lỗi đối sánh, do vậy cửa sổ dịch chuyển với giá trị 10. Lần thứ bẩy: ATCTAACATCATAACCCTAATTGGCAGAGAGAGAATCAATCGAATCA 1 GCAGAGAG Tổng số thực hiện thử nghiệm: 7 Tổng số so sánh ký tự: 16 Như chỉ ra ở trên, so sánh của các ký tự cuối cùng của mẫu và cửa sổ bị lỗi.
Giá trị dịch chuyển được tính toán nhưng cửa sổ không dịch chuyển vì nó đã ra
ngoài cùng bên phải của văn bản. Số lần thử nghiệm và so sánh ký tự tương ứng trong suốt giai đoạn tìm kiếm
đối với SSABS. Các giá trị được thực hiện bởi thuật toán TVSBS cho thấy hiệu quả
của phương pháp luận đã được triển khai. 2.4. Thuật toán Faster Quick Search 2.4.1. Giới thiệu Thuật toán Faster Quick Search (FQS) do Jie Lin và cộng sự công bố vào
năm 2014 [3]. Thuật toán FQS là một thuật toán cải tiến dựa trên thuật toán đối
sánh mẫu chính xác QS. FQS tính toán độ dài dịch chuyển dự kiến, cho phép các
dịch chuyển tối đa và một số lượng so sánh nhỏ hơn giữa mẫu và văn bản. FQS
cũng sử dụng bảng dịch chuyển xuất hiện của thuật toán QS trong giai đoạn tiền xử
lý mẫu. 2.4.2. Thuật toán Giai đoạn tiền xử lý Trong giai đoạn tiền xử lý, FQS cần xác định 3 yếu tố: - Vị trí dịch chuyển tối đa dự kiến (pos) cho mẫu P bằng Biểu thức pos=min(k│ESk=max(ESj), 0≤ j ≤ m- 1) (2.2) - Bảng dịch chuyển cho mẫu P sử dụng thuật toán QS. 25 - Bảng dịch chuyển cho P[0,…,pos – 1], tiền tố của P, sử dụng thuật toán QS. Vị trí
dịch chuyển dự kiến tối đa pos sử dụng quy tắc dịch chuyển xuất hiện, pos được
tính toán từ mẫu P trong giai đoạn tiền xử lý. Tính toán trong mảng ES: Trong tính toán đơn giản, ESj = Pc ( j – prepos( c)) cho ký tự c, c ϵ ∑ số
phức hợp thời gian cho tính toán tất cả ESj, nơi đó 0 ≤ j ≤ m -1, là O(m││). ESj có
thể được tính toán từ ESj-1 khi j > 0. Điều đó có nghĩa rằng, giá trị bước nhảy dự
kiến ở vị trí hiện tại có thể được tính toán bằng cách sử dụng giá trị bước nhảy dự
kiến đã biết ở vị trí trước. Sự khác nhau giữa ESj và ESj-1 là: ESj– ESj – 1 = Σc(j – preposj(c)) – Σc( j – 1–preposj -1(c)) (2.3) =Σc(j – preposj(c)) – ( j – 1–preposj -1(c))) = Σc(1 – (preposj(c) –preposj -1(c))) = Σc(1) – Σc(preposj(c) –preposj -1(c))) Since Σc(1)= |Σ|, then ESj– ESj – 1= |Σ| - Σc(preposj(c) –preposj -1(c)) Với mỗi c ∑ và c ≠ P[j], preposj – 1 = preposj (c)). Các ký hiệu trong
mẫu P, ESj đều có preposj(c) = preposj-1(c) chỉ trừ một ký hiệu ở vị trí hiện tại là j.
Nói cách khác, trừ ký hiệu hiện tại trong mẫu P, tất cả các ký hiệu khác trong Σ sẽ
có preposj(c) = preposj-1(c). Sự khác nhau giữa ESj và Esj - 1 được phân tích như
sau: ESj– ESj – 1 = |Σ| - Σc(preposj(c) –preposj -1(c)) = |Σ| - preposj(P[j]) –preposj -1(P[j])) (2.3) = |Σ| - (j–preposj -1(P[j])) Ta có: ESj= ESj – 1 + |Σ| - (j–preposj -1(P[j])) (2.4) Giai đoạn tiền xử lý của thuật toán Sử dụng một hàng Prepos với độ dài |Σ|, để giữ vị trí trước đó cho mỗi ký tự
c, tại đó c ∑ . Theo phân tích ở trên, các tác giả có thể có ESj từ ESj = ESj-1 + |Σ| -
(j − preposj− 1(P[j])), tại đó m-1 ≥ j ≥ 1. Phép tính có thể được thực hiện trong thời
gian liên tục cho mỗi vị trí được đưa ra j. 26 Từ tính toán về vị trí dịch chuyển tối đa dự kiến (pos), ta biết được độ phức
tạp thời gian là Θ(m + |Σ|). Thời gian cần thiết dự kiến là Θ(pos + |Σ|) và độ phức
tạp thời gian giai đoạn tiền xử lý tổng thể cho FQS là Θ(m + |Σ|) khi pos < m. 2.4.2.2. Giai đoạn tìm kiếm Trong giai đoạn tìm kiếm, FQS bắt đầu so sánh vị trí trong mẫu P, có giá trị
dịch chuyển tối đa dự kiến, chứ không phải vị trí ngoài cùng bên phải trong P như
trong QS (và các biến thể BM khác). Sau bước tiền xử lý, chiến lược tìm kiếm FQS như sau: Bước 1: Kiểm tra các ký tự ở vị trí dịch chuyển tối đa dự kiến pos, đó là vị trí so sánh các biểu tượng P[pos] và T[j+pos]; Bước 2: Nếu có một lỗi đối sánh, dịch chuyển mẫu P dựa trên khoảng cách được xác định bằng next[T[j+pos]]. Đi tới bước 1 để tiếp tục kiểm tra vị trí pos; Bước 3: Nếu không thì tiến hành so sánh P[0,…,m-1] với T[j,…,j+m-1] theo
cách như trong thuật toán QS. Nếu tất cả đều đối sánh, một mẫu đối sánh sẽ được
tìm thấy tại vị trí j trong T; Bước 4: Dù tất cả đều đối sánh hay không, dịch chuyển mẫu sang bên phải dựa trên giá trị của shift[T[j+m]] bằng việc sử dụng thuật toán QS cổ điển. Bước 5: Lặp lại các bước từ 1-4 ở trên trong vòng lặp cho tới khi văn bản T bị trống (j>n-m). 2.4.2.3. Phân tích thuật toán Tính chính xác của thuật toán FQS : Kế thừa chủ yếu từ tính chính xác của
thuật toán QS. Trong giai đoạn tìm kiếm, FQS sử dụng 2 hàng dịch chuyển ký tự
xuất hiện trong 2 bước, khi so sánh mẫu P với văn bản T, FQS trước tiên kiểm tra vị
trí pos trong P, vị trí dịch chuyển tối đa dự kiến so sánh nó với vị trí j + pos trong T.
Nếu có một lỗi đối sánh, nó sử dụng hàng dịch chuyển next, để dịch chuyển mẫu tới
vị trí bên phải kế tiếp. Giá trị dịch chuyển ở hầu hết pos + 1. Nó sẽ không bỏ qua bất
kỳ vị trí đối sánh quan trọng nào. Sau mỗi so sánh biểu tượng đầu tiên (P[pos] vàT[j
+ pos]), các bước còn lại được thực hiện tương tự như trong thuật toán QS. Độ phức tạp của thuật toán : Trong giai đoạn tìm kiếm, thuật toán FQS tích
hợp một bước tiền xử lý với thuật toán QS. Độ phức tạp thời gian của bước này
vẫn liên tục và tổng phức tạp thời gian là O(n). Độ phức tạp thời gian trong trường
hợp xấu nhất đối với giai đoạn tìm kiếm trong FQS là O(mn) và độ phức tạp thời
gian trung bình là O(n). Không gian mở rộng được yêu cầu bởi FQS là trong
O(|Σ|). Thuật toán FQS có yêu cầu thời gian và không gian trong trường hợp xấu 27 nhất và trung bình tương tự như QS. Cũng như với thuật toán BM thông thường,
độ phức tạp trong trường hợp xấu nhất có thể được cải thiện O(n + m + |Σ|) bằng
sử dụng phương pháp thử nghiệm dịch chuyển khớp đã ghi nhớ. 2.4.2.4. Thực hiện Thuật toán 1: Giai đoạn tiền xử lý (Có giá trị dịch chuyển dự kiến tối đa) GETPOS(P, m, |Σ|)
1 ES ← 0, maxES ← 0, pos ← 0
2 for (i ← 0 to |Σ| − 1) do
3 PrePos[i] ← −1 /*initializing all of prepos*/
4 end for
5 for (j ← 0 to m − 1) do
6 ES ← ES + |Σ| − (j − PrePos[P[j]]);
7 PrePos[P[j]] ← j;
8 if ES ≥ maxES then
9 maxES ← ES;
10 pos ← j;
11 end if
12 end for
13 return pos Thuật toán 1 cho thấy các bước chi tiết của giai đoạn tiền xử lý để tính toán
vị trí dịch chuyển tối đa (pos) cho mẫu P[0,…, m-1] sử dụng Biểu thức (2.1). Trong
đó, biến ES là giá trị dịch chuyển dự kiến, được khởi tạo bằng 0. Trong bước đầu
tiên của vòng lặp trong Dòng 5-12, ES0 sẽ được thiết lập bằng |Σ| − 1. Biến maxES
là giá trị dịch chuyển tối đa dự kiến. Đồng thời, pos, một vị trí trong mẫu P, là vị trí
ở nơi mà giá trị dịch chuyển tối đa dự kiến nằm ở trong mẫu P. Thuật toán 2: Giai đoạn tìm kiếm (Thuật toán FQS(P, m, T, n, |Σ|)
1 pos ← GetPos (P,m,|Σ|)
2 next ← preQS(P,pos)
3 shift ← preQS(P,m)
4 j ← 0
5 while (j ≤ n − m)
6 while (P[pos] = T[j+pos])
7 j ← j + next[T[j + pos]]
8 ifj > n − m then do
9 return
10 end if 28 11 end while
12 Compare P[0, ..., m − 1] and T[j, ..., j + m − 1]
13 if all matched then do
14 output j
15 end if
16 j ← j + shift[T[j + m]]
17 end while Dòng 1 gọi Thuật toán 1 để có được vị trí pos với giá trị dịch chuyển dự kiến
tối đa. Các Dòng 2 và 3 tính toán 2 bảng dịch chuyển (gọi là next và shift) cho tiền
tố P[0,…,pos-1] và toàn bộ mẫu P, trong giai đoạn tiền xử lý FQS còn thêm vào 2
dòng: Dòng 1 và Dòng 2. Tổng phức hợp thời gian của 3 bước vẫn là O(m + |Σ|). FQS quyết định vị trí dịch chuyển dự kiến tối đa. Vị trí này có một khoảng
cách dịch chuyển thống kê tối đa. Một khi có lỗi đối sánh được tìm thấy, thuật toán
nhảy đến vị trí mới, có khoảng cách dịch chuyển dự kiến tối đa. Cơ chế này tăng tốc
đáng kể cho thuật toán FQS. Dòng 2-4 khởi tạo giá trị của mỗi biểu tượng bằng “-1” cho hàng vị trí mới xuất hiện PrePos bằng biểu thức: (2.5) ESj = c (j - preposj (c)), 0 j m-1, c Còn các Dòng từ 5-12 là vòng lặp for tính toán giá trị dịch chuyển dự kiến
của mỗi vị trí là ES và quyết định giá trị dịch chuyển tối đa dự kiến. Dòng 6 tính
toán giá trị dịch chuyển dự kiến ES bằng việc sử dụng phương pháp tịnh tiến, như
đã được thảo luận ở trên (Biểu thức (2.3)). Trong Thuật toán 2, các dòng từ 5-17 bắt vào giai đoạn tìm kiếm. So với
thuật toán QS, FQS thêm các Dòng từ 6-11 trong giai đoạn tìm kiếm. Trong giai
đoạn này, ban đầu, văn bản T được sắp xếp với mẫu P, ở các vị trí T[j] và P[0], tại
đó 0 ≤ j ≤ n – m. FQS trước tiên sẽ bắt đầu so sánh vị trí giá trị dịch chuyển dự kiến
tối đa, pos trong P, với vị trí tương ứng j + pos trong T. Nếu lỗi đối sánh xảy ra,
mẫu được dịch chuyển tới 1 vị trí được xác định bằng giá trị next[T[j + pos]]. Các
bước này được thực hiện trong các Dòng 6-11. Nếu không thì, thuật toán FQS làm
việc tương tự như thuật toán QS bằng việc bắt đầu so sánh mẫu P[0,…,m-1] và
T[j,…,j + m-1] từ phải sang trái. Các dòng từ 9-12 tìm kiếm giá trị dịch chuyển tối đa dự kiến maxES. Cuối
cùng thuật toán trở về vị trí dịch chuyển tối đa dự kiến pos, trong Dòng 13. Quy
trình tiền xử lý này chỉ thực hiện một lần cho mẫu P với thời gian O(m + |Σ|). 29 2.4.3. Ví dụ Cho văn bản T = “GCATCGCAGTCAG TATACAGTAC” (n = 23) và mẫu
P = “GCAGTCAG” (m = 8). Văn bản và mẫu là các trình tự DNA từ bảng chữ Σ =
{A, C, G, T}, do vậy |Σ| = 4. Tính toán vị trí dịch chuyển dự kiến tối đa (pos) cho mẫu P Để tính toán giá trị dịch chuyển dự kiến tối đa của mẫu P = “GCAGTCAG”,
trong Dòng 3 của Thuật toán 3, vị trí xuất hiện tại hàng PrePos trong Thuật toán 3
cho 4 biểu tượng này được khởi tạo bằng “1”. Sau đó, Thuật toán 3 tính toán pos
cho mẫu P, bằng cách quét từ trái sang phải. Khi ký tự đầu tiên P[0] = G được đọc (j = 0), PrePos[G] có giá trị khởi tạo “-
1”. Dòng 6 thiết lập ES = 0 + 4 -(0 -(-1)1) = 3. ES = 3 là khoảng cách dịch chuyển
dự kiến cho Vị trí 0 trong mẫu P. Trong Dòng 7, PrePos[G] được thiết lập tới vị trí
hiện tại 0; điều này chỉ ra rằng ký tự G xuất hiện ít nhất 1 lần tại thời điểm này.
Trong các Dòng 8-10, khoảng cách dịch chuyển tối đa dự kiến đã thiết lập bằng
maxES = 3. Khi ký tự thứ hai P[1] = C được đọc (j = 1), Dòng 6 thiết lập ES = 3 + 4-(1-
(-1)) = 5. Trong Dòng 7, PrePos[C] được thiết lập vị trí hiện tại của nó là 1. Trong
Dòng 9, khoảng cách dịch chuyển tối đa dự kiến được thiết lập là 5. Khi ký tự thứ ba P[2] = A được đọc (j = 2), Dòng 6 sẽ thiết lập ES = 5 + 4 -
(2 -(-1)) = 6. Trong Dòng 7, PrePos[A] được thiết lập vị trí hiện tại là 2. Trong
Dòng 9, khoảng cách dịch chuyển tối đa dự kiến được thiết lập là 6. Khi ký tự thứ tư P[3] = G được đọc (j = 3), giá trị PrePos[G] được thay đổi
tới vị trí xuất hiện trước đó; trong trường hợp này, PrePos[G] = 0. Dòng 6 sẽ thiết
lập ES = 6 + 4 -(3 -(0)) = 7. Trong Dòng 7, PrePos[G] được thiết lập vị trí hiện tại
là 3. Trong Dòng 9, khoảng cách dịch chuyển tối đa dự kiến được thiết lập là 7. 30 Bảng 2.2. Các hàng ES, next và shift cho một mẫu ví dụ j 0 1 2 4 5 6 7 3 P[j] G C A T C A G G 3 5 6 6 6 6 6 7 ESj Σ A C G T Next 1 2 3 4 Σ A C G T Shift 2 3 1 4 Các ký tự còn lại trong mẫu P được xử lý theo cùng một cách giống nhau.
Các khoảng cách dịch chuyển dự kiến cuối cùng cho mỗi vị trí trong mẫu P[0,…,m-
1] là 3, 5, 6, 7, 6, 6, 6, 6. Vị trí dịch chuyển dự kiến tối đa trong P[3] = G, có giá trị
bằng 7. Do đó, các tác giả có khoảng cách dịch chuyển tối đa dự kiến trong Vị trí 3
của mẫu P, đó là, pos = 3 (xem Bảng 2.2). Tính toán các Bảng dịch chuyển: next và shift Các tác giả tính toán bảng dịch chuyển cho mẫu tiền tố P[0,…,pos – 1] =
P[0,…,2] = “GCA”, được biểu thị là next với giá trị của next (A, C, G, T) = [1, 2, 3,
4]. Đồng thời, bảng dịch chuyển cho mẫu P[0,…,m-1] = P[0…7] được biểu thị bằng
hàng shift, trong đó shift(A,C, G, T) = [2,3,1,4]. Cả hàng next và shift đều được tính
toán bằng thuật toán QS cổ điển; Tìm kiếm mẫu P trong T Sau các bước tiền xử lý, giai đoạn tìm kiếm bắt đầu: Thử nghiệm thứ nhất: Thử nghiệm đầu tiên này so sánh mẫu P với văn bản T từ
khởi đầu. x Next[A,C,G,T] = {1,2,3,4} G C A T C G C A G T C A G T A T A C A G T A C G C A G T C A G Do vị trí dịch chuyển tối đa dự kiến bằng 3 (pos = 3), cho nên so sánh bắt
đầu ở P[3] =G đối với vị trí tương ứng trong văn bản T[j + pos] = T[0 + 3] = T[3].
Đó sẽ là biểu tượng ‘T’, do vậy dẫn đến một lỗi đối sánh. Thuật toán dịch chuyển 31 mẫu P tới vị trí kế tiếp với khoảng cách dịch chuyển được xác định bằng next
[T[3]] = next[T] = 4. Đồng thời giá trị j được cập nhật là j = j + next[T[3]] = 4. Thử nghiệm thứ hai: Thuật toán vẫn bắt đầu so sánh P[3] = G với vị trí tương ứng
trong văn bản T[j +pos] = T[4+3] = T[7] = A. Nhưng vẫn diễn ra một lỗi đối sánh.
Khoảng cách dịch chuyển là next[T[7]] = next[A] = 1. Giá trị của j được cập nhật là j = j + next[T[7]] = 4 + 1 = 5. x Next[A,C,G,T] = {1,2,3,4} G C A T C G C A G T C A G T A T A C A G T A C G C A G T C A G Thử nghiệm thứ ba: Thuật toán so sánh P[3] = G với văn bản T[j + pos] = T[5 + 3] =
T[8] = G các ký tự đối sánh. Tiếp theo Thuật toán tiến hành như thuật toán QS cổ
điển. Sau mỗi lần so sánh, thuật tìm thấy một đối sánh chính xác. Nó cho biết vị trí
xảy ra và xác định khoảng cách dịch chuyển là j. Khoảng cách dịch chuyển này
được xác định bằng thuật toán QS cổ điển. j = j + shift[T[j + m]] = 5 + shift[T[5 + 8]] = 5 + shift[T[13]] = 5 + shift[T]=5 + 4= 9 x shift[A,C,G,T] = {2,3,1,4} G C A T C G C A G T C A G T A T A C A G T A C G C A G T C A G Thử nghiệm thứ bốn: Thuật toán FQS so sánh P[3] = G văn bản T[j + pos] = T[9 +
3] = G. Khi các biểu tượng đối sánh, thuật toán theo các bước của thuật toán QS cổ
điển bằng việc so sánh từ phải sang trái. Ký tự ngoài cùng bên phải của mẫu là G
không đối sánh với biểu tượng tương ứng là A trong T. Thuật toán xác định khoảng
cách dịch chuyển kế tiếp shift[T[j + m]] = shift[T[9 + 8]] = shift[C] = 3, và giá trị
của j được cập nhật là j = j + shift[T[j + m]] = 9 + shift[T[9 + 8]] = 9 + shift[T[17]]
= 9 + shift[C] = 9 + 3 = 12. shift[A,C,G,T] = {2,3,1,4} x G C A T C G C A G T C A G T A T A C A G T A C G C A G T C A G Thử nghiệm thứ năm: 32 Thuật toán so sánh P[3] = G với vị trí tương ứng trong văn bản T[j + pos] =
T[12 + 3] = T[15] = T. Xảy ra lỗi đối sánh. Khoảng cách dịch chuyển được xác định
bằng giá trị dịch chuyền FQS next[T[15]] = 4, và giá trị của j được cập nhật là j = j
+ next[T[15]] = 12 + 4 = 16. Đối với n = 23; m = 8, khi j = 16 > n -m = 15, văn bản
T bị rỗng. Giai đoạn tìm kiếm dừng lại. next[A,C,G,T] ={1,2,3,4} x G C A T C G C A G T C A G T A T A C A G T A C G C A G T C A G Vậy số lần thử nghiệm là: 5 Tổng số ký tự được so sánh là: 13. 2.5. Kết luận chương 2 Chương 2 trình bày một họ thuật toán sánh mẫu chính xác nhanh SSABS
(Sheik- Sumit- Anindya- Balakrishnan-Seka) - TVSBS (Thathoo- Virmani- Sai-
Balakrishnan- Sekar) – FQS (faster quick search). Đây là một nhóm thuật toán biến
thể của thuật toán Quick Search được kiểm định là có lợi thế khi mẫu ngắn với bảng
chữ nhỏ hoặc mẫu dài với bảng chữ lớn với đại diện là thuật toán TVSBS. 33 3.1. Giới thiệu Bài toán đặt ra trong chương trình thực nghiệm là bài toán sánh mẫu ngoại
tuyến (offline pattern matching) trong đó cả mẫu P và văn bản T đã có sẵn. Một
trường hợp đặc biệt chính là cả mẫu P và văn bản T đã có trong bộ nhớ. Trong sánh
mẫu ngoại tuyến, việc tiền xử lý dữ liệu đối với P và T có thể được tiến hành từ
trước để tạo điều kiện tạo nên các cơ chế phù hợp (bao gồm các cấu trúc dữ liệu bổ
sung thích hợp) để tăng tốc độ quá trình sánh mẫu. Thông tin cơ bản như độ dài của
P và T được coi như một thông tin tiên liệu về quá trình sánh mẫu. Luận văn lựa
chọn bộ công cụ SMART để tiến hành thực nghiệm hai thuật toán sánh mẫu SSABS
và TVSBS. Để thuận tiện cho việc thực hiện bài toán sánh mẫu ngoại tuyến, chương
trình đăng nhập qua bộ trung gian PUTTY. 3.2. Bộ công cụ Smart SMART (String Matching Algorithms Research Tool: công cụ nghiên cứu
các thuật thoán sánh xâu) do Thierry Lecroq [10] và Simone Faro [10] xây dựng
nhằm cung cấp một khung chuẩn cho các nhà nghiên cứu về sánh xâu. Bộ công cụ
giúp người sử dụng kiểm tra, thiết kế, đánh giá và hiểu biết các giải pháp hiện có
đối với bài toán sánh xâu. Hơn nữa, nó cung cấp một bộ công cụ cho việc triển khai
hầu hết các thuật toán sánh xâu và một kho ngữ liệu rộng của các bộ đệm văn bản. Bộ công cụ phiên bản 13.2 (tháng 6/2015) chứa tập thi hành 86 thuật toán
sánh mẫu chính xác và một kho ngữ liệu ví dụ kiểm tra với 12 bộ dữ liệu. Theo
Thierry Lecroq và Simone Faro, tập 86 thuật toán sánh mẫu được đưa vào bộ công
cụ SMART đã được đề xuất và khảo sát trong 65 bài báo được công bố từ năm 1977
tới năm 2013.[11] Các thành phần chính trong bộ công cụ SMART bao gồm: (i) Một bộ thi hành 86 thuật toán sánh xâu chính xác (tính tới tháng 6/2015), (ii) Một bộ 12 kho ngữ liệu để thử nghiệm, (iii) Các tài liệu hướng dẫn SMART. 3.2.1. Các thành phần chính trong bộ công cụ SMART 3.2.1.1. Bộ thi hành các thuật toán sánh xâu chính xác 34 Từ năm 1970 đến nay, đã có trên 80 thuật toán sánh xâu được đề xuất, chủ
yếu là trong khoảng 10 năm gần đây. Công cụ SMART cung cấp một tập các thuật
toán sánh xâu thông minh dựa trên ngôn ngữ lập trình C, giúp người tìm kiếm có
thể biểu diễn các kết quả thử nghiệm và so sánh chúng trên thực nghiệm. SMART
cũng cung cấp một cơ sở thực hành chuẩn cho việc thử nghiệm các thuật toán sánh
xâu và chia sẻ kết quả với cộng đồng. Bảng 3.1 giới thiệu danh sách các thuật toán sánh xâu từ năm 1970 được cài
đặt trong công cụ SMART, mỗi thuật toán đều được bổ sung phiên bản đầy đủ trong
SMART. Để thử nghiệm phiên bản đã được thi hành trong SMART ta chỉ cần lựa
chọn tên phiên bản. Ví dụ, có thể sử dụng lệnh ./select bf để lựa chọn thuật toán
Brute Force. Từ đường link tên thuật toán, ta có thể tìm thấy trang thông tin chi tiết
và sơ đồ dẫn đến thư mục đó. Từ đường link tên phiên bản, ta có thể tìm thấy trang
mã hóa (code) của thuật toán viết trên C. Bảng 3.1.Danh sách tất cả các thuật toán sánh xâu từ năm 1970 trên SMART Tên gọi Thuật toán Năm
công bố trong SMART Brute Force bf 1990 Deterministic Finite Automaton aut 1990 Morris Pratt mp 1970 Knuth Morris-Pratt kmp 1977 Boyer Moore bm 1977 Horspool hor 1980 Apostolico Giancarlo ag 1986 Karp Rabin kr 1987 Zhu Takaoka zt 1987 Optimal Mismatch om 1990 Maximal Shift ms 1990 35 Quick Search qs 1990 Apostolico Crochemore ac 1991 Two Way tw 1991 Tuned Boyer Moore tunedbm 1991 Colussi col 1991 Smith smith 1991 Galil Giancarlo gg 1992 Raita raita 1992 String Matching on Ordered ALphabet smoa 1992 Reverse Factor rf 1992 Shift Or so 1992 Shift And sa 1992 Not So Naive nsn 1993 Simon simon 1993 Turbo Boyer Moore tbm 1994 Reverse Colussi rcol 1994 Turbo Reverse Factor trf 1994 Forward DAWG Matching fdm 1994 Backward DAWG Matching bdm 1994 Skip Search skip 1998 Alpha Skip Search askip 1998 36 KMP Skip Search kmpskip 1998 Backward Nondeterministic DAWG Matching bndml 1998 Berry Ravindran br 1999 Backward Oracle Matching bom 1999 Double Forward DAWG Matching dfdm 2000 Ahmed Kaykobad Chowdhury akc 2003 Fast Search fs 2003 2003 sbndm Simplified Backward Nondeterministic DAWG
Matching Two-Way Nondeterministic DAWG Matching tndm 2003 2003 lbndm Backward Nondeterministic DAWG Matching for
long patterns Shift Vector Matching svm0 2003 Forward Fast Search ffs 2004 Backward Fast Search, Fast Boyer Moore bfs 2004 Tailed Substring ts 2004 SSABS ssabs 2004 Wide Window ww 2005 Linear DAWG Matching ldm 2005 2005 bndmq2 Backward Nondeterministic DAWG Matching
with loop unrolling Simplified BNDM with loop unrolling sbndm2 2005 37 2005 sbndm-bmh Backward Nondeterministic DAWG Matching
with Horspool Shift Horspool with BNDM test bmh-sbndm 2005 Forward Nondeterministic DAWG Matching fndm 2005 Bitparallel Wide Window bww 2005 Fast Average Optimal Shift Or faoso2 2005 Average Optimal Shift Or aoso2 2005 TVSBS tvsbs 2006 Boyer Moore Horspoolusing Probabilities pbmh 2006 Improved Linear DAWG Matching ildm1 2006 Improved Linear DAWG Matching 2 ildm2 2006 Franek Jennings Smyth fjs 2007 Wu Manber for Single Pattern Matching hash3 2007 Two Sliding Window tsw 2008 Bit Parallel Length Invariant Matcher blim 2008 Genomic Rapid Algofor String Pattern Matching graspm 2009 SSEF ssef 2009 Extended Backward Oracle Matching ebom 2009 Forward Backward Oracle Matching fbom 2009 Simplified Extended Backward Oracle Matching sebom 2009 Simplified Forward Backward Oracle Matching sfbom 2009 Succint Backward DAWG Matching sbdm 2009 38 2009 fsbndm Forward Simplified Backward Nondeterministic
DAWG Matching 2009 bndmq2 Backward Nondeterministic DAWG Matching
with q-grams 2009 sbndmq2 Simplified Backward Nondeterministic DAWG
Matching with q-grams Shift Or with q-grams ufndmq2 2009 Small Alphabet Bit Parallel sabp 2009 Bit Parallel2 Wide Window bp2ww 2010 Bit Parallel Wide Window2 bpww2 2010 2010 kbndm Factorized Backward Nondeterministic DAWG
Matching Factorized Shift And ksa 2010 BNDM with Extended Shift bxs 2010 2011 fsbndm20 Forward Simplified BNDM using q-grams and s-
forward characters algorithm using SSE 2011 ssecp Crochemore-Perrin
instructions Backward SNR DAWG Matching bsdm 2012 Exact Packed String Matching algorithm epsm 2013 Theo Thierry Lecroq và Simone Faro, hai thuật toán Brute Force và
Deterministic Finite Automaton được Thomas H. Cormen, Charles E. Leiserson,
Ronald L. Rivest, Clifford Stein giới thiệu. 3.2.1.2. Bộ các kho ngữ liệu thử nghiệm Công cụ SMART cũng cung cấp một ngữ liệu 12 văn bản mà trên đó các
thuật toán đối sánh xâu có thể được kiểm tra. Các văn bản trong dữ liệu có rất nhiều 39 loại khác nhau, bao gồm các văn bản ngôn ngữ tự nhiên, trình tự gene, trình tự
protein và văn bản ngẫu nhiên với sự phân bố đồng đều các kí tự. Công cụ SMART cũng cung cấp một ngữ liệu 12 văn bản mà trên đó các
thuật toán đối sánh xâu có thể được kiểm tra. Các văn bản trong dữ liệu có rất nhiều
loại khác nhau, bao gồm các văn bản ngôn ngữ tự nhiên, trình tự gene, trình tự
protein và văn bản ngẫu nhiên với sự phân bố đồng đều các kí tự. Bảng 3.2. Danh sách bộ các kho ngữ liệu thử nghiệm Tên bộ dữ liệu Mô tả englishTexts một văn bản tiếng Anh (6,1 MB) chứa phiên bản The King
James của Kinh thánh (3,9 MB) và cuốn sách về thế giới thực
của CIA (2,4 MB). italianTexts một văn bản tiếng Ý (5 MB) chứa cuốn sách La Gerusalemme
Liberata (690,1 KB), Il fu Mattia Pascal (447,3 KB), La divina
commedia (551,9 KB) I promessi sposi (1,3 MB), Orlando
furioso (1,5 MB), Ultime lettere di Jacopo Ortis (281,2 kB) và Il
canzoniere (296,3 kB). frenchTexts một văn bản tiếng Pháp (6,6 MB) chứa các tác phẩm của Victor
Hugo như: Notre-Dame de Paris (1,1 MB), L'homme qui rit (1,2
MB), Les misèrables Tome I (713 KB), Tome II (631 KB),
Tome III (557 KB), Tome IV (791 KB) và Tome V (676 KB). chineseTexts một văn bản tiếng Trung (5,7 MB) chứa các tác phẩm: Yue Wei
Cao Tang Bi Ji (1,2 MB), Zhong Guo Shi Da Jin Shu Zhi Guo
Shai Tian Xiang (786 KB), Journey to the West (2,3 MB), Huan
Xi Yuan Jia (745 KB) và một số tiểu thuyết lịch sử Trung Quốc
(688 KB) midimusic một xâu dữ liệu đa phương tiện MIDI (2,7 MB) chứa 206 tệp
MIDI về Johann Sebastian Bach work (1685-1750) có kích
thước dữ liệu khoảng 4 KB đến 205 KB. genome một xâu dữ liệu gen (4,4 MB) chứa các bộ gen hoàn chỉnh của
vi khuẩn E. Coli (4,4 MB). protein một xâu dữ liệu protein (3,1 MB) chứa một chuỗi protein trong
bộ chuỗi gen người (3.1 MB). 40 Các văn bản ngẫu nhiên có độ dài 5 MB trong các bảng chữ cái
tương ứng có số lượng ký tự là 2, 4, 8, 16, 32, 64, 128, 256. rand2, rand4,
rand8, rand16,
rand32, rand64,
rand128,
rand256 3.2.1.3. Tài liệu hướng dẫn về SMART Tài liệu hướng dẫn về SMART gồm hướng dẫn phân bổ bộ nhớ cho SMART
trong các hệ điều hành MAC, WINDOWS và Linux, cài đặt và sử dụng công cụ
SMART. Phần dưới đây của luận văn giới thiệu về cài đặt công cụ SMART. Cài đặt công cụ SMART: • Tải về các gói nhị phân chính xác từ các trang download, tương ứng với hệ thống của máy. Đây là một tài liệu nén có chứa mã nhị phân và dạng văn bản. • Sao chép lưu trữ và giải nén trong một thư mục địa phương. Điều này sẽ tạo thư mục mới, có tên SMART, và có chứa các tập tin và thư mục sau đây: • docs/ là thư mục chứa các tập tin tài liệu; • source/ là thư mục chứa các mã nhị phân của tất cả các thuật toán chuỗi kết hợp; • results/ là thư mục chứa các tập tin với dữ liệu thực nghiệm; • data/ là thư mục chứa ngữ liệu được sử dụng để thử nghiệm các chuỗi kết hợp các thuật toán; • copyright.txt chứa từ chối trách nhiệm về bản quyền; • gpl-3.0.txt chứa giấy phép công cộng chung GNU; • SMART là chương trình chính được sử dụng để chạy kiểm tra thử nghiệm; • test là một tiện ích thông minh được sử dụng để kiểm tra tính đúng đắn của thuật toán chuỗi kết hợp; • select là một tiện ích thông minh được sử dụng để lựa chọn / bỏ chọn các thuật toán chuỗi kết hợp. Lựa chọn thuật toán thử nghiệm Chương trình chọn có thể được sử dụng để lựa chọn hay bỏ chọn các thuật
toán cho kết quả thử nghiệm. Viết tên của thuật toán (hay một danh sách các thuật 41 toán), chỉ sau khi lệnh select, để chọn hoặc bỏ chọn nó. Ví dụ, lệnh $ ./select Bndm
fs hash3 sẽ chọn BNDM, thuật toán tìm kiếm Fast-Search và thuật toán HASH3.
Các lệnh tiếp theo $ ./select Fs sẽ bỏ chọn các thuật toán tìm kiếm Fast-Search. Tham số lệnh which thể hiện các thuật toán đã được lựa chọn cho kết quả thử nghiệm. Do đó chạy lệnh $ ./select -which sẽ đưa ra output là: bndm hash3 Tham số lệnh -Show liệt kê tên của tất cả các thuật toán có thể có trong kết
quả thử nghiệm. Hơn nữa sử dụng các tham số lệnh -none bỏ chọn tất cả các thuật
toán và -All để chọn tất cả các thuật toán. Ví dụ lệnh $ ./select -none KMP bf bỏ
chọn tất cả các thuật toán trước đó và lựa chọn thuật toán Knuth-Morris-Pratt và
Brute-Force. Tương tự ta có lệnh $ ./select -all KMP bf sẽ chọn tất cả các thuật toán
với các ngoại lệ của Knuth-Morris-Pratt và Brute-Force. Cuối cùng tham số -h sẽ cho ra một danh sách các trợ giúp. Cách chạy chương trình kiểm tra thử nghiệm Lệnh chính SMART (chương trình smart ở thư mục smart.13.02/source/)
được sử dụng để chạy kiểm tra thử nghiệm. Cách đơn giản nhất để sử dụng SMART
là để chạy một tìm kiếm duy nhất cho một mô hình tùy chỉnh và một văn bản tùy
chỉnh. Ta có thể sử dụng các tham số -simple, tiếp theo là các mô hình và các văn
bản. Ví dụ lệnh $ ./smart -simple let sampletext sẽ tìm kiếm văn bản sampletext cho
lần xuất hiện của mô hình cho phép. Quan sát thấy kích thước mô hình đầu vào
chứa 100 ký tự, trong khi kích thước văn bản chứa 1000 ký tự. Các chế độ -
simple không ra bản đồ thử nghiệm. Nếu không, ta có thể chọn các dạng đó để tính
toán các kết quả thử nghiệm bằng cách sử dụng các tham số -text (tham số này là
bắt buộc). Ví dụ lệnh $ ./smart -text englishTexts sẽ tính toán kết quả thí nghiệm
trên englishTexts. Các dữ liệu hay thư mục nằm trong thư mục chính SMART, có
chứa tất cả các tập văn bản mà có thể được chọn thông minh. Có thể xem danh sách
tất cả các tập văn bản trong SMART. Nếu không, ta có thể chọn các tham số -text
all để chạy kiểm tra thử nghiệm cho tất cả các ngữ liệu. $ ./smart -text all Ta có thể thiết lập một kích thước giới hạn trên của kích thước văn bản được
sử dụng để thử nghiệm các thuật toán chuỗi kết hợp. Theo mặc định kích thước giới
hạn trên này được thiết lập để 1MB (1024 bytes). Điều này có nghĩa rằng (ít nhất)
1024 byte đầu tiên của văn bản được chọn sẽ được sử dụng để thử nghiệm. Bạn có
thể thay đổi mặc định kích thước trên ràng buộc bằng cách sử dụng các tham số - 42 tsize, tiếp theo là một số nguyên chỉ ra Mbytes mà sẽ được sử dụng. Ví dụ lệnh $
./smart -văn Bản englishTexts -tsize 4 sẽ thực hiện các bài kiểm tra trên nhiều nhất 4
MB của corpus englishText. Các bộ đệm văn bản được lưu trữ trong bộ nhớ chia sẻ, do đó nếu thiết lập
các ràng buộc trên một K giá trị của nó là cần thiết để hệ thống của máy cho phép
phân bổ ít nhất K MB bộ nhớ chia sẻ. Theo mặc định cho mỗi tập tin đầu vào, SMART tạo ra bộ 500 mẫu có chiều
dài cố định, được triết xuất một cách ngẫu nhiên từ các văn bản (500 bản sao của
cùng một khuôn mẫu trong trường hợp chế độ Đơn giản). Chiều dài của mô hình
chạy trên các giá trị 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 và 4096. Đối với
mỗi tập các mô hình công cụ báo cáo trung bình trong thời gian chạy của 500 mẫu.
Mỗi lần chạy được thể hiện trong một số phần nghìn của giây. Sử dụng các tham số -pset để thay đổi kích thước của tập hợp các mẫu tạo ra
bởi công cụ. Ví dụ lệnh $ ./smart -texts Gen -pset 100 sẽ chạy kiểm tra thử nghiệm
trên văn bản gen tạo ra bộ 100 mẫu có chiều dài cố định (giá trị mặc định là 500). Ta có thể sử dụng các tham số Short để thực hiện các bài kiểm tra thử
nghiệm trên các mẫu ngắn. Đặc biệt các lệnh $ ./smart -texts Gen -pset 100 Short
thực hiện kiểm tra thử nghiệm bằng cách tạo ra bộ 100 mẫu có chiều dài cố định
khác nhau, trên các giá trị 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 và 32. Nếu muốn hạn chế việc tìm kiếm một mô hình chiều dài nhất định, sử dụng
các tham số -plen và xác định một ràng buộc trên và một ràng buộc thấp hơn cho độ
dài của mô hình. Ví dụ lệnh $ ./smart -texts Gen -pset 100 -plen 16 128 thực hiện
kiểm tra thử nghiệm trên độ dài các giá trị 16, 32, 64, 128. Nếu muốn thử nghiệm
các thuật toán cho một chiều dài duy nhất của mô hình (ví dụ 128) sử dụng lệnh $
./smart -texts Gen -pset 100 -plen 128 128. Trong việc thực hiện các bài kiểm tra
các công cụ in ra các lần chạy của mỗi thuật toán (đây là thiết lập mặc định). Sử
dụng các -occ tham số để in ra cũng là số lần xuất hiện tìm thấy bởi các thuật toán
trong thời gian chạy. Kể từ khi mẫu được chiết xuất một cách ngẫu nhiên từ các văn
bản, số lần xuất hiện ít nhất 1. Cuối cùng các tham số -h sẽ tạo ra một danh sách trợ giúp. Các công ty liên kết công cụ SMART cho bất kỳ thí nghiệm có một mã số và
chữ độc đáo trên 13 ký tự, bắt đầu với EXP, tiếp theo là 10 con số. Việc thực hiện
các lệnh sau đây: $ ./smart -text gen -pset 100 -occ bắt đầu thử nghiệm trên văn bản gen, sử dụng bộ 100 mẫu mô hình. 43 3.2.2. Sử dụng bộ công cụ Smart Việc thực hiện một kiểm tra thử nghiệm theo công cụ SMART sẽ lưu trữ dữ
liệu thử nghiệm trong các kết quả thư mục /EXPCODE, tại đó EXPCODE là mã
duy nhất có liên kết với kiểm tra thử nghiệm. Các file bao gồm dữ liệu thử nghiệm được đặt tên cùng với tên ngữ liệu được lựa
chọn. Hệ thống này có thể lưu dữ liệu thử nghiệm trong 3 định dạng khác nhau:
latex, xml và html. Các kết quả thử nghiệm theo định dạng html được lưu một cách mặc định. Đồng
thời có thể tạo kho dữ liệu thử nghiệm của SMART theo định dạng latex hoặc txt
bằng cách sử dụng các tùy chọn –tex và –txt, tùy ý. Các file có định dạng html trình bày dữ liệu theo dạng bảng. Sẽ có thêm một file
định dạng index.html được sinh ra bao gồm một danh sách toàn bộ các kết quả thử
nghiệm đã được tính toán trong quá trình kiểm tra. Các tập tin trong định dạng văn bản có phần mở rộng .txt và cấu trúc như sau: BF 10,45 10,85 10,65 10,71 10,64 10,70 .... BNDM 12,32 8,26 5,43 3,95 3,30 3,42 .... FS 9.22 6.70 5.61 4.62 4.48 4.32 .... HASH3 - 6,90 3,87 2,93 2,58 3,40 .... Các tập tin ở định dạng xml có phần mở rộng .xml. Chúng báo cáo dữ liệu
trong một định dạng có cấu trúc phù hợp để được xử lý hoặc chứa trong các file
html. 3.2.2.1. Khởi động hệ thống - Tải về các gói nguồn từ các trang download [13]. Đây là các file nén có chứa tất cả các mã nguồn C và các văn bản. - Sao chép lưu trữ trong một thư mục địa phương, nơi muốn cài đặt SMART,
và giải nén. Điều này sẽ tạo thư mục mới, có tên SMART, và có chứa các tập tin và
thư mục sau đây: • docs/ là thư mục chứa các tập tin tài liệu; • source/ là thư mục chứa mã nguồn C của tất cả các chuỗi kết hợp các thuật toán và các tiện ích; • results/ là thư mục sẽ chứa các tập tin với dữ liệu thực nghiệm; 44 • data/ là thư mục chứa các tập văn được sử dụng để thử nghiệm các chuỗi kết hợp các thuật toán; • copyright.txt chứa từ chối trách nhiệm về bản quyền; • gpl-3.0.txt chứa giấy phép công cộng chung GNU; • makefile là file bash sử dụng để biên soạn các tập tin nguồn của công cụ C. Chạy lệnh ./makefile để biên dịch công cụ SMART. Mã của mỗi thuật toán
chuỗi kết hợp được biên soạn với một thử nghiệm riêng biệt. Các mã nhị phân kết
quả được lưu trong thư mục directorysource /bin. 3.2.2.2. Thi hành hệ thống sánh mẫu Bước 1. Đăng nhập hệ thống SMART bằng máy ảo Putty, chọn server, chọn
load, chọn open, nhập user name và mật khẩu. Sau đó nhấn chọn Load để đăng nhập
vào hệ thống. Bước 2.Chạy công cụ SMART bằng lệnh cd smart.13.02 Bước 3. Thi hành lệnh sánh mẫu trên tất cả các tệp văn bản của hệ thống SMART: ./smart -text all ./smart -text all -txt Bước 4. Xem kết quả 3.3. Bộ trung gian PUTTY Như đã giới thiệu ở trên, luận văn lựa chọn bộ công cụ SMART để tiến hành
thực nghiệm hai thuật toán sánh mẫu SSABS và TVSBS. Để thuận tiện cho việc
thực hiện bài toán sánh mẫu ngoại tuyến, chương trình đăng nhập qua bộ trung gian
PUTTY. PUTTY được biết đến như là SSH client miễn phí phổ biến nhất thế giới do
Simon Tatham [12] xây dựng và công bố. PUTTY cho phép người dùng Windows
kết nối đến máy chủ, hệ thống từ xa thông qua Internet bởi giao thức SSH (Secure
Shell: một giao thức mạng dùng để thiết lập kết nối mạng một cách bảo mật,Telnet.
Như vậy, PUTTY giúp người sử dụng kết nối với máy chủ (máy ảo) qua giao thức
SSH để điều khiển bằng giao diện dòng lệnh (command line hay viết tắt là CLI).
Đây là chương trình tương tác giữa máy chủ và máy khách có sử dụng cơ chế mã
hoá đủ mạnh nhằm ngăn chặn các hiện tượng nghe trộm, đánh cắp thông tin trên
đường truyền. Các chương trình trước đây: telnet, rlogin không sử dụng phương 45 pháp mã hoá. Vì thế bất cứ ai cũng có thể nghe trộm thậm trí đọc được toàn bộ nội
dung của phiên làm việc bằng cách sử dụng một số công cụ đơn giản. Sử dụng SSH
là biện pháp hữu hiệu bảo mật dữ liệu trên đường truyền từ hệ thống này đến hệ
thống khác. Sau khi cài đặt PUTTY, chúng ta có thể đăng nhập bằng username và password từ cửa sổ Putty Configuration (Hình 3.1). Hình 3.1. Đăng nhập bằng bộ trung gian PUTTY Tiếp theo, có thể chạy công cụ SMART bằng lệnh cd smart.13.02 Cuối cùng, thi hành lệnh sánh mẫu trên tất cả các tệp văn bản của hệ thống SMART: ./smart -text all -txt Mỗi lần thực hiện lệnh sánh mẫu, chương trình sẽ cho ra một kết quả nhất
định. Các kết quả này có thể khác nhau tại mỗi thời điểm. Trong phạm vi luận văn
này, tôi tiến hành hai lần thực nghiệm để có được các kết quả và nhận xét dưới đây. 3.4. Kết quả thực nghiệm và nhận xét 3.4.1. Thực nghiệm đánh giá hiệu năng hai thuật toán SSABS và TVSBS Như đã trình bày tại mục 3.2, công cụ SMART định hướng cho các nhà phát
triển đánh giá hiệu năng của các thuật toán sánh mẫu chính xác, vì vậy, dòng thi 46 hành chính của công cụ là nhằm đánh giá hiệu năng. Thực hiện đầu tiên thực hiện
đánh giá hiệu năng của hai thuật toán sánh mẫu SSABS và TVSBS về mặt hiệu
năng là khảo sát thời gian chạy của hai thuật toán tiến hành trên các bộ dữ liệu mẫu
của SMART (Phụ lục 1). Hình 3.2. Kết quả thực nghiệm 1 Bảng dưới đây cho tổng hợp các kết quả thực nghiệm: Bảng 3.3. Bảng kết quả thử nghiệm 1 Thời gian (ms) Thời gian (ms) Bộ dữ liệu Bộ dữ liệu Độ dài
mẫu SSABS TVSBS SSABS TVSBS 2 12.11 11.78 9.00 8.48 4 13.12 12.49 7.35 6.43 8 15.25 12.77 6.23 5.21 RAND2 RAND4 16 15.27 12.51 7.71 4.42 32 14.86 12.31 7.26 3.40 64 15.63 12.81 6.03 2.59 128 15.24 12.81 5.85 2.58 47 12.78 16.86 256 5.88 3.14 12.55 15.44 512 5.95 2.66 13.00 15.92 1024 5.93 3.20 12.80 15.60 2048 5.89 3.26 -- 15.33 4096 6.36 -- 5.80 6.29 2 4.92 4.68 4.19 4.49 4 3.29 3.57 3.18 3.21 8 2.12 2.87 2.00 3.23 16 1.79 1.51 1.37 2.38 32 1.36 1.46 1.10 2.35 64 1.50 0.87 RAND8 RAND16 1.52 2.76 128 1.19 0.80 0.94 2.35 256 1.14 0.72 0.93 2.33 512 1.14 0.70 0.94 2.38 1024 1.22 0.87 0.95 2.41 2048 1.19 1.77 -- 2.54 4096 1.20 -- 4.20 4.37 2 4.32 4.29 3.03 2.80 4 2.57 3.51 2.08 1.74 8 1.66 2.08 1.43 1.14 16 1.16 12.51 1.04 0.86 32 1.25 1.45 RAND32 RAND64 0.83 0.72 64 0.66 1.24 1.38 0.69 128 0.51 0.78 0.69 0.68 256 0.47 0.70 0.68 0.73 512 0.48 0.66 0.67 0.68 1024 0.47 0.63 0.76 0.72 2048 0.49 0.81 48 4096 -- 0.75 0.72 -- 2 4.59 4.00 3.93 5.65 4 3.37 2.49 2.45 4.28 8 2.35 1.65 2.74 3.01 16 1.66 0.98 0.92 1.95 32 1.15 0.63 0.60 1.42 64 1.29 0.50 0.45 1.08 RAND128 RAND256 128 1.23 0.44 0.37 0.85 256 1.19 0.52 0.51 1.20 512 0.78 0.42 0.35 0.66 1024 0.84 0.47 0.44 0.90 2048 0.65 0.43 0.47 1.17 4096 -- 0.46 0.44 -- 2 5.20 5.37 5.67 5.24 4 3.82 3.60 3.61 3.86 8 2.68 3.24 2.37 2.48 16 1.70 1.62 1.61 1.68 32 1.28 1.22 1.20 1.21 64 0.96 0.99 0.97 0.94 Italian text English
text 128 1.68 1.09 0.81 0.83 256 0.73 0.81 0.72 0.73 512 0.71 0.61 0.67 0.71 1024 0.68 0.55 0.62 0.68 2048 0.77 0.51 0.59 0.67 4096 -- 0.54 0.57 -- Nhận xét - Tính trung bình trong mọi trường hợp thì thuật toán SSABS mất 3.46425ms
và thuật toán TVSBS mất 3.20618182 ms, thể hiện rằng kết quả thực nghiệm cho 49 thấy thuật toán TVSBS có tốc độ trung bình thực hiện tốt hơn. Điều này chứng tỏ
rằng ý tưởng cải tiến thuật toán SSABS tới thuật toán TVSBS là được minh chứng. - 500 mẫu sinh ra là ngẫu nhiên trong quá trình thực hiện thuật toán; do đó với mỗi lần thực hiện thì kết quả đối sánh có thể khác nhau. - Một số trường hợp với mẫu có độ dài 4096 thì hệ thống cho kết quả là “--”,
chúng tôi cho rằng trong trường hợp này sánh mẫu không tìm thấy mẫu trong văn
bản. - Với các bộ dữ liệu được sinh ngẫu nhiên (RANDxx) thì kết quả thực
nghiệm cho thấy một xu hướng là độ dài bảng chữ càng lớn thì thời gian thực hiện
càng nhỏ. Chúng tôi dự báo rằng khả năng số lượng lần xuất hiện mẫu càng hiếm
(do số ký tự trong bảng chữ lớn) có thể giảm thời gian thực hiện. 3.4.2. Thực nghiệm về kết quả sánh mẫu của hai thuật toán SSABS và TVSBS Thực nghiệm này hướng đến khảo sát trực quan hoạt động của hai thuật toán
SSABS và TVSBS trong việc tìm ra sự xuất hiện của mẫu trong văn bản cho sẵn
trên dòng lệnh (Phụ lục 2) và văn bản được cho trong một file dữ liệu (Phụ lục 3). 3.4.2.1. Thực nghiệm mẫu và văn bản được cho trong dòng lệnh Trong SMART, ta thực hiện lệnh tìm kiếm mẫu "thao" trong chuỗi "nguyen thi phuong thao" sử dụng các lệnh: ./ssabs "thao" "nguyen thi phuong thao" ./tvsbs "thao" "nguyen thi phuong thao" Hình 3.3 cho thấy kết quả tìm kiếm là tìm thấy một lần xuất hiện mẫu "thao" trong chuỗi "nguyen thi phuong thao" ở vị trí 18 bằng cả hai thuật toán. 50 Hình 3.3. Kết quả thực nghiệm 2 tìm mẫu trong chuỗi 3.4.2.2. Thực nghiệm với văn bản được cho bằng tên file trên dòng lệnh Tiếp tục, ta thực hiện lệnh tìm kiếm mẫu "thao" trong một file dữ liệu cho trước data.txt sử dụng các lệnh: ./ssabsf "thao" data.txt ./tvsbsf "thao" data.txt Hình 3.4 cho thấy kết quả tìm kiếm là tìm thấy một lần xuất hiện mẫu "thao"
trong chuỗi "nguyen thi phuong thao viet tri phu tho" của tệp data.txt ở vị trí 19
bằng cả hai thuật toán, bổ sung đếm lên 1 và in kết quả từ vị trí mẫu được tìm thấy
cho đến cuối văn bản. 51 Hình 3.4. Kết quả thực nghiệm 2 tìm mẫu trong file Nhận xét Kết quả này cho thấy thuật toán SSABS và TVSBS thi hành tốt việc tìm
kiếm một mẫu trong chuỗi và trong file. Đồng thời, số lần xuất hiện của mẫu trong
văn bản cũng được chỉ ra. Có được kết quả này là do lệnh đếm lần xuất hiện sự xuất
hiện của mẫu trong văn bản của chương trình (Phụ lục 2, 3) đã được bổ sung thêm
các thao tác ghi nhận vị trí xuất hiện mẫu trong chuỗi (file) và in ra kết quả số lần
xuất hiện sau khi kết thúc duyệt mẫu trong văn bản. 3.5. Kết luận chương 3 Chương 3 của luận văn đã trình bày những nghiên cứu về công cụ sánh xâu
SMART, các thành phần chính của nó và cách khởi động, thi hành hệ thống. Công
cụ SMART được xây dựng nhằm cung cấp một khung chuẩn cho các nhà nghiên
cứu về sánh xâu. Bộ công cụ giúp người sử dụng kiểm tra, thiết kế, đánh giá và hiểu
biết các giải pháp hiện có đối với bài toán sánh xâu. Hơn nữa, nó cung cấp một bộ
công cụ cho việc triển khai hầu hết các thuật toán sánh xâu và một kho ngữ liệu
rộng của các bộ đệm văn bản. Các thử nghiệm hai thuật toán sánh mẫu SSABS và TVSBS để giải quyết bài
toán sánh mẫu ngoại tuyến bằng công cụ SMART thông qua bộ trung gian PUTTY.
Các kết quả thực nghiệm cho thấy thuật toán SSABS và TVSBS đã thi hành thành 52 công bài toán sánh mẫu với thời gian hợp lý. Khi chạy thực nghiệm trong chương
trình SMART chỉ tính về hiệu năng để biết được vị trí mẫu trùng với vị trí của văn
bản. Không chỉ có vậy, ở Thực nghiệm 2 còn tiến hành thực nghiệm để tìm sự xuất
hiện của mẫu trong văn bản và mẫu trong file dữ liệu mà còn cho ra được số lần
xuất hiện, bổ sung đếm lên 1, vị trí xuất hiện mẫu trong chuỗi, trong file và in ra kết
quả từ vị trí mẫu được tìm thấy cho đến cuối văn bản bằng việc phải vào dữ liệu gốc
để chỉnh sửa. Tuy nhiên thuật toán có hạn chế là vẫn chưa thi hành được tất cả các
mẫu, một số trường hợp chưa ra kết quả. 53 Kết quả luận văn đạt được Luận văn đã trình bày các nội dung cơ bản nhất về các bài toán sánh mẫu
cũng như ứng dụng của bài toán sánh mẫu. Luận văn tập trung khảo sát một nhóm
ba thuật toán sánh mẫu chính xác là SSABS, TVSBS, FQS. Đồng thời, luận văn
cũng nghiên cứu bộ công cụ phần mềm nguồn mở sánh mẫu SMART. Luận văn đã
tiến hành thực nghiệm trên cơ sở dữ liệu của bộ công cụ SMART để từ đó có một
số nhận xét và so sánh các thuật toán sánh mẫu chính nhanh SSABS và TVSBS về
thời gian thực hiện thuật toán. Luận văn cũng tiến hành thực nghiệm trực quan hoạt
động của hai thuật toán này và kết quả cho thấy hai thuật toán hoạt động chính xác. Hạn chế Thuật toán thứ ba trong họ các thuật toán sánh mẫu chính xác được luận văn
đề cập (thuật toán FQS) mới được đề xuất năm 2014 nên chưa được đưa vào bộ
công cụ SMART. Vì vậy, do năng lực của bản thân và thời gian có hạn, tôi chưa thể
trình bày thực nghiệm thuật toán FQS trong phạm vi luận văn này. Hướng nghiên cứu tiếp theo Nếu điều kiện cho phép, tôi sẽ tiếp tục nghiên cứu thuật toán thứ FQS để thi hành thử nghiệm thuật toán này trong bộ công cụ sánh mẫu SMART. 54 Tiếng Việt: [1] Nguyễn Thị Thúy (2012). Một họ thuật toán sánh mẫu WU-MANBER và thực nghiệm. Luận văn Thạc sỹ, Trường Đại học Công nghệ. Tiếng Anh: [2] C. Charras and T. Lecroq (2004). Handbook of exact string matching algorithms. King’s College Publications. [3] Jie Lin, Donald A. Adjeroh, Yue Jiang (2014). A Faster Quick Search Algorithm. Algorithms 7(2): 253-275. [4] Rahul Thathoo and Ashish Virmani and Sai S Lakshmi, and N. Balakrishnan,
and K. Sekar (2006). TVSBS: A fast exact pattern matching algorithm for
biological sequences. Current Science 91 (1). pp. 47-53. [5] Simone Faro, Thierry Lecroq (2010). The Exact String Matching Problem: a Comprehensive Experimental Evaluation. CoRR abs/1012.2547. [6] Simone Faro, Thierry Lecroq (2011). 2001-2010: Ten Years of Exact String Matching Algorithms. Stringology 2011: 1-2. [7] Simone Faro, Thierry Lecroq (2013). The exact online string matching problem: A review of the most recent results. ACM Comput. Surv. 45(2): 13. [8] S. S. Sheik, Sumit K. Aggarwal, Anindya Poddar, N. Balakrishnan, Krishna
Sekar (2004). A FAST Pattern Matching Algorithm. Journal of Chemical
Information and Modeling 44(4): 1251-1256. [9] Timo Raita (1992). Tuning the Boyer-Moore-Horspool String Searching Algorithm. Softw., Pract. Exper. 22(10): 879-884. Trang web: [10] http://www-igm.univ-mlv.fr/~lecroq/lec_en.html (Thierry Lecroq) và http://www.dmi.unict.it/~faro/ (Simone Faro) [11] Bộ công cụ smart tại trang web: http://www.dmi.unict.it/~faro/smart/, địa chỉ tải bộ công cụ:http://www.dmi.unict.it/~faro/smart/download.php. [12] http://www.chiark.greenend.org.uk/~sgtatham/putty/ PHỤ LỤC Phụ lục 1. Phiên bản thi hành thuật toán SSABS và TVSBS trong SMART int i;
for (i=0;i /*SSABS
* SMART: string matching algorithms research tool.
* Copyright 2012Simone Faro and Thierry Lecroq
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
*(at your option) any later version.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.See the
* GNU General Public License for more details.
* You should have received a copy of the GNU General Public License
* along with this program.If not, see Phụ lục 1.1. Thuật toán SSABS (unsigned char int *x, int m, /*TVSBS
* SMART: string matching algorithms research tool.
* Copyright 2012Simone Faro and Thierry Lecroq
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
*(at your option) any later version.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.See the
* GNU General Public License for more details.
* You should have received a copy of the GNU General Public License
* along with this program.If not, see int a, b, i;
for (a = 0; a < SIGMA; ++a) for (b = 0; b < SIGMA; ++b) brBc[a][b] = m + 2; for (a = 0; a < SIGMA; ++a)
brBc[a][x[0]] = m + 1;
for (i = 0; i < m - 1; ++i) brBc[x[i]][x[i + 1]] = m - i; for (a = 0; a < SIGMA; ++a)
brBc[x[m - 1]][a] = 1; }
int search (unsigned char *x, int m, unsigned char *y, int n)
{ int count,i,j =0;
int BrBc[SIGMA][SIGMA];
unsigned char firstCh, lastCh;
count = 0;
TVSBSpreBrBc (x, m, BrBc);
firstCh = x[0];
lastCh = x[m -1];
for (i=0; i if (lastCh == y[j + m - 1] && firstCh == y[j])
{ for (i = m-2; i > 0 && x[i] == y[j + i]; i--);
if (i <= 0) count++; } j += BrBc[y[j + m]][y[j+m+1]];
}
return count; Phụ lục 1.2. Thuật toán TVSBS //mandatory parameters //the set of pattern legths
//size of the alphabet
//number of runs for each //non mandatory parameters
PATT_SIZE = PATT_LARGE_SIZE;
int alpha = 256;
int VOLTE = 500; int TSIZE = 1048576;
int SIMPLE = 0; //set to 1 if we run a int occ = 0; //set to 1 for int dif = 0; //set to 1 for int txt = 0; //set to 1 for int tex = 0; //set to 1 for int php = 0; //set to 1 for int std = 0; //set to 1 for int limit = 300; //set to 300 running time //text and pattern //file pointer for char c; /* processing of input parameters */
if (argc==1) {printf("No parameter given. Use -h for if (!strcmp("-h", argv[1])) {printManual(); return 0;}
int par = 1;
while(par if (par par++;
if(par>=argc) {printf("Error in input parameters. strcpy(parameter, argv[par++]);
if(!isInt(parameter)) {printf("Error in input VOLTE = string2decimal(parameter); int main(int argc, const char *argv[])
{
char *filename = (char*) malloc (sizeof(char) * (100));
pattern length
single search with custom pattern and text
printing number of occurrences
printing the best and the worst running time
printing results in txt format
printing results in latex format
printing results in php format
printing the standard deviation value
bound
char *simplePattern = (char*) malloc (sizeof(char) * (100));
//used for the simple run of SMART
char *simpleText = (char*) malloc (sizeof(char) * (1000));
//used for the simple run of SMART
/* useful variables */
unsigned char *T ;
int n, tshmid,try;
//length of the text
FILE *ip;
input text
char parameter[1000];
srand( time(NULL) );
help.\n\n"); return 0;}
Use -h for help.\n\n"); return 0;}
parameters. Use -h for help.\n\n"); return 0;} }
if (par Phụ lục 1.3. Chương trình chính main.h trong file chương trình smart par++;
if(par>=argc) {printf("Error in input parameters. strcpy(parameter, argv[par++]);
if(!isInt(parameter)) {printf("Error in input TSIZE = string2decimal(parameter); TSIZE *= MG; par++;
if(par>=argc) {printf("Error in input parameters. }
if (par strcpy(parameter, argv[par++]);
if(!isInt(parameter)) {printf("Error in input limit = string2decimal(parameter); par++;
if(par>=argc) {printf("Error in input parameters. }
if (par strcpy(parameter, argv[par++]); par++;
if(par>=argc) {printf("Error in input parameters. strcat(filename, parameter);
}
if (par strcpy(parameter, argv[par++]);
MINLEN = string2decimal(parameter);;
if(MINLEN<1 || MINLEN>4200) {printf("Error in if(par>=argc) {printf("Error in input parameters. strcpy(parameter, argv[par++]);
MAXLEN = string2decimal(parameter);;
if(MAXLEN<1 || MINLEN>MAXLEN) {printf("Error in }
if (par par++;
if(par>=argc) {printf("Error in input parameters. strcpy(parameter, argv[par++]); strcpy(simplePattern, parameter); if(strlen(simplePattern)>100) {printf("Error in strcpy(parameter, argv[par++]); strcpy(simpleText, parameter); if(strlen(simpleText)>1000) {printf("Error in SIMPLE=1; }
if (par Use -h for help.\n\n"); return 0;}
parameters. Use -h for help.\n\n"); return 0;}
Use -h for help.\n\n"); return 0;}
parameters. Use -h for help.\n\n"); return 0;}
Use -h for help.\n\n"); return 0;}
Use -h for help.\n\n"); return 0;}
input parameters. The minimum length is not a valid
argument.\n\n"); return 0;}
Use -h for help.\n\n"); return 0;}
input parameters. The maximum length is not a valid
argument.\n\n"); return 0;}
Use -h for help.\n\n"); return 0;}
input parameters. Max 100 chars for P parameter.\n\n"); return 0;}
if(par>=argc) {printf("Error in input parameters.
Use -h for help.\n\n"); return 0;}
input parameters. Max 1000 chars for T parameter.\n\n"); return
0;} par++;
occ = 1; par++;
dif = 1; par++;
txt = 1; par++;
std = 1; par++;
tex = 1; par++;
php = 1; par++;
PATT_SIZE = PATT_SHORT_SIZE; par++;
PATT_SIZE = PATT_VERY_SHORT; }
if (par && strcmp("-alpha", argv[par])!=0
&& strcmp("-tsize", argv[par])!=0
&& strcmp("-plen", argv[par])!=0
&& strcmp("-occ", argv[par])!=0
&& strcmp("-dif", argv[par])!=0
&& strcmp("-txt", argv[par])!=0
&& strcmp("-tb", argv[par])!=0
&& strcmp("-simple", && strcmp("-tex", argv[par])!=0 && strcmp("-std", argv[par])!=0 && strcmp("-php", argv[par])!=0
&& strcmp("-pset", argv[par])!=0
&& strcmp("-veryshort", && strcmp("-short", }
if(strcmp(filename,"") && SIMPLE) {printf("Error in input if(!strcmp(filename,"") && !SIMPLE) {printf("Error in input //get information about the set of algorithms argv[par])!=0
argv[par])!=0
argv[par])!=0) {printf("Error in input parameters. Use -h for
help.\n\n"); return 0;}
parameters. Both parameters -simple and -text defined.\n\n");
return 0;}
parameters. No filename given.\n\n"); return 0;} getAlgo(ALGO_NAME,EXECUTE); size_t size = sizeof(unsigned char) * TSIZE+10; tkey = rand()%1000;
tshmid = shmget(tkey, TSIZE+10, IPC_CREAT | 0666); } while(++try<10 && tshmid<0); printf("\nShared memory allocation failed!\nYou need at shmctl(tshmid, IPC_RMID,0);
exit(1); //experimental results on a single pattern and a single if( SIMPLE ) { n = strlen(simpleText);
int m = strlen(simplePattern);
strcpy(T,simpleText);
alpha = 250;
PATT_CUSTOM_SIZE[0] = m;
PATT_CUSTOM_SIZE[1] = 0;
PATT_SIZE = PATT_CUSTOM_SIZE;
//if ( !(alpha = getAlpha(filename)) ) return 0;
printf("\n\tText of %d chars : %s\n", n,T);
printf("\tPattern of %d chars : %s\n", srand(time(NULL));
char expcode[100];
generateCode(expcode);
printf("\tStarting experimental tests with code run_setting("", tkey, T, n, alpha, FREQ, VOLTE, occ, shmctl(tshmid, IPC_RMID,0);
return 0; //experimental results on a single corpus
printf("\n\tTry to process archive %s\n", filename);
char fullpath[100];
strcpy(fullpath,"data/");
strcat(fullpath, filename);
//initialize the frequency vector
if( !(n = getText(T,fullpath,FREQ,TSIZE) ) ) {
}
if ( !(alpha = getAlpha(filename)) ) {
shmctl(tshmid, IPC_RMID,0);
return 0; //allocate space for text in shered memory
key_t tkey = rand()%1000;
try = 0;
do {
if (tshmid < 0) {
perror("shmget"); exit(1);
}
if ((T = shmat(tshmid, NULL, 0)) == (unsigned char *) -1) {
least 12Mb of shared memory\nPlease, change your system settings
and try again.\n");
perror("shmat");
}
text
m,simplePattern);
%s\n",expcode);
dif, expcode, tshmid, txt, tex, php, simplePattern, std, limit);
//no output is given for the simple case;
}
else if( strcmp(filename, "all") ) { }
printf("\tText buffer of dimension %d byte\n", n);
srand(time(NULL));
char expcode[100];
generateCode(expcode);
printf("\tStarting experimental tests with code run_setting(filename, tkey, T, n, alpha, FREQ, VOLTE, outputINDEX(filename,expcode); char fullpath[100];
strcpy(fullpath,"data/");
strcat(fullpath, SETTING_BUFFER[sett]);
alpha = SETTING_ALPHA_SIZE[sett];
printf("\n\tTry to process archive %s\n", shmctl(tshmid, IPC_RMID,0);
return 0; //initialize the frequency vector
if( !(n = getText(T,fullpath,FREQ,TSIZE) ) ) {
}
printf("\tText buffer of dimension %d byte\n", n);
printf("\tStarting experimental tests with code run_setting((char*)SETTING_BUFFER[sett], tkey, T, n, //free shared memory
shmctl(tshmid, IPC_RMID,0); %s\n",expcode);
occ, dif, expcode, tshmid, txt, tex, php, "", std, limit);
}
else {
//starts experimental results on all texts
srand(time(NULL));
char expcode[100];
generateCode(expcode);
int sett;
for(sett=0; sett Phụ lục 2. Phiên bản thuật toán SSABS và TVSBS trong SMART với chuỗi int i;
for(i=0;i if(count==0)printf("Found at: ");
printf("%d: %s ",(j+1),(y+j));
count++; } #include "include/define.h"
#include "include/main.h"
void preQsBc(unsigned char *P, int m, int qbc[])
{
}
////////////Searching Phase/////////////////////////////////////
int search(unsigned char *x, int m, unsigned char *y, int n){
int count,i,j =0;
int qsBc[SIGMA];
unsigned char firstCh, lastCh;
count = 0;
preQsBc(x, m, qsBc);
firstCh = x[0];
lastCh = x[m -1];
for(i=0; i Phụ lục 2.1. SSABS với chuỗi #include "include/define.h"
#include "include/main.h"
void TVSBSpreBrBc(unsigned char *x, int m, int brBc[SIGMA][SIGMA])
{
int a, b, i;
for (a = 0; a < SIGMA; ++a)
for (b = 0; b < SIGMA; ++b)
brBc[a][b] = m + 2;
for (a = 0; a < SIGMA; ++a)
brBc[a][x[0]] = m + 1;
for (i = 0; i < m - 1; ++i)
brBc[x[i]][x[i + 1]] = m - i; Phụ lục 2.2. TVSBS với chuỗi strcpy(z,y); if(count==0) printf("Found at: ");
printf("%d: %s\n",(j+1),(z+j));
count++; } for (a = 0; a < SIGMA; ++a)
brBc[x[m - 1]][a] = 1;
}
int search(unsigned char *x, int m, unsigned char *y, int n){
int count,i,j =0;
int BrBc[SIGMA][SIGMA];
unsigned char firstCh, lastCh;
unsigned char *z=malloc(n+1);
count = 0;
TVSBSpreBrBc(x, m, BrBc);
firstCh = x[0];
lastCh = x[m -1];
for(i=0; i unsigned char *p,*t;
int m,n;
if(argc < 3) { return 1; }
p = argv[1];
m = strlen(argv[1]);
t = argv[2];
n = strlen(argv[2]);
int occ = search(p,m,t,n);
printf(" total of %d occurrences\n",occ);
return 0; int main(int argc, char *argv[])
{
// int search(unsigned char *x, int m, unsigned char *y, int n){
printf("%s Phụ lục 2.3. Chương trình chính main.h với chuỗi Phụ lục 3. Phiên bản thuật toán SSABS và TVSBS trong SMART với file int i;
for(i=0;i int count,i,j =0;
int qsBc[SIGMA];
unsigned char firstCh, lastCh;
char * y =malloc(n+1);
strcpy(y,z);
count = 0;
preQsBc(x, m, qsBc);
firstCh = x[0];
lastCh = x[m -1];
for(i=0; i //Stage 2
for(i = m-2; i > 0 && x[i] == y[j + i]; i-- if(count==0)printf("Found at: ");
printf("%d: %s",(j+1),(z+j));
count++; if(i <= 0) {
} }
// Stage 3
j += qsBc[y[j + m]]; }
return count; #include "include/define.h"
#include "include/mainf.c"
void preQsBc(unsigned char *P, int m, int qbc[])
{
}
////////////Searching Phase///////////////////////////////////////
int search(unsigned char *x, int m, unsigned char *z, int n){
);
} Phụ lục 3.1. SSABS với file #include "include/define.h"
#include "include/mainf.c"
void TVSBSpreBrBc(unsigned char *x, int m, int brBc[SIGMA][SIGMA])
{
int a, b, i;
for (a = 0; a < SIGMA; ++a)
for (b = 0; b < SIGMA; ++b)
brBc[a][b] = m + 2; Phụ lục 3.2. TVSBS với file if(count==0) printf("Found at: ");
printf("%d: %s, ",(j+1),(z+j));
count++; } for (a = 0; a < SIGMA; ++a)
brBc[a][x[0]] = m + 1;
for (i = 0; i < m - 1; ++i)
brBc[x[i]][x[i + 1]] = m - i;
for (a = 0; a < SIGMA; ++a)
brBc[x[m - 1]][a] = 1;
}
int search(unsigned char *x, int m, unsigned char *z, int n){
int count,i,j =0;
int BrBc[SIGMA][SIGMA];
unsigned char firstCh, lastCh;
unsigned char *y =malloc(n+1);
strcpy(y,z);
count = 0;
TVSBSpreBrBc(x, m, BrBc);
firstCh = x[0];
lastCh = x[m -1];
for(i=0; i unsigned char *p,*t;
FILE * fp;
int m,n;
if(argc < 3) { return 1; printf("Failed to open file: %s\n",argv[2]);
exit(2); #include }
p = argv[1];
m = strlen(argv[1]);
if((fp=fopen(argv[2],"r"))==NULL){
} Phụ lục 3.3. Chương trình chính main.h với file fseek(fp,0,SEEK_END);
n=ftell(fp);
rewind(fp);
t=malloc(n+1);
fread(t,1,n,fp);
fclose(fp);
t[n]='\0';
int occ = search(p,m,t,n);
printf(" total of %d occurrences\n",occ);
if(t)free(t);
return 0; }mi
[,1
mx
i
1
]
}
c
1:min{
i
m
CHƯƠNG 2: HỌ THUẬT TOÁN SÁNH MẪU CHÍNH XÁC NHANH
SSABS - TVSBS – FQS
CHƯƠNG 3: CHƯƠNG TRÌNH THỰC NGHIỆM HỌ THUẬT TOÁN
ĐỐI SÁNH MẪU CHÍNH XÁC NHANH VỚI BỘ CÔNG CỤ SMART
KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU TIẾP THEO
TÀI LIỆU THAM KHẢO
