Luận văn 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 và smartphones)

- Đề 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ữ.