Ktl-icon-tai-lieu

Một họ thuật toán sánh mẫu Wu-Manber và thực nghiệm

Được đăng lên bởi bai-tap-on-thi
Số trang: 11 trang   |   Lượt xem: 2201 lần   |   Lượt tải: 1 lần
Một họ thuật toán sánh mẫu Wu-Manber và
thực nghiệm
Nguyễn Thị Thúy
Trường Đại học Công nghệ
Luận văn ThS. ngành: Hệ thống thông tin; Mã số: 60 48 05
Người hướng dẫn: PGS.TS. Hà Quang Thụy
Năm bảo vệ: 2012
Abstract. Chương 1: Bài toán và thuật toán sánh mẫu: giới thiệu chung về bài toán
sánh mẫu, cho thấy một lượng lớn thuật toán sánh mẫu đã được đề xuất. Các thuật
toán sánh mẫu được chia ra hai lớp chính là lớp thuật toán chính xác và lớp thuật
toán tương tự; giới thiệu một số thuật toán sánh mẫu điển hình nhất [CL00]. Chương
2: Họ thuật toán Wu - Manber: Giới thiệu thuật toán sánh mẫu văn bản chính xác
WM được Sun Wu và Udi Manber công bố vào năm 1994 [WM94] với ý tưởng kết
hợp cách thức nhảy của thuật toán BM do R. S. Boyer và J. S. Moore [BM77] và
hàm băm. Một số phiên bản nâng cấp thuật toán WM được phân tích trong chương
này [SWG06, DX08, ZCP09, ZCP09a]. Chương 3: Thực nghiệm: sử dụng công cụ
phần mềm Agrep để thi hành thực nghiệm thuật toán sánh mẫu WM; thực nghiệm
sánh mẫu cho 60 cặp file (mẫu, văn bản). Thực nghiệm cho thấy công cụ Agrep thi
hành thuật toán chính xác với thời gian nhanh.
Keywords. Thuật toán; Công nghệ thông tin; Phần mềm Agrep; Thuật toán sánh
mẫu
Content
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
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.
1.2. Phát biểu bài toán
Như đã giới thiệu, đối sán...
Mt h thuật toán sánh mẫu Wu-Manber và
thc nghim
Nguyn Th Thúy
Trường Đại hc Công nghệ
Luận văn ThS. ngành: H thống thông tin; Mã số: 60 48 05
Người hướng dn: PGS.TS. Hà Quang Thụy
Năm bảo v: 2012
Abstract. Chương 1: Bài toán thut toán sánh mu: gii thiu chung v bài toán
sánh mẫu, cho thy một lượng ln thuật toán sánh mẫu đã được đề xut. c thuật
toán sánh mẫu được chia ra hai lớp chính lớp thuật toán chính xác lớp thut
toán tương t; gii thiu mt s thuật toán sánh mẫu điển hình nht [CL00]. Chương
2: H thuật toán Wu - Manber: Gii thiu thut toán sánh mẫu văn bn chính xác
WM được Sun Wu Udi Manber công bố vào năm 1994 [WM94] với ý ng kết
hợp cách thức nhy ca thuật toán BM do R. S. Boyer J. S. Moore [BM77]
hàm băm. Một s phiên bản ng cấp thut toán WM được phân ch trong chương
này [SWG06, DX08, ZCP09, ZCP09a]. Chương 3: Thực nghim: s dụng công cụ
phn mềm Agrep để thi hành thực nghim thuật toán sánh mẫu WM; thc nghim
sánh mẫu cho 60 cp file (mẫu, văn bản). Thc nghim cho thy công cụ Agrep thi
hành thuật toán chính xác với thi gian nhanh.
Keywords. Thuật toán; Công nghệ thông tin; Phn mm Agrep; Thuật toán sánh
mu
Content
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
Dng ph biến nht của bài toán tìm kiếm văn bản là: Cho trước nguồn tìm kiếm
mt tp D các n bản (hoặc là cơ sở d liệu văn bản, hoặc 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à mt t, một xâu văn bản ngắn), y tìm tất c các
văn bản thuc D mà có chứa q. Trong nhiều trường hp (chng hạn, tìm kiếm thông qua máy
tìm kiếm) thì q còn được gọi "truy vấn" bài toán còn tên gọi "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 vn q, h thống tìm kiếm cn phi kim
tra văn bn truy vn q là mt xâu con của các văn bản thuc tp D hay không (sánh mẫu)
và đưa ra các văn bn đáp ng. Trong nhiều trường hợp, i toán còn đòi hỏi tìm tất c các v
trí của các u con trong n bn trùng với q. Đồng thi, điều kiện tìm kiếm có th được làm
"xp xỉ" theo nghĩa n bản kết qu thể không cần cha q (không cần có mt xâu con ca
Một họ thuật toán sánh mẫu Wu-Manber và thực nghiệm - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Một họ thuật toán sánh mẫu Wu-Manber và thực nghiệm - Người đăng: bai-tap-on-thi
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
11 Vietnamese
Một họ thuật toán sánh mẫu Wu-Manber và thực nghiệm 9 10 701