Đề tài Nghiên cứu công nghệ khai phá dữ liệu văn bản, áp dụng cho các trang tin tức trên các thiết bị cầm tay (pdas & smartphones)

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ VŨ NGỌC ANH NGHIÊN CỨU CÔNG NGHỆ KHAI PHÁ DỮ LIỆU VĂN BẢN, ÁP DỤNG CHO CÁC TRANG TIN TỨC TRÊN CÁC THIẾT BỊ CẦM TAY (PDAS & SMARTPHONES) LUẬN VĂN THẠC SỸ KHOA HỌC HÀ NỘI-2006 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ VŨ NGỌC ANH NGHIÊN CỨU CÔNG NGHỆ KHAI PHÁ DỮ LIỆU VĂN BẢN, ÁP DỤNG CHO CÁC TRANG TIN TỨC TRÊN CÁC THIẾT BỊ CẦM TAY (PDAS & SMARTPHONES) NGÀNH CÔNG NGHỆ THÔNG TIN CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN MÃ SỐ: 01.01.10 LUẬN VĂN THẠC SỸ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. HÀ QUANG THỤY HÀ NỘI-2006 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 2 LỜI CAM ĐOAN Tôi xin cam đoan các kết quả nêu trong luận văn là trung thực và chưa từng được công bố trong các công trình khác. Tác giả luận văn Vũ Ngọc Anh Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 3 MỤC LỤC TÓM TẮT........................................................................................................... 5 CÁC THUẬT NGỮ VÀ CÁC TỪ VIẾT TẮT .................................................. 6 CHÚ GIẢI KÝ HIỆU VÀ MÔ HÌNH................................................................ 7 CÁC HÌNH MINH HỌA.................................................................................... 8 MỞ ĐẦU ............................................................................................................ 9 CHƯƠNG I. XÂY DỰNG KÊNH CUNG CẤP TIN ĐIỆN TỬ TRÊN THIẾT BỊ CẦM TAY ................................................................................................... 12 1.1. Báo điện tử và công nghệ Internet không dây........................................ 12 1.1.1. Báo điện tử - một thành tựu của Internet ........................................ 12 1.1.2. Sự phát triển của các thiết bị cầm tay ............................................. 13 1.1.3. Công nghệ kết nối internet không dây............................................ 14 1.2. Bài toán xây dựng kênh tin tức điện tử trên thiết bị cầm tay ................. 15 1.2.1. Mô tả bài toán ................................................................................. 15 1.2.2. Mô tả các chức năng cơ bản của hệ thống...................................... 16 1.3. Hướng tiếp cận giải quyết bài toán ........................................................ 16 Chương II. THUẬT TOÁN RTDM VÀ ỨNG DỤNG TRONG TRÍCH XUẤT TIN.................................................................................................................... 18 2.1. Khái niệm “Chi phí chuyển đổi cây” ..................................................... 18 2.2. Thuật toán RTDM .................................................................................. 22 2.3. Áp dụng RTDM trích xuất tin tức tự động............................................. 29 2.3.1 Phân cụm trang ................................................................................ 31 2.3.2 Trích xuất mẫu chung ...................................................................... 32 2.3.3 Khớp dữ liệu .................................................................................... 35 2.3.4 Gán nhãn dữ liệu.............................................................................. 37 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 4 Chương III . PHÂN TÍCH THIẾT KẾ HỆ THỐNG........................................ 39 3.1.Giới thiệu................................................................................................. 39 3.2. Mô hình Use Case: ................................................................................. 40 3.2. Mô hình lớp ............................................................................................ 45 3.4. Danh sách các thực thể ........................................................................... 47 3.5. Mô hình thực thể liên kết ....................................................................... 48 Chương IV. KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ ............................ 49 4.1. Giới thiệu chung về hệ thống ................................................................. 49 4.2. Thực nghiệm và đánh giá kết quả .......................................................... 49 KẾT LUẬN....................................................................................................... 54 TÀI LIỆU THAM KHẢO ................................................................................ 55 PHỤ LỤC. MÔ TẢ CHI TIẾT CÁC THỰC THỂ ........................................... 58 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 5 TÓM TẮT Luận văn quan tâm nghiên cứu các giải pháp trích chọn thông tin trên Web nhằm xây dựng một hệ thống cung cấp tin tức trên các thiết bị cầm tay thông minh mà tin tức này được trích chọn từ các báo điện tử tiếng Việt. Luận văn sử dụng thuật toán RTDM (Restricted Top-Down Mapping) do Davi de Castro Reis và các đồng tác giả đề xuất [28], một thuật toán được đánh giá rất hiệu quả trong việc trích chọn tin tức tức tự động thông qua việc phân tích cấu trúc cây. Hiện nay RTDM được dùng như là thành phần lõi chính của hệ thống trích xuất tin tức có tên là AkwanClipping (Akwan Information Technologies, thuộc công ty Google tại Braxin) cung cấp tin tức hàng ngày của các tờ báo phổ biến nhất tại Braxin. Luận văn đã tiến hành chi tiết và hoàn thiện các phần nội dung không công bố của thuật toán RTDM, đồng thời tiến hành xây dựng một hệ thống kênh cung cấp tin điện tử trên các thiết bị cầm tay thông minh. Hệ thống thử nghiệm việc trích chọn tin tức trên các báo điện tử tiếng Việt phổ dụng hiện nay và đã cho kết quả đáng khích lệ. Chúng tôi đang tiến hành cải tiến tốc độ làm việc của hệ thống nhằm tiến tới đưa hệ thống vào hoạt động thực tế. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 6 CÁC THUẬT NGỮ VÀ CÁC TỪ VIẾT TẮT Từ viết tắt Giải nghĩa RTDM Restricted Top-Down Mapping PDA Personal digital assistant Data extraction Trích xuất dữ liệu Trees Cây biểu diễn cấu trúc trang HTML Edit distance Chi phí chuyển đổi giữa 2 cây (thay thế, chèn, xoá nút) PK Primary Key FK Foreign Key PF Primary & Foreign Key Tx Cây biểu diễn trang Web. Tx[i] Nút thứ i của cây Tx t[i] Cây con có nút gốc tại vị trí thứ i Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 7 CHÚ GIẢI KÝ HIỆU VÀ MÔ HÌNH STT Ký hiệu Giải thích 1 Tiến trình thực hiện một nhiệm vụ nào đó trong hệ thống 2 Tác nhân của hệ thống, đóng vai trò tương tác với hệ thống trong quá trình thực hiện 3 Nguồn thông tin cung cấp cho hệ thống 4 Điều kiện kiểm tra và đưa ra các quyết định tương ứng với các kết quả nhận được 5 Miêu tả sự phụ thuộc lẫn nhau của các đối tượng Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 8 CÁC HÌNH MINH HỌA Hình 3 - Ví dụ về ánh xạ giữa 2 cây ................................................................. 20 Hình 4 – Ví dụ ánh xạ trên-xuống .................................................................... 21 Hình 5 – Một ví dụ về ánh xạ trên xuống hạn chế............................................ 23 Hình 6 - Một mẫu tin chi tiết Quốc tế trên trang tienphongonline.com.vn ...... 30 Hình 7: Các bước trích xuất tin tức [28]........................................................... 31 Hình 8 - Các bước hình thành ne-pattern từ các nhóm..................................... 37 Hình 9 : Gói các lớp quản lý các cây HTML.... Error! Bookmark not defined. Hình 10 : Gói các lớp phục vụ tính toán giá trị RTDM.................................... 46 Hình 11 : Gói các lớp quản lý các trang tin tức ................................................ 46 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 9 MỞ ĐẦU Sự phát triển của báo điện tử, một thành quả của Internet nói riêng và của Công nghệ thông tin nói chung, đã dẫn tới các thay đổi lớn đối với thói quen đọc báo. Internet với ưu thế về tốc độ và khả năng vươn xa cho phép độc giả có thể tiếp cận tin tức mọi lúc mọi nơi. Với sự tiến bộ không ngừng của công nghệ viễn thông, ngày nay thiết bị cầm tay thông minh ngày càng được phổ biến với giá cả ngày càng hạ và đã trở thành một công cụ đắc lực, bình dân và không thể thay thế. Tốc độ kết nối Internet không dây được cải thiện không chỉ về tốc độ mà cả về phạm vi phủ sóng, trong đó, thế hệ mạng không dây chuẩn WIMAX (IEEE 802.16) cho phép khoảng cách phủ sóng tới 50km và thông lượng tối đa tới 70Mbps. Tất cả những yếu tố trên đây đã trở thành tiền đề cho việc đáp ứng nhu cầu xem tin tức trên thiết bị cầm tay, một nhu cầu đã trở thành thiết yếu, hàng ngày, hàng giờ của mỗi người dùng cuối các thiết bị này. Tuy nhiên, việc đọc báo trên các thiết bị cầm tay còn nhiều bất tiện. Khung màn hình hạn chế của thiết bị cầm tay không cho phép hiển thị trang Web được thiết kế cho máy tính để bàn: font chữ thường bị lỗi khi xem tin tức trên thiết bị cầm tay, các thông tin quảng cáo và banner cũng được tải về cùng với tin tức làm giảm đáng kể tốc độ và gây tràn màn hình… Chính vì vậy, mục đích của luận văn này là xây dựng một hệ thống cho phép dễ dàng và thuận tiện xem tin tức tiếng Việt của báo điện tử bất kỳ trên thiết bị cầm tay thông minh. Luận văn sử dụng thuật toán RTDM (Restricted Top-Down Mapping) do Davi de Castro Reis và các đồng tác giả đề xuất [28], một thuật toán được đánh giá rất hiệu quả trong việc trích xuất tin tức tức tự động thông qua việc phân tích cấu trúc cây. Thuật toán RTDM được cải tiến trên thuật toán trích xuất thông tin Web đã có để áp dụng đặc thù riêng cho bài toán trích xuất tin tức. Qua thực nghiệm trên 35 trang tin tức, thuật toán RTDM cho kết quả trung bình 87.71% trích xuất tin tức thành công không cần có sự can thiệp của con người. Hiện tại, RTDM được sử dụng như là thành phần lõi chính của hệ thống trích xuất tin tức có tên là AkwanClipping (Akwan Information Technologies, Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 10 thuộc công ty Google tại Braxin) cung cấp tin tức hàng ngày của các tờ báo phổ biến nhất tại Braxin. Chúng tôi đã chi tiết và hoàn thiện các nội dung không công bố của thuật toán RTDM, đồng thời tiến hành xây dựng một hệ thống kênh cung cấp tin điện tử trên các thiết bị cầm tay thông minh. Hệ thống thử nghiệm đã trích chọn thông tin trên các báo điện tử tiếng Việt phổ dụng hiện nay. Chúng tôi đã tiến hành đánh giá hệ thống và các kết quả đánh giá cho thấy hệ thống là hữu dụng. Tuy nhiên, để đưa hệ thống vào hoạt động thực tiễn cần phải nghiên cứu tăng tốc độ hoạt động của nó. Nội dung của luận văn được tổ chức thành bốn chương được giới thiệu sơ bộ như dưới đây. Chương 1. Xây dựng kênh tin tức điện tử trên các thiết bị cầm tay giới thiệu sự phát triển nhanh chóng của báo điện tử và công nghệ kết nối Internet không dây, tiền đề cho việc ra đời của kênh cung cấp tin điện tử trên các thiết bị cầm tay. Mô tả bài toán và hướng tiếp cận giải quyết bài toán xây dựng kênh tin điện tử từ các báo điện tử tiếng Việt trên các thiết bị cầm tay cũng được trình bày. Bài toán xây dựng kênh tin tức điện tử trên các thiết bị cầm tay được giải quyết trên cơ sở phân cụm các trang Web trong site báo điện tử theo đó nội dung tin tức cần trích chọn được lấy từ vùng nội dung thông tin trong cấu trúc các trang Web của site đó. Chương 2. Thuật toán RTDM và ứng dụng trong trích xuất tin trình bày vấn đề đánh giá tính tương đồng của các trang Web thông qua khái niệm chi phí chuyển đổi cây đối với kiến trúc cây mô tả các trang Web. Sau khi phân cụm, lớp tương ứng với mỗi cụm được gán nhãn để tạo dựng mô hình phân lớp cho các trang Web mới và trích chọn tin tức. Luận văn đề xuất một phiên bản chi tiết của thuật toán để thi hành hệ thống trích chọn tin tức trên các báo điện tử. Với phiên bản này, vấn đề thi hành hệ thống trở nên dễ dàng hơn. Chương 3 giới thiệu quá trình phân tích và thiết kế hệ thống theo tiếp cận hướng đối tượng. Các mô hình tương ứng được trình bày ở đây. Chương 4. trình bày hệ thống thực nghiệm với một số nhận xét đánh giá kết quả thực nghiệm. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 11 Phần Kết luận tóm tắt các kết quả chính yếu nhất của luận văn. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 12 CHƯƠNG I. XÂY DỰNG KÊNH CUNG CẤP TIN ĐIỆN TỬ TRÊN THIẾT BỊ CẦM TAY 1.1. Báo điện tử và công nghệ Internet không dây 1.1.1. Báo điện tử - một thành tựu của Internet Đọc báo chí, xem tin tức là một nhu cầu không thể thiếu của mỗi người trong xã hội thông tin, không phân biệt lứa tuổi. Các loại báo chí được phát hành đa dạng về nội dung, hình thức phù hợp với nhu cầu riêng biệt của từng độc giả. Hiện nay, với sự phát triển lớn mạnh của internet kéo theo sự bùng nổ thông tin, thông qua các trang báo điện tử. Chỉ với một thao tác tìm kiếm đơn giản, ta cũng có thể tìm được hàng trăm đến hàng ngàn trang báo đủ chủng loại. Chẳng hạn ta sử dụng công cụ tìm kiếm của Google để tìm theo từ khoá "Báo điện tử" và những trang từ Việt nam, hàng loạt các trang tin tức được liệt kê như vietnamnet.vn, vnexpress.net, dantri.com.vn, tuoitre.com.vn… Theo thống kê của google.com.vn thì có đến 755.000 kết quả tìm được, tất nhiên trong số đó rất nhiều các kết quả là trùng nhau, nhưng con số đó cũng đủ để nói lên sự phát triển lớn mạnh về số lượng của các trang tin tức điện tử tại Việt Nam hiện nay. Một ưu điểm lớn của các tin tức trên các trang báo điện tử đó là tính thời sự, cập nhật rất cao. Đối với các tin tức trên báo in giấy, có khi ta phải đợi đến ngày hôm sau mới được xem. Nhanh nhất như báo "Thể thao Việt nam", cũng phải đến 5h sáng hôm sau mới có thể đăng thông tin về các trận đấu trong buổi đêm ngày hôm đó. Ngược lại, đối với các báo điện tử, thông tin có thể được cập nhật gần như lập tức khi có sự kiện. Theo thống kê trên diễn đàn nghiệp vụ báo chí Việt Nam vào tháng 11 năm 20041, hiện có khoảng 2 triệu người Việt Nam truy cập Internet, và không ít hơn số đó là độc giả của các tờ báo điện tử như VietNamNet, VnExpress, TuoitreOnline, Lao động điện tử... Do ưu thế về phương tiện công nghệ mà báo điện tử ngày càng thu hút được nhiều độc giả. Ở Mỹ, nếu tính theo số lượng độc giả thì báo giấy đang ngày càng bị thất thế so với báo điện tử. Một nghiên cứu hồi tháng 3-2005 của Hiệp 1 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 13 Hội Báo In Hoa Kỳ (NNA) cho thấy với các tờ báo lớn và được tín nhiệm nhất ở nước Mỹ như New York Times, Washington Post, số người đọc báo qua mạng đã vượt trội số người đọc báo in (New York Times: 12,8 triệu/5 triệu; Washington Post: 7.8 triệu/1.8 triệu, Los Angeles Times: 4.3 triệu/2.4 triệu)1,2. Cũng vì sự phát triển bùng nổ như vậy nên việc đọc thông tin trên báo điện tử một cách hiệu quả cũng không phải là dễ dàng. Hiện tượng người đọc báo điện tử khó kiểm soát tin và nội dung tin đã đọc đã trở thành thực tế. Cần thiết xây dựng phương tiện hỗ trợ người dùng giải quyết hiện tượng nói trên. 1.1.2. Sự phát triển của các thiết bị cầm tay Ngày nay, với sự phát triển vượt bậc của khoa học công nghệ, các sản phẩm cầm tay đã thực sự đem lại rất nhiều hiệu quả lao động cho con người. Các thiết bị có thể kể đến ở đây là các điện thoại thông minh (smart phone), máy tính bỏ túi (pocket pc). Cùng với sự phát triển công nghệ, các thiết bị này đã được hỗ trợ khả năng lướt Web không dây với tốc độ ngày càng cải thiện. Do đó, đây cũng là một kênh tiếp cận thông tin, tin tức điện tử thuận tiện nhanh chóng, gọn nhẹ mọi lúc mọi nơi. Hơn thế nữa, do nhu cầu công việc của con người cộng với giá cả cũng hợp lý nên các thiết bị này cũng ngày càng được dùng phổ biến hơn (nhiều nhất vẫn là trong các doanh nghiệp). Những thuận 2 Hình 1. Tin tức điện tử trên các thiết bị cầm tay Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 14 lợi này là cơ sở dẫn tới nhu cầu xem tin tức điện tử trên các thiết bị cầm tay ngày một phát triển3. 1.1.3. Công nghệ kết nối internet không dây Song song với sự phát triển của các thiết bị cầm tay, công nghệ kết nối không dây cũng phát triển ngày càng mạnh mà mới đây nhất là chuẩn Wimax - 802.16e với khả năng kết nối với tốc độ 20Mbps trong phạm vi 3km và có thể tiến xa hơn. Wimax hay còn gọi là chuẩn 802.16, mới được công nhận vào tháng 1/2003, cung cấp khả năng truy cập băng rộng không dây giữa người sử dụng và điểm kết nối bằng các băng tần từ 2 đến 11 GHz, có thể kết nối mà không cần điều kiện tầm nhìn thẳng. Hiện tại, chuẩn này đã được kết nối thử nghiệm tại khoảng trên 100 điểm trên toàn thế giới. Công nghệ này đặc biệt phù hợp với việc phổ cập Internet băng rộng tại nhiều miền sâu, vùng xa. Trên thế giới hiện có khoảng 100 cuộc thử nghiệm công nghệ WiMAX đang được tiến hành. Sự quan tâm của các chính phủ và các nhà cung cấp dịch vụ về triển khai công nghệ WiMAX là bằng chứng rõ ràng cho thấy công nghệ này rất thiết thực, người dùng cuối sẽ được tận hưởng những giá trị sử dụng cao từ dịch vụ băng rộng không dây và khả năng di động không giới hạn. Hiện nay, công nghệ WiMAX đang được sử dụng làm công nghệ không dây cố định cho truy cập băng rộng đầu cuối trong năm 2005 và sẽ tiến tới di động hoàn toàn trong những năm tới4 Chưa cần đến khả năng kết nối tốc độ cao, các dịch vụ truy cập internet di động cũng sẽ được hình thành tại VN trong thời gian tới với tốc độ chấp nhận được 156Kbps đối với các thiết bị di động. Dịch vụ băng rộng di động của EVN Telecom sử dụng công nghệ CDMA 2000-1X, tần số 450 Mhz, cho phép người sử dụng kết nối Internet trực tiếp trên máy điện thoại hoặc thông qua máy tính cá nhân với tốc độ 156 Kbps đối với mạng 1X tại bất cứ nơi nào có phủ sóng5. 3 4 5 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 15 1.2. Bài toán xây dựng kênh tin tức điện tử trên thiết bị cầm tay 1.2.1. Mô tả bài toán Mục tiêu của luận văn là nghiên cứu các công nghệ khai phá dữ liệu văn bản, áp dụng cho việc xây dựng một kênh tin tức điện tử hỗ trợ cho những người sử dụng có thể đọc tin tức trên thiết bị cầm tay (PDA). Hệ thống này sẽ trích lọc, thu gọn các trang báo cồng kềnh thành các trang tin gọn nhẹ, dễ đọc với sự loại bỏ các thông tin dư thừa, các banner quảng cáo, thu nhỏ các hình ảnh sao cho phù hợp với màn hình hạn chế của các thiết bị cầm tay (Hình 1). Hình 2 mô tả sơ đồ của hệ thống kênh tin tức điện tử cho các thiết bị cầm tay. Hệ thống được tích hợp vào phục vụ truy nhập Web của các thiết bị cầm tay, cung cấp dịch vụ đọc tin tức PDA. Mỗi khi người dùng cuối sử dụng dịch vụ này, hệ thống căn cứ vào các khuôn mẫu đã được nhận biết về mỗi báo điện tử để trích chọn chỉ nội dung tin tức cần thiết cho người dùng. Cách làm như vậy rất thích hợp với việc khai thác tin tức từ các thiết bị cầm tay. Hình 2. Sơ đồ hệ thống Kênh tin tức cho các thiết bị cầm tay Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 16 1.2.2. Mô tả các chức năng cơ bản của hệ thống Hệ thống cần thực hiện được các chức năng cơ bản là xác định các tin - mục tin trên các báo điện tử, xử lý trang tin và định dạng hiển thị tin trên các thiết bị cầm tay. Dưới đây là một số yêu cầu cơ bản của các chức năng này. a) Chức năng xác định các tin - mục tin trên các báo điện tử - Yêu cầu: xác định được các mục tin của các trang báo điện tử, trong các trang chi tiết, hệ thống phải xác định được các vùng tin cần trích xuất, vùng tin có thể loại bỏ. Các vùng tin tức sau khi trích xuất sẽ được định dạng lại cho phép hiển thị trên thiết bị cầm tay. - Đề xuất giải pháp: Sử dụng kĩ thuật phân tích cấu trúc trang tin sử dụng thuật toán RTDM [28]. Giải pháp này áp dụng định dạng cho các trang tin bất kì có thể xem được trên các màn hình thiết bị cầm tay có kích thước hạn chế. b) Chức năng xử lý trang tin - Yêu cầu: xử lý nội dung trang tin cần xem, xác định kiểu trang tin, lọc bỏ các thông tin dư thừa và xây dựng lại trang tin cho phép hiển thị trên thiết bị cầm tay. c) Chức năng định dạng hiển thị tin trên các thiết bị cầm tay - Yêu cầu: Hiển thị các trang tin (phân phối giữa hình ảnh, văn bản cho phù hợp để có thể hiển thị tốt trên các thiết bị cầm tay) - Đề xuất giải pháp: Bản thân các trình duyệt trên các thiết bị cầm tay khi kết nối vào một trang bất kì sẽ hiển thị hết nội dung của trang đó, do vậy ta xây dựng một Web site thu nhỏ kích thước của trang Web tin tức. Công việc chỉnh sửa này thực hiện trên Web server sẽ làm tăng hiệu quả hoạt động của thiết bị cầm tay do tốc độ xử lý của các thiết bị cầm tay là không yêu cầu cao. 1.3. Hướng tiếp cận giải quyết bài toán Nội dung đề tài này là giải quyết bài toán phân cụm các trang web theo nội dung. Trên cơ sở bài toán phân cụm các trang web, hệ thống tìm ra các khuôn mẫu trang Web trong một site cung cấp tin tức điện tử, mỗi khuôn mẫu đó Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 17 được coi là một lớp các trang Web tương ứng trong site. Đối với mỗi khuôn mẫu, hệ thống áp dụng việc trích xuất nội dung các trang tin tức và định dạng lại cho phép xem được trên các thiết bị cầm tay. Như vậy, một bài toán cốt lõi của hệ thống là phân cụm các trang Web thuộc site báo điện tử để xác định các lớp trang Web có chung khuôn dạng trình diễn, qua đó nhận diện được vùng trong khuôn mẫu này chứa các nội dung cần trích chọn. Vấn đề xác định tính tương đồng giữa các trang Web, nền tảng để phân cụm, được trình bày trong chương tiếp theo thông qua khái niệm chi phí chuyển đổi cây và thuật toán RTDM [28]. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 18 Chương II. THUẬT TOÁN RTDM VÀ ỨNG DỤNG TRONG TRÍCH XUẤT TIN 2.1. Khái niệm “Chi phí chuyển đổi cây” Như giới thiệu ở chương trước, việc tìm kiếm hoặc trích xuất dữ liệu từ các trang Web có thể được thực hiện thông qua việc phân tích cấu trúc của các trang Web đó. Với việc phân tích cấu trúc của các trang Web này, ta có thể nhóm các trang có cùng cấu trúc thành một nhóm trang và tìm những biểu diễn giống nhau của cấu trúc của các trang Web này trong một nhóm. Nội dung chính của chương này được tổng hợp các nội dung cơ bản của [28]. Phiên bản chi tiết của thuật toán RTDM do luận văn đề xuất. Ngoài ra, luận văn cũng đưa ra một số nhận xét, ý tưởng có thể dùng để cải tiến thuật toán. Theo Davi de Castro Reis và các đồng tác giả [28], cấu trúc của các trang Web có thể được biểu diễn dưới dạng một cây (Ví dụ như Cây DOM), vì vậy chúng ta sử dụng khái niệm chi phí chuyển đổi cây (Tree Edit Distance) để đánh giá mức độ giống nhau giữa các trang. Một cách trực quan, khoảng cách giữa hai cây TA và TB là "giá tối thiểu" phải trả cho một tập các thao tác để chuyển đổi TA thành TB. Mặc dù có thể áp dụng cho cây bất kỳ, nhưng để thuận tiện áp dụng nên trong luận văn này, chúng tôi tập trung chủ yếu vào cây có thứ tự, được gán nhãn, có gốc cố định (labeled ordered rooted tree). Một cây có gốc (rooted tree) là cây có đỉnh gốc là cố định. Cây có thứ tự có gốc (ordered rooted tree) là cây có gốc cố định và thứ tự các con là cố định với mỗi đỉnh. Cây có thứ tự, được gán nhãn, có gốc cố định là cây có mỗi đỉnh được gán nhãn l. Từ đây về sau, chúng ta sẽ đơn giản sử dụng khái niệm "cây" để chỉ cây có thứ tự, được gán nhãn, có gốc cố định, các trường hợp khác sẽ được chú thích cụ thể. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 19 Để mô tả cấu trúc cây của các trang Web, ta giả sử rằng các trang Web này được biểu diễn dưới dạng một cây "cây có thứ tự, được gán nhãn, có gốc cố định". Các nhãn ở đây chính là các thẻ HTML như , , … Hình 3. Ví dụ cây có thứ tự, được gán nhãn, có gốc cố định Chi phí tính toán chi phí chuyển đổi cây thông qua việc sử dụng 3 thao tác chính là Xoá đỉnh, Chèn đỉnh, Thay thế đỉnh. Chi phí cho từng thao tác này là khác nhau tuỳ trường hợp. Giải pháp của bài toán chính là tìm tập hợp các thao tác được thực hiện với chi phí là nhỏ nhất để chuyển đổi giữa hai cây. Một bài toán tương đương chính là bài toán tìm ánh xạ chuyển đổi (dưới đây gọi tắt là ánh xạ) giữa hai cây với chi phí nhỏ nhất. Trong các phần trình bày dưới đây, kí hiệu Tx để chỉ một cây và kí hiệu Tx[i] để chỉ đỉnh thứ i của Tx. Kích thước của một cây chính là số đỉnh có trong cây đó. Davi de Castro Reis và các đồng tác giả đã xem xét khái niệm ánh xạ chuyển đổi cây như một khái niệm cơ bản trong phương pháp của họ [28]. Định nghĩa 1 [17, 18, 21, 25, 28] Ánh xạ giữa cây T1 kích thước n1 và cây T2 kích thước n2 là một tập hợp M các cặp có thứ tự (i, j) thoả mãn các điều kiện sau với mọi (i1, j1), (i2, j2) ∈ M: • i1 = i2 khi và chỉ khi j1 = j2. • T1[i1] ở bên trái của T1[i2] khi và chỉ khi T2[j1] ở bên trái T2[j2] Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 20 • T1[i1] là tổ tiên của T1[i2] khi và chỉ khi T2[j1] là tổ tiên của T2[j2] Hình 1 - Ví dụ về ánh xạ giữa 2 cây Điều kiện 1 xác định một đỉnh của một cây không xuất hiện quá 1 lần trong ánh xạ, điều kiện thứ 2 bảo toàn thứ tự trái - phải giữa các nút, còn điều kiện thứ 3 đảm bảo cấu trúc phân cấp giữa 2 cặp nút trong ánh xạ. Nói một cách đơn giản, phép ánh xạ cho phép mô tả các bước hiệu chỉnh từ cây này thành cây kia, không quan tâm đến thứ tự các thao tác được áp dụng. Trong hình 3, những đường nét đứt giữa các đỉnh của cây T1 và các đỉnh của cây T2 phải thay đổi nếu các đỉnh này khác nhau, các đỉnh còn lại không phải thay đổi. Đỉnh không có đường nào nối tới trên cây T1 là đỉnh sẽ bị xoá, còn đỉnh không có đường nào nối tới trên cây T2 là đỉnh phải được chèn vào. Như đã đề cập ở trên, việc tìm chi phí chuyển đổi cây tương đương với việc tìm chi phí nhỏ nhất cho ánh xạ giữa 2 cây. Gọi M là ánh xạ giữa hai cây T1 và cây T2, gọi S là tập con các cặp (i,j) ∈ M với các nhãn riêng biệt, D là tập hợp các nút trong T1 mà không xuất hiện trong bất cứ cặp (i,j) ∈ M, I là tập hợp các nút trong T2 mà không xuất hiện trong bất cứ cặp (i,j) ∈ M. Khi đó chi phí cho việc ánh xạ được cho bởi công thức: c = Sp + Iq + Dr Trong đó p, q, r tương ứng là chi phí cho thao tác thay thế, chèn và xóa một nút. Ta có thể giả thiết các chi phí này là bằng nhau nhưng khi cài đặt vào ứng dụng thực thì các chi phí này có thể khác nhau. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 21 Bài toán tính toán chi phí chuyển đổi giữa hai cây là một bài toán khó, có một số giải thuật, đưa vào một số các yếu tố cân bằng khác nhau, được đề xuất gần đây, tuy nhiên tất cả đều có độ phức tạp tính toán trên cấp đa thức bậc hai. Hơn nữa, người ta chứng minh rằng nếu hai cây không có thứ tự thì bài toán có độ phức tạp là NP-đầy đủ. Thuật toán đầu tiên về bài toán ánh xạ (được giới thiệu trong tài liệu [18]) với độ phức tạp là O(n1n2h1h2) với n1 và n2 là kích thước của cây, h1 và h2 là độ cao tương ứng. Đây là thuật toán tính toán động thực hiện việc tính toán đệ quy chi phí chuyển đổi giữa các xâu biểu diễn tập hợp các đỉnh con của các đỉnh của cây. J. T. L. Wang và các đồng tác giả [21] đã giới thiệu một thuật toán với độ phức tạp O(d2n1n2min(h1,l1)min(h2,l2)) với d là chi phí chuyển đổi giữa các cây con, h1 và h2 là chiều cao còn l1 và l2 là số các lá của mỗi cây. Một trong các cách tiếp cận điển hình là tiếp cận dựa trên phép ánh xạ trên- xuống, phép ánh xạ trên-xuống hạn chế các thao tác chèn và xoá ở các nút lá. Hình 4 minh hoạ một ánh xạ trên-xuống như định nghĩa dưới đây. Định nghĩa 2 Ánh xạ M giữa cây T1 và cây T2 được gọi là trên-xuống khi và chỉ khi với mọi cặp (i1,i2) ∈ M, ta cũng có một cặp (cha(i1), cha(i2)) ∈ M với i1 và i2 tương ứng không phải là nút gốc của T1 và T2. Hình 2 – Ví dụ ánh xạ trên-xuống Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 22 Thuật toán đầu tiên giải quyết bài toán tính toán chi phí chuyển đổi cho ánh xạ trên - xuống được Selkow giới thiệu trong [17]. Yang [25] giới thiệu một thuật toán quy hoạch động với độ phức tạp là O(n1n2) trong đó n1, n2 là kích thước tương ứng của T1 và T2. S. S. Chawathe [5] giới thiệu một thuật toán khác khá phổ biến giải quyết bài toán ánh xạ trên-xuống cũng với độ phức tạp O(n1n2), tuy nhiên thuật toán này không sử dụng phương pháp quy hoạch động mà được giải quyết bằng thuật toán đơn hình. Ánh xạ trên-xuống cũng đã áp dụng thành công trong một số ứng dụng liên quan đến Web, ví dụ như ứng dụng phân loại tài liệu. Trong [16], Nierman và Jagadish sử dụng thuật toán tính toán chi phí chuyển đổi cho ánh xạ trên xuống để phân nhóm các tài liệu XML. Trong bài toán "Trích xuất tin tức tự động", luận văn này chỉ quan tâm đến vấn đề xác định sự tương đồng giữa cấu trúc của các trang Web. Thực sự là các trang Web có cấu trúc hoặc là cấu trúc HTML hoặc là XML, như đã đề cập ở trên, có thể biểu diễn dưới dạng cây có thứ tự được gán nhãn, có gốc cố định. Thường mô hình DOM được vận dụng để mô tả cây. Trong phần tiếp theo sẽ trình bày thuật toán mới xác định chi phí ánh xạ giữa các cây biểu diễn cấu trúc của các trang Web cho lớp bài toán giới hạn đó là ánh xạ trên-xuống, kết quả của thuật toán này chính là chi phí chuyển đổi giữa các cây đó. 2.2. Thuật toán RTDM Mục này sẽ trình bày một thuật toán xác định một kiểu ánh xạ "trên-xuống hạn chế" (Restricted Top-Down Mapping) [28]. Một cách trực quan, trong phép ánh xạ trên-xuống hạn chế, các thao tác chèn, xóa, thao tác thay thế các đỉnh chỉ hạn chế thao tác với các lá của cây. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 23 Định nghĩa 3 [28] Một ánh xạ trên-xuống M giữa cây T1 và cây T2 được gọi là trên-xuống hạn chế khi và chỉ khi với mọi cặp (i1,i2) ∈ M, mà t1[i1] ≠ t2[i2], thì sẽ không có con cháu của i1 và i2 thuộc M, với i1 và i2 không phải là nút gốc của các cây T1, T2. Hình 3 – Một ví dụ về ánh xạ trên xuống hạn chế Theo [28], thuật toán RTDM là kết hợp giữa ý tưởng được nêu trong các công trình [19, 25]. Để xác định ánh xạ giới hạn trên-xuống giữa 2 cây T1 và T2, đầu tiên thuật toán RTDM tìm các cây con cùng mức giống hệt nhau của T1 và T2. Bước này của thuật toán thực hiện trong thời gian tuyến tính sử dụng đồ thị các lớp tương đương thực hiện tương tự như trong [19], tuy nhiên thuật toán trong [28] thực hiện duyệt cây theo thứ tự sau và cách tiếp cận đơn giản hơn vì chỉ quan tâm đến những cây con cùng mức giống hệt nhau. Sau khi các đỉnh của cây được nhóm thành các lớp tương đương, chúng ta áp dụng thuật toán của Yang [25] để tìm ánh xạ trên-xuống hạn chế nhỏ nhất giữa các cây. Nội dung thuật toán RTDM được trình bày như sau: 1 RTDM(T1, T2, ε: ngưỡng) 2 begin 3 m ← số con của nút gốc của cây T1 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 24 4 n ← số con của nút gốc của cây T2. 5 M [i,0] ←0 ∀i = 0,....m 6 M[0,j] ←0 ∀j = 0,....n 7 for i=1 to m do 8 for j=1 to n do 9 Ci ← {con của (t1[i])} 10 Cj ← {con của (t2[j])} 11 d ← M[i - 1, j] + tổng_chi_phí_xoá(T1[k]); (T1[k] là các đỉnh ∈ Ci) 12 i ← M[i, j -1 ] + tổng_chi_phí_chèn(T2[k]) ; (T2[k] là các đỉnh ∈ Cj) 13 if M[i -1, j -1] > ε then 14 s ← ∞ 15 elseif T1[i] và T2[j] là các cây con giống nhau 16 s ← 0 17 elseif 18 if T1[i] là lá 19 s ← chi_phí_thay_thế(T1[i], T2[j]) 20 s ← s + tổng_chi_phí_chèn (T2[k]) ; (T2[k] là các đỉnh ∈ Cj) 21 elseif T2[j] là lá 22 s ← chi_phí_thay_thế(t1[i], t2[j]) 23 s ← s + tổng_chi_phí_xoá(T1[k]); (T1[k] là các đỉnh ∈ Ci) 24 else 25 s ← RTDM(T1[i], T2[j], ε) 26 end if 27 end if Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 25 28 M[i, j] ← min(d, i, s) 29 end for 30 end for 31 return M[m, n] 32 End Như diễn giải trong [28], thuật toán chuyển đổi cây trên-xuống thông thường của Chawathe trình bày trong bài báo [5] thực hiện trong thời gian O(n1n2), và theo lý thuyết thì đây là thuật toán tốt nhất hiện nay. Còn với thuật toán RTDM thì thời gian thực hiện trong trường hợp tồi nhất cũng chỉ là O(n1n2). Tuy nhiên trong thực tế, nó thực hiện tốt hơn nhiều do nó chỉ thực hiện trên ánh xạ trên- xuống hạn chế. Thuật toán RTDM có chi phí thời gian tính toán tồi nhất khi hai cây giống hệt nhau. Trong các trường hợp khác, chi phí thường được cắt giảm khi thuật toán bỏ qua các dòng lệnh 18-23 hoặc 15-16. Ở đây thuật toán có đưa ra khai niệm “ngưỡng” để đề phòng trường hợp thuật toán rơi vào vòng lặp vô hạn, khi đó thuật toán bỏ qua các dòng lệnh 13-14, trường hợp này rất hay xẩy ra khi chúng ta phân cụm các cây dựa trên cấu trúc tương tự của chúng. Chúng ta cũng nhận thấy rằng, nếu bỏ các dòng lệnh 18-23 thì thuật toán mới thu được áp dụng cho việc tính toán chi phí chuyển đổi cây trên-xuống thông thường. Một khía cạnh đáng chú ý khác của thuật toán RTDM là tính linh hoạt của chi phí các thao tác trên cây cho phép kết quả đưa ra có tính phức hợp cao. Nó cho phép so sánh cây cho trước với mẫu có kích thước biến đổi. Thuật toán sẽ được áp dụng để tìm kiếm tin tức tự động trên các trang Web và trích xuất các thành phần của tin tức (ví dụ như: tiêu đề, nội dung,…). Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 26 Tuy nhiên thuật toán trên mới chỉ cho phép tính toán chi phí chuyển đổi cây, giá trị trả về là tổng các chi phí xoá, chèn và thay thế. Giá trị đó chỉ có thể áp dụng trong bước 1 (phân cụm) trong 4 bước trích xuất đề cập trong phần sau. Các bước trích xuất mẫu, khớp dữ liệu yêu cầu phải xác định được ánh xạ giữa hai cây. Vì yếu tố bí mật kinh doanh nên Davi de Castro Reis và các đồng tác giả đã không đưa vào các bước cho phép lưu giữ ánh xạ giữa hai cây trong thuật toán này. Chính vì vậy luận văn này xin đề xuất thuật toán sửa đổi thuật toán RTDM của nhóm tác giả Braxin cho phép tính toán chi phí chuyển đổi cây và lưu giữ ánh xạ giữa 2 cây này. 1 SetTreeNodeIndex(T1) SetTreeNodeIndex(T2) Đánh số thứ tự cho các nút trên cây T1 và T2 theo thứ tự duyệt trước 2 Mapping[i,j] = 0; (∀i = 0,....M, ∀j = 0,....N) Biến toán cục, Mapping[i,j]= 1- có ánh xạ giữa nút thứ i trên cây T1 và nút thứ j trên cây T2, 0 – không có ánh xạ, M- số con cháu của T1, N – số con cháu của T2 3 RTDM(T1, T2, ε: ngưỡng) 4 begin 5 m ← số con của nút gốc của cây T1 6 n ← số con của nút gốc của cây T2. 7 M [i,0] ←0 ∀i = 0,....m 8 M[0,j] ←0 ∀j = 0,....n 9 Action[i,j] = 0; (∀i = 0,....m, ∀j = 0,....n) Lưu giữ thao tác cho chi phí nhỏ nhất, Action[i,j] = 1 – thay thế, 2 – xóa, 3 – chèn 10 for i=1 to m do Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 27 11 for j=1 to n do 12 Ci ← {con của (t1[i])} 13 Cj ← {con của (t2[j])} 14 d ← M[i - 1, j] + tổng_chi_phí_xoá(T1[k]); (T1[k] là các đỉnh ∈ Ci) 15 i ← M[i, j -1 ] + tổng_chi_phí_chèn(T2[k]) ; (T2[k] là các đỉnh ∈ Cj) 16 Action[i, j] = 1; Mặc định là thay đổi 17 if M[i -1, j -1] > ε then 18 s ← ∞ 19 elseif T1[i] và T2[j] là các cây con giống nhau 20 s ← 0 21 elseif 22 if T1[i] là lá 23 s ← chi_phí_thay_thế(T1[i], T2[j]) 24 s ← s + tổng_chi_phí_chèn (T2[k]) ; (T2[k] là các đỉnh ∈ Cj) 25 elseif T2[j] là lá 26 s ← chi_phí_thay_thế(t1[i], t2[j]) 27 s ← s + tổng_chi_phí_xoá(T1[k]); (T1[k] là các đỉnh ∈ Ci) 28 else 29 s ← RTDM(T1[i], T2[j], ε) 30 end if 31 end if 32 M[i, j] ← min(d, i, s) 33 if (d = min(d, i, s)) Action[i, j] = 2; Chi phí xoá nhỏ nhất 34 if (i = min(d, i, s)) Action[i, j] = 3; Chi phí chèn nhỏ nhất Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 28 35 end for 36 end for 37 ii = m; 38 jj = n; 39 while ((ii > 0) && (jj > 0)) theo vết ngược về vị trí M[0,0] tuỳ theo giá trị của Action để gán ánh xạ giữa các nút 40 switch (Action[ii, jj]) 41 case 1: thay đổi 42 Mapping[ii,jj] = 1 43 ii--; 44 jj--; 45 case 2: xoá 46 Mapping[ii,jj] = 0 47 ii--; 48 case 3: chèn 49 Mapping[ii,jj] = 0 50 jj--; 51 endswitch 52 endwhile 53 return M[m, n] 54 End Trong thuật toán sửa đổi, hai cây trước khi đưa vào thuật toán RTDM sẽ được đánh số thứ tự cho các nút. Nút gốc sẽ có số thứ tự 1, các nút còn lại trong cây được đánh số theo thứ tự duyệt trước của cây. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 29 Thuật toán đưa vào biến toàn cục Mapping là mảng có kích thước MxN, trong đó M và N là số con cháu tương ứng của 2 cây. Biến Mapping sẽ lưu giữ ánh xạ giữa 2 cây, nếu giá trị tại vị trí i, j là 1 thì nút thứ i trên cây T1 có ánh xạ sang nút thứ j trên cây T2. Biến Action là mảng 2 chiều có kích thước mx n, trong đó m, n là số con tương ứng của cây T1 và cây T2. Biến mảng Action sẽ theo vết các thao tác (chèn, xoá, thay thế) có chi phí nhỏ nhất. Bước cuối cùng sẽ căn cứ giá trị của mảng Action thuật toán theo vết tìm ngược về vị trí khởi tạo và gán ánh xạ cho các nút có chi phí thay đổi là nhỏ nhất. Mảng kết quả thu được Mapping sẽ xác định giữa 2 nút tương ứng trên 2 cây có ánh xạ hay không. 2.3. Áp dụng RTDM trích xuất tin tức tự động Trong mục này, chúng ta xem xét ứng dụng của thuật toán RTDM trong việc trích xuất tin tức tự động, bao gồm xác định nội dung tin và các thành phần liên quan, loại bỏ các thông tin dư thừa của trang Web tin tức như mục quảng cáo, các liên kết. Công việc trích xuất này bao gồm 2 quá trình: (1) duyệt một loạt các trang tin tức cần xem để lấy thông tin của trang đó về, trích xuất các tin tức từ những trang HTML đã chọn lựa. Các kĩ thuật duyệt qua các trang html của một Website đã được trình bày tại một số tài liệu, chẳng hạn [12], chúng ta chỉ xem xét quá trình trích xuất tin tức từ các trang này. Để xác định được một nội dung tin tức, ta cần phải tìm ra các điểm chung của các trang tin (news portal). Các tờ báo tin tức thường có cấu trúc như sau: “trang chủ” (home page) chỉ hiển thị một số tiêu đề tóm tắt của các mục tin, các “trang mục tin” có các tin tức theo chủ đề nhất định và các tin này được tóm tắt bằng tiêu đề, hình ảnh đi kèm, và tin tóm lược. Những “trang tin chi tiết” chứa nội dung tin thường có tiêu đề, tên tác giả, ngày đăng và nội dung Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 30 của tin tức. Nhiệm vụ của chúng ta là phải xác định được chính xác nội dung tin tức, bỏ qua các thông tin khác. Cách tiếp cận trong luận văn của chúng tôi dựa trên giả thiết là nội dung trang tin tức có thể chia thành các nhóm mà mỗi nhóm có chung một định dạng và thuộc tính dàn trang. Giả thiết này là có cơ sở khi ngày này các trang Web được xây dựng sử dụng chương trình hoặc các đoạn mã chương trình lấy thông tin từ cơ sở dữ liệu, lên khuôn dạng và tự động sinh ra trang HTML. Chúng ta gọi những định dạng chung này là một mẫu (template). Hình sau giới thiệu một mẫu trên trang Tiền Phong Online. Hình 4 - Một mẫu tin chi tiết Quốc tế trên trang tienphongonline.com.vn Định nghĩa 4: Template là một tập hợp các khuôn dạng có cấu trúc và đặc trưng chung xuất hiện trong tập các trang HTML được sinh ra bởi một chương trình hoặc một đoạn mã chương trình. Với các trang Web tin tức, các nhà báo chỉ việc điền thông tin vào một template hoặc thông qua một giao diện cập nhật vào cơ sở dữ liệu. Mỗi một trường trong template đó được gọi là một đối tượng siêu dữ liệu (data-rich object). Vì thế, nhiệm vụ của ta là phải xác định được chính xác các template để từ đó trích xuất được nội dung tin, tiêu đề, ngày xuất bản… Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 31 Các bước để thực hiện trích xuất tin tức bao gồm 4 bước sau: (1) nhóm các trang html, (2) xác định mẫu chung, (3) khớp dữ liệu và (4) gán nhãn dữ liệu. Hình sau minh hoạ cho các bước này: Hình 5: Các bước trích xuất tin tức [28] 2.3.1 Phân cụm trang Bước Phân cụm trang (Page Clustering) là thu thập một tập các trang Web (các trang huấn luyện) rồi phân cụm các trang có các thuộc tính dàn trang và định dạng tương tự nhau. Mỗi một nhóm này sẽ được tổng quát hoá thành các template ở bước tiếp theo. Việc phân cụm này không chỉ đơn thuần là nhóm các URL lại với nhau, bởi vì chỉ với một sự thay đổi rất nhỏ của chương trình hoặc đoạn mã cũng có thể sinh ra một trang HTML hoàn toàn khác. Để xây dựng các nhóm, chúng ta sử dụng thuật toán phân cấp truyền thống với biện pháp phân biệt là giá trị đầu ra của thuật toán RTDM. Sẽ không có số lượng các nhóm được xác định trước, thay vì đó ta sẽ chấp nhận một giá trị ngưỡng để sao cho 2 nhóm có thể hợp nhất, giá trị ngưỡng trong đồ án này là sự tương đương 80% giữa 2 nhóm. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 32 2.3.2 Trích xuất mẫu chung Nhiệm vụ chính trong bước Trích xuất mẫu chung (Extraction Pattern Generation) là tổng quát hoá các nhóm trang thành các mẫu chung ne-pattern (node extraction pattern). Khái niệm ne-pattern là một cây được định nghĩa như sau: Định nghĩa 5 [28] Mẫu chung (ne-pattern) là một cây có thứ tự được gán nhãn, có gốc cố định (rooted ordered labeled tree) có chứa các đỉnh đặc biệt gọi là các thẻ đại diện (wildcard). Mỗi một wildcard phải là một lá của cây và thuộc một trong các dạng sau: SINGLE ( .): Wildcard đại diện cho một cây con và bắt buộc phải có. PLUS (+): Wildcard đại diện cho một số cây con và bắt buộc phải có. OPTION (?): Wildcard đại diện cho một cây con và có thể bỏ qua. KLEENE (*): Wildcard đại diện cho một số cây con và có thể bỏ qua. Ta có thể coi ne-pattern như một biểu diễn đơn giản của cây. Mục đích của bước này là đảm bảo rằng mỗi một wildcard sẽ phù hợp với một vùng thông tin (data-rich) trong template. Single và plus wildcard sẽ tương ứng với các đối tượng ta cần tìm như title của tin tức, kleene wildcard sẽ tương ứng với các đối tượng khác như danh sách các tin tức liên quan. Ta nói ne-pattern khớp với một cây khi và chỉ khi chi phí ánh xạ giữa ne- pattern và cây đó là hữu hạn. Như thế, mục đích của bước này là: với đầu vào là một nhóm trang, ta phải xây dựng được một ne-pattern mà phù hợp với mọi trang trong nhóm đó. Như vậy, các nội dung khác nhau của các trang sẽ được biểu diễn trong ne-pattern dưới dạng các wildcard. Để xây dựng được ne- pattern, ta xây dựng một phép toán kết hợp như sau: Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 33 Định nghĩa 6 [28] Gọi T x1 và T x2 là 2 ne-pattern khác nhau, ta có kết hợp của T x1 và T x2 là một ne- pattern T x3 sao cho: • Cho S1 là tập hợp các cây khớp với mẫu T x1 • Cho S2 là tập hợp các cây khớp với mẫu T x2 • Cho S3 là tập hợp các cây khớp với mẫu T x3 • Khi đó S1 ∪ S2 ⊆ S3. Quá trình xây dựng ne-pattern của một nhóm được tiến hành bằng cách khởi tạo các cây của tất cả các trang Web trong nhóm, sau đó tiến hành từng bước kết hợp mỗi cây với các cây khác trong nhóm để tạo ra một ne-pattern phù hợp với 2 ne-pattern trước đó (chú ý rằng: mỗi một cây có thể coi là một ne-pattern không có các Wildcard). Tại bước cuối cùng, ta có một ne-pattern chấp nhận mọi trang Web trong nhóm. Để cải thiện quá trình kết hợp này, ta sử dụng thuật toán RTDM như sau (Giả sử cho 2 ne-pattern T x1 và T x2 , ta cần tìm T x3 là kết hợp của T x1 và T x2 ). - Ta gọi 2 đỉnh a và b của một ne-pattern là tương đương khi và chỉ khi: + a và b là các wildcard cùng kiểu + a và b không phải là widlcard nhưng nhãn của a và b là giống nhau - Ta xác định ánh xạ giữa T x1 và T x2 (chính là một tập các cặp (i, j) ∈M), từ ánh xạ này ta xác định được kết hợp của T x1 và T x2 theo luật sau: + Nếu đỉnh a ∈ T x1 không có trong ánh xạ thì chèn a' vào T x3 với a' = f(a,?). + Nếu a ∈ T x1 ánh xạ đến b ∈ T x2 thì chèn a' vào T x3 với a' = f(a,b) Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 34 + f(a,b) được định nghĩa như sau: f(∗, ∗) = ∗ f(∗, +) = ∗ f(∗, ?) = ∗ f(∗, ⋅) = ∗ f(∗, n) = ∗ f(+, +) = + f(+, ⋅) = + f(+, ?) = ∗ f(+, n) = + f(⋅, ⋅) = ⋅ f(⋅, ?) = ? f(⋅ , n) = ⋅ f( ?, ?) = ? f(? , n) = ? f(n1, n2) = n1 nếu n1 và n2 cùng nhãn f(n1, n2) = ⋅ nếu n1 và n2 có nhãn khác nhau Với n1, n2 là các đỉnh không phải là wildcard (thứ tự của n1, n2 trong f không quan tâm). Các luật ở trên có ý nghĩa là: với các wildcard là option (?) thì sau khi kết hợp có thể giữ lại hoặc không (ghép với các khác), còn các wildcard kleene (*) và plus (+) thì phải được giữ lại đến cuối của quá trình tạo ne-pattern. Còn đối với một đỉnh không phải wildcard kết hợp với một đỉnh khác cũng không phải wildcard thì có thể tạo ra một loại wildcard. Ta cũng chú ý rằng, một vài vùng dữ liệu thông tin có thể trải dài trên nhiều cây con (chẳng hạn như nội dung của tin tức). Việc nhóm các phần này thành một thực thể duy nhất là nhiệm vụ của kleene và wildcard. Bên cạnh đó, nếu xem xét kĩ hàm f(a, b) thì ta sẽ thấy, các wildcard kleene (*) và plus (+) chỉ được sinh ra nếu như một trong 2 wildcard là (*) hoặc (+). Các wildcard này cũng sẽ được tạo ra sau một bước hậu xử lý như sau: • Các wildcard đứng trước một tập hợp các wildcard option (?) thì nên chuyển thành wildcard kleene hoặc plus. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 35 • Nếu như wildcard đứng trước tập hợp các wildcard option là một wildcard single hay plus thì tập hợp các wildcard option và wildcard đó sẽ đuợc chuyển thành 1 wildcard plus duy nhất. • Nếu wildcard là một option hay kleene wildcard thì wildcard này và cả wildcard option kề với nó sẽ được chuyển thành 1 wildcard kleene. • Việc gộp các wildcard có thẻ tiến hành nếu như các wildcard không cách nhau quá 3 đỉnh non-wildcard. 2.3.3 Khớp dữ liệu Mục đích của bước Khớp dữ liệu (Data matching) là khớp các ne-pattern đã được sinh ra với các trang Web huấn luyện để tìm ra ne-pattern thích hợp nhất với các trang Web huấn luyện (ta sử dụng RTDM để thực hiện công việc này). Trước hết, ta phải hiểu nếu như một wildcard ánh xạ đến một đỉnh của cây HTML thì wildcard đó đại diện cho đỉnh đó. Định nghĩa 7 [28] Ánh xạ giữa một ne-pattern và cây biểu diễn cấu trúc trang HTML là một luật thỏa mãn: 1. Mọi đỉnh non-wildcard được ánh xạ thành một đỉnh duy nhất trong cây HTML. 2. Mọi đỉnh của cây HTML phải được ánh xạ một đỉnh duy nhất trong ánh xạ hoặc bằng một wildcard. 3. Single wildcard biểu diễn một cây con của cây HTML 4. Plus wildcard phải biểu diễn ít nhất một cây con của cây HTML 5. Option wildcard phải biểu diễn một cây con của cây HTML nếu có thể Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 36 6. Kleene wildcard phải biểu diễn ít nhất một cây con của cây HTML nếu có thể 7. Plus wildcard thay thế càng nhiều các cây con cùng cha càng tốt 8. Kleene wildcard phải thay thế càng nhiều các cây con cùng cha của cây HTML càng tốt Các luật 1, 2, 3, 4 là đủ để đảm bảo ne-pattern khớp với cây HTML. Các luật 5, 6 làm cho điều kiện khớp chặt chẽ hơn. Luật 7, 8 luôn luôn thỏa mãn, chúng chỉ giúp ta hiểu rõ hơn về cách thức hoạt động của một ne-pattern. Hàm đánh giá cho RTDM được thực hiện như sau: Giả sử a là một đỉnh của ne-pattern, b là một đỉnh của cây HTML. Chi phí hình thức của thuật toán RTDM là: • Chi phí cho thao tác thay thế đỉnh: (A) a là wildcard Æ 0 (B) nếu không Æ ∞ • Chi phí cho thao tác chèn đỉnh: (C) Tồn tại cha của b mà được xây dựng từ wildcard Æ 0 (D) Đỉnh cùng cha bên trái của b là một wildcard (*) Æ 0 (E) Đỉnh cùng cha bên trái của b là một wildcard (+) Æ 0 (F) Nếu không thì Æ ∞ • Chi phí cho thao tác xóa đỉnh: (G) Nếu a là một wildcard (*) hoặc (+) Æ 0 (H) Nếu không Æ ∞ Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 37 Chi phí thay thế (A) đảm bảo chỉ có một wildcard có thể bị thay thế bởi một cây con mà chúng sử dụng. Chi phí chèn (C) cho phép một cây con hoàn chỉnh được thay thế bởi một wildcard. Chi phí chèn (D), (E) cho phép các wildcard có thể thay thế một danh sách các cây con. Chi phí (G) đảm bảo chỉ có các đỉnh optional mới có thể bị xóa, ta thường thay thế chi phí này bằng chi phí (A). Chi phí (B), (F), (H) đảm bảo ne-pattern phải phù hợp với trang Web, nếu không sẽ có chi phí vô hạn. Khi ne-pattern đã được xây dựng, quá trình trích xuất tin tức sẽ được thực hiện qua bước 4. 4 Hình 6 - Các bước hình thành ne-pattern từ các nhóm 2.3.4 Gán nhãn dữ liệu Kết quả của bước Khớp dữ liệu là một tập hợp các text pasages có thứ tự, mỗi một text-pasage chính là một tập hợp các đỉnh mà được đại diện bởi một wildcard trong ne-pattern. Chúng ta có thể xác định lại các tập hợp này như Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 38 sau: T = (t1, p1), (t2, p2),…, (tn, pn) với ti là text-pasage được lấy bởi wildcard và pi là vị trí đỉnh của wildcard này. Mục đích của bước Gán nhãn dữ liệu (Data Labeling) là lựa chọn từ T hai giá trị ti, tj là tiêu đề và nội dung của tin tức. Để làm được việc này, cần thực hiện một luật heuristic trên tập hợp T như sau: + length(ti) là số từ trong pasage ti. + ti ∩ tk là số từ xuất hiện trong pasage ti và tk + ti là nội dung tin khi và chỉ khi length(ti) > length(tk) với mọi 1<k<n (k≠i) và length(tk) >100. + tj là tiêu đề của tin tức khi và chỉ khi 1 ≤ length(ti) ≤ 20 và ik ik ij ij pp tt pp tt − ∩>− ∩ với mọi 1<k< j (k≠j). Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 39 CHƯƠNG III . PHÂN TÍCH THIẾT KẾ HỆ THỐNG 3.1.Giới thiệu Hệ thống kênh tin tức điện tử cho thiết bị cầm tay được thiết kế theo mô hình CSDL quan hệ, công cụ được sử dụng ở đây là phần mềm Dezign for Database version 3.4 (chi tiết tham khảo Đây là phần mềm thiết kế cơ sở dữ liệu rất gọn nhẹ và trực quan phù hợp với mọi bài toán có kích thước khác nhau, đặc biệt là phù hợp với hệ thống cơ sở dữ liệu cho Kênh tin tức điện tử trên thiết bị cầm tay. Hệ thống sử dụng hệ quản trị MySQL, đây là một hệ quản trị cơ sở dữ liệu mã nguồn mở phổ biến nhất hiện nay. MySQL có ưu thế gọn nhẹ, bảo mật và tốc độ truy xuất cao, đặc biệt thích hợp với các hệ thống ứng dụng trên Web. Các module hệ thống được thiết kế theo mô hình UML 2.0 bằng chương trình Enterprise Architect 6.1 (chi tiết tham khảo: Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 40 3.2. Mô hình Use Case: Các thành phần trong mô hình: Mã số Tên xử lý Giải thích Process 1 Tạo cây HTML Tạo cây theo mô hình DOM (Document Object Model) Process 2 Tạo nhóm trang Phân nhóm các trang HTML Process 3 Xác định mẫu Xây dựng mẫu cho từng Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 41 kiểu trang HTML Process 4 Thiết lập giá trị các lá của cây mẫu Process 5 Hiển thị trang tin Hiển thị teho định đạng của thiết bị cầm tay Process 6 Tính RTDM Tính giá trị RTDM cho từng cặp cây HTML Actor 1 Người đọc tin Event 1 Nhập URL trang tin Info 1 Nhóm trang Info 2 Cây HTML Check 1 Kiểm tra link Resource 1 Trang web huấn luyện Khi người dùng cuối nhập địa chỉ một trang tin tức hoặc lựa chọn trang tin có sẵn, hệ thống sẽ tiến hành kiểm tra liên kết (Url) đó: • Nếu tờ báo (News Site) đó đã được duyệt trước đó thì hệ thống sẽ tiến hành xác định mẫu của trang (page) tin tức cần xem và gán nhãn cho cây mẫu với thông tin của trang tin tức, sau đó tạo trang HTML và trả lại kết quả cho người dùng cuối. • Nếu tờ báo đó chưa được duyệt lần nào, hệ thống sẽ phải tiến hành phân nhóm và tạo mẫu. Để tiến hành phân nhóm và tạo mẫu, hệ thống sẽ phải lấy về một số trang huấn luyện (cỡ khoảng 200 trang với độ sâu cấp 3 của site). Từ các trang huấn luyện thu được, hệ thống sẽ tạo cây HTML theo mô hình DOM và áp dụng thuật toán RTDM để tính giá trị RTDM cho từng cặp cây này. Căn cứ vào các giá trị RTDM hệ thống sẽ nhóm các trang HTML cùng kiểu và tạo ra các mẫu. Các mẫu này sẽ được gán nhãn và trên cơ sở các nhãn này, hệ thống sẽ tiến hành loại bỏ hay giữ lại Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 42 các thông tin trên cây HTML sau khi được gán giá trị thực của trang tin. Process 1 – Tạo cây HTML Dùng để tạo các cây HTML rồi chèn vào Cơ sở dữ liệu. Đầu vào của tiến trình này là url của trang tin. Để thực hiện công việc tạo cây, ta sử dụng gói có sẵn “MILHTML”. Gói tiện ích MIL HTML cho phép biểu diễn trang HTML theo mô hình DOM, gói được chia sẻ trên diễn đàn codeproject tại địa chỉ sau: Process 2 – Tạo nhóm trang Module này nhằm tạo ra các nhóm trang từ các trang huấn luyện. Việc tạo nhóm trang sẽ chia site tin tức ra thành các nhóm trang khác nhau: nhóm các trang chủ, nhóm các trang mục tin, nhóm các trang tin chi tiết…. Việc phân nhóm trang được thực hiện nhờ vào phép tính RTDM giữa các cây HTML của trang web cần phân nhóm trang. Số lượng nhóm trang không giới hạn, ta coi 2 cây HTML là cùng chung một nhóm trang nếu chúng giống nhau đến 80% (giá trị ngưỡng này có thể thay đổi để phù hợp với từng trang web) Process 3 – Xác định mẫu Xác định mẫu là Module xác định cây HTML chung nhất của một nhóm trang. Cây HTML đó là cây có các là là các kí tự đại diện, thể hiện các vùng chứa thông tin. Mẫu của một nhóm trang sẽ xác định cây khung của nhóm trang đó. Để xác định mẫu của một nhóm trang, ta cũng kết hợp kết quả của RTDM đã được lưu trong CSDL cùng với thuật toán xây dựng wildcard. Mẫu cây của một nhóm sẽ được lưu trong bảng HtmlTree trong cơ sở dữ liệu với trường isPattern = YES. Process 4 – Thiết lập các giá trị lá của cây mẫu. Module này nhằm điền lại nhãn của các lá của cây “mẫu”, xác định xem các lá của nó có nhãn là gì: … Nhãn của lá ở đây chỉ bao gồm các thẻ Html mà không có nội dung bên trong của thẻ đó. Một Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 43 cây “mẫu” khi được dán nhãn và hiển thị theo định dạng html sẽ cho ta thấy được “khung” của trang tin tức. Process 5 – Hiển thị trang tin Module này xác định nội dung cần hiển thị rồi hiển thị chúng lên trên trình duyệt. Để có thể hiển thị theo như mong muốn của người dùng,module này cần kiểm tra, loại bỏ những vùng thông tin dư thừa và chỉ hiển thị các vùng thông tin cần thiết, đồng thời tinh chỉnh các đối tượng cho phù hợp với diện tích của màn hình thiết bị di động. Module này kết hợp kết quả đạt được từ module dán nhãn cho các lá của cây mẫu với một số mẹo heuristic. Process 6 – Tính giá trị RTDM Module này tính giá trị RTDM giữa 2 cây và chi phí ánh xạ giữa 2 nút bất kì của 2 cây khác nhau. Các giá trị này sau khi tính được sẽ được lưu trong CSDL. Nhập Url trang tin: Là sự kiện người dùng nhập địa chỉ cần xem tin tức qua thiết bị cầm tay. Module này lấy url mà người dùng nhập vào rồi chuyển qua cho module kiểm tra tính hợp lệ của url. Người đọc tin: Là người sử dụng cuối của hệ thống. Người sử dụng này gửi các yêu cầu đọc trang tin cho hệ thống. Nhóm trang Là các bảng chứa thông tin về trang tin tức cùng với các nhóm trang tin tức đã được xây dựng và cây mẫu của nhóm trang đó nhằm tăng khả năng thực hiện của hệ thống. Với những thông tin này, hệ thống không cần phải tạo mới một quá trình xử lý mà có thể sử dụng ngay những thông tin đã có để tiến hành xử lý trang tin. Các trang tin HTML Là nơi lưu trữ thông tin về các cây HTML cùng với các nút của cây đã được xây dựng từ các trang HTML có trong site Tin tức. Các cây này dung để thực Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 44 hiện các quá trình phân tích cấu trúc trang tin và xây dựng lại trang tin theo khuôn dạng mới. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 45 3.2. Mô hình lớp Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 46 Hình 7 : Gói các lớp phục vụ tính toán giá trị RTDM Hình 8 : Gói các lớp quản lý các trang tin tức Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 47 3.4. Danh sách các thực thể STT Tên các thực thể Mô tả thực thể 1. NewsCategory Danh mục tin tức của site 2. NewsSite Site tin tức 3. Template Trang mẫu 4. TemplateType Kiểu trang mẫu 5. NodeType Kiểu nút 6. NodeMapping Chi phí ánh xạ của 2 nút 7. RtdmTreeValue Giá trị RTDM của cây 8. TreeNode Nút của cây HTML 9. HtmlTree Cây HTML 10. DefautMappingValue Chứa giá trị mặc định cho chi phí xoá đỉnh, chèn đỉnh, thay thế đỉnh Mô tả chi tiết các thực thể được trình bày trong Phần phụ lục. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 48 3.5. Mô hình thực thể liên kết Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 49 CHƯƠNG IV. KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ 4.1. Giới thiệu chung về hệ thống Hệ thống được chia thành 2 module chính sau: Module quản trị và Module xem tin tức. Module quản trị là chương trình cho phép quản lý, chỉnh sửa, nhận dạng mẫu các trang tin tức mới và các trang đã được nhận dạng. Module xem tin tức là trang web cho phép người dùng cuối truy cập từ thiết bị cầm tay để xem tin tức từ các site mà hệ thống đã nhận dạng được. 4.2. Thực nghiệm và đánh giá kết quả Kết quả thực nghiệm trên thuật toán RTDM Theo thực nghiệm của Davi de Castro Reis và các đồng tác giả [28], khi so sánh thuật toán RTDM với thuật toán Chawathe [5] (thời gian tính toán cỡ O(n1.n2)) trong việc trích xuất mẫu chung, kết quả cho thấy RTDM trung bình nhanh hơn 4 lần, có trường hợp RTDM nhanh hơn 10 lần. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 50 Kết quả thực nghiệm trên hệ thống Kết quả thực nghiệm của luận văn trên 7 trang tin tức: Thanh Niên Online (thanhnien.com.vn), VN Express (vnexpress.net), Dân trí (dantri.com.vn), Việt Nam Net (vietnamnet.vn), Chúng Ta (chungta.com), Tiền phong Online (tienphongonline.com.vn), Tuổi Trẻ Online (tuoitre.com.vn) với trên 1388 trang HTML mẫu thu. Tất cả các thực nghiệm được thực hiện trên máy tính với cấu hình như sau: 1 CPU Pentium M 1.6 GHz 2 RAM 512Mb 3 Đường truyền ADSL tốc độ download/upload 2048bps/512bps Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 51 Kết quả thực nghiệm: STT Trang tin tức Chiều sâu Chiều rộng Số trang tối đa Ngưỡng Số trang mẫu Số mẫu Thời gian huấn luyện (giây) 1 thanhnien.com.vn 4 100 300 300 264 24 821 2 vnexpress.net 4 80 250 200 203 13 374 3 dantri.com.vn 4 100 300 300 235 21 2012 4 vietnamnet.vn 4 80 400 300 323 19 1203 5 chungta.com 4 100 200 200 76 9 230 6 tienphongonline.com.vn 4 80 300 200 165 9 523 7 tuoitre.com.vn 5 50 150 200 122 22 404 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 52 Một số hình ảnh chương trình: Chức năng quản trị: Các hình ảnh chương trình trên thiết bị cầm tay: Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 53 Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 54 KẾT LUẬN Kết quả đạt được Luận văn đã tiến hành nghiên cứu giải pháp trích chọn thông tin trên Web nhằm xây dựng một hệ thống trích xuất tin tức cho phép xem được trên thiết bị cầm tay. Giải pháp đề xuất trong luận văn này sử dụng thuật toán RTDM (Restricted Top-Down Mapping) do Davi de Castro Reis và các đồng tác giả đề xuất [28]. Thuật toán RTDM là thành phần lõi chính cho phép xây dựng một hệ thống nhận dạng các mẫu của trang tin tức và tiến hành trích xuất tin tức hoàn toàn tự động. Luận văn cũng đã tiến hành chi tiết và hoàn thiện các phần nội dung không công bố của thuật toán RTDM. Trên cơ sở lý thuyết đã nghiên cứu, tác giả đã tiến hành phân tích, thiết kế và xây dựng hệ thống kênh cung cấp tin tức điện tử trên các thiết bị cầm tay thông minh hoàn chỉnh. Hệ thống đã được thử nghiệm cho các trang tin tức trên các báo điện tử tiếng Việt phổ dụng hiện nay và cho kết quả tốt. Kết quả chưa đạt được và kế hoạch trong tương lai Do thời gian nghiên cứu và xây dựng hệ thống có hạn cộng với thuật toán RTDM không được công bố đầy đủ nên chương trình thực nghiệm còn một số tính năng chưa hoàn thiện. Tốc độ nhận dạng mẫu, khớp dữ liệu còn chậm, trích xuất được một tin tức còn chiếm nhiều thời gian xử lý CPU và bộ nhớ RAM, vì vậy chưa khả thi để áp dụng thực tế. Trong tương lai, tác giả dự định hoàn thiện thuật toán RTDM nhằm tăng tốc độ cho phép nhận dạng, trích xuất. Song song với việc tăng tốc thuật toán RTDM, kiến trúc chương trình cũng sẽ cần hoàn thiện cho phép nhiều truy cập đồng thời và nâng cao tính ổn định của hệ thống. Trên cơ sở đó sẽ áp dụng triển khai thực tế cho các trang tin tức tiếng Việt cũng như các trang tin tức tiếng Anh, Pháp,... Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 55 TÀI LIỆU THAM KHẢO [1] A. Arasu, H. Garcia-Molina, and S. University. Extracting structured data from Web pages. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, 337-348, ACM Press, 2003. [2] L. Arllota, V. Crescenzi, G. Mecca, and P. Merialdo. Automatic annotation of data extraction from large Web sites. In Proceedings of the International Workshop on the Web and Databases, 7-12, San Diego, USA, 2003. [3] R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley, Harlow, England, 1st edition, 1999. [4] V. Boyapati, K. Chevrier, A. Finkel, N. Glance, T. Pierce, R. Stockton, and C. Whitmer. ChangedetectorTM: a site-level monitoring tool for the WWW. In Proceedings of the 11th International Conference on World Wide Web, 570-579. ACM Press, 2002. [5] S. S. Chawathe. Comparing hierarchical data in external memory. In Proceedings of the 25th International Conference on Very Large Data Bases, 90-101, Edinburgh, Scotland, U.K., 1999. [6] W. Chen. New algorithm for ordered tree-to-tree correction problem. Journal of Algorithms, 40:135-158, 2001. [7] V. Crescenzi, G. Mecca, and P. Merialdo. RoadRunner: Towards automatic data extraction from large Web sites. In Proceedings of the 27th International Conference on Very Large Data Bases, 109-118, Rome, Italy, 2001. [8] V. Crescenzi, G. Mecca, and P. Merialdo. Wrapping-oriented classi_cation of Web pages. In Proceedings of the 2002 ACM Symposium on Applied Computing, 1108-1112. ACM Press, 2002. [9] D. Florescu, A. Levy, and A. Mendelzon. Database techniques for the world-wide Web: a survey. SIGMOD Rec., 27(3):59-74, 1998. [10] M. Garofalakis, A. Gionis, R. Rastogi, S. Seshadri, and K. Shim. Xtract: a system for extracting document type descriptors from xml documents. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, 165-176. ACM Press, 2000. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 56 [11] S. Grumbach and G. Mecca. In search of the lost schema. In C. Beeri and P. Buneman, editors, Proceedings of 7th International Conference on Database Theory, Lecture Notes in Computer Science, 314-331, Jerusalem, Israel, 1999. Springer. [12] A. Heydon and M. Najork. Mercator: A scalable, extensible Web crawler. World Wide Web, 2(4):219-229, 1999. [13] A. Laender, B. Ribeiro-Neto, A. Silva, and J. S. Teixeira. A brief survey of Web data extraction tools. SIGMOD Record, 31(2):84-93, 2002. [14] B. Liu, R. Grossman, and Y. Zhai. Mining data records in Web pages. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 601-606. ACM Press, 2003. [15] J.K. Min, J.Y. Ahn, and C.-W. Chung. Ef_cient extraction of schemas for xml documents. Information Processing Letters, 85(1):7-12, 2003. [16] A. Nierman and H. V. Jagadish. Evaluating structural similarity in XML documents. In Proceedings of the 5th International Workshop on the Web and Databases (WebDB 2002), Madison, Wisconsin, USA, June 2002. [17] S. M. Selkow. The tree-to-tree editing problem. Information Processing Letters, 6:184-186, Dec. 1977. [18] K.-C. Tai. The tree-to-tree correction problem. J. ACM, 26(3):422-433, 1979. [19] G. Valiente. An efficient bottom-up distance between trees. In Proceedings of the 8th International Symposium on String Processing and Information Retrieval, 212-219, Santiago, Chile, 2001. IEEE Computer Science Press. [20] G. Valiente. Tree edit distance and common subtrees. Research Report LSI-02-20-R, Universitat Politecnica de Catalunya, Barcelona, Spain, 2002. [21] J. T.-L. Wang, B. A. Shapiro, D. Shasha, K. Zhang, and K. M. Currey. An algorithm for finding the largest approximately common substructures of two trees. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(8):889-895, 1998. Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 57 [22] J. T. L. Wang and K. Zhang. Finding similar consensus between trees: an algorithm and a distance hierarchy. Pattern Recognition, 34:127- 137, 2001. [23] P. Willett. Recent trends in hierarchic document clustering: a critical review. Information Processing and Management, 24(5):577-597, 1988. [24] G. Yang, I. V. Ramakrishnan, and M. Kifer. On the complexity of schema inference from Web pages in the presence of nullable data attributes. In Proceedings of the 12th International Conference on Information and Knowledge Management, 224-231. ACM Press, 2003. [25] W. Yang. Identifying syntactic differences between two programs. Softw. Pract. Exper., 21(7):739-755, 1991. [26] K. Zhang, D. Shasha, and J. T. L. Wang. Approximate tree matching in the presence of variable length don't cares. J. Algorithms, 16(1):33-66, 1994. [27] K. Zhang, R. Statman, and D. Shasha. On the editing distance between unordered labeled trees. Information Processing Letters, 42(3):133- 139, 1992. [28] Davi de Castro Reis, Paulo B. Golgher, Altigran S. da Silva, Alberto H. F. Laender. Automatic Web News Extraction Using Tree Edit Distance. In Proceedings of the Thirteenth International World Wide Web Conference, ACM Press, New York, NY, May 2004, ISBN 1581139128, 502-601. [29] Một số bài báo trên các trang www.vnexpress.net , www.tuoitre.com.vn,... Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 58 PHỤ LỤC. MÔ TẢ CHI TIẾT CÁC THỰC THỂ NewsSite STT Tên thuộc tính Kiểu Loại khoá Mô tả 1 Id Int PK Id của tờ báo (trang tin tức) 2 Url Varchar(500) Đường dẫn tới trang tin tức 3 SiteName Varchar(200) Tên của trang tin tức 4 Threshold Float Giá trị ngưỡng để nhóm các trang tin lại 5 InsertCost Float Chi phí chèn đỉnh 6 UpdateCost Float Chi phí thay thế đỉnh 7 DeleteCost Float Chi phí xoá đỉnh Bảng này chứa danh sách các tờ báo điện tử mà người dùng đã ghé thăm, địa chỉ Url ở đây chỉ lưu trữ địa chỉ của trang chủ. Các chi phí chèn, thay thế và xoá đỉnh có thể xác định giá trị cho từng tờ báo. NewsCategory STT Tên thuộc tính Kiểu Loại khoá Mô tả 1 Id Int PK ID của mục tin 2 NewsSiteId Int FK ID của tờ báo (trang tin tức) liên kết đến 3 ParentId Int FK ID của mục tin cấp trên 4 CategoryName Varchar(200) Tên của mục tin 5 CategoryUrl Varchar(500) Đường dẫn đến mục tin Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 59 đó Bảng NewsCategory lưu trữ các mục tin chính của tờ báo. Template STT Tên thuộc tính Kiểu Loại khoá Mô tả 1 Id Int PK Id của trang mẫu 2 NewsSiteId Int Id của tờ báo 3 TemplateTypeId Int FK Kiểu trang mẫu (trang chủ, mục tin hay tin chi tiết) Bảng này lưu trữ các mẫu trang tin, các trang mới ghé thăm sẽ được so sánh với trang mẫu để xác định kiểu trang tin (trang chủ, mục tin hay trang tin chi tiết…) và căn cứ vào kiểu trang tin sẽ có hình thức trích xuất tương ứng. TemplateType STT Tên thuộc tính Kiểu Loại khoá Mô tả 1 Id Int PK Id của TemplateType 2 TemplateTypeName Varchar(100) Tên của templateType 3 Description varchar(500) Mô tả templateType Kiểu trang tin: trang chủ, mục tin hay trang tin chi tiết… NodeType STT Tên thuộc tính Kiểu Loại khoá Mô tả 1 Id Int PK Id của NodeType 2 NodeName Varchar(100) Tên của NodeType Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 60 3 Description varchar(500) Mô tả NodeType Lưu trữ kiểu nút trong cây HTML, kiểu nút sẽ xác định nút đó có được giữ lại hay có thể loại bỏ khỏi cây. NodeMapping STT Tên thuộc tính Kiểu Loại khoá Mô tả 1 Id Int PK Id của NodeMapping 2 NodeConnectedId Int Nút kết nối trong ánh xạ 3 MappingValue Float Giá trị của ánh xạ 2 TreeNodeId Int FK Id của nút Bảng này lưu trữ chi phí ánh xạ giữa 2 nút. RtdmTreeValue STT Tên thuộc tính Kiểu Loại khoá Mô tả 1 Id Int PK Id của RtdmTreeValue 2 TreeConnectedId Int FK Cây kết nối trong phép tính rtdm 3 Value Float Giá trị Rtdm Lưu trữ giá trị RTDM tính được khi chuyển đổi cây HTML sang cây có giá trị Id là: TreeConnectedId. HtmlTree STT Tên thuộc tính Kiểu Loại khoá Mô tả Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 61 1 Id Int PK Id của TreeHtml 2 Url Varchar(500) Địa chỉ đến site tương ứng 3 isPattern Varchar(3) Cây có là pattern không 4 TemplateId Int FK Template chứa cây Lưu trữ tất cả các trang Url đã được ghé thăm, mỗi một trang được ghé thăm sẽ tương ứng với một cây HTML. TreeNode STT Tên thuộc tính Kiểu Loại khoá Mô tả 1 Id Int PK Id của TreeNode 2 Label Varchar(40) Nhãn của nút 3 ParentId Int FK Id của nút cha 4 Level Int Độ sâu của nút tính từ gốc 5 OrderNumber Int Số thứ tự của nút trong cùng cha 6 NodeTypeId Int FK Kiểu nút 7 HtmlTreeId Int FK Cây chứa nút 8 TreeOrder Int Thứ tự trong cây (duyệt theo thứ tự trước) Lưu trữ các nút của cây tương ứng với Url được ghé thăm, các thông tin của nút xác định được cấu trúc của cây HTML được lưu trữ.