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 đỡ

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

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ọ 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

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

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)
y
x


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
x

b

u

a

u
shift

x

b

không chứa b

Dịch để ký tự b ăn khớp với văn bản.



(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 BoyerMoore 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 BoyerMoore 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

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 (m4), ngắn (4 < m  32), dài (32 < m  256) và rất



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

CHƯƠNG 2: HỌ THUẬT TOÁN SÁNH MẪU CHÍNH XÁC NHANH
SSABS - TVSBS – FQS
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

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


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., i.
nih.gov/genomes/H_sapiens/protein/).
Toàn bộ trình tự theo định dạng FASTA: >gi|4504279|ref|
NP_002098.1|H3histone,family3A[Homosapiens]MARTKQTARKSTGGKAPRK
QLATKAARKSAPSTGGVKKPHRYRPGTVALREIRRYQKSTELLIRKLPFQR

V W Y

6

8

8

3

8

2

8

8

8

8

8

8

8

1


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