Automatic Tree and String Based Wrapper Generation for Semi-structured Documents

Automatic Tree and String Based Wrapper Generation for Semi-structured Documents

Yasuhiro Yamada, Daisuke Ikeda and Sachio Hirokawa

Phần lớn các trang (page) trong 1 web đều có chung 1 mẫu (template). Việc trích lọc được các template này và tận dụng nó để tìm ra sự thay đổi giữa các trang web sẽ giúp ích rất nhiều cho việc trích lọc thông tin, vì nó sẽ chỉ tập trung đến các phần thay đổi và bỏ qua các phần thừa bị lặp đi lặp lại giữa các trang với nhau. 
1 chương trình trích lọc được các template này được gọi là các chương trình wrapper. 

Bài viết này giới thiệu phương pháp mới gọi là "PLR wrapper". Phương pháp này là sử dụng cả tính chất cây (cấu trúc cây) và tính chất văn bản của 1 trang. 
Ngoài ra, 1 trang sẽ được coi là 1 "văn bản bán cấu trúc": có cấu trúc cây, nhưng ý nghĩa của các nút (tags) không rõ ràng. 

Phương pháp PLR:

  1 văn bản bán cấu trúc sẽ được biểu diễn bằng 1 tập hợp các qui tắc. Các qui tắc này là đường dẫn từ root đến các yếu tố (node) (1 dạng giống như XPath) và các kí tự phân tách trái và phải. Trong 1 node sẽ có các thông tin cần thiết và các thông tin rác; các kí tự phân tách trái và phải sẽ giúp chương trình lọc các thông tin rác này. 

Thuật toán xác định phần chung giữa các pages:

  Từ tập hợp các văn bản bán cấu trúc, tách thành 2 phần: phần có tần suất xuất hiện cao và phần có tần suất xuất hiện thấp. Khi đó, phần có tần suất xuất hiện cao sẽ tương ứng với template. 
  Thuật toán này sẽ cho kết quả là cặp số (n, a) được gọi là cut-point. n là độ dài của chuỗi con, a là tỉ lệ phần trăm (1<= a <= 100).
  Gọi D là tập hợp các chuỗi văn bản. Trong tất cả các chuỗi con có độ dài n trong D, nếu tần suất cao hơn a% thì sẽ coi là bộ phận có tần suất xuất hiện cao. 
  Việc chọn lựa giá trị n trong thuật toán này là rất quan trọng. Nếu n quá nhỏ, sẽ không tách được template. Nếu n quá lớn, các chuỗi con sẽ có tần suất xuất hiện thấp và khó tách được template. 

Tách lấy phần chung:

  Sử dụng thuật toán cut-point. 
  Gồm 3 bước:
  1. xác định phần chung
  2. tách lọc các qui tắc
  3. loại bỏ các qui tắc thừa 

Đánh giá chủ quan : 

   Bài viết đã khá cũ (2003) nên thuật toán không thực sự hiệu quả trong việc trích chọn phần chung. Hiện có nhiều thuật toán hiệu quả hơn khi tính chất cây của các pages được xem trọng hơn. 
  Tuy nhiên, đây được xem là 1 trong những bài báo khởi đầu cho phương pháp sử dụng template để trích lọc thông tin. Vì thế những ý tưởng trong bài viết này vẫn rất hữu dụng. 

Comments