Bài giảng Tích hợp dữ liệu và XML - Chương 10: Đối sánh chuỗi

Bài giảng Tích hợp dữ liệu và XML - Chương 10: Đối sánh chuỗi. Chương này cung cấp cho sinh viên những nội dung gồm: giới thiệu; phát biểu bài toán; phương pháp tính độ tương đồng dựa trên chuỗi và dựa trên tập hợp;... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Tích hợp dữ liệu và XML - Chương 10: Đối sánh chuỗi 21/04/2013 Nội dung 1. Giới thiệu Đối sánh chuỗi 2. Phát biểu bài toán 3. Phương pháp tính ñộ tương ñồng 3.1. Dựa trên chuỗi Nguyễn Hồng Phương 3.2. Dựa trên tập hợp Email: phuong.nguyenhong@hust.edu.vn Site: http://is.hut.edu.vn/~phuongnh Bộ môn Hệ thống thông tin Viện Công nghệ thông tin và Truyền thông Đại học Bách Khoa Hà Nội 1 21. Giới thiệu 2. Phát biểu bài toán Là bài toán tìm các chuỗi trỏ tới cùng một Cho hai tập chuỗi X và Y; tìm tất cả các cặp thực thể trong thế giới thực. chuỗi (x, y), x∈X và y∈Y, sao cho x và y trỏ tới cùng thực thể thế giới thực. Ví dụ Chuỗi David Smith trong 1 CSDL có thể chỉ tới Gọi các cặp như vậy là các sánh ñôi (match) cùng một người David R. Smith trong CSDL Ví dụ: khác. Chuỗi 1210 W. Dayton St, Madison WI và 1210 Tập X Tập Y Sánh ñôi West Dayton, Madison WI 53706 cùng chỉ tới x1 = Dave Smith y1 = Dave D. Smith (x1,y1) một ñịa chỉ vật lý x2 = Joe Wilson y2 = Daniel W. Smith (x3,y2) x3 = Dan Smith Đối sánh chuỗi ñóng vai trò then chốt trong bài toán tích hợp dữ liệu, trích rút thông tin,… 3 4 3. Phương pháp tính ñộ tương ñồng Thách thức Độ tương ñồng s ánh xạ cặp (x,y) vào 1 Tính chính xác giá trị ∈[0,1] Lỗi chính tả s càng lớn thì x,y càng tương ñồng Định dạng khác nhau Thuật ngữ khác: khoảng cách, chi phí Tên khác nhau giá trị càng nhỏ thì ñộ tương ñồng càng cao => thước ño ñộ tương ñồng s(x,y)∈[0,1] Tính mở rộng Độ tương ñồng s mở rộng cho nhiều cặp của 2 tập X và Y => bùng nổ tích Đề-các => chỉ áp dụng s(x,y) với các bộ ñôi triển vọng 5 6 1 21/04/20133.1. Độ tương ñồng dựa trên chuỗi Phương pháp Edit Distance Coi các chuỗi là một dãy tuần tự các kí tự Còn gọi là khoảng cách Levenshtein Tính toán chi phí biến ñổi một chuỗi thành d(x,y) chi phí tối thiểu biến ñổi chuỗi x chuỗi kia thành chuỗi y Một số phương pháp Việc biến ñổi chuỗi sử dụng các thao tác Edit Distance sau: xóa một kí tự, chèn một kí tự, thay thế một Needleman-Wunch kí tự Affine Gap Ví dụ: chi phí biến ñổi chuỗi x=David Smith-Waterman Smiths thành chuỗi y=Davidd Simth là 4 Jaro Thêm d sau David; thay thế m bởi i; thay thế i Jaro-Winkler bởi m; xóa kí tự s cuối cùng d(x,y)=d(y,x) 7 8Phương pháp Edit Distance (tiếp) Phương pháp Edit Distance (tiếp) Mối quan hệ giữa hàm khoảng cách d(x,y) Giá trị của d(x,y) có thể ñược tính toán và hàm tương ñồng s(x,y) dựa trên qu ...