ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ THÚY MỘT HỌ THUẬT TOÁN SÁNH MẪU WU-MANBER
VÀ THỰC NGHIỆM


MỘT HỌ THUẬT TOÁN SÁNH MẪU WU-MANBER
VÀ THỰC NGHIỆM Ngành : Công nghệ thông tin
Chuyên ngành : Hệ thống thông tin
Mã số :
60 48 05 LUẬN VĂN
THẠC SĨ CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS Hà Quang Thụy


1.3.6. Các thuật toán khác 14

CHƯƠNG 2: HỌ THUẬT TOÁN WM 16

2.1. Thuật toán WM 16

2.1.1. Tổng quan về thuật toán 16

2.1.2. Thuật toán 17

2.1.2.1. Phác thảo của thuật toán 17

2.1.2.2. Giai đoạn tiền xử lý 18

2.1.2.3. Giai đoạn tìm kiếm mẫu 21

2.1.3. Phân tích thuật toán 22

2.2. Một thuật toán WM với bảng băm cô đọng 25

2.2.1. Phác thảo của thuật toán 25

2.2.2. Cải tiến của thuật toán 26

2.3. Thuật toán WM đồng thời cao 28

2.3.1. Cải tiến của thuật toán 28

2.3.2. Giai đoạn tiền xử lý và tìm mẫu của HCWM 29
viDANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT

quan tâm nhiều nhất. Trong bối cảnh bùng nổ thông tin hiện nay, cần phải có các
công cụ tìm kiếm thông tin tự động để hỗ trợ người dùng. Để xây dựng được các
công cụ tìm kiếm tốt, chúng ta phải dựa vào các thuật toán tìm kiếm theo một
câu hỏi dưới dạng một xâu ký tự. Các thuật toán tìm kiếm xâu ký tự được sử
dụng rất nhiều trong các chương trình máy tính, đặt biệt là các thuật toán tìm
kiếm mẫu giải quyết bài toán tìm kiếm một đoạn văn bản (mẫu) trong các văn
bản (đích) thuộc một tập các văn bản của miền tìm kiếm. Bài toán nói trên được
gọi là bài toán sánh mẫu (pattern matching, còn được gọi là so mẫu).
Bài toán sánh mẫu không chỉ có trong miền dữ liệu văn bản mà còn có
trong các miền dữ liệu đa phương tiện khác (ảnh, video, âm thanh,…). 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 trong hệ điều hành UNIX), cơ chế kiểm tra một
file nhiễm virus (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, xác định mẫu gene bệnh xuất hiện trong đoạn gene
của người
Trong thời đại bùng nổ thông tin với tốc độ lượng thông tin tăng gấp đôi
sau chu kỳ 18 tháng [CL00], dù cho tốc độ và khả năng lưu trữ của máy tính
tăng nhanh thì vấn đề nghiên cứu, phát triển nâng cao hiệu quả của các thuật
toán sánh mẫu luôn là chủ đề nghiên cứu thời sự. Nói riêng, thuật toán sánh mẫu
Wu-Manber do S. Wu và U. Manber công bố vào năm 1994 [WM94] tiếp tục có
nhiều phiên bản nâng cấp gần đây [SWG06, DX08, ZCP09, ZCP09a].
Chính vì thế, luận văn này định hướng nghiên cứu một số thuật toán sánh
mẫu văn bản, tập trung vào họ thuật toán Wu-Manber do họ thuật toán này tỏ ra
có nhiều ưu việt trong bài toán sánh mẫu. Nội dung chủ yếu của luận văn là
nghiên cứu họ thuật toán sánh mẫu văn bản Wu-Manber, phân tích chi tiết một
vài thuật toán trong họ nói trên [SWG06, DX08, ZCP09, ZCP09a], khai thác
công cụ để thực nghiệm thuật toán Wu-Manber (trong một số trường hợp, luận
văn sử dụng cách viết tắt là WM).
CHƯƠNG 1: BÀI TOÁN VÀ THUẬT TOÁN SÁNH MẪU

1.1. Giới thiệu về bài toán sánh mẫu
Kiểu dữ liệu văn bản (Text) là dạng trình bày thông tin gần gũi nhất với
con người, vì vậy, đây cũng là dạng trình bày thông tin số rất phổ biến. Chính vì
lẽ đó, bài toán tìm kiếm văn bản (text searching) là một trong những bài toán
quan trọng nhất trong hoạt động tìm kiếm thông tin của con người. Trong thời
đại ngày nay, văn bản số hóa đang tăng trưởng "bùng nổ" trong các cơ sở dữ liệu
trên Internet, dung lượng tăng gấp đôi sau mỗi chu kỳ 18 tháng [CL00]. Trong
bối cảnh đó, vấn đề tìm kiếm văn bản một cách tự động đã rất quan trọng thì lại
ngày càng quan trọng hơn.
Dạng phổ biến nhất của bài toán tìm kiếm văn bản là: Cho trước nguồn
tìm kiếm là một tập D các văn bản (hoặc là cơ sở dữ liệu văn bản, hoặc là tập
các văn bản trên Internet). Cho một câu hỏi dạng văn bản q (thường là một từ,
một xâu văn bản ngắn), hãy tìm tất cả các văn bản thuộc D mà có chứa q. Trong
nhiều trường hợp (chẳng hạn, tìm kiếm thông qua máy tìm kiếm) thì q còn được
gọi là "truy vấn" và bài toán còn có tên gọi là "tìm kiếm theo truy vấn". Để tìm
được các văn bản có chứa văn bản truy vấn q, hệ thống tìm kiếm cần phải kiểm
tra văn bản truy vấn q có là một xâu con của các văn bản thuộc tập D hay không
(sánh mẫu) và đưa ra các văn bản đáp ứng. Trong nhiều trường hợp, bài toán còn
đòi hỏi tìm tất cả các vị trí của các xâu con trong văn bản trùng với q. Đồng
thời, điều kiện tìm kiếm có thể được làm "xấp xỉ" theo nghĩa văn bản kết quả có
thể không cần chứa q (không cần có một xâu con của văn bản trùng một cách
hoàn toàn chính xác với q) mà chỉ cần "liên quan" tới q (có xâu con trong văn
bản "xấp xỉ" q). Có thể thấy, các máy tìm kiếm sử dụng cả cơ chế tìm kiếm xấp
xỉ khi mà văn bản kết quả tìm kiếm không chứa hoàn toàn chính xác văn bản
truy vấn.
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 tìm kiếm thông
tin và các hệ thống sinh- tin học. Một lý do nữa, con người ngày nay không chỉ

(|D|>>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 đề xuấ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ó luôn là một chủ đề nghiên cứu được 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ỉ được đặt ra, trong đó, tìm 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
[WM92]. 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
(M≤30), 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 5số 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ẹ.

Luận văn này đề cập tới bài toán sánh mẫu chính xác và tập trung vào
sánh mẫu nhẹ.
1.3. Một số thuật toán sánh mẫu cơ bản
Theo Christian Charras và Thierry Lecroq [CL00], bốn cách tiếp cận chủ
yếu của các thuật toán sánh mẫu được phân loại theo thứ tự đối sánh các ký tự
của mẫu với văn bản: (1) tuần tự từ trái sang phải; (2) tuần tự từ phải sang trái;


y

G

C

A

T

C

G

C

A

G

A

G

T

A

T

C

A

G

A

G

A

G
Dịch 1
Lần kiểm tra thứ hai

y

G

C

A

T

C


C

G 1

x G

C

A

G

A

G

A

GDịch 1
Lần kiểm tra thứ ba


A

C

A

G

T

A

C

G 1
Dịch 1

Thuật toán Brute Force sẽ thực hiện 30 so sánh như vậy cho đến hết văn bản
Ví dụ:
TWO ROADS DIVERGED IN A YELLOW WOOD


Việc tìm kiếm bằng Brute-Force có thể là rất chậm đối với một số mẫu nào
đó, ví dụ nếu xâu cần xét là một xâu nhị phân chỉ gồm hai ký tự thường xuất
hiện trong các ứng dụng xử lý ảnh và lập trình hệ thống.
1.3.2. Thuật toán Knuth-Morris-Pratt
Thuật toán Knuth-Morris-Pratt [CL00] có những đặc điểm chính sau:
thuật toán thực hiện so sánh từ trái qua phải, độ phức tạp về thời gian trong giai
đoạn tiền xử lý là O(M), độ phức tạp thời gian trong giai đoạn tìm mẫu là
O(M+N), trong quá trình sánh mẫu thuật toán thực hiện nhiều nhất 2N-1 lần so
sánh, giới hạn trì hoãn là log
φ
(M) với φ=
2
51+

Thuật toán Knuth-Morris-Pratt là thuật toán có độ phức tạp tuyến tính đầu
tiên được phát hiện ra, dựa trên thuật toán Brute Force với ý tưởng lợi dụng lại
những thông tin của lần thử trước cho lần sau. Trong thuật toán brute force vì
chỉ dịch cửa sổ đi một ký tự lên có đến M-1 ký tự của cửa sổ mới là những ký tự
của cửa sổ vừa xét. Trong đó có thể có rất nhiều ký tự đã được so sánh giống với
mẫu và bây giờ lại nằm trên cửa sổ mới nhưng được dịch đi về vị trí so sánh với
mẫu. Việc xử lý những ký tự này có thể được tính toán trước rồi lưu lại kết quả.
Nhờ đó lần thử sau có thể dịch đi được nhiều hơn một ký tự, và giảm số ký tự
phải so sánh lại.
Xét lần thử tại vị trí j, khi đó cửa sổ đang xét bao gồm các ký tự
y[j…j+m-1] giả sử sự khác biệt đầu tiên xảy ra giữa hai ký tự x[i] và y[j+i-1].
Khi đó x[1…i]=y[j…i+j-1]=u và a=x[i]
≠
y[i+j]=b. Với trường hợp này, dịch
cửa sổ phải thỏa mãn v là phần đầu của xâu x khớp với phần đuôi của xâu u trên

5:i=4,j=2:i:= 5;j:= 3;next[5] := 3;
6:i=5,j=3:i:= 6;j:= 4;next[6] := 4;
7:i=6,j=4:j:=next[4] = 2;
8:i=6,j=2:j:=next[2] = 1;
9:i=6,j=1:j:=next[1] = 0;
10:i=6,j=0:i:= 7;j:= 1;next[7] := 1;
Và khi quá trình tìm kiếm được thực hiện:

12345678910…
1: ababbabaa
2: ababac j=next[5]=3
3: ababac j=next[3]=1
4: ababac j=next[1]=0
5: ababac j=next[4]=2
6: ababac j=next[2]=1
7: ababac

Ví dụ 2:
Một ví dụ khác của thuật toán sẽ cho ta thấy nếu như trong mẫu các ký tự
từng đôi một khác nhau thì Knuth-Morris-Pratt sẽ không khác gì so với Brute-
Force. Khi đó next[1] = 0 còn next[j] = 1với mọi j >1 9

trí xuất hiện ở mẫu.
Thuật toán này có phần giống thuật toán Knuth-Morris-Pratt trong việc
nhảy về trạng thái trước khi gặp một ký tự không khớp, nhưng thuật toán DFA 10

có sự đánh giá chính xác hơn vì việc xác định vị trí nhảy về dựa trên ký tự
không khớp của văn bản (trong khi thuật toán KMP lùi về chỉ dựa trên vị trí
không khớp).
Việc xây dựng hệ automat khá đơn giản khi được cài đặt trên ma trận kề.
Khi đó thuật toán có thời gian xử lý là O(N) và thời gian để tạo ra hệ automat là
O(M*N) (tùy cách cài đặt)
Nhưng ta nhận thấy rằng trong DFA chỉ có nhiều nhất M cung thuận và M
cung nghịch, vì vậy việc lưu trữ các cung không cần thiết phải lưu trên ma trận
kề mà có thể dùng cấu trúc danh sách kề Forward Star để lưu trữ. Như vậy thời
gian chuẩn bị và lượng bộ nhớ chỉ là O(M). Tuy nhiên thời gian tìm kiếm có thể
tăng lên một chút so với cách lưu ma trận kề.
1.3.4. Thuật toán Boyer-Moore
Thuật toán Boyer Moore là thuật toán tìm kiếm chuỗi rất có hiệu quả
trong thực tiễn, các dạng khác nhau của thuật toán này thường được cài đặt trong
các chương trình soạn thảo văn bản.
Đặc điểm chính của thuật toán là kiểm tra các ký tự của mẫu từ phải sang
trái và khi phát hiện sự khác nhau đầu tiên thuật toán sẽ tiến hành dịch cửa sổ đi,
độ phức tạp về thời gian ở giai đoạn tiền xử lý là O(M+δ), ở giai đoạn tìm mẫu
là O(M*N), trong trường hợp tốt nhất là O(N/M).
Trong thuật toán này có hai cách dịch cửa sổ:
Cách thứ 1: gần giống như cách dịch trong thuật toán KMP, 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.


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.

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).

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

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
b u

x
a u
shift

x

không chứa b 12

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.
bmBc[c]=



=−−−≤≤
m
cimxmii }]1[,11:min{

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-

lại xảy ra sự không khớp, nhưng S lại có xuất hiện trong mẫu vì vậy ta dịch mẫu
đi 5 vị trí tức là cho đến khi ký tự S trong văn bản khớp với ký tự S trong mẫu.
Quá trình trên tiếp diễn tương tự cho đến khi so sánh G với ký tự T trong
CONSISTING. Có sự không trùng khớp, nhưng T lại có xuất hiện trong mẫu
nên ta dịch mẫu đi 4 vị trí cho đến khi nó trùng với ký tự T trong mẫu. Và ở vị
trí mới ta tìm được một sự trùng khớp hoàn toàn của mẫu trong văn bản. Với
phương pháp này đưa ta đến kết quả chỉ sau 7 bước so sánh (và thêm 5 lần so
sánh các ký tự trong STING với văn bản nữa để chỉ ra sự trùng khớp hoàn toàn).
1.3.5. Thuật toán Karp-Rabin
Thuật toán Karp-Rabin là thuật toán sử dụng hàm băm, độ phức tạp về
thời gian trong giai đoạn tiền xử lý là O(M), giai đoạn tìm mẫu là O(M*N). Đây
là bài toán tìm kiếm mẫu không khác nhiều so với bài toán tìm kiếm chuẩn. Tại
đây một hàm băm được dùng để tránh đi sự so sánh không cần thiết. Thay vì
phải so sánh tất cả các vị trí của văn bản, ta chỉ cần so sánh những cửa sổ bao
gồm những ký tự “có vẻ giống” mẫu.
Trong thuật toán này hàm băm phải thỏa mãn một số tính chất như phải
dễ dàng tính được trên mẫu, và đặc biệt công việc tính lại phải đơn giản để ít ảnh
hưởng đến thời gian thực hiện của thuật toán. Và hàm băm được chọn ở đây là:
hash(w[0…m-1]) = h = (w[0]*2
m-1
+ w[1]*2
m-2
+… w[m-1]*2
0
) mod q
Việc tính lại hàm băm sau khi dịch cửa sổ đi một ký tự chỉ đơn giản như sau:

Rehash(a,b,h)=h = ((h – a*2
m-1
)*2 + b)mod q

dịch sang phải một vị trí so với văn bản và tiếp tục so sánh. Kết quả là tìm thấy
mẫu trong văn bản khi có hai giá trị băm là bằng nhau.
1.3.6. Các thuật toán khác
Một số thuật toán nêu trên chưa phải là tất cả các thuật toán tìm kiếm
chuỗi hiện có. Nhưng chúng đã đại diện cho đa số các tư tưởng dùng để giải bài
toán tìm kiếm chuỗi.
Các thuật toán sánh mẫu lần lượt từ trái sang phải thường là các dạng cải
tiến (và cải lùi) của thuật toán Knuth-Morris-Pratt và thuật toán sử dụng
Automat như: Forward Dawg Matching, Apostolico-Crochemore, Not So
Naïve…
Các thuật toán sánh mẫu từ phải sang trái đều là các dạng của thuật toán
Boyer-Moore. Phải nói lại rằng thuật toán BM là thuật toán tìm kiếm rất hiệu
quả trên thực tế nhưng độ phức tạp tính toán lý thuyết lại là O(M*N).
Chính vì vậy những cải tiến của thuật toán này cho độ phức tạp tính toán
lý thuyết tốt như: thuật toán Apostolico-Giancarlo đánh dấu lại những ký tự đã
so sánh rồi để khỏi bị so sánh lặp lại, thuật toán Turbo-BM đánh giá chặt chẽ 15

hơn các thông tin trước để có thể dịch được xa hơn và ít bị lặp, … Còn có một
số cải tiến khác của thuật toán BM không làm giảm độ phức tạp lý thuyết mà
dựa trên kinh nghiệm để có tốc độ tìm kiếm nhanh hơn trong thực tế. Ngoài ra,
một số thuật toán kết hợp quá trình tìm kiếm của BM vào hệ thống Automat
mong đạt kết quả tốt hơn.
Các thuật toán sánh mẫu theo thứ tự đặc biệt
* Thuật toán Galil-Seiferas và Crochemore-Perrin chia mẫu thành hai
đoạn, đầu tiên kiểm tra đoạn ở bên phải rồi mới kiểm tra đoạn bên trái với chiều
từ trái sang phải.
* Thuật toán Colussi và Galil-Giancarlo lại chia mẫu thành hai tập và tiến

thuật toán AC-BM và thuật toán Wu-Manber (WM) [CL00], trong đó, thuật toán
WM có hiệu quả cao được sử dụng rộng rãi trong việc tìm kiếm. Aho và
Corasick [AC75] trình bày một thuật toán tuyến tính thời gian cho bài toán sánh
mẫu, dựa trên phương pháp tiếp cận thiết bị tự động. Thuật toán này là một cơ
sở cho các công cụ UNIX fgrep. Thuật toán tuyến tính thời gian là tối ưu trong
trường hợp xấu nhất (thuật toán BM) nhưng bị coi như một thuật toán tìm kiếm
chuỗi thông thường được chứng minh bởi Boyer và Moore [BM77], nó bỏ qua
một bộ phận lớn trong văn bản khi tìm kiếm, cho kết quả nhanh hơn so với thuật
toán tuyến tính trong trường hợp trung bình. Commentz và Walter [CW79] trình
bày thuật toán Commentz-Walter cho các vấn đề sánh mẫu kết hợp với kỹ thuật
Boyer-Moore và các thuật toán Aho-Corasick. Trong thực tế, các thuật toán
Commentz-Walter nhanh hơn đáng kể so với thuật toán AC. Hume [Hu91] thiết
kế một công cụ gọi là gre dựa trên thuật toán này, và phiên bản 2.0 của fgrep
đang được sử dụng trong dự án GNU [Ha93]. Baeza-Yates [Ba89] cũng đã đưa
ra một thuật toán được kết hợp từ các thuật toán Boyer-Moore-Horspool [Ho80]
(một biến thể của thuật toán Boyer-Moore cổ điển) với thuật toán Aho-Corasick.
Như giới thiệu ở trên, thuật toán WM được Sun Wu và Udi Manber đề
xuất vào năm 1994, sử dụng ý tưởng BM và băm. Thuật toán WM là một trong
các thuật toán sánh mẫu thuộc loại nhanh nhất.
Thuật toán WM dựa trên một ý tưởng tốt trong sánh mẫu, nhưng trong
ứng dụng thực tế, nhiều vấn đề có thể được cải tiến hơn nữa. Hiện nay, có rất
nhiều phiên bản thuật toán WM cải tiến. Thuật toán WM sửa đổi (MWM:
Modified WM) được sử dụng trong Snort, sử dụng bảng SHIFT và bảng băm
tiền tố. Thêm các chức năng của bộ lọc tiền tố để thuật toán WM có được hiệu
quả tốt. Để sánh mẫu nhanh hơn, một bảng tiền tố được thêm vào. Ý tưởng của
thuật toán QS (một thuật toán WM cải tiến) là tăng cường khoảng cách dịch
chuyển. Bảng HASH được sửa đổi, và danh sách liên kết các mẫu hậu tố được
thêm vào để tránh sự mất mát, vì vậy khi một mẫu trong danh sách liên kết xuất
hiện, các mẫu sau đó không cần phải xuất hiện nữa. Người ta phân chia tất cả
các mẫu thành hai nhóm, nhóm mẫu ngắn và nhóm mẫu dài, và sau đó đối sánh

2.1.2. Thuật toán
2.1.2.1. Phác thảo của thuật toán
Ý tưởng cơ bản của thuật toán sánh mẫu Boyer-Moore [BM77] là thuật
toán sẽ kiểm tra các ký tự của mẫu từ phải sang trái và khi phát hiện sự khác
nhau đầu tiên thuật toán sẽ tiến hành dịch cửa sổ đi. Giả sử rằng chiều dài của
mẫu là m. Ta bắt đầu bằng cách so sánh ký tự cuối cùng của mẫu đối lập t
m
, ký
tự thứ m' của văn bản. Nếu có một mẫu không phù hợp (trong hầu hết các văn
bản, khả năng đối sánh không phù hợp lớn hơn nhiều so với khả năng phù hợp),
thì ta xác định rằng có sự xuất hiện của ký tự ngoài cùng bên phải t
m
trong mẫu
và dịch chuyển một cách phù hợp. Ví dụ, nếu t
m
không xuất hiện trong tất cả các
mẫu, ta dịch chuyển m ký tự và chuyển sang ký tự tiếp theo, ký tự t
2m
. Trong các
văn bản ngôn ngữ tự nhiên, thay đổi kích thước m sẽ khiến cho thuật toán xử lý
rất nhanh. 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ách quét mẫu từ phải sang trái để sử dụng cách dịch này. Ta sẽ sử
dụng ý tưởng giống như vậy cho các vấn đề sánh mẫu.
Thuật toán WM có hai cơ chế cốt lõi, cơ chế bộ lọc dựa trên công nghệ
băm và công nghệ dịch chuyển ký tự xấu (ký tự “không khớp”) từ thuật toán
BM.
Bằng cách tính toán giá trị băm của các khối hậu tố trong mẫu, các mẫu
có cùng hậu tố được liên kết trong một danh sách. Danh sách các mục lưu trữ
trong một bảng băm. Khi tìm kiếm một văn bản, chúng ta tính toán giá trị băm

Giả sử văn bản "T = t
1
, t
2
, , t
n
", "n" là chiều dài của "T", mẫu "P={P
1
, P
2
,
, P
l
}", "l" là chiều dài của "P", kích thước cửa sổ đối sánh là "m", kích thước
khối ký tự "B=2".
(1) Thành lập bảng SHIFT.
Giả sử "X" là một khối văn bản bên trong cửa sổ đối sánh hiện tại, bằng
cách tính toán băm, "X" ánh xạ tới vị trí "i" trong bảng SHIFT, nghĩa là
hash(X)= i. Khoảng cách dịch chuyển trong bảng SHIFT được tính như sau.
19

SHIFT[i]=
{



∈≤≤+−=−

c
2M, thực tế, ta thường sử dụng hoặc B = 2 hoặc B = 3. Bảng
SHIFT đóng vai trò tương tự như trong các thuật toán Boyer-Moore thông
thường, ngoại trừ việc nó xác định sự dịch chuyển dựa trên các ký tự B cuối
cùng chứ không phải chỉ một ký tự. Ví dụ, nếu chuỗi ký tự B trong văn bản
không xuất hiện trong các mẫu, ta có thể dịch chuyển m - B + 1. Giả sử bảng
SHIFT chứa một mục nhập cho mỗi chuỗi có thể có của kích thước B, thì kích
thước của nó là |Σ|
B
(ta sử dụng một bảng nén với chuỗi ánh xạ vào cùng một
mục để tiết kiệm không gian). Mỗi chuỗi kích thước B được sắp xếp vào một số
nguyên và sử dụng như một chỉ số của SHIFT. Các giá trị trong bảng SHIFT xác
định bằng cách dịch chuyển lên phía trước (bỏ qua) trong khi quét văn bản. Đặt
nếu "X" không có mặt trong bất kỳ mẫu nào.
20

X = x
1
x
b
lần lượt là các ký tự B trong văn bản đang quét, và giả sử rằng X là
ánh xạ thứ i’ của SHIFT. Có hai trường hợp:
1. X không xuất hiện như một chuỗi con trong bất kỳ mẫu nào của P.
Trong trường hợp này, ta dịch chuyển m-B+1 ký tự trong văn bản. Ta lưu
trữ m-B+1 trong SHIFT[i].
2. X xuất hiện trong một số mẫu.
Trong trường hợp này, ta sẽ thấy sự xuất hiện ở vị trí ngoài cùng bên phải

Khi giá trị dịch chuyển lớn hơn 0, chúng ta có thể dịch chuyển một cách
an toàn và tiếp tục quét. Ví dụ, các giá trị dịch chuyển tiêu tốn khoảng 0%-5%
thời gian cho 100 mẫu, 27% cho 1000 mẫu, và 53% cho 5000 mẫu. Nếu không,
nó có thể là chuỗi con trong văn bản hiện hành phù hợp với một số mẫu trong
danh sách mẫu. Tuy nhiên, để tránh việc phải so sánh tất cả các chuỗi con trong
danh sách mẫu, ta sử dụng kỹ thuật băm để giảm thiểu số lượng mẫu so sánh.
Người ta đã tính toán sắp xếp các ký tự B vào một số nguyên và sử dụng nó như
là một chỉ số của bảng SHIFT. Ta sử dụng các số nguyên chính xác cùng chỉ số
vào một bảng, gọi là bảng HASH. Mục thứ i của HASH, HASH[i], có chứa một
con trỏ trỏ đến một danh sách các mẫu mà ký tự cuối B băm vào i. Các bảng
HASH thông thường chỉ chứa mẫu trong khi bảng SHIFT chứa tất cả các chuỗi
có thể có của B. Điều này sẽ làm tốn bộ nhớ, nhưng nó cho phép chúng ta tái sử
dụng hàm băm, do đó tiết kiệm rất nhiều thời gian. 21

Đặt h là giá trị hash của các hậu tố trong văn bản hiện hành và cho
SHIFT[h] = 0. Giá trị HASH[h] là một con trỏ p trỏ đến hai bảng riêng biệt tại
cùng một thời gian: ta lưu trữ danh sách các con trỏ trỏ đến các mẫu,
PAT_POINT, sắp xếp theo các giá trị hash của các ký tự B cuối cùng của mỗi
một mẫu. Con trỏ p trỏ vào đầu danh sách các mẫu có giá trị băm là h. Để tìm
giá trị cuối của danh sách này, ta tăng giá trị con trỏ cho đến khi nó bằng giá trị
HASH[h +1] (bởi vì toàn bộ danh sách được sắp xếp theo các giá trị hash). Vì
vậy, nếu SHIFT[h] # 0, thì HASH[h]=HASH[h +1].
Ngoài ra để sắp xếp các ký tự B cuối cùng của tất cả các mẫu, ta cũng
phải sắp xếp các ký tự B đầu tiên của tất cả các mẫu vào bảng PREFIX (ta thấy
rằng B = 2 là một giá trị tốt). Khi chúng ta tìm thấy một giá trị SHIFT=0 và đi
vào bảng HASH để xác định nếu có 1 đối sánh, ta sẽ kiểm tra các giá trị trong
bảng PREFIX. Bảng HASH không chỉ chứa các hậu tố, danh sách của tất cả các