Bài giảng Tìm kiếm và trình diễn thông tin - Bài 20: Thu thập dữ liệu - Nguyễn Bá Ngọc

Nội dung text: Bài giảng Tìm kiếm và trình diễn thông tin - Bài 20: Thu thập dữ liệu - Nguyễn Bá Ngọc

1. (IT4853) Tìm kiếm và trình diễn thông tin Thu thập dữ liệu
2. Giảng viên  TS. Nguyễn Bá Ngọc  Địa chỉ: Viện CNTT & TT/BM HTTT/B1-603  Email: ngocnb@soict.hust.edu.vn  Website: 2
3. Nội dung chính  Bộ thu thập đơn giản  Bộ thu thập trong thực tế 3
4. Thu gom dữ liệu khó tới đâu?  Máy tìm kiếm phải tự động thu gom dữ liệu.  Thu gom dữ liệu trên Web rất phức tạp:  Ví dụ, đánh chỉ mục tất cả tệp trên ổ đĩa cứng: chỉ thực hiện duyệt đệ quy trên hệ thống tệp;  Cần nhiều thời gian. 4
5. Thao tác thu thập thông tin cơ bản  Khởi tạo hàng đợi với URLs với tập trang mầm  Lặp  Lấy URL từ hàng đợi  Nạp và đọc trang web  Tách URLs từ trang web  Thêm URLs vào hàng đợi Giả thuyết cơ bản: Web là đồ thị liên thông. 5
6. Hạn chế của bộ thu thập sau là gì? urlqueue := (some carefully selected set of seed urls) while urlqueue is not empty: myurl := urlqueue.getlastanddelete() mypage := myurl.fetch() fetchedurls.add(myurl) newurls := mypage.extracturls() for myurl in newurls: if myurl not in fetchedurls and not in urlqueue: urlqueue.add(myurl) addtoinvertedindex(mypage) 6
7. Hạn chế của bộ thu thập đơn giản  Quy mô  Cần phân tán quá trình thu thập  Không thể đánh chỉ mục tất cả  Cần lựa chọn nội dung, tích hợp khả năng phát hiện trùng lặp và spam  Nguyên tắc lịch thiệp  Thời gian nghỉ giữa những yêu cầu gửi tới một địa chỉ  Tính cập nhật  Cần thu thập lại theo chu kỳ;  Web rất lớn, chỉ có thể thường xuyên thu thập một phần nhỏ; Vấn đề xác định độ ưu tiên là cấp thiết. 7
8. Quy mô của bài tóan thu thập  Nạp 20,000,000,000 trang mỗi tháng . . .  . . . cần nạp khoảng 8000 trang mỗi giây!  Thực tế: có thể cần nhiều hơn vì nhiều trang thu được sẽ trùng lặp, không tải được, spam v.v. 8
9. Robots.txt  Giao thức hạn chế quyền truy cập của chương trình duyệt web tự động (“robots”), được thiết lập từ 1994  Ví dụ:  User-agent: * Disallow: /yoursite/temp/  User-agent: searchengine Disallow: / 9
10. Ví dụ robots.txt (nih.gov) User-agent: PicoSearch/1.0 Disallow: /news/information/knight/ Disallow: /nidcd/ Disallow: /news/research_matters/secure/ Disallow: /od/ocpl/wag/ User-agent: * Disallow: /news/information/knight/ Disallow: /nidcd/ Disallow: /news/research_matters/secure/ Disallow: /od/ocpl/wag/ Disallow: /ddir/ Disallow: /sdminutes/ 10
11. Khuyến cáo  Thiết kế hệ thống phân tán  Khả mở:  Dễ mở rộng quy mô thu thập bằng cách thêm nhiều máy  Nạp những trang chất lượng cao trước  Thu thập liên tục  Thu thập phiên bản mới của những trang đã biết 11
12. Nội dung chính  Bộ thu thập đơn giản  Bộ thu thập trong thực tế 12
13. Hàng đợi URL 13
14. Hàng đợi URL  Hàng đợi URL: URL frontier  Hàng đợi URL là cấu trúc dữ liệu lưu trữ và quản lý URLs mà chúng ta đã thấy, nhưng chưa được thu thập.  Có thể bao gồm nhiều trang từ một máy chủ  Chánh nạp tất cả cùng lúc  Cần sử dụng tất cả các phân luồng thu thập 14
15. Kiến trúc tổng quát của bộ thu thập 15
16. Chuẩn hóa URL  Có nhiều URLs được trích rút từ tài liệu là những URLs tương đối.  Ví dụ, trong địa chỉ aboutsite.html  Tương đương với:  Cần phải chuẩn hóa tất cả các URLs tương đối thành dạng tuyệt đối. 16
17. Nội dung đã xem  Với mỗi trang được nạp: Kiểm tra liệu nội dung đã có trong chỉ mục  Kiểm tra dựa trên tổng đại diện hoặc biểu diễn khung  Bỏ qua những tài liệu có nội dung đã được đánh chỉ mục 17
18. Thu gom phân tán  Chạy nhiều phân luồng thu thập, có thể thực hiện ở những nút khác nhau  Có thể phân tán theo vị trí địa lý  Phân chia các máy chủ đang bị thu thập tới các nút khác nhau 18
19. Những trung tâm dữ liệu của Google (wazfaring. com) 19
20. Thu gom dữ liệu phân tán 20
21. Các điểm cần lưu ý với hàng đợi URL  Sự lịch thiệp: Không truy cập một máy chủ web quá thường xuyên  Ví dụ, chèn một khoảng thời gian giữa hai yêu cầu thành công được gửi đến cùng một máy chủ  Tính cập nhật:  Đảm bảo tính ưu tiên cho những trang quan trọng, thường xuyên thay đổi.  Đây là vấn đề khó, hàng đợi đơn giản sẽ không giải quyết được vấn đề này. 21
22. Hàng đợi URL của Mercator . Luồng URLs tới bộ nạp phải qua hai hàng đợi: phía trước và phía sau. . Hàng đợi phía trước quản lý độ ưu tiên. . Hàng đợi phía sau đảm bảo sự lịch thiệp. . Các hàng đợi là FIFO. 22
23. Hàng đợi phía trước . Bộ ưu tiên gán cho mỗi URL một độ ưu tiên nguyên trong khoảng từ 1 đến F. . Sau đó thêm URL vào hàng đợi tương ứng . Xác định độ ưu tiên bằng giải thuật tham lam: tốc độ cập nhật, PageRank v.v. 23
24. Hàng đợi phía trước . Hàng đợi phía sau gửi yêu cầu tới hàng đợi phía trước . Chọn một hàng đợi phía trước: Theo vòng, ngẫu nhiên, v.v. , đảm bảo sự ưu tiên đối với hàng đợi có mức ưu tiên cao . Lấy ra URL tiếp theo 24
25. Hàng đợi phía sau 25
26. Hàng đợi phía sau . Nguyên tắc 1. Mỗi hàng đợi phía sau được đảm bảo khác rỗng cho tới khi kết thúc thu thập. . Nguyên tắc 2. Mỗi hàng đợi phía sau chỉ chứa những URL từ một máy chủ. . Duy trì một bảng tham chiếu các máy chủ tới các hàng đợi phía sau. 26
27. Hàng đợi phía sau . Hệ thống còn lưu trong bộ nhớ heap một thời gian đợi cho mỗi hàng đợi phía sau . Thời gian đợi là thời gian te sớm nhất có thể gửi yêu cầu tới máy chủ tương ứng của hàng đợi phía sau. . Thời gian te sớm nhất được xác định dựa trên thời gian xử lý cuối cùng. 27
28. Hàng đợi phía sau . Bộ thu thập giao tiếp với hàng đợi phía sau như thế nào? . Lặp (i) lấy URL từ q hiện tại (q là một hàng đợi phía sau) . (ii) nạp URL u vào đầu hàng đợi q 28
29. Hàng đợi phía sau . Nếu q trở thành rỗng . Lặp (i) lấy những URL u từ hàng đợi phía trước và (ii) thêm u vào hàng đợi phía sau tương ứng của nó . Nếu u không có hàng đợi phía sau tương ứng, thì (i) tạo một hàng đợi mới, (ii) đưa u vào đó và (iii) thiết lập thời gian đợi cho hàng đợi mới tạo. 29