Luận văn Khai thác dữ liệu trên web và xây dựng ứng dụng hỗ trợ nhập liệu

ỚNG DẪN KHOA HỌC: TS. Nguyễn Văn Đồn HÀ NỘI - 2014 1 LỜI CẢM ƠN Trước hết, tơi xin bày tỏ lịng cảm ơn chân thành TS. Nguyễn Văn Đồn, là người tận tình hướng dẫn tơi trong thời gian làm luận văn tốt nghiệp. Tơi xin cảm ơn các thầy, cơ giáo ở Viện Cơng nghệ thơng tin - Đại học Quốc gia Hà Nội đã giảng dạy tơi trong suốt thời gian học tập tại viện và tạo điều kiện giúp đỡ tơi hồn thành luận văn này. Cảm ơn các bạn bè, đồng nghiệp đã cổ vũ động viên tơi trong suốt quá trình học tập tại viện. Tuy đã cĩ những cố gắng nhất định nhưng do thời gian và trình độ cĩ hạn nên chắc chắn luận văn này cịn nhiều thiếu sĩt và hạn chế nhất định. Kính mong nhận được sự gĩp ý của thầy cơ và các bạn. Luận văn thạc sĩ này được thực hiện trong khuơn khổ đề tài nghiên cứu mang mã số Chuyên ngành đào tạo thí điểm, Đại học Quốc gia Hà Nội. Hà Nội, ngày 10 tháng 01 năm 2014 Học viên Nguyễn Bình Minh 2 LỜI CAM ĐOAN Tơi xin cam đoan kết quả đạt được trong luận văn là sản phẩm nghiên cứu, tìm hiểu của riêng cá nhân tơi. Trong tồn bộ nội dung của luận văn, những điều được trình bày hoặc là của cá nhân tơi hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều cĩ xuất xứ rõ ràng và được trích dẫn hợp pháp. Tơi xin hồn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà Nội, ngày 10 tháng 01 năm 2014 Học viên Nguyễn Bình Minh 3 TĨM TẮT LUẬN VĂN Trong những năm gần đây cùng với phát triển nhanh chĩng của khoa học kỹ thuật là sự bùng nổ về tri thức. Kho dữ liệu, nguồn tri thức của nhân loại cũng trở nên đồ sộ, vơ tận làm cho vấn đề khai thác các nguồn tri thức đĩ ngày càng trở nên nĩng bỏng và đặt ra thách thức lớn cho nền cơng nghệ thơng tin thế giới. Hiện nay, lượng thơng tin trên Internet càng ngày càng khổng lồ, điều này khiến việc sử dụng Internet để khai thác thơng tin hữu ích, phục vụ cho các mục đích của tổ chức hay cá nhân luơn cĩ những khĩ khăn nhất định của nĩ. Nhất là đối với những mục đích địi hỏi cần khai thác thơng tin với khối lượng lớn trên Web, chẳng hạn một cơng ty quảng cáo muốn thu thập thật nhiều thơng tin liên lạc của các doanh nghiệp trong nhiều lĩnh vực để gửi thư quảng cáo. Những cơng việc như thế này nếu được thực hiện thủ cơng bằng sức người thì sẽ mất rất nhiều thời gian, cơng sức, và chúng cũng khá tẻ nhạt do tính chất phải lặp đi lặp một vài thao tác của việc thu thập dữ liệu. Do những vấn đề cấp thiết được đề cập ở trên nên em chọn đề tài: “Khai thác dữ liệu trên Web và xây dựng ứng dụng hỗ trợ nhập liệu”. Mục tiêu của đề tài nhằm đưa ra phương pháp cũng như cơng cụ cĩ khả năng hỗ trợ con người trong những bài tốn cĩ yêu cầu thu thập dữ liệu, giúp giảm thời gian và sức lực của con người nhưng vẫn đảm bảo tính tồn vẹn của dữ liệu. 4 MỤC LỤC MỞ ĐẦU .................................................................................................................................... 7 CHƯƠNG 1. TỔNG QUAN VỀ KHAI THÁC DỮ LIỆU TRÊN WEB................................... 9 1.1 TÌM HIỂU CÁC KIẾN THỨC TỔNG QUAN .......................................................... 9 1.1.1 WORLD WIDE WEB ............................................................................................ 9 1.1.2 TRÌNH THU THẬP DỮ LIỆU WEB – WEB CRAWLER ................................... 9 1.1.3 TRÌNH BĨC TÁCH VÀ TRÍCH XUẤT THƠNG TIN – WEB SCRAPER ....... 10 1.1.4 PHÂN LOẠI WEB ............................................................................................... 11 1.1.4.1 Phân loại dựa vào sự thể hiện của tính động ................................................ 11 1.1.4.2 Phân loại dựa vào cách thức tạo ra tính động ............................................... 12 1.1.4.3 Khả năng của các web crawler ..................................................................... 12 1.2 CÁC CHIẾN LƯỢC THU THẬP DỮ LIỆU ........................................................... 13 1.2.1 CHIẾN LƯỢC THU THẬP DỮ LIỆU THEO CHIỀU SÂU .............................. 14 1.2.2 CHIẾN LƯỢC THU THẬP DỮ LIỆU THEO CHIỀU RỘNG ........................... 14 1.3 ĐÁNH GIÁ SƠ BỘ .................................................................................................. 15 CHƯƠNG 2. PHÂN TÍCH VÀ THIẾT KẾ ỨNG DỤNG ...................................................... 17 2.1 CÁC KIẾN THỨC NỀN TẢNG VÀ CƠNG NGHỆ LIÊN QUAN ........................ 17 2.1.1 HTML ................................................................................................................... 17 2.1.2 XML ..................................................................................................................... 18 2.1.3 XHTML ................................................................................................................ 19 2.1.3.1 Tính chuẩn của một tài liệu XML (well-formed) ......................................... 19 2.1.3.2 Tên các phần tử và tên các thuộc tính phải ở dạng chữ in thường ............... 19 2.1.3.3 Các thẻ khơng rỗng bắt buộc phải cĩ thẻ đĩng............................................. 19 2.1.3.4 Các thuộc tính luơn phải ghi rõ giá trị .......................................................... 20 2.1.3.5 Các phần tử rỗng ........................................................................................... 20 2.1.4 XPATH ................................................................................................................. 20 2.1.4.1 Cú pháp và ngữ nghĩa ................................................................................... 21 2.1.4.2 Axis specifier ................................................................................................ 22 2.1.4.3 Node test ....................................................................................................... 23 2.1.4.4 Predicate ....................................................................................................... 23 2.1.4.5 Các hàm và tốn tử ....................................................................................... 23 5 2.1.5 CÁC THƯ VIỆN HỖ TRỢ .................................................................................. 24 2.1.5.1 HTML Tidy .................................................................................................. 24 2.1.5.2 cURL ............................................................................................................ 26 2.2 PHÂN TÍCH ............................................................................................................. 26 2.2.1 PHÁT BIỂU BÀI TỐN ..................................................................................... 26 2.2.2 PHÂN LOẠI CÁC TRANG WEB DỰA TRÊN CÁCH CHUYỂN TRANG ..... 29 2.2.3 ĐỀ XUẤT GIẢI PHÁP ........................................................................................ 30 2.3 THIẾT KẾ ỨNG DỤNG .......................................................................................... 33 2.3.1 SƠ ĐỒ USE CASE .............................................................................................. 33 2.3.2 KIẾN TRÚC ỨNG DỤNG................................................................................... 34 2.3.2.1 Thành phần front-end ................................................................................... 34 2.3.2.2 Thành phần back-end.................................................................................... 36 CHƯƠNG 3. HIỆN THỰC ỨNG DỤNG VÀ ĐÁNH GIÁ KẾT QUẢ .................................. 39 3.1 ĐẶC TẢ DỮ LIỆU ĐẦU VÀO BẰNG XML ......................................................... 39 3.1.1 ĐẶC TẢ THƠNG TIN CHUNG CHO ROBOT ................................................. 39 3.1.2 ĐẶC TẢ CÁC TRANG ....................................................................................... 40 3.1.3 ĐẶC TẢ BẢNG CƠ SỞ DỮ LIỆU ..................................................................... 44 3.2 CẤU TRÚC CƠ SỞ DỮ LIỆU ................................................................................ 45 3.3 SƠ ĐỒ TUẦN TỰ CHO CÁC CHỨC NĂNG ........................................................ 46 3.3.1 BOT MANAGER ................................................................................................. 46 3.3.2 ROBOT ................................................................................................................. 47 3.3.2.1 Quản lý tiến trình của Robot ........................................................................ 48 3.3.2.2 Thực hiện quy trình thu thập dữ liệu ............................................................ 49 3.3.3 CRAWLER ........................................................................................................... 50 3.3.3.1 Simple Crawler ............................................................................................. 51 3.3.3.2 Advanced Crawler ........................................................................................ 51 3.3.4 EXTRACTOR ...................................................................................................... 54 KẾT LUẬN .............................................................................................................................. 55 TÀI LIỆU THAM KHẢO ........................................................................................................ 56 6 MỤC LỤC HÌNH ẢNH Hình 1-1. World Wide Web ............................................................................................ 9 Hình 1-2. Sơ đồ hoạt động của một web crawler đơn giản ........................................... 10 Hình 1-3. Phân loại web cùng khả năng của các web crawler ...................................... 13 Hình 2-1. Một trang web danh bạ .................................................................................. 27 Hình 2-2. Sơ đồ Use Case của ứng dụng DESS ............................................................ 33 Hình 2-3. Sơ đồ các trạng thái của Bot.......................................................................... 35 Hình 2-4. Quá trình hoạt động tổng quát của ROBOT ................................................. 37 Hình 3-1. Sơ đồ cấu trúc cơ sở dữ liệu của chương trình .............................................. 45 Hình 3-2. Sơ đồ tuần tự của tác vụ start Bot ................................................................. 46 Hình 3-3. Sơ đồ tuần tự của tác vụ resume Bot ............................................................. 46 Hình 3-4. Sơ đồ tuần tự của tác vụ pause Bot ............................................................... 47 Hình 3-5. Sơ đồ tuần tự của tác vụ stop Bot .................................................................. 47 Hình 3-6. Sơ đồ tuần tự thể hiện quá trình hoạt động tổng quát của Robot .................. 48 Hình 3-7. Quá trình thu thập dữ liệu tổng quát ............................................................. 49 Hình 3-8. Sơ đồ class của các Crawler .......................................................................... 50 Hình 3-9. Sơ đồ tuần tự hoạt động của Simple Crawler ............................................... 51 Hình 3-10. Sơ đồ tuần tự hoạt động của Advanced Crawler ......................................... 51 Hình 3-11. Sơ đồ class của các Extractor ...................................................................... 54 7 MỞ ĐẦU Trong thập kỷ qua, chúng ta đã được chứng kiến sự phát triển đến chĩng mặt của Internet mà tiêu biểu là các trang thơng tin. Internet đã và đang được coi là một nguồn cung cấp tin khổng lồ với mọi chuyên mục, mọi vấn đề mà người sử dụng cần đến. Với sự phát triển này, lượng thơng tin từ Internet mang đến cho người sử dụng là quá lớn dẫn tới việc chúng ta cần phải cĩ các ứng dụng Internet thơng minh và hiệu quả hơn đối với người sử dụng. Tuy nhiên nếu lượng thơng tin mà họ cần khai thác là quá nhiều thì quá trình duyệt web, trích xuất và lưu trữ theo cách thủ cơng lại trở thành một cơng việc khĩ khăn, hao tốn nhiều sức lực, thời gian của con người. Một số ví dụ cĩ thể kể ra như: nhu cầu trích xuất thơng tin về tất cả các mặt hàng thuộc một chuyên mục của một website bán hàng nào đĩ nhằm phục vụ mục đích khảo sát thị trường, nhu cầu tổng hợp tin tức từ các website tin tức để xây dựng các trang web thơng tin tổng hợp, nhu cầu thu thập thơng tin về các doanh nghiệp thuộc một ngành nào đĩ trên website danh bạ doanh nghiệp để gửi email quảng cáo, tiếp thị, v.v Chính những ví dụ thực tế như trên đã nảy sinh ra nhu cầu: cần phải cĩ một phương thức hoặc cơng cụ nào đĩ cĩ khả năng tìm kiếm, trích xuất thơng tin trên web và lưu trữ lại thơng tin đĩ theo ý muốn của con người, một cách tự động và hiệu quả, và đĩ cũng chính là mục tiêu được đặt ra cho đề tài này. Đĩ là: Tìm hiểu phương pháp khai thác lượng dữ liệu trên, từ đĩ xây dựng được một ứng dụng thu thập dữ liệu tự động từ các website, phục vụ cho các nhu cầu của cá nhân hay tổ chức. Các nhiệm vụ:  Tìm hiểu về các kiến thức nền tảng  Tìm hiểu về các kỹ thuật khai thác dữ liệu tự động từ các website  Tìm hiểu về các cơng nghệ liên quan và xây dựng ứng dụng khai thác dữ liệu trên một website cụ thể Bố cục của luận văn: Mở đầu: Đặt vấn đề về ý nghĩa , tính cấp thiết, nhiệm vụ và tính thực tiễn của đề tài. Chương 1: Tổng quan về khai thác dữ liệu trên Web Trong chương này, chúng ta sẽ tìm hiểu các khái niệm cơ bản về trình thu thập web (web crawler), các chiến lược thu thập dữ liệu, trình bĩc tách và trích xuất thơng tin (web scraper), sự phân loại các trang web, từ đĩ vẽ ra bức tranh chung về khai thác dữ liệu trên web để hiểu hơn về các giá trị thực tiễn mà nĩ mang lại trong đời sống con người. Chương 2: Phân tích, thiết kế ứng dụng 8 Phần đầu chương sẽ trình bày về các kiến thức nền tảng và các cơng nghệ liên quan, ở phần tiếp theo nêu phát biểu cho bài tốn khai thác dữ liệu trên web cũng như giải pháp thực hiện, kiến trúc thành phần của ứng dụng. Chương 3: Hiện thực ứng dụng và đánh giá kết quả thu được Đặc tả thơng tin đầu vào cho ứng dụng, lược đồ cơ sở dữ liệu tương ứng và chức năng của các module trong chương trình. Phần tiếp theo trình bày ví dụ cụ thể và kết quả thu được khi thực hiện ứng dụng. Kết luận: Phần cuối của luận văn sẽ nhìn lại những điều đã làm được, nêu lên những hạn chế, từ đĩ đề ra hướng phát triển sau này. 9 CHƯƠNG 1. TỔNG QUAN VỀ KHAI THÁC DỮ LIỆU TRÊN WEB 1.1 TÌM HIỂU CÁC KIẾN THỨC TỔNG QUAN 1.1.1 WORLD WIDE WEB World Wide Web (WWW, hay gọi tắt là Web) là một ứng dụng phổ biến và phát triển mạnh mẽ nhất của Internet hiện nay. World Wide Web là một mạng lưới bao gồm các tài liệu siêu văn bản (hypertext) được đặt trên các máy tính nằm trong mạng Internet. Các siêu văn bản này cĩ khả năng liên kết lẫn nhau thơng qua các siêu liên kết (hyperlink). Sử dụng một trình duyệt web (web browser), con người cĩ thể xem được các trang web (web page, cũng chính là một siêu văn bản) trên màn hình máy vi tính, nội dung các trang web cĩ thể cĩ chữ, hình ảnh, video, thậm chí cĩ thể tương tác với người sử dụng thơng qua các thiết bị như bàn phím, chuột. Cũng chính nhờ các hyperlink mà các trang web cĩ thể liên kết được với nhau thơng qua chỉ một cú click chuột, đây là khả năng đem lại sự mở rộng vơ cùng lớn cho world wide web. Hình 1-1. World Wide Web Nội dung các trang web chủ yếu được viết bằng ngơn ngữ HTML hoặc XHTML. Khi muốn truy cập một trang web, trình duyệt web sẽ gửi yêu cầu đến máy chủ (web server) chứa trang web đĩ. Máy chủ sẽ hồi đáp bằng nội dung trang web được yêu cầu trong trường hợp trang web đĩ thật sự tồn tại trên máy chủ và được cho phép truy cập. Cả hai quá trình yêu cầu và hồi đáp này đều được thực hiện dựa trên giao thức HTTP (Hyper Text Transfer Protocol). 1.1.2 TRÌNH THU THẬP DỮ LIỆU WEB – WEB CRAWLER Một Web Crawler là một chương trình máy tính cĩ thể “duyệt web” một cách tự động và theo một phương thức nào đĩ được xác định trước. Vì là một chương trình nên quá trình “duyệt web” của các web crawler khơng hồn tồn giống với quá trình duyệt web của con người (web crawler phải sử dụng các phương thức dựa trên HTTP trực tiếp chứ khơng thơng qua web browser như con người). Các web crawler thường bắt đầu với một danh sách URL của các web page để ghé thăm đầu tiên. Khi ghé thăm 10 một URL, crawler sẽ đọc nội dung web page, tìm tất cả các hyperlink cĩ trong web page đĩ và đưa các URL được trỏ tới bới các hyperlink đĩ vào danh sách URL. Dựa vào danh sách URL này, Crawler lại tiếp tục quá trình duyệt đệ quy để ghé thăm tất cả các URL chưa được duyệt đến. Quá trình này được gọi là web crawling hoặc là web spidering, các web crawler cịn được gọi là các robot (bot) hoặc nhện web (web spider). Thường thì các crawler được tạo ra để phục vụ cho một mục đích, tác vụ nào đĩ. Ví dụ các máy tìm kiếm (search engine) sử dụng crawler để tải các web page, các web page này sau đĩ được search engine đánh chỉ mục để cĩ thể cho kết quả nhanh hơn khi được tìm kiếm. Hình 1-2. Sơ đồ hoạt động của một web crawler đơn giản Về bản chất, web crawling chính là quá trình duyệt đệ quy một đồ thị cây cĩ các node là các web page. Tùy thuộc vào chiến lược của crawler, các node cĩ thể được duyệt theo chiều sâu hoặc duyệt theo chiều rộng. Trong thực tế, quá trình crawling web sẽ phải đối diện với rất nhiều vấn đề khĩ khăn như: kích thước khổng lồ của world wide web, các trang web HTML được viết khơng chuẩn, hạn chế ghé thăm một URL đã được ghé thăm trước đĩ, các trang web động, nội dung các trang web được cập nhật thường xuyên v.v 1.1.3 TRÌNH BĨC TÁCH VÀ TRÍCH XUẤT THƠNG TIN – WEB SCRAPER Các trang web chủ yếu được viết bằng các ngơn ngữ đánh dấu như HTML, XHTML và được nhắm đến đối tượng sử dụng là con người chứ khơng phải máy tính. Các trang web lại chứa đựng nhiều thơng tin cĩ ích mà con người cĩ thể muốn thu thập và lưu trữ lại, chính vì thế mà các web scraper được ra đời. Web Scraper là một thuật ngữ để chỉ các phần mềm cĩ khả năng bĩc tách và trích xuất thơng tin chứa trên các web page một cách tự động. Cơng việc này được gọi là web scraping. Các web scraper khác với web crawler ở chỗ, trong khi web crawler tập trung vào việc duyệt các trang web thơng qua các liên kết hyperlink, thì web scraper lại tập trung vào việc chuyển đổi nội dung khơng cấu trúc của các trang web (chủ yếu được viết bằng HTML) sang thành nội dung cĩ cấu trúc, sau đĩ bĩc tách, trích xuất phần thơng tin 11 mong muốn và lưu trữ lại vào các cơ sở dữ liệu hoặc spreadsheet. Các web scraper cũng cĩ thể thực hiện thêm các cơng đoạn phân tích dữ liệu sau khi đã trích xuất được để phục vụ cho một mục đích nào đĩ. Một số ứng dụng của web scraping bao gồm: so sánh giá cả thị trường trực tuyến, nghiên cứu thị trường, thu thập thơng tin để thống kê, theo dõi thơng tin thời tiết trên các website dự báo thời tiết, tổng hợp tin tức từ nhiều website v.v Một số kỹ thuật được sử dụng trong web scraping cĩ thể kể ra như:  So trùng: một kỹ thuật đơn giản nhưng khá hiệu quả để tìm kiếm các phần nội dung chữ cĩ sự tương đồng với nhau (do nội dung trang web chủ yếu là ở dạng ký tự). Kỹ thuật này thường sử dụng regular expression (biểu thức chính quy) để so trùng và tìm kiếm.  Lập trình HTTP: ta cĩ thể lấy được nội dung trang web bằng cách gửi một yêu cầu HTTP đến web server, cũng giống như cách web browser làm. Đây cũng là một kỹ thuật được sử dụng bởi các web crawler.  Phân tích cấu trúc DOM: phân tích nội dung HTML của web page và xây dựng một cây DOM (Document Object Model), giúp scraper cĩ thể duyệt các node trên cây này và chỉ lấy ra phần nội dung mà nĩ cần. 1.1.4 PHÂN LOẠI WEB World Wide Web cĩ thể được phân loại thành hai loại: các trang web tĩnh và các trang web động. Sriram và Hector [3] đưa ra định nghĩa sau về trang web động: “Một trang P được gọi là động nếu như một phần hoặc tất cả nội dung của nĩ được sinh ra tại thời điểm chạy (tức là sau khi yêu cầu của máy khách được máy chủ nhận) bởi một chương trình thực thi nằm trên máy chủ hoặc máy khách. Điều này ngược lại với một trang tĩnh P1, khi mà tồn bộ nội dung của P1 đã tồn tại sẵn trên máy chủ và luơn sẵn sàng được gửi cho máy khách ngay sau khi một yêu cầu được nhận.” Các trang web động cĩ thể được phân loại theo hai tiêu chí sau: sự thể hiện và cách thức tạo ra [3]. 1.1.4.1 Phân loại dựa vào sự thể hiện của tính động Theo thời gian (temporal dynamism): đây là những trang web mà nội dung của chúng cĩ thể được thay đổi, cập nhật theo thời gian. Điều này đồng nghĩa với việc: các yêu cầu đến cùng một trang web, khi được gửi ở hai thời điểm khác nhau cĩ thể sẽ nhận được hai nội dung khác nhau. Theo máy khách (client-based dynamism): những trang web cĩ khả năng tùy biến theo người sử dụng (client) sẽ được xếp vào mục này. Ví dụ một trang tin tức tổng hợp cĩ khả năng chọn lọc các tin tức khác nhau, tùy thuộc vào sở thích của người 12 sử dụng đang đăng nhập. Những trang kiểu này thường khơng thể trực tiếp truy xuất vào được mà phải vượt qua một bước xác thực danh tính (authentication). Theo truy vấn (input dynamism): đây là những trang cĩ nội dung phụ thuộc vào truy vấn của người sử dụng. Một ví dụ điển hình là những trang cĩ các mẫu nhập liệu (form), chẳng hạn một trường nhập liệu để tìm kiếm một hoặc nhiều mĩn hàng trong cơ sở dữ liệu của trang web. Những trang kiểu này cũng khơng luơn luơn truy xuất trực tiếp được (tùy thuộc vào phương thức truyền các tham số - GET hoặc POST – chi tiết về vấn đề này sẽ được phân tích ở phần 4), các trang kết quả nhận được cũng thường cĩ số lượng rất lớn (tùy thuộc số tổ hợp của các tham số truy vấn). Đây cũng thường là những trang web khơng thể crawl được hồn tồn bởi các crawler, và được gọi là Web ẩn (hidden Web, deep Web, invisible Web). 1.1.4.2 Phân loại dựa vào cách thức tạo ra tính động Thực thi các chương trình nằm trên máy chủ (server-side programs): Trong kỹ thuật này, một chương trình sẽ được thực thi trên máy chủ và sinh ra tồn bộ nội dung HTML của trang web, sau đĩ được gửi đến máy khách yêu cầu. Ví dụ tiêu biểu cho loại này là CGI hoặc Java Servlet. Những chương trình phía máy chủ này cũng thường được dùng để xử lý các truy vấn từ người sử dụng. Nhúng mã với sự thực thi phía máy chủ (embedded code with server-side execution): các trang web động sẽ chứa cả nội dung HTML tĩnh cùng với các đoạn mã được nhúng vào cùng với HTML. Khi một yêu cầu được nhận, các đoạn mã nhúng này sẽ được thực thi trên máy chủ và sẽ sinh ra các đoạn code HTML thay thế cho chúng. Kỹ thuật này khác kỹ thuật trên ở chỗ khơng phải tồn bộ mà chỉ một phần nội dung HTML được sinh động. Các mã nhúng này cĩ thể là PHP, Java Scriplet, ASP hoặc các mã server-side khác. Nhúng mã với sự thực thi phía máy khách (cĩ thể cĩ cả sự thực thi ở phía máy chủ) (embedded code with client-side execution): Với ký thuật này thì các đoạn mã được nhúng khơng chạy trên server mà chúng được máy khách tải về và được thực thi trên máy khách. Nếu mã chỉ chạy trên máy khách thì đĩ cĩ thể là JavaScript, Java Applet hoặc Flash. Nếu vừa cĩ sự thực thi ở máy khách và cả ở máy chủ thì đĩ chính là Ajax, trong trường hợp này mã clien-side cĩ thể trao đổi thơng tin với server thơng qua một đối tượng đặc biệt là XMLHttpRequest để cĩ thể thay đổi nội dung trang web một cách động mà khơng cần load trang web mới. 1.1.4.3 Khả năng của các web crawler Nhìn chung, các web crawler hiện nay hầu hết đều chỉ cĩ thể crawl một phần rất nhỏ của World Wide Web, đĩ là những trang web cĩ thể đến được bằng cách đi theo các liên kết hyperlink. Các crawler này thường phải bỏ qua các trang cĩ tính động theo 13 máy khách (client-based dynamism) và theo truy vấn (input dynamism). Cũng đã cĩ một vài cơng trình nghiên cứu xây dựng các hidden-web crawler như HiWE [3], tuy nhiên đây khơng phải một vấn đề tầm thường và cũng vẫn cịn đang được tiếp tục nghiên cứu và phát triển. Hình 1 cho thấy cái nhìn tổng quan về sự phân loại các trang web tĩnh - động, cùng với khả năng của các web crawler (thương mại) hiện nay. Thể hiện Cách thức Nội dung tĩnh Nội dung động Thời gian Client-based Truy vấn Trang tĩnh hồn tồn Khơng cần xét vì trang tĩnh hồn tồn khơng thể tạo ra nội dung động Chương trình thực thi server-side Khơng cần xét vì nội dung đã là tĩnh Mã nhúng thực thi server- side Mã nhúng thực thi client- side Các crawler truyền thống (Web nổi) Một vài crawler (Web ẩn) Các crawler cá nhân (Các web tùy biến) Khơng cĩ Hình 1-3. Phân loại web cùng khả năng của các web crawler 1.2 CÁC CHIẾN LƯỢC THU THẬP DỮ LIỆU Trong phần này chúng ta sẽ thảo luận về một số chiến lược thu thập dữ liệu bao gồm [1]: - Chiến lược thu thập dữ liệu theo chiều sâu. - Chiến lược thu thập dữ liệu theo chiều rộng. Như đã nĩi ở phần trước về bản chất, quá trình thu thập web chính là quá trình duyệt đệ quy một đồ thị. Các website được xem như một đồ 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ì thế các chiến thuật thu thập dữ 14 liệu cũng được xây dựng dựa trên các thuật tốn tìm kiếm trên đồ thị. Các thuật tốn tìm kiếm trên đồ thị bao gồm: - Tìm kiếm theo chiều sâu (Depth-First Search): Là thuật tốn tìm kiếm bằng cách mở rộng nút đồ thị theo chiều sâu. - Tìm kiếm theo chiều rộng (Breath-First Search): Là thuật tốn tìm kiếm bằng cách mở rộng nút đồ thị theo chiều rộng. 1.2.1 CHIẾN LƯỢC THU THẬP DỮ LIỆU THEO CHIỀU SÂU Quá trình thực hiện: Bước 1: Lấy URL đầu tiên trong danh sách (frontier) để thu thập. - Nếu cĩ qua bước 2. - Nếu khơng qua bước 5. Bước 2: Lấy trang tương ứng với URL qua HTTP. - Nếu cĩ qua bước 3. - Nếu khơng quay lại bước 1. Bước 3: Kiểm tra xem trang này đã được thăm chưa? - Nếu chưa qua bước 4. - Nếu rồi quay lại bước 1. Bước 4: Đánh dấu trang này đã được thăm. Bĩc tách trang và tìm các liên kết cĩ trong trang này. - Nếu cĩ, thêm các liên kết vào đầu danh sách. Quay lại bước 3. - Nếu khơng, quay lại bước 1. Bước 5: Kết thúc. 1.2.2 CHIẾN LƯỢC THU THẬP DỮ LIỆU THEO CHIỀU RỘNG Quá trình thực hiện: Bước 1: Lấy URL đầu tiên trong danh sách để thu thập. - Nếu cĩ qua bước 2. - Nếu khơng qua bước 5. Bước 2: Lấy trang tương ứng với URL qua HTTP. - Nếu cĩ qua bước 3. - Nếu khơng quay lại bước 1. 15 Bước 3: Kiểm tra xem trang này đã được thăm chưa? - Nếu chưa qua bước 4. - Nếu rồi quay lại bước 1. Bước 4: Đánh dấu trang này đã được thăm. Bĩc tách trang và tìm các liên kết cĩ trong trang này. - Nếu cĩ, thêm liên kết vào cuối danh sách. Quay lại bước 3. - Nếu khơng, quay lại bước 1. Bước 5: Kết thúc. Ngồi 2 chiến lược kể trên cịn phải kể đến các chiến lược thu thập dữ liệu khác như: Chiến lược thu thập dữ liệu theo lựa chọn tốt nhất ngây thơ (Nạve Best-First), tìm kiếm tham ăn (Shark Search). Chúng sử dụng thuật tốn tìm kiếm theo quy tắc tính điểm số cho các URL dựa trên các tiêu chí để đánh giá độ quan trọng của một trang web như là: từ khĩa, thẻ title và meta, số lượng liên kết ngồi. Các chiến lược kể trên khơng thuộc phạm vi nghiên cứu của đề tài. 1.3 ĐÁNH GIÁ SƠ BỘ Cĩ thể thấy được rằng, ứng dụng mà đề tài cần xây dựng chính là một chương trình vừa cĩ thể crawl web một cách tự động, vừa cĩ khả năng bĩc tách, trích xuất dữ liệu như một web scraper. Từ đĩ cĩ thể hình dung ứng dụng sẽ gồm 2 module chính: crawler module và data extractor module. Crawler module sẽ giúp ứng dụng “duyệt” nhiều trang web tương tự một cách tự động (ví dụ các trang phân trang của cùng một trang danh mục), với mỗi trang web được duyệt qua crawler module sẽ tải nội dung trang web về và lưu trữ tạm. Nội dung trang web sau đĩ được chuyển cho data extractor module, data extractor module cĩ nhiệm vụ phân tích, xử lý nội dung trang web, chuyển đổi nĩ sang một cấu trúc trung gian nào đĩ để thuận tiện cho việc sử dụng trong bước nhập liệu. Ứng dụng phải cĩ tính tùy biến cao, phục vụ cho các mục đích cụ thể chứ khơng như các web crawler của các search engine (crawl phần Web nổi để đánh index), như vậy ứng dụng phải hỗ trợ được cả (một) phần Web ẩn. Vì phải phục vụ cho các mục đích cụ thể nên ứng dụng cũng cần được “dẫn đường” bởi người sử dụng. Thành phần data extractor của ứng dụng sẽ khơng cĩ nhiều khác biệt với các web scraper khác. Ứng dụng phải cĩ thể bĩc tách, trích xuất các dữ liệu (cĩ sự tương đồng, do người sử dụng đặc tả) một cách tự động. Ngồi ra, trong lĩnh vực trích xuất thơng tin (Information Retrieval) cũng cĩ một hướng nghiên cứu khác khá gần gũi với lĩnh vực khai phá dữ liệu (data mining) và trí tuệ nhân tạo (artificial intelligence). Hướng nghiên cứu này sẽ xây dựng, phát triển các 16 cơng cụ cĩ khả năng tự động crawl và trích xuất thơng tin một cách hồn tồn tự động, khơng cần hoặc cần rất ít sự can thiệp của con người, và hơn nữa các cơng cụ này cịn cĩ khả năng tự học (machine learning) thơng qua các dữ liệu mẫu [6], nhờ đĩ nĩ cĩ thể ứng dụng được trên nhiều loại trang web cĩ cấu trúc khác nhau một cách tự động. Ưu điểm của hướng tiếp cận này là tính tự động cao, cĩ thể chạy được trên nhiều website khác nhau (cùng lĩnh vực) một cách tự động. Tuy nhiên các cơng cụ kiểu này thường chỉ cĩ thể sử dụng cho các lĩnh vực cụ thể và phổ biến (domain-specific), chẳng hạn như lĩnh vực tin tức trực tuyến. Vì lý do hạn chế về thời gian nên đề tài luận văn này sẽ khơng đi theo hướng này. Hướng tiếp cận của đề tài sẽ là xây dựng một ứng dụng cĩ khả năng giải quyết các vấn đề trích xuất thơng tin rất rời rạc và cụ thể. Ứng dụng cũng sẽ được xây dựng như một framework cĩ khả năng mở rộng được, tùy biến được bởi người sử d