Luận văn Thạc sĩ Công nghệ thông tin: Khai thác dữ liệu trên web và xây dựng ứng dụng hỗ trợ nhập liệu

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:58

Thêm vào BST

Báo xấu

31
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu nghiên cứu chính của luận văn là: tìm hiểu về các kiến thức nền tảng, 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ể. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: Khai thác dữ liệu trên web và xây dựng ứng dụng hỗ trợ nhập liệu

ĐẠI HỌC QUỐC GIA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN NGUYỄN BÌNH MINH KHAI THÁC DỮ LIỆU TRÊN WEB VÀ XÂY DỰNG ỨNG DỤNG HỖ TRỢ NHẬP LIỆU LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN HÀ NỘI – 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN NGUYỄN BÌNH MINH KHAI THÁC DỮ LIỆU TRÊN WEB VÀ XÂY DỰNG ỨNG DỤNG HỖ TRỢ NHẬP LIỆU Ngành: Công nghệ thông tin Chuyên ngành: Quản lý hệ thống thông tin Mã số: Chuyên ngành đào tạo thí điểm LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Văn Đoàn HÀ NỘI - 2014
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 Đoà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 hoà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 1
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 toà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 hoà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 2
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 toá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 toàn vẹn của dữ liệu. 3
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à toán tử ....................................................................................... 23 4
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 TOÁ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 5
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 6
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 7
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 toá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. 8
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 hoàn toà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 9
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 10
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à toà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 11
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 hoàn toà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 toà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 toà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 12
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 Nội dung Nội dung động tĩnh Cách thức Thời gian Client-based Truy vấn Không cần xét vì trang tĩnh hoàn toàn không Trang tĩnh hoàn toàn thể tạo ra nội dung động Chương trình thực thi server-side Không cần Mã nhúng thực thi server- xét vì nội side dung đã là tĩnh Mã nhúng thực thi client- side Các crawler truyền thống Một vài crawler (Web ẩn) (Web nổi) Các crawler cá nhân Không có (Các web tùy biến) 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ữ 13
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ị bao gồm: - Tìm kiếm theo chiều sâu (Depth-First Search): Là thuật toá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 toá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. 14
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. Ngoà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ơ (Naïve Best-First), tìm kiếm tham ăn (Shark Search). Chúng sử dụng thuật toá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 ngoà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. Ngoà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 15
công cụ có khả năng tự động crawl và trích xuất thông tin một cách hoàn toà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ụng, để có thể sử dụng cho nhiều loại website khác nhau, nhược điểm là mỗi khi sử dụng ứng dụng cho một website có cấu trúc khác, người sử dụng sẽ phải đặc tả lại các thông số đầu vào. 16
CHƯƠNG 2. PHÂN TÍCH VÀ THIẾT KẾ ỨNG DỤNG 2.1 CÁC KIẾN THỨC NỀN TẢNG VÀ CÔNG NGHỆ LIÊN QUAN 2.1.1 HTML HTML (HyperText Markup Language – ngôn ngữ đánh dấu siêu văn bản) là một ngôn ngữ đánh dấu được thiết kế ra để tạo nên các trang web. HTML được xem như là một ứng dụng của SGML (Standard Generalized Markup Language – một chuẩn ISO định nghĩa các ngôn ngữ đánh dấu văn bản tổng quát). HTML được tổ chức World Wide Web Consortium (W3C) duy trì và là ngôn ngữ đánh dấu cốt lõi của World Wide Web. Phiên bản mới nhất của nó hiện là HTML 4.01. Tuy nhiên HTML hiện không còn được phát triển tiếp mà người ta đã thay thế nó bằng XHTML – một chuẩn HTML mở rộng dựa trên XML và có cú pháp chặt chẽ hơn HTML. Mặc dù vậy nhưng phần lớn các trang web hiện nay vẫn được viết bằng HTML, bởi nhiều nguyên nhân khác nhau (sử dụng các công cụ soạn thảo HTML cũ, người viết code ngại thay đổi v.v…). Một tài liệu HTML được tạo nên bởi các phần tử HTML. Một cách tổng quát, một phần tử HTML bao gồm 3 thành phần: một cặp thẻ (tags) gồm một thẻ bắt đầu và một thẻ kết thúc; các thuộc tính (nằm trong thẻ bắt đầu); và toàn bộ phần ký tự, hình ảnh, nội dung thông tin sẽ được hiển thị lên màn hình. Một phần tử HTML là mọi thứ nằm giữa hai thẻ đầu cuối, tính cả hai thẻ này. Một thẻ HTML đơn giản là một từ khóa được đặt giữa một cặp hai dấu bé hơn (). Thẻ đóng của một phần tử HTML luôn có một ký tự “/” ngay sau ký tự “
 Các phần tử thành phần điều khiển giúp tạo ra các đối tượng điều khiển như các nút bấm, các ô textbox để nhập liệu. HTML là ngôn ngữ không phân biệt hoa thường (hai thẻ và đều là một). Các phần tử HTML cần có một thẻ mở và một thẻ đóng, tuy nhiên điều này không luôn luôn đúng, có nhiều phần tử không cần thẻ đóng, ví dụ các thẻ , và . Ngoài ra khi lồng nhau, các phần tử HTML cũng không cần thiết phải lồng nhau theo đúng thứ tự (tức là thẻ nào mở trước thì phải đóng sau) ví dụ sau là hợp lệ trong HTML: đoạn văn này được in đậm Sự lồng nhau không đúng thứ tự của các phần tử HTML được gọi là overlapping (phủ lên nhau), mặc dù điều này không được phép trong đặc tả SGML, nhưng lại được chấp nhận bởi hầu hết các trình duyệt hiện nay. Từ các đặc điểm trên ta có thể nhận thấy HTML không phải là một ngôn ngữ có cú pháp chặt chẽ, các đặc điểm như không cần đóng thẻ hoặc không cần lồng nhau đúng thứ tự sẽ là các trở ngại cho công việc đọc và phân tích văn bản HTML (HTML parsing), đặc biệt nếu sử dụng phương pháp tìm kiếm so trùng. Chính vì vậy, chúng ta cần phải chuyển đổi nội dung viết bằng HTML sang một định dạng ngôn ngữ khác có sự chặt chẽ hơn về cú pháp, điều này sẽ đem lại thuận lợi hơn cho quá trình xử lý về sau. Một ngôn ngữ đánh dấu được định nghĩa ra để thay thế cho HTML đó chính là XHTML. 2.1.2 XML XML (Extensible Markup Language – ngôn ngữ đánh dấu mở rộng) là một ngôn ngữ đánh dấu mà người sử dụng có thể tự tạo ra các thẻ riêng của mình. Giống như HTML, XML cũng được dựa trên SGML. Tuy nhiên, XML được thiết kế nhằm mục đích truyền tải và lưu trữ thông tin, trong khi HTML tập trung vào việc thể hiện thông tin đó như thế nào. Về tính cấu trúc của nội dung, XML có thể dùng để định nghĩa các cấu trúc ngẫu nhiên tùy ý trong khi HTML hoàn toàn bị giới hạn. Ví dụ của một tài liệu XML đầy đủ: 50501352 Bill Gates 18