KHOA CÔNG NGHỆ THÔNG TIN
_______________ _______________
BÀI TẬP LỚN MÔN HỌC
MÔN HỌC: PHÂN TÍCH VÀ ĐÁNH GIÁ THUẬT TOÁN
ĐỀ TÀI: THUẬT TOÁN ĐỐI SÁNH MẪU AHO-CORASICK
Người hướng dẫn : TS Đào Thanh Tĩnh
Người thực hiện : Hồ Sỹ Tấn
Lớp : CHHTTT25B13
HÀ NỘI, THÁNG 05 - 2014
Thuật toán đối sánh mẫu Aho-Corasick
LỜI NÓI ĐẦU
Hiện nay, máy tính đã thâm nhập vào hầu hết các lĩnh vực của xã hội. Việc
số hóa dữ liệu, lưu trữ và xử lý các văn bản trên máy tính là một việc làm hết
sức quan trọng.
Trong một hệ xử lý văn bản, các thuật toán xử lý xâu ký tự được coi là yếu
tố quan trọng trong việc nâng cao hiệu quả về thời gian, độ chính xác khi xử lý
một văn bản. Trong các phép toán cơ bản trên chuỗi ký tự, phép toán đối sánh
chuỗi luôn được chú trọng phát triển, đặc biệt là trong điều kiện các dữ liệu văn
bản ngày càng nhiều.
Bài toán đối sánh chuỗi ký tự có thể được đặc trưng như một bài toán tìm
kiếm, trong đó mẫu P được xem như khoá, tuy nhiên các thuật toán tìm kiếm
thông thường không áp dụng được một cách trực tiếp vì mẫu P có thể dài và nó
trải trên văn bản theo một cách không biết trước. Đây là một bài toán thú vị và
đã có nhiều thuật toán khác nhau được đưa ra để giải quyết nó như Brute-Force
PHẦN II - THUẬT TOÁN AHO-CORASICK.......................................................................................................... 7
1. GIỚI THIỆU VỀ THUẬT TOÁN
7
2. PHÂN TÍCH THUẬT TOÁN
7
2.1. Máy tìm kiếm mẫu...................................................................................................................................7
2.2. Xây dựng hàm goto, failure và output...................................................................................................10
2.3. Đánh giá độ phức tạp của thuật toán....................................................................................................14
3. ỨNG DỤNG CỦA THUẬT TOÁN AHO-CORASICK
16
3.1. Ứng dụng trong các hệ phát hiện xâm nhập (IDS).................................................................................16
3.2. Phát hiện đạo văn...................................................................................................................................17
3.3. Tin sinh học.............................................................................................................................................17
3.4. Kỹ thuật Forensics...................................................................................................................................17
3.5. Khai thác văn bản..................................................................................................................................18
PHẦN III - CÀI ĐẶT CHƯƠNG TRÌNH THỬ NGHIỆM........................................................................................ 19
1. MÔ TẢ CHƯƠNG TRÌNH THỬ NGHIỆM
3. CHẠY THỬ NGHIỆM CHƯƠNG TRÌNH
4. MỘT VÀI NHẬN XÉT VỀ CHƯƠNG TRÌNH THỬ NGHIỆM
19
20
23
KẾT LUẬN..................................................................................................................................................... 24
TÀI LIỆU THAM KHẢO................................................................................................................................... 25
3
hãy chỉ ra vị trí trong T mà tại đó chuỗi mẫu P được tìm thấy.
Cụ thể hơn chuỗi mẫu P được tìm thấy trong T bắt đầu từ vị trí s+1 thì 0 ≤
s ≤ n-m và T(s,...,s+m) = P(1...m) tức là T(s + j) = P(j) với 1≤ j ≤ m và s được
gọi là giá trị dịch chuyển. Còn trong trường hợp ngược lại (tức là không tìm thấy
mẫu P trong T), s được gọi là giá trị dịch chuyển không hợp lệ.
4
Thuật toán đối sánh mẫu Aho-Corasick
3. MỘT SỐ THUẬT TOÁN ĐỐI SÁNH MẪU
3.1. Thuật toán Brute Force
Thuật toán so sánh tuần tự giản đơn (Brute Force) thử kiểm tra tất cả các vị
trí trên văn bản từ 0 cho đến n-m. Sau mỗi lần thử thuật toán Brute Force dịch
mẫu sang phải một ký tự cho đến khi kiểm tra hết văn bản. Thuật toán Brute
Force không cần giai đoạn tiền xử lý cũng như các mảng phụ cho quá trình tìm
kiếm. Độ phức tạp tính toán của thuật toán này là O(n*m).
3.2. Thuật toán Knuth-Morris-Pratt
Thuật toán Knuth-Morris-Pratt (KMP) 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.
3.3. Thuật toán automat hữu hạn
Trong lớp thuật toán dạng này, quá trình tìm kiếm được đưa về một quá
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.
3.6. Các thuật toán khác
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
hành tìm kiếm trên mỗi tập với một chiều khác nhau.
- Thuật toán Optimal Mismatch và Maximal Shift sắp xếp thứ tự mẫu dựa
vào mật độ của ký tự và khoảng dịch được.
- Thuật toán Skip Search, KMP Skip Search và Alpha Skip Search dựa sự
phân bố các ký tự để quyết đinh vị trí bắt đầu của mẫu trên văn bản.
Các thuật toán sánh mẫu theo thứ tự bất kỳ. Đó là các thuật toán có thể tiến
hành sánh mẫu với cửa sổ theo một thứ tự ngẫu nhiên. Đặc trưng là họ thuật
toán sánh mẫu văn bản Wu-Manbers (ký hiệu là WM) được Sun Wu và Udi
Manber công bố vào năm 1994 [WM94]. Các tác giả sử dụng các ý tưởng nhảy
của thuật toán BM do R. S. Boyer và J. S. Moore [BM77] và hàm băm.
6
Thuật toán đối sánh mẫu Aho-Corasick
PHẦN II - THUẬT TOÁN AHO-CORASICK
1. GIỚI THIỆU VỀ THUẬT TOÁN
Thuật toán tìm kiếm chuỗi kết hợp Aho-Corasick được xây dựng bởi Alfred
V. Aho and Margaret J. Corasick. Đây là một thuật toán đơn giản và hiệu quả
lý chuỗi văn bản x bằng cách liên tục đọc các ký tự trong x, thay đổi trạng thái
và liên tục đưa ra kết quả . Máy này gồm có 3 hàm: goto g, failure f, và output.
7
Thuật toán đối sánh mẫu Aho-Corasick
Hình 1 biểu diễn máy so khớp mẫu trạng thái sử dụng các hàm với một bộ từ
khóa {he, she, his, hers}.
Hình 1: Máy so khớp mẫu trạng thái hữu hạn.
Trong Hình 1 có 9 trạng thái là 0,1,…, 9, trong đó trạng thái 0 luôn được
thiết kế là trạng thái bắt đầu. Hàm goto g ánh xạ với trạng thái và ký tự của trạng
thái đó hoặc thông báo fail. Hình 1(a) mô tả về hàm goto. Ví dụ, mũi tên trỏ từ
trạng thái 0 đến 1 được gán nhãn h nên g(0, h) = 1. Trái lại nếu không có mũi
tên này thì kết quả là fail. Do vậy với tất cả các ký tự đầu vào khác e và i thì
g(0, ) = fail. Tất cả các máy so khớp mẫu đều được xây dựng thỏa mãn g(0, )
fail với tất cả các ký tự đầu vào là . Chúng ta sẽ thấy đặc điểm này trong hàm
goto tại trạng thái 0 để đảm bảo rằng đối với mỗi ký tự đầu vào sẽ được máy so
khớp mẫu xử lý trong mỗi chu kỳ máy.
Hàm failure f ánh xạ một trạng thái vào một trạng thái. Hàm failure được
truy vấn bất cứ khi nào hàm goto trả về kết quả fail. Khi trạng thái đầu ra đã xác
định có nghĩa là tập từ khóa được tìm thấy. Hàm output là sự kết hợp của một bộ
các từ khóa (có thể rỗng) với mỗi trạng thái.
Một chu kỳ hoạt động của một máy so khớp mẫu được định nghĩa như sau.
Giả sử s là trạng thái hiện tại của máy và a là ký tự hiện tại của chuỗi văn bản
đầu vào x.
1. Nếu g(s, a) = s', máy sẽ thực hiện goto transition (quá trình chuyển tiếp
của hàm goto). Máy sẽ nhập vào trạng thái s' và ký tự tiếp theo của x là ký tự
8
Đầu ra: Vị trí của các từ khóa xuất hiện trong x.
Phương thức:
begin
state = 0;
for i= 1 to n do
begin
while g(state,ai)= fail do state = f(state);
state = g(state,ai);
9
Thuật toán đối sánh mẫu Aho-Corasick
if output(state) != empty then
begin
print i;
print output(state);
end
end
end
Trong thuật toán trên, mỗi vòng lặp for là một chu kỳ hoạt động của máy.
2.2. Xây dựng hàm goto, failure và output
Chúng ta nói rằng ba hàm g, f và output là hợp lệ với một bộ các từ khóa
nếu với các hàm này đưa ra điểm kết thúc từ khóa y tại vị trí i của chuỗi văn bản
x khi và chỉ khi x = uyv và độ dài của uy là i.
Bây giờ chúng ta sẽ xem làm thế nào để xây dựng các hàm goto, failure và
output hợp lệ với một bộ các từ khóa. Quá trình xây dựng gồm có hai phần.
Phần thứ nhất, chúng ta sẽ xác định trạng thái và hàm goto. Phần thứ hai, chúng
ta sẽ tính toán hàm failure. Việc tính toán hàm output được bắt đầu trong phần
thiện việc xây dựng hàm goto, chúng ta thêm một vòng lặp từ trạng thái 0 đến
trạng thái 0 đối với tất cả các ký tự đầu vào khác h và s. Như vậy, chúng ta đã
xây dựng xong một đồ thì có hướng đã được chỉ ra trên hình 1(a). Đồ thị này đại
diện cho hàm goto.
Hàm failure được xây dựng từ hàm goto. Định nghĩa độ sâu của trạng thái s
trong đồ thị goto là độ dài đường dẫn ngắn nhất từ trạng thái bắt đầu tới s. Trong
hình 1(a), trạng thái bắt đầu có độ sâu là 0, trạng thái 1 và 3 là 1, trạng thái 2,4
và 6 là 2,…
11
Thuật toán đối sánh mẫu Aho-Corasick
Chúng ta sẽ tính toán hàm failure cho tất cả các trạng thái có độ sâu là 1, 2,
… và cứ tiếp tục như thế cho đến khi hàm failure tính toán xong cho tất cả các
trạng thái (ngoại trừ trạng thái 0 thì hàm failure không định nghĩa).
Thuật toán để tính toán hàm failure f tại một trạng thái được trình bày khá
đơn giản. Chúng ta đặt f(s) = 0 cho tất cả các trạng thái s có độ sâu là 1. Bây giờ,
giả sử f đã tính toán cho tất cả các trạng thái có độ sâu nhỏ hơn d. Trạng thái có
độ sâu d được xác định từ giá trị nonfail của hàm goto tới trạng thái có độ sâu d
- 1.
Cụ thể, để tính toán hàm failure cho trạng thái có độ sâu d, chúng ta xem
xét một trạng thái r có độ sâu d-1 và thực hiện như sau:
1. Nếu g(r, a) = fail với mọi a, không làm gì cả.
2. Ngược lại, với mỗi một ký tự a sao cho g(r, a) = s chúng ta thực hiện:
a. Gán state = f(r).
b. Thực hiện gán state
f(state) cho đến khi giá trị của state thỏa mãn
g(state, a) fail. (Chú ý rằng do g(0,a) fail với mọi a nên một trạng thái sẽ
luôn luôn được tìm thấy).
begin
newstate = 0;
for i=1 to k do enter(yi);
for (tất cả a mà g(0,a)=fail)do g(0,a) = 0;
end
procedure enter (a1a2a3…am)
begin
state = 0;
j = 1;
while g(state,aj) != fail do
begin
state = g(state,aj);
j = j + 1;
end
for p=j to m do
begin
newstate = newstate + 1;
g(state, ap) = newstate;
state = newstate;
end
output(state) = {a1a2…am};
end
Thuật toán sau sẽ tính toán hàm failure và thuật toán này có vòng lặp bên
trong giống thuật toán 1.
Thuật toán 3: Xây dựng hàm failure
Đầu vào: Hàm goto g và hàm output từ Thuật toán 2;
Đầu ra: Hàm failure f
và hàm output;
Vòng lặp for đầu tiên tính toán các trạng thái có độ sâu là 1 và nhập các
trạng thái vào danh sách vào trước – ra trước được ký hiệu bởi biến queue. Vòng
lặp chính while tính toán các trạng thái có độ sâu d từ các trạng thái có độ sâu d1.
Thuật toán 3 tính toán hàm failure không tối ưu trong các trường hợp sau.
Xem xét máy so khớp mẫu ở hình 1, chúng ta có thể nhìn thấy g(4, e) = 5. Nếu
M đang ở trạng thái 4 và ký tự đầu vào hiện tại là a không phải là e, thì M sẽ
nhập trạng thái f(4)=1. Bởi vì M đã xác định được
, nên M sẽ không cần
xem xét giá trị của hàm goto tại trạng thái 1 là e. Thực tế, nếu từ khóa "his"
không được đưa vào thì M có thể trực tiếp chuyển từ trạng thái 4 về trạng thái 0
và bỏ qua quá trình chuyển tiếp trung gian đến trạng thái 1.
Để tránh quá trình chuyển tiếp hàm failure không cần thiết ta có thể sử
dụng f' như sau. Chúng ta gán f'(1) = 0, với i > 1 và f'(i) = f'(f(i)) nếu tất cả các
ký tự đầu vào a thỏa mãn g(f(i), a) fail tức là g(i, a) fail; mặt khác f'(i) = f(i).
Tuy nhiên để tránh việc đánh dấu các quá trình chuyển tiếp failure tại tất cả các
vị trí, ta có thể sử dụng máy trạng thái hữu hạn xác định sử dụng thuật toán 1.
2.3. Đánh giá độ phức tạp của thuật toán
Chúng ta sẽ xem xét độ phức tạp tính toán của thuật toán 1, 2, 3. Phần này
sẽ trình bày cách sử dụng các hàm goto, failure, output và sự thay đổi trạng thái
trong quá trình xử lý chuỗi văn bản độc lập với số lượng các từ khóa. Ngoài ra
chúng ta cũng tìm hiểu làm thế nào để thuật toán 2 và 3 có thể thực hiện trong
thời gian tỉ lệ tuyến tính với tống chiều dài của các từ khóa trong tập K.
Định lý 1: Sử dụng hàm goto, failure, output được xây dựng bởi thuật toán
2, 3; thuật toán 1 tạo ra ít hơn 2n quá trình chuyển tiếp trạng thái trong việc xử
lý một chuỗi văn bản có độ dài n.
Chứng minh: Trong mỗi chu kỳ hoạt động, sau một quá trình chuyển tiếp
của hàm goto thì thuật toán 1sẽ tạo ra 0 hoặc nhiều quá trình chuyển tiếp của
hàm failure. Từ một trạng thái s có độ sâu là d, thuật toán 1 có thể không bao giờ
tạo ra nhiều hơn d quá trình chuyển tiếp failure trong một chu kỳ hoạt động. Bởi
vậy, tổng số lần quá trình chuyển tiếp failure phải ít hơn tổng số lần quá trình
thể được xác định trong một thời gian cụ thể đối với mỗi trạng thái s.
Bởi vậy, phần không được biểu diễn của thuật toán 1 có thể được bổ sung
để xử lý một chuỗi văn bản có độ dài n trong cn bước, với c là một hằng số
không phụ thuộc vào số các từ khóa.
Bây giờ chúng ta sẽ đi xem xét về thời gian cần thiết để biểu diễn đầu ra.
Chúng ta có thể sử dụng mảng một chiều để xác định giá trị output(s) là rỗng
trong một thời gian cụ thể đối với mỗi trạng thái s. Chi phí cho việc biểu diễn
kết quả đầu ra trong mỗi chu kỳ hoạt động tỷ lệ với tổng các độ dài của các từ
khóa trong output(s) với s là trạng thái mà thuật toán 1 kết thúc chu kỳ vận hành.
Trong nhiều ứng dụng đầu ra output(s) thường chứa một từ khóa, bởi vậy thời
gian cần thiết để biểu diễn kết quả đầu ra tại mỗi vị trí là hằng số.
Tuy nhiên, trong trường hợp một số lượng lớn các từ khóa xuất hiện tại mọi
vị trí của chuỗi văn bản thì thuật toán 1 sẽ mất nhiều thời gian để biểu điễu kết
quả đầu ra. Trong trường hợp xấu nhất, chúng ta có thể phải biểu diễu tất cả các
từ khóa trong K tại hầu hết các vị trí trong chuỗi văn bản. (Xem xét trường hợp
15
Thuật toán đối sánh mẫu Aho-Corasick
sau với
, và chuỗi văn bản là , ở đây kí hiệu cho chuỗi i:
). Tuy nhiên, với bất kỳ thuật toán so khớp mẫu nào chúng ta cũng phải biểu
diễn số lượng các từ khóa tại mỗi một vị trí của chuỗi văn bản là giống nhau. Vì
vậy, khi so sánh các thuật toán so khớp mẫu chúng ta phải so sánh thời gian
thuật toán sử dụng để xác định vị trí từ khóa xuất hiện.
Ngoài ra chúng ta cũng so sánh hiệu suất của thuật toán 1 với thuật toán
xác định tất cả các từ khóa trong K, mà các từ khóa này là chuỗi con của văn
bản đầu vào. Theo thuật toán này, ta có thể lấy lần lượt mỗi từ khóa trong K và
liên lục tìm từ khóa này tại tất cả các vị trí trong chuỗi văn bản. Thời gian thực
hiện thuật toán tỷ lệ thuận với số lượng các từ khóa trong K lần độ dài chuỗi văn
biết đến. Phát hiện sự xâm nhập hệ thống được phân loại như: xâm nhập dựa
trên chữ ký của hệ thống và những bất thường của hệ thống. Những kẻ xâm
16
Thuật toán đối sánh mẫu Aho-Corasick
nhập đã ký kết, như virut máy tính có thể được phát hiện sử dụng phần mềm.
Snort là một mã nguồn mở IDS sẵn sàng cho người sử dụng. NIDS là hệ thống
phát hiện xâm nhập nắm bắt các gói dữ liệu đang di chuyển trên các phương tiện
truyền thông mạng và kết hợp chúng vào một cơ sở dữ liệu chữ ký. Các hệ thống
phát hện sự xâm nhập sử dụng thuật toán tìm kiếm Aho-Corsick tìm thấy tất cả
các lần xuất hiện của mô hình trong một chuỗi văn bản.
3.2. Phát hiện đạo văn
Phát hiện đạo văn là quá trình tìm kiếm đạo văn trong một tác phẩm hoặc
tài liệu. Đạo văn là hành vi sao chép ý tưởng của người khác, đây là một vấn đề
nghiêm trọng đang phải đối mặt trên thế giới hiện nay. Nhiều loại đạo văn đã
được nghiên cứu như: “Copy & Paste plagiarism”, “Word Switch Plagiarism”,
Styte Plagiarism”, “Metaphor Plagiarism”, “Idea Plagiarism”.
3.3. Tin sinh học
Sinh học là khoa học nghiên cứu về sinh học với các phương pháp lưu trữ,
lấy và phân tích dữ liệu sinh học , chẳng hạn như axit nucleic (DNA/RNA) và
trình tự protein , cấu trúc , chức năng và tương tác di truyền. Tin sinh học là
miền công nghệ thông tin và khoa học máy tính kỹ thuật liên quan đến việc giải
quyết các vấn đề sinh học, thường là để giải quyết vấn đề trong trình tự gen .
Một trong những ứng dụng của chuỗi thuật toán kết hợp là xử lý việc tìm kiếm
thông tin trình tự sinh học. Phù hợp gần đúng với một mô hình tìm kiếm trong
chuỗi văn bản là một nhu cầu cơ bản trong phân tử sinh học. Mô hình được gọi
là "truy vấn" và văn bản được gọi là " Cơ sở dữ liệu trình tự " , nhưng chúng tôi
sẽ sử dụng " mô hình" và "văn bản" phù hợp với việc sử dụng trong khoa học
máy tính . Trong khi chuỗi thuật toán chính xác, phù hợp thường được sử dụng
toán 3) ở trên được cài đặt bằng ngôn ngữ C++ có thể biên dịch và chạy trên
Bloodshed Dev C++ IDE hoặc một trình biên dịch hỗ trợ C++ tương đương.
Toàn bộ chương trình được lưu trong tệp /SOURCE/AhoCorasick.cpp kèm
theo báo cáo này.
Nội dung của chương trình gồm 3 phương thức:
int buildMatchingMachine(const vector<string> &words, char
lowestChar = 'a', char highestChar = 'z')
int findNextState(int currentState, char nextInput, char
lowestChar = 'a')
int main()
Phương thức buildMatchingMachine
Phương thức đảm này nhiệm việc xây dựng máy so khớp mẫu. Tham số
đầu vào của phương thức là một vector dạng chuỗi ký tự chứa tập các từ khóa
(keyword) cần tìm. Ngoài ra, có hai tham số lowestChar và highestChar để giới
hạn tập ký tự của bảng chữ cái được sử dụng trong văn bản cần tìm. Phương
thức này trả về số trạng thái của máy so khớp mẫu.
Các hàm goto g, failure f và output mô tả trong thuật toán được thi công
trong phương thức này.
Phương thức findNextState
Phương thức này đảm nhiệm việc tìm trạng thái tiếp theo trong máy so
khớp mẫu để chuyển giao tác xử lý đến trạng thái đó.
Các tham số của phương thức:
- currentState: Trạng thái hiện tại của máy so khớp, nhận giá trị từ 0 đến
tổng số trạng thái trừ 1.
- nextInput: Ký tự tiếp theo nhập vào máy, giá trị nằm trong khoảng
lowestChar và highestChar.
- lowestChar: Ký tự đầu tiên của bảng chữ cái, tương đương giá trị
lowestChar trong phương thức buildMatchingMachine.
Phương thức main
became
indochina
- Nội dung tệp document.txt như sau:
20
Thuật toán đối sánh mẫu Aho-Corasick
vietnamvietnamesepronunciationlistenofficiallythesocialistrepu
blicofvietnamaboutthissoundlistenistheeasternmostcountryonthei
ndochinapeninsulainsoutheastasiawithanestimatedmillioninhaviet
namwasachinesecolonyforamillenniumfrombctoadthevietnamesebecam
eindependentfromimperialchinainadfollowingthevietnamesevictory
in
Để chạy chương trình, gọi Command Shell của Windows và chuyển đến
thư mục chứa tệp AhoCorasick.exe.
Chạy tệp AhoCorasick.exe, kết quả xuất ra Console và tệp output.txt.
Có thể xem kết quả trong tệp output.txt.
Searching keywords:
vietnamese
21
Thuật toán đối sánh mẫu Aho-Corasick
victory
french
Độ dài chuỗi văn bản
Thời gian
Lần 1
10
17.500
~ 1 giây
Lần 2
10
50.000
~ 2 giây
Lần 3
10
100.000
~ 3 giây
Lần 4
Lần 9
15
500.000
~ 20 giây
Lần 9
18
500.000
~ 25 giây
Lần 10
20
500.000
~ 33 giây
22
Thuật toán đối sánh mẫu Aho-Corasick
hiện thực như phát hiện sự xâm nhập, đạo văn, tin sinh học, pháp y kỹ thuật số,
văn bản khai thác và nhiều hơn nữa. Aho-Corsick là một trong nhữngthuật toán
hiệu quả trong khoa học máy tính.
Môn học phân tích và thiết kế thuật toán là môn học rất cơ bản và rất quan
trọng với sinh viên ngành công nghệ thông tin. Thuật toán cùng với cấu trúc dữ
liệu tạo nên chương trình. Việc chọn lựa cấu trúc dữ liệu, việc thiết lập các thuật
toán đúng đắn, có cấu trúc tốt và có hiệu quả là những vấn đề mấu chốt của việc
thiết kế phần mềm. Hai khía cạnh này của việc phát triển phần mềm có tầm quan
trọng như nhau và trong thực tế không thể tách rời nhau, cái này không thể thực
hiện một cách độc lập với cái kia. Qua phần bài tập lớn này đã giúp chúng tôi
hiểu hơn về phương pháp phân tích thiết kế thuật toán và ý nghĩa của nó trong
việc xây dựng phần mềm. Một lần nữa cho phép chúng tôi được cảm ơn thầy
giáo Đào Thanh Tĩnh đã giúp chúng tôi trong suốt thời gian học tập môn học
cũng như giải đáp các thắc mắc, cho tôi một cách nhìn, một phương pháp luận
đúng đắn về phương pháp phân tích thiết kế giải thuật.
24
Thuật toán đối sánh mẫu Aho-Corasick
TÀI LIỆU THAM KHẢO
[1]
Đào Thanh Tĩnh, “Bài giảng môn Phân tích đánh giá thuật toán”.
[2]
Alfred V.Aho and Margaret J.Corasick, “Efficient string matching:
An aid to biblographic search”, Bell Laboratories, 1975.
[3]
Copyright: Tài liệu đại học ©