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 & smartphones)

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í