Khóa luận Bài toán trích xuất thông tin cho dữ liệu bán cấu trúc và áp dụng xây dựng hệ thống tìm kiếm giá cả sản phẩm

n phẩm để trích xuất các thông tin hữu dụng về sản phẩm. Hình 4. Ví dụ về hệ thống tìm kiếm giá cả 10 Chương 2. Một số phương pháp sử dụng trong bài toán trích xuất thông tin cho dữ liệu bán cấu trúc Có nhiều kỹ thuật cũng như giải thuật được sử dụng để giải quyết bài toán trích xuất thông tin cho dữ liệu bán cấu trúc. Chương 2 sẽ giới thiệu những kỹ thuật trích xuất sử dụng cây DOM [15],[6] và biểu thức chính qui[2]. Chương này cũng đề cập đến hai giải thuật trong bài toán trích xuất thông tin cho dữ liệu bán cấu trúc và các ưu nhược điểm của giải thuật đó. 2.1 Trích xuất thông tin dựa vào cây DOM 2.1.1 Khái nhiệm cây DOM Theo W3C thì DOM (Document Object Model) là một giao diện lập trình ứng dụng (API) cho các văn bản HTML hợp lệ và các văn bản XML có cấu trúc chặt trẽ. Nó định nghĩa cấu trúc logic của các văn bản và cách thức một văn bản được truy cập và thao tác[15]. Ví dụ về một bảng được lấy văn bản HTML: Shady Grove Aeolian Over the River, Charlie Dorian Dạng biểu diễn cây DOM của mã HTML 11 2.1.2 Xây dựng cây DOM Xây dựng cây DOM từ những trang Web đầu vào là một bước cần thiết trang nhiều giải thuật trích xuất dữ liệu [2]. Có hai phương pháp cơ bản để xây dựng các cây DOM. - Sử dụng các thẻ riêng biệt Hầu hết các thẻ HTML làm việc trong một cặp. Mỗi cặp chứa một thẻ mở và một thẻ đóng . Bên trong mỗi cặp thẻ có thể có những cặp thẻ khác, kết quả là cấu trúc trở nên chồng chéo. Xây dựng một cây DOM từ một trang Web bằng cách sử dụng mã HTML của nó là một vấn đề cần thiết. Trong một cây DOM, mỗi cặp thẻ là một node, những cặp thẻ ẩn bên trong là node con của node hiện tại. Có hai nhiệm vụ cần thi hành đó là: ¾ Làm sạch mã HTML: Một vài thẻ không cần thẻ đóng (như , ,) mặc dù chúng có thẻ đóng. Bởi vậy một thẻ đóng nên được chèn vào để tất cả các thẻ được cân bằng. Các thẻ được định dạng không tốt cũng cần thiết được sửa chữa. Một thẻ sai thường là một thẻ đóng, đó là thẻ cắt ngang các khối ẩn bên trong. Ví dụ: … … … , sẽ rất khó để sửa lỗi trường hợp này nếu tồn tại sự chồng chéo đa cấp. Có một vài phần mềm mã nguồn mở để làm sạch mã HTML, một số những phần mềm thông dụng như: JTidy, NekoHTML, HTMLCleaner. ¾ Xây dựng cây: Chúng ta có thể đi theo các khối con của các thẻ HTML để xây dựng được cây DOM. - Sử dụng các thẻ và các hộp ảo (visual cue) Thay vì phân tích mã HTML để sửa lỗi, có thể sử dụng sự biểu diễn hoặc các thông tin ảo (ví dụ như: địa chỉ trên màn hình mà các thẻ được biểu diễn) để suy luận mối quan hệ có cấu trúc của các thẻ và có thể xây dựng được cây DOM. Phương thức xây dựng có thể phân tích mã HTML thành cây DOM, miễn là trình duyệt có thể hiển thị được đoạn mã đó một cách chính xác. Trong một trình duyệt web, mỗi phần tử HTML (chứa đựng một thẻ mở, các thuộc tính tùy chọn, nội dung HTML được nhúng tùy ý và một thẻ đóng, thẻ này có thể thiếu) được biểu diễn như một hình chữ nhật. Thông tin ảo này có thể lấy được sau khi mã 12 HTML được biểu diễn trên trình duyệt. Một cây DOM sau đó có thể được xây dựng dựa vào các thông tin ảo này. Các bước xử lý như sau: ¾ Tìm 4 đường biên của hình chữ nhật ứng với mỗi phần tử HTML thông qua việc công cụ trình diễn của trình duyệt, ví dụ: Internet Explorer. ¾ Theo sự tuần tự của các thẻ mở và sự kiểm tra xem một hình chữ nhật có nằm trong một hình chữ nhật khác không, để xây dựng cây DOM. Ví dụ minh họa về sử dụng visual cue: Một đoạn mã HTML có 3 lỗi. sử dụng thông tin ảo có thể dễ dàng xây dựng được cây DOM. Hình 5. Ví dụ xây dựng cây DOM sử dụng hộp ảo 2.1.3 Sử dụng cây DOM để trích xuất thông tin Để trích xuất được thông tin cần thiết ở một node của cây DOM, chúng ta cần chỉ rõ đường đi từ gốc của cây đến node cần trích xuất thông tin. Đường đi này gọi là một XPath[16]hay mẫu trích xuất. Trích xuất thông tin web dựa vào cây DOM trước tiên việc trích xuất này được hỗ trợ bởi xây dựng cây DOM cho mã HTML của trang. Các mẫu trích xuất có thể được làm rõ như đường dẫn từ gốc của cây DOM đến node chứa nội dung cần trích xuất. 13 Ví dụ : Đây là cây DOM của một đoạn mã HTML chứa thông tin về cuốn sách, gồm tên cuốn sách (title) và tên tác giả (author). Bài toán đặt ra là sử dụng cây DOM này trích xuất các thông tin về tên sách và tác giả viết sách. Mẫu trích xuất được xây dựng sau: 2.2 Trích xuất thông tin dựa theo các mẫu biểu thức chính qui 2.2.1 Khái niệm biểu thức chính qui Một biểu thức chính qui có thể được sử dụng để mô hình mã hóa HTML [2]. Cho một tập các ký tự alphabe ∑ và một token “#text” không thuộc ∑, một biểu thức chính qui trên ∑ là một chuỗi trên ∑∪{#text, *,?,|,(,)} được định nghĩa như sau : Sample DOM Tree Extraction Mẫu trích xuất tên sách: HTMLÆBODYÆBÆCharacterData Mẫu trích xuất tên tác giả: HTMLÆ BODYÆFONTÆAÆ CharacterData HTML BODY FONT B Age of Spiritual Machines Ray Kurzwei Element Character-Data HEADER A 14 Một chuỗi rỗng ε và tất cả các phần tử trong ∑ ∪ {#text} đều là một biểu thức chính qui. Nếu A và B là một biểu thức chính qui, thì AB, (A|B) và (A)? cũng là một biểu thức chính qui, trong đó (A|B) tức là A hoặc B và (A)? thức là (A|ε). Nếu A là một biểu thức chính qui, thì (A)* cũng là biểu thức chính qui, trong đo (A)*= {ε, A, AA, AAA,…}. Chúng ta cũng sử dụng (A)+ để chỉ A(A)*. Nếu biểu thức chính qui không có chứa (A|B) thì nó gọi là biểu thức chính qui kết hợp tự do. Một biểu thức chính qui thường dùng để thể hiện một mẫu trích xuất. 2.2.2 Sử dụng biểu thức chính qui để trích xuất thông tin Với một biểu thức chính qui, một otomat hữu hạn trạng thái có thể được xây dựng và được sử dụng để so khớp sự xuất hiện của nó trong chuỗi tuần tự các trang web. Trong quá trình này, dữ liệu có thể được trích xuất. Ví dụ: Với mã HTML như sau: Tinh Tong cua cac so tu 1->n Để lấy được phần tiêu đề của đoạn mã này thì ta có thể xây dựng biểu thức chính qui như sau: .*?(#text) 2.3 Một số giải thuật trích xuất thông tin cho dữ liệu bán cấu trúc 2.3.1 Hai kiểu biểu diễn của các trang giàu dữ liệu Các trang giàu dữ liệu được chia thành hai loại thông qua sự biểu diễn của chúng[2] - List Page: là trang chứa đựng một vài danh sách của các đối tượng. Hình 8 giới thiệu một list page. Có hai dạng trang list, đó là trang list bố trí theo chiều ngang 15 hoặc chiều dọc. Bên trong mỗi vùng, bản ghi dữ liệu được định dạng sử dụng cùng một mẫu và mẫu sử dụng trong hai vùng khác nhau là khác nhau [2]. - Detail Page: là trang chỉ giới thiệu một đối tượng đơn. Ví dụ hình 9 là một trang detail page giới thiệu về sản phẩm . Nó chứa đựng tất cả các thuộc tính của sản phẩm như: tên, ảnh, giá, thông số kỹ thuật, thời gian bảo hành [2] . Hình 6. Dạng biểu diễn của trang list page Hình 7. Dạng biểu diễn của trang detail page 16 2.3.2 Một số giải thuật điển hình Hiện nay tư tưởng của phương pháp trích xuất thủ công không còn được sử dụng . Vì vậy khóa luận chỉ giới thiệu phương pháp trích xuất thông tin tự động và bán tự động cho “bài toán trích xuất thông tin cho dữ liệu bán cấu trúc”. • Phương pháp Wrapper qui nạp: đây là phương pháp trích xuất bán tự động Giải thuật được nêu ra dưới đây là giải thuật dựa trên hệ thống Stalker. - Một ví dụ về trích xuất theo giải thuật dựa trên hệ thống Stalker. Một trang Web có thể được nhìn dưới dạng có thứ tự của token S (ví dụ như: các từ, các số và các thẻ HTML). Việc trích xuất sử dụng một cấu trúc cây gọi là cây EC(embedded catalog tree), đây là công cụ để mô hình dữ liệu nhúng trong một trang HTML. Gốc của cây là văn bản chứa tất cả các token tuần tự S của trang, nội dung của mỗi node con là một chuỗi con của node cha. Để trích xuất một node, Wrapper sử dụng miêu tả cây EC của trang đó và tập hợp các luật trích xuất. Ví dụ bên dưới là sự chuyển đổi một đoạn mã HTML sang cây EC. Chú ý rằng chúng ta sử dụng LIST ở đây bởi vì tập hợp các địa chỉ luôn luôn có thứ tự. Hình 8. Chuyển đổi từ mã HTML sang cây EC 17 Với mỗi node trong cây, Wrapper nhận dạng hoặc trích xuất nội dung của node từ cha của nó, node cha là node chứa đựng chuỗi token của tất cả các node con. Mỗi trích xuất được thực hiện bởi 2 luật, Start Rule và End Rule. Start Rule chỉ ra sự bắt đầu của node và End Rule chỉ ra sự kết thúc của node. Phương thức này có thể áp dụng cho cả node lá và các node danh sách (list node). Các luật trích xuất dựa trên ý tưởng của mỏ neo (landmark). Mỗi mỏ neo là một chuỗi các token liên tiếp và nó dùng để đánh dấu sự bắt đầu hay kết thúc của một phần tử mục tiêu. Hình dưới đây là trình diễn mã HTML của trang web trong hình 10. Restaurant Name: Good Noodles 205 Willow, Glen, Phone 1-773-366-1987 25 Oak, Forest, Phone (800) 234-7903 324 Halsted St., Chicago, Phone 1-800-996-5023 700 Lake St., Oak Park, Phone: (708) 798-0008 Để trích xuất được tên của quán ăn “Good Noodles” thì luật trích xuất sẽ là: Start Rule: R1: SkipTo() tức là hệ thống nên xuất phát ở điểm bắt đầu của trang và bỏ qua tất cả các token cho đến khi chúng thấy được thẻ đầu tiên. Các luật SkipTo(:) hoặc SkipTo(i) đề không đúng. Vì theo cây EC trong hình 10 R1 là cha của node name, như vậy nó sẽ là node gốc. Node gốc thì chứa chuỗi token tuần tự của cả trang Web. Tương tự End Rule : R2: SkipTo () sẽ xác định được điểm kết thúc tên của quán ăn. - Quá trình học luật Trong hệ thống Wrapper qui nạp quá trình học là một quá trình chủ đạo. Khóa luận này sẽ trình bày giải thuật học của wrapper để sinh ra các luật trích xuất. Ý tưởng cơ bản của giải thuật học luật như sau: Để sinh ra Start Rule cho một node của cây EC, một vài token tiền tố hay các đại diện của node được nhận dạng như các mỏ neo, chúng có thể nhận dạng đơn nhất sự bắt đầu của một node. Để sinh ra End Rule cho một node, một vài token hậu tố hay các đại 18 diện của node được nhận dạng như một mỏ neo. Tiến trình sinh Start Rule và End Rule là giống nhau. Cho trước một tập các mẫu huấn luyện đã được gán nhãn, giải thuật học sẽ sinh ra các luật trích xuất tổng quan để trích xuất tất cả các phần tử mục tiêu (positive items) mà không trích xuất các phần tử khác (nagertive items). Sau quá trình này thì một wrapper đã được sinh ra , nó sẽ được áp dụng cho các trang web khác chứa đựng các dữ liệu tương tự và được định dạng cùng một cách với tập mẫu huấn luyện. - Ưu điểm và nhược điểm ƒ Ưu điểm: Người sử dụng chỉ phải gán nhãn một lượng nhỏ các dữ liệu mẫu.Quá trình học là quá trình tự động để sinh ra luật trích xuất. ƒ Nhược điểm: Nếu một site thay đổi, làm sao để wrapper biết được sự thay đổi đó? Nếu phát hiện chính xác có sự thay đổi, làm sao để tự động sử wrapper? Vì phương pháp này phụ thuộc vào việc gán nhãn bằng tay nên nó không phù hợp cho trích xuất một lượng lớn các trang. Ví dụ, nếu một trang kinh doanh sản phẩm muốn trích xuất tất cả các các sản phẩm được bán trên Web, việc gán nhãn bằng tay hầu như là nhiệm vụ không thể. Việc duy trì wrapper là việc làm rất tốn kém, vì web là một môi trường động. Các site thì luôn luôn thay đổi. • Phương pháp trích xuất tự động Để hạn chế nhược điểm của Wrapper qui nạp, phương pháp trích xuất tự động đã được nghiên cứu rất nhiều. Việc trích xuất tự động là hoàn toàn có thể bởi vì dữ liệu trên một website thường được mã hóa với một số lượng mẫu cố định. Có thể tìm những khuôn mẫu đó bằng việc khai phá những mẫu lặp lại trong nhiều trang của một website. Trong một vài ứng dụng, chúng ta cần trích xuất dữ liệu từ các trang detail-page, vì những trang này chứa nhiều thông tin hơn. Ví dụ: trong một trang list-page, thông tin của mỗi sản phẩm thông thường chỉ là tên, ảnh và giá. Tuy nhiên nếu ứng dụng cần những thông tin miêu tả sản phẩm thì chúng ta cần trích xuất từ những trang detail. 19 Một thuật toán trích xuất tự động khá tiêu biểu mà có thể trích xuất ở cả trang detail và trang list đó là RoadRunner. - Mô tả giải thuật Đầu vào: Một tập hợp các trang mẫu, mỗi trang chứa đựng một hay nhiều bản ghi (một trang có thể là list page hoặc detail page). Đầu ra: Một mẫu trích xuất có thể trích xuất được tất các các trang trong tập mẫu, trong giải thuật này mẫu trích xuất đó là biểu thức chính qui kết hợp tự do. - Phương thức tiếp cận Ban đầu, giải thuật sẽ lấy một số lượng ngẫu nhiên các trang với mẫu trích xuất W. Mẫu trích xuất W sau đó được định nghĩa lại bởi việc kết hợp có thứ tự với mã HTML của mỗi trang pi khác trong tập mẫu, để giải quyết vấn đề sai khác giữa các mẫu trích xuất của các trang trong tập mẫu. Cuối sung giải thuật sinh ra một wrapper chung có thể trích xuất được tất cả các trang trong tập mẫu. Wrapper này sẽ được áp dụng trích xuất cho những trang khác có cấu trúc tương tự với những trang trong mẫu Sự sai khác xuất hiện khi một vài token của trang pi xuất hiện sai khác so với W. Có hai kiểu sai khác trong việc so khớp đó là: ¾ Sự sai lệch xâu văn bản (string mismatch) : Chúng biểu thị thông qua các trường dữ liệu hay các mục. ¾ Sự sai khác giữa các thẻ (tag mismatch). Giải thuật này được làm rõ trong hình dưới đây: 20 Hình 9. Ví dụ giải thuật RoadRunner [12] - Ưu, nhược điểm của giải thuật ƒ Ưu điểm: Không cần sự gán nhãn của người dùng với tập mẫu huấn luyện, có thể tự động xây dựng được mẫu trích xuất. ƒ Nhược điểm: Nó không thể tự động nhận dạng được đâu là thực thể thông tin mong muốn của người dùng. Vì vậy người sử dụng sẽ vẫn phải tự gán nhãn những kết quả đầu ra. Ví dụ: hình trên khi nó xác định được thẻ có dữ liệu tương đương của 2 trang nhưng nó không thể xác định đấy là tên của quyển sách, mà chỉ có thể xác định nó là một xâu ký tự. 21 Chương 3. Áp dụng bài toán trích xuất thông tin bán cấu trúc để xây dựng hệ thống tìm kiếm giá cả sản phẩm Việc áp dụng bài toán trích xuất thông tin cho dữ liệu bán cấu trúc để xây dựng hệ thống tìm kiếm giá cả sản phẩm là vấn đề quan trọng nhất của khóa luận. Trong chương này khóa luận sẽ đề cập đến khái niệm của hệ thống tìm kiếm giá cả, phương pháp xây dựng hệ thống và cách đánh giá các hệ thống đang tồn tại. 3.1 Khái quát hệ thống tìm kiếm giá cả của sản phẩm Trong phần này khóa luận sẽ đề cập tới khái niệm về hệ thống tìm kiếm giá cả, các phương pháp xây dựng, ưu nhược điểm của các hệ thống tìm kiếm giá cả hiện tại, từ đó đưa ra cách tiếp cận để xây dựng hệ thống tìm kiếm giá cả phù hợp. 3.1.1 Khái niệm Hệ thống tìm kiếm giá cả (hay còn được biết đến với tên là “dịch vụ so sánh giá cả”) là một khái niệm thuộc lĩnh vực thương mại điện tử. Các hệ thống này cho phép người sử dụng tìm kiếm và thấy được sự so sánh giá cả của một sản phẩm cụ thể trên nhiều trang web bán hàng khác nhau [18]. Hệ thống tìm kiếm giá cả thông thường không phải là một hệ thống bán hàng trực tuyến, tuy nhiên nó chính là một công cụ gián tiếp hỗ trợ việc giới thiệu sản phẩm của các cửa hàng kinh doanh cũng như việc mua hàng của người sử dụng. 3.1.2 Các phương pháp xây dựng Do các hệ thống tìm kiếm giá cả tập trung vào việc thể hiện các thông tin giá cả trên nhiều trang web bán hàng khác nhau nên hướng tiếp cận để giải quyết bài toán này cũng đều đi sâu vào việc tạo ra một môi trường tốt nhất cho việc thu thập, trao đổi thông tin sản phẩm giữa các cửa hàng có sản phẩm và hệ thống. Thông thường có ba phương pháp để xây dựng hệ thống dựa vào đặc trưng trên [18] : - Phương pháp dựa vào sự cung cấp thông tin trực tiếp từ các cửa hàng. Các hệ thống dạng này sẽ nhận được sự cung cấp thông tin của các cửa hàng về thông tin, giá cả của sản phẩm, người quản trị hệ thống sẽ cập nhập vào cơ sở dữ liệu của hệ thống. Các cửa hàng sẽ không tương tác trực tiếp lên hệ thống. 22 - Phương pháp dựa vào sự tương tác của cửa hàng trên hệ thống. Các hệ thống dạng này thường được biết đến như là các mô hình B2C(Business To Customer), B2B (Business To Business) trong thương mại điện tử. Hệ thống sẽ tạo ra môi trường giao diện, cho phép các cửa hàng tương tác trực tiếp với hệ thống để cung cấp thông tin. - Phương pháp tự động thu thập thông tin từ các trang web bán hàng hay giới thiệu sản phẩm của các cửa hàng. Hệ thống dạng này sẽ không dựa vào sự cung cấp thông tin của các cửa hàng mà tự động truy nhập vào các trang web của cửa hàng để trích xuất các thông tin sản phẩm đưa về cơ sở dữ liệu của hệ thống. 3.1.3 Các hệ thống hiện tại • Các hệ thống hiện tại. Đối với ba phương pháp tiếp cận đã được giới thiệu ở mục 3.1.2, việc áp dụng hai phương pháp đầu sẽ gặp phải các hạn chế do dữ liệu của hệ thống hoàn toàn phụ thuộc vào sự cung cấp của các cửa hàng trong khi giá cả là dạng dữ liệu biến động liên tục theo thời gian đòi hỏi phải có sự cập nhật liên tục thông tin vào cơ sở dữ liệu. Bên cạnh đó, việc áp dụng hai phương pháp này, cơ sở dữ liệu sẽ bị giới hạn về số lượngcửa hàng cung cấp dữ liệu cho hệ thống. Do đó hai phương pháp này không phải là phương pháp tối ưu để xây dựng hệ thống tìm kiếm giá cả. Còn ở phương pháp tiếp cận thứ ba, dữ liệu được thu thập thông qua các trang kinh doanh sản phẩm. Hệ thống sẽ quét qua những trang web cửa hạng để nhận được giá cả của sản phẩm, thay vì phải sử dụng nguồn cung cấp của người kinh doanh. Vì vậy đây là phương pháp có giá trị nhất tình tới thời điểm hiện nay. Có rất nhiều bài toán được đề xuất theo phương thức tiếp cận thứ ba để xây dựng hệ thống tìm kiếm giá cả như: - “Bootstrapping Information Extraction from Semi-structured Web Pages” được đề xuất bởi Andrew Carlson và Charles Schafer áp dụng cho những trang cho thuê nhà và du lịch …. [1]. - “Automated Price Comparison Shopping Search Engine” của Elwin Chai, Rick Jones áp dụng cho hệ thống PriceHunter [3]. - “A Scalable Comparison-Shopping Agent for the World-Wide Web” của Robert Bo Doorenbos, Oren Etzioni và Daniel So Weld [7]. 23 • Các vấn đề của bài toán nêu trên Các bài toán này được đề xuất để xây dựng những hệ thống tìm kiếm giá cả sản phẩm, tuy nhiên chúng gặp phải một vấn đề, đó là các tên của sản phẩm phải được cung cấp trước và các trang kinh doanh sản phẩm phải xác định rõ trên hệ thống. Ở Việt Nam hiện nay cũng có một vài hệ thống khá tiêu biểu như : Vatgia1, Aha2. Tuy nhiên hai hệ thống này lại xây dựng theo cách tiếp cận thứ hai, nên phải phụ thuộc nhiều vào các nhà kinh doanh. Từ những nhận định đã nêu trên, khóa luận này sử dụng cách tiếp cận thứ ba để xây dựng hệ thống và sẽ giải quyết một số tồn tại một số phương pháp xây dựng hệ thống tìm kiếm giá cả hiện tại. 3.2 Cơ sở thực tiễn Hiện nay các trang web đều xây dựng trên nền những ngôn ngữ lập trình động như PHP, ASP…. Khi người dùng vào một trang kinh doanh sản phẩm và tìm kiếm một sản phẩm nào đó thì kết quả được trả về và hiển thị trên trình duyệt theo một số khuôn mẫu định sẵn, các trang trong cùng khuôn mẫu này thì có chung cấu trúc HTML. Tức là khi chúng ta biết mẫu để trích xuất một trang trong khuôn mẫu này, thì có thể sử dụng mẫu đó để trích xuất những thông tin của những trang khác có cùng khuôn mẫu. Ví dụ : Với website www.trananh.vn, hình 13,14 là hai sản phẩm của laptop HP được biểu diễn bởi hai trang detail. 1 2 vn 24 Hình 10. Trang giới thiệu sản phẩm HP CQ60-203TX Hình 11. Trang giới thiệu sản phẩm HP CQ60-101TX Hai trang detail này tuy giới thiệu về hai sản phẩm khác nhau nhưng đều có chung một dạng biểu diễn của cây DOM 25 Hình 12. Biểu diễn cây DOM của mã HTML hai trang về sản phẩm HP Mẫu trích xuất các thông tin Tên Sản phẩm: HTML Æ BODY Æ TABLE Æ TR[1] Æ TD[1] Æ TÊN SẢN PHẨM (1). Giá Sản Phẩm: HTML Æ BODY Æ TABLE Æ TR[3] Æ TD[1] Æ DIV[1] Æ FONT [1]Æ GIÁ SẢN PHẨM (2). Nhận xét: Vì các trang trong cùng một website có cấu trúc tuân theo một vài khuôn mẫu nhất định nên ta có thể sử dụng những mẫu trích xuất (1) để trích xuất tên sản phẩm và (2) để trích xuất giá sản phẩm từ trang khác có cùng cây DOM trên. 3.3 Cơ sở khoa học Phần cơ sở lý thuyết sẽ nêu và giải quyết những bài toán cơ sở để xây dựng hệ thống tìm kiếm giá cả. Trong phần này sẽ tập trung vào hai bài toán chính đó là “bài toán về xác định giá thực của một sản phẩm” và “bài toán tự động trích xuất thông tin về tên và giá 26 sản phẩm”. “Bài toán xác định giá thực một sản phẩm” sẽ bổ trợ để giải quyết “bài toán tự động trích xuất thông tin về tên và giá của sản phẩm”. Đây chính là thành phần cốt lõi để xây dựng hệ thống tìm kiếm giá cả sản phẩm. 3.3.1 Phân loại trang kinh doanh Các trang kinh doanh sản phẩm được chia làm hai loại chính: - Các trang kinh doanh sản phẩm thuần tuý: đây là các trang có bố cục và trình bày rõ ràng, các thông tin được cung cấp theo những khuôn mẫu nhất đinh. Hình 13. Ví dụ về trang kinh doanh thông thường 27 - Các trang rao vặt: các trang có bố cục không rõ ràng, tùy thuộc vào người sử dụng. Hình 14. Ví dụ về trang rao vặt 3.3.2 Bài toán trích xuất thông tin giá cả của một sản phẩm xác định • Bài toán tiền đề: xác định giá trong một trang Web - Đầu vào: Mã nguồn HTML của một trang Web. - Đầu ra: Các giá chứa trong mã nguồn đó. Ví dụ: Với một trang Web về kinh doanh sản phẩm “HP Mini-note”. Hình 15. Ví dụ về trích xuất giá trong một trang web Thì các giá trích xuất được sẽ là: Tiền tố: Giá Hậu tố: VNĐ 28 - 6,559,000 VNĐ - 4,950,000 VNĐ - 13,999,000 VNĐ - 14,399,000 VNĐ Phương pháp khóa luận sử dụng đó là xây dựng cây DOM tương ứng với mã HTML của trang, sau đó sẽ duyệt qua cây DOM để xác định được giá chứa trong trang. Để xác định được node nào trong cây DOM là chứa giá thì khóa luận đã xây dựng được bộ luật xác định giá. Để xác định được giá ta sử dụng một số luật sau: - Trước giá thì có một vài tiền tố: như “GIÁ”, “PRICE” - Sau giá cũng có các hậu tố như: “VNĐ”, “USD”, “VND”,”Đ”,”$” …. - Định dạng của giá: dạng số , tức là bao gồm các ký tự {0, 1, 2,…, 9, “,”, “.”} - Node chứa giá là: #text Tuy nhiên trong quá trình thống kê này chúng tôi cũng thấy có nhiều giá không liên quan ví dụ như trường hợp trên thì “300.000 VNĐ” không phải là giá mặc dù nó chứa hậu tố VNĐ. Trong một số trường hợp như hình 19 thì mặc dù thỏa mãn các điều kiện về tiền tố, hậu tố và định dạng của giá. Nhưng nó không phải là giá có ý nghĩa với người sử dụng. Vì vậy khóa luận này xây dựng các tiền tố loại trừ để loại trừ các giá không ý nghĩa đó. Một số tiền tố loại trừ như : “GIÁ CŨ”, “GIÁ BÌA”, “GIÁ THỊ TRƯỜNG”… 29 Hình 16. Ví dụ về sản phẩm chứa những giá không đúng • Bài toán trích xuất thông tin giá cả của sản phẩm Mô tả bài toán - Đầu vào: Tên sản phẩm và trang Web lên quan đến sản phẩm. - Đầu ra: Giá thực của sản phẩm, mẫu trích xuất giá thực đó và mẫu trích xuất tên sản phẩm. Ví dụ: đầu vào là trang web bán sản phẩm Nokia 1200 như sau. Hình 17. Ví dụ về trích xuất giá thực của trang sản phẩm Giá không đúng Tiền tố loại trừ Giá thực 30 Đầu ra sẽ là giá của sản phẩm này : VNĐ 540.000 là giá thực của sản phẩm, mẫu trích xuất tên sản phẩm này là “HTML Æ BODY Æ TABLE[1] Æ TR[1] Æ TD[1] Æ Tên sản phẩm” và mẫu trích xuất giá này là “HTML Æ BODY Æ TABLE[1] Æ TR[2] Æ TD[2] Æ Giá thực sản phẩm”. Xác định đước giá của sản phẩm là một bài toán hết sức quan trọng trong hệ thống tìm kiếm giá cả. Tuy nhiên không có một chuẩn để nhận dạng được giá mà có thể áp dụng để nhận dạng tất cả các trang. Phương pháp giải quyết bài toán Để xác định giá phương pháp được thực hiện thông qua những bước sau: Xây dựng cây DOM tương ứng với mã HTML của trang Web đầu vào - Bước 1: Xác định được node của cây DOM chứa tên sản phẩm và lấy được mẫu trích xuất tên sản phẩm. - Bước 2: Xác định tất các các node chứa giá trong trang Web như đã nêu ở trong bài toán tiền đề và lấy được mẫu trích xuất tương ứng với những giá đó. - Bước 3: Loại trừ các giá không phù hợp. - Bước 4: Xác định được giá thực của sản phẩm thông qua mối quan hệ giữa tên và giá của sản phẩm. Tại bước 1, ta sẽ duyệt qua cây DOM, xác định node chứa tên sản phẩm (tên sản phẩm đã định rõ từ đầu vào). Từ các node này ta sẽ sinh ra mẫu trích xuất tương ứng với tên sản phẩm. Tại bước 2 sau khi xác định được node có chứa giá theo bài toán tiền đề, ta có thể lấy được mẫu trích xuất tương ứng với node đó theo phương pháp trích xuất sử dụng cây DOM đã nêu ở phần 2.1. Sau khi đã xác định được tất cả các mẫu trích xuất giá và mẫu trích xuất tên sản phẩm, để xác định được giá thực của sản phẩm ta phải loai trừ những giá không phù hợp, đó là những giá nằm trông một số thẻ hay thẻ . Giá có thể xuất hiện độc lập hoặc không độc lập, ví dụ: giá 120.000 vnđ là giá độc lập trong khi giá 100.000 vnđ (30%) là giá không độc lập. Nếu chỉ có một giá độc lập thì giá này được coi là giá thực. Nếu có nhiều giá độc lập, thì 31 tất cả các giá đó đều có thể là giá của sản phẩm. Vì vậy ta phải dựa vào mối quan hệ giữa tên sản phẩm và giá của sản phẩm đó. Mối quan hệ giữa tên sản phẩm và giá của