Chương 1: Tổng quan — Giới thiệu tổng quan, lý do hình thành, mục tiêu, đối tượng, phạm vi nghiên cứu, phương pháp nghiên cứu của đề tài. Chương 2: Cơ sở lý thuyết — Trinh bay tong quan về cơ sở lý thuyết và các nghiên cứu liên quan. Chương 3:Bài toán thu thập thông tin và phương pháp thực hiện - Trình bày mô hình của hệ thống, quá trình xây dựng hệ thống. Chương 4: Kết qua nghiên cứu — Trình bày kết quả của dé tài.
Chương 5: Kết luận - Kết luận từ kết quả nghiên cứu, nêu những hạn chế và hướng nghiên cứu tiếp theo cho đề tài. Chương2: CƠ SỞ LÝ THUYET Chương 2 trình bày tổng quan về lý thuyết bài toán thu thập thông tin, các nghiên cứu có liên quan làm cơ sở dé xây dựng hệ thống thu thập thông tin nhăm hỗ trợ cho người dùng.1 Giới thiệu web crawler: 2.1 Web crawler: Trinh thu thập web (Web crawler) là một chương trình máy tinh có thé duyệt website một cách tự động theo một phương thức nao đó được xác định trước thông qua URLs (Uniform Resource Locator). Web crawler cũng được xem như web spider hay web robot [5]. Hau hết các công cụ tìm kiếm online hiện nay đều sử dung quá trình nay để thu thập va cập nhập kho dữ liệu phục vụ nhu cầu tìm kiếm của người dùng.
Mục dich chung của các hệ thống search engine là số lượng trang web dau vảo dat giá tri cao nhất có thể, trong đó web crawler làm công việc chính là duy trì co sở dữ liệu được đánh chỉ mục, trả về giá trị của bộ thu thập và bộ lập chỉ mục để có thể cho kết quả nhanh hơn khi được tìm kiếm. Ví dụ như Google Crawler của Google, các website trên internet được Google Crawler duyệt qua và thu thập lại nội dung và lưu trữ trong cơ sở dữ liệu và được tìm kiếm khi có yêu cau từ phía người dùng. Ở Việt Nam, cũng có một số mô hình thu thập thông tin như: baomoi.com, phần mềm VietSpider. h World Wide h | Web ! Web pages | URLs Mioulti-threaded ! > Scheduler downloader l 3 F h Queue f§ 8 3 Ñ 5 Stora ge 3 | Hình 2.1: Kiến trúc chuẩn của web crawler [5].
> Queue: nhận danh sách dia chỉ cần crawling, lưu trữ, chuân hóa va chuyền cho Scheduler. > Scheduler: » Xac định mot thứ tự crawling cho các dia chi (ordering). = Phân bố các địa chi cho hệ thống crawler phân tán. =» Xác định thời gian để Re-crawling một địa chỉ.
Đề làm những nhiệm vụ này, Scheduler cần được xây dựng dựa trên các chính sách (crawling policies): = Selection Policies: xác định những địa chi nao cần được crawling dựa trên PageRank, nếu đã có trên máy chủ dựa vào Content. = Re-visit Policies: xác định khoảng thời gian để hệ thong crawling địa chỉ này lần tiếp theo dựa trên PageRank, Content. = Politeness Policies: xác định những khu vực cắm crawling: thông tin có giá trị thương mại, bản quyền. dựa trên giao thức robots exclusion protocol cho phép quản tri của webserver câu hình được khu vực nào crawler không thê vào.
= Parallelization Policies: cho phép tổ chức crawling song song và phân tán. Nguyên lý hoạt động của một crawler: xuất phát từ những trang cho trước gọi là hạt giống (seed pages)đây là những địa chỉ website muốn thu thập thông tin, và duyệt từ trang này đến trang khác thông qua những liên kết chứa trong những trang mà nó đi qua, quá trính này gọi là crawling. Crawler tổng hợp nội dung (văn bản và những liên kết) từ những website và lưu chúng vào trong cơ sở dữ liệu. “——=—-—-—-—--—~-~—-—~—--—-~—--—~--—-~--—~-——-—~-——-—~--—~~-——~—-—~~=—————~=——~———>~_~——~ = — —= = — m m — mm ee ——m I | : Initialize frontier with L seed URLs | [done] —( Check for termination) >@) end || [not done] | | + h C Pick URL » [no URL] ! from frontier [URL] | CLraowlinpg | C Fetch page › | C Parse page › | ( Add URLs » | to frontier Hình 2.2: Quy trình hoạt động cua crawler [6].1 Frontier: Là một danh sách công việc của một crawler hay còn gọi là To-do list.
Frontier dùng dé chứa những URL chưa được crawler duyệt qua. Ban dau Frontier chứa các URL hạt nhân do người dùng hoặc chương trình khác cung cấp. Mỗi vòng lặp crawling bao gồm: lay các URL tiếp theo cần được tải về từ Frontier, nap trang web tương ứng với URL bằng giao thức HTTP, tải nội dung trang web. Quá trình crawling kết thúc khi: > Đạt được điều kiện dừng ví dụ như SỐ lượng trang web tải về đáp ứng được yêu câu đặt ra.
> Danh sách các URL tai Frontier rỗng, không còn trang web yêu cầu crawler tải về. Frontier có thể coi như một hàng đợi làm việc theo cơ chế FIFO (First In First Out), vào trước ra trước trong trường hợp sử dụng thuật toán tìm kiếm theo chiều rộng (Breadth-First) để thu thập thông tin. Crawler sử dụng thuật toán tìm kiếm này gọi là thu thập theo chiều rộng. Các URL được lay ra thu thap duoc chon từ trên xuống dưới trong danh sách va các URL mới được thêm vào đuôi của danh sách.
Trong frontier, các URL chỉ được lay một lần. Dé tránh việc trùng lặp URL được trích xuất đã có trong danh sách chưa dùng hàm băm với URL là khóa. Hàm băm này sinh ra các giá trị băm tương ứng với mỗi URL. Sử dụng hàm băm sé tim kiếm nhanh hơn vì việc so sánh các giá trị băm nhanh hơn nhiều việc so sánh một giá trị với một khối dữ liệu lớn.
Khi frontier đạt đến miễn giới hạn, thì các trình thu thập theo chiều rộng sẽ làm việc theo cơ ché: sau khi đưa một URL ra khỏi frontier để tiễn hành quá trình thu thập trang tương ứng thay vì việc lấy tất cả URL trong trang này trình thu thập sẽ chỉ lay URL chưa thăm dau tiên và thêm vào frontier. Frontier có thé coi như một hàng đợi ưu tiên trong trường hợp sử dụng thuật toán tìm kiếm tối ưu (Best-First). Trinh thu thập sử dụng thuật toán tim kiếm này gọi là thu thập ưu tiên. Hàng đợi ưu tiên là một mảng với các phần tử các URL được sắp xếp theo điểm đánh giá.
Trình thu thập ưu tiên làm việc theo cơ chế: URL lay ra khỏi Frontier dé tiễn hành thu thập thông tin luôn là URL tốt nhất. Sau khi thu thập trang web tương ứng, các URL được trích xuất ra đưa vào Frontier và danh sách URL được sắp xếp lại theo thời điểm đánh giá. Dé tránh việc trùng lặp URL dùng hàm băm với URL là khóa. Khi frontier đạt đến miền giới hạn, cơ chế làm việc của trình thu thập tối ưu cũng giống với trình thu thập theo chiều rộng chỉ khác là các URL được lấy là các URL tốt nhất (URL có điểm đánh giá cao nhất).
Nhiều khi trình thu thập có thể bắt gặp spider trap dẫn nó đến một lượng lớn các URL khác nhau nhưng trỏ đến cùng một trang web. Một cách để giảm bớt van dé này là hạn chế số lượng trang mà các trình thu thập truy cập từ một tên miễn nhất định. Các mã liên kết với frontier có thể đảm bảo rằng trong một chuỗi liên kết các URL trong frontier sẽ chỉ chứa một URL từ một tên miền máy chủ. Như vậy trình thu thập sẽ tốt hơn bởi không truy cập vào cùng một trang quá thường xuyên và các trang truy cập cũng có xu hướng đa dạng hơn.2 Cách thức chuyển trang khi thu thập dữ liệu của crawler: Vấn đề cốt lõi hoạt động của crawler để lấy nội dung các trang web một cách tự động là dựa vào cách thức chuyền trang từ trang web này sang trang web khác, hoặc thay đối nội dung này sang nội dung khác trong cùng một trang web.
> Chuyén trang sử dung các phương thức HTTP GET, HTTP POST. Các trang web loại này không sử dụng JavaScript hoặc có su dung JavaScript nhưng không ảnh hưởng đến cách thức chuyển trang hoặc nội dung trang web. > Chuyển trang sử dung đến các đoạn mã nhúng client-side như JavaScript làm thay đổi cau trúc DOM hoặc nội dung bên trong của trang web. Ví dụ như: công nghệ Ajax sử dụng JavaScript để thực hiện các yêu cầu GET hoặc POST chỉ dé lay và nhận dữ liệu, dữ liệu nhận được từ máy chủ được JavaScript xử lý để hiển thị kết quả cho người dùng.2 Cac chiến lược thu thập dữ liệu: Quá trình thu thập web chính là quá trình duyệt đệ quy một đồ thị.
Các web được xem như một do thị với các trang là các đỉnh (node) và các siêu liên kết là các cạnh. Chính vì vậy các chiến lược thu thập dữ liệu cũng được xây dựng dựa trên các thuật toán tìm kiếm trên đồ thị. Các thuật toán tìm kiếm trên đồ thị: tìm kiếm theo chiêu sâu, tìm kiêm theo chiêu rộng và tìm kiêm ngâu nhiên [15]. > Chiến lược thu thập dữ liệu theo chiều sâu Từ một danh sách chứa các liên kêt cân duyệt, thực hiện các bước sau: (1) Cho danh sách = {trang đầu tiên} (2) Lay trang dau tiên trong danh sách.
- Nếu có, qua (3) - Nếu không, qua (5) (3) Trang này đã xét tới chưa ? - Nếu rồi, quay lại (2) - Nếu chưa, qua (4) (4) Đánh dấu trang này đã tới rồi. Phân tích và tìm các liên kết có trong trang đó không? - Nếu có, thêm liên kết này vào đầu danh sách. Chiến lược thu thập dữ liệu theo chiều rộng Từ một danh sách chứa các liên kêt cân duyệt, thực hiện các bước Sau: (1) Cho danh sách = {trang dau tiên} II (2) Lay trang đầu tiên trong danh sách - Nếu có, qua (3) - Nếu không, qua (5) (3) Trang này đã xét tới chưa? - Nếu rồi, quay lại (2) - Nếu chưa, qua (4) (4) Đánh dấu trang này đã tới rồi. Phân tích và tìm các liên kết có trong trang đó không? - Nếu có, thêm liên kết này vào cuối danh sách.
- Nếu không, quay lại (2) (5) Kết thúc. Chiến lược thu thập dữ liệu theo ngẫu nhiên Từ một danh sách chứa các liên kêt cân duyệt, thực hiện các bước Sau: (1) Cho danh sách = {trang đầu tiên} (2) Lay ngẫu nhiên một trang trong danh sách - Nếu có, qua (3) - Nếu không, qua (5) (3) Trang này đã xét tới chưa? - Nếu rồi, quay lại (2) - Nếu chưa, qua (4) (4) Đánh dấu trang này đã tới rồi. Phân tích và tìm các liên kết có trong trang đó không? - Nếu có, thêm liên kết này vào cuối danh sách. Quay lại (4) - Nếu không, quay lại (2) (5) Kết thúc.