Mẫu 1a
MẪU BÌA LUẬN VĂN CĨ IN CHỮ NHŨ VÀNG Khổ 210 x 297 mm

PHẠM NGUYỄN TUẤN ANH

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------

Phạm Nguyễn Tuấn Anh

CƠNG NGHỆ THƠNG TIN

TỰ ĐỘNG TRÍCH XUẤT THƠNG TIN SẢN PHẨM
TRÊN WEB ỨNG DỤNG KỸ THUẬT SIMHASH

LUẬN VĂN THẠC SĨ KHOA HỌC
CÔNG NGHỆ THÔNG TIN

2009
Hà Nội – 2011


MẪU TRANG PHỤ BÌA LUẬN VĂN

Mẫu 1b

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------------------Phạm Nguyễn Tuấn Anh

TỰ ĐỘNG TRÍCH XUẤT THƠNG TIN SẢN PHẨM
TRÊN WEB ỨNG DỤNG KỸ THUẬT SIMHASH

Chuyên ngành :

Công nghệ thông tin

LUẬN VĂN THẠC SĨ KHOA HỌC
CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC :
TS. NGUYỄN KHANH VĂN

Hà Nội – 2011


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

MỤC LỤC
MỤC LỤC...........................................................................................1
T
6
2

26T

ĐẶT VẤN ĐỀ .....................................................................................4
T
6

2

26T

CHƯƠNG I: KHÁI QT BÀI TỐN TRÍCH XUẤT THƠNG
T
6
2

TIN CHO DỮ LIỆU BÁN CẤU TRÚC ............................................9
T
6
2

1. Bài tốn trích xuất thơng tin ......................................................................... 9
T
6
2

T
6
2

1.1. Giới thiệu bài toán ................................................................................................... 9
T
6
2

26T


1.2. Dữ liệu của bài toán.................................................................................................. 9
T
6
2

26T

2. Các hướng tiếp cận trong bài toán trích xuất thơng tin ................................................... 11
T
6
2

T
6
2

3. Bài tốn trích xuất thông tin cho dữ liệu bán cấu trúc .................................................... 12
T
6
2

T
6
2

3.1. Vấn đề đặt ra với bài toán ........................................................................................12
T
6
2


T
6
2

3.2. Một số phương pháp trích xuất thơng tin cho dữ liệu bán cấu trúc ............................13
T
6
2

T
6
2

3.3. Phương pháp đánh giá .............................................................................................13
T
6
2

26T

3.4. Ứng dụng của bài tốn trích xuất thơng tin cho dữ liệu bán cấu trúc .........................14
T
6
2

T
6
2

CHƯƠNG II: MỘT SỐ PHƯƠNG PHÁP SỬ DỤNG TRONG

T
6
2

BÀI TỐN TRÍCH XUẤT THƠNG TIN CHO DỮ LIỆU BÁN
CẤU TRÚC.......................................................................................17
26T

1. Trích xuất thơng tin dựa vào cây DOM ...................................................... 17
T
6
2

T
6
2

1.1. Khái nhiệm cây DOM .............................................................................................17
T
6
2

26T

1.2. Xây dựng cây DOM ................................................................................................18
T
6
2

26T


1.3. Sử dụng cây DOM để trích xuất thơng tin ................................................................20
T
6
2

T
6
2

2. Trích xuất thơng tin dựa theo các mẫu biểu thức chính qui ........................ 21
T
6
2

T
6
2

2.1. Khái niệm biểu thức chính qui .................................................................................21
T
6
2

T
6
2

2.2. Sử dụng biểu thức chính qui để trích xuất thơng tin .................................................22
T

6
2

T
6
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 ................... 22
T
6
2

T
6
2

-1-


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

3.1 Hai kiểu biểu diễn của các trang giàu dữ liệu ...........................................................22
T
6
2

T
6
2


3.2. Một số giải thuật điển hình ......................................................................................23
T
6
2

T
6
2

CHƯƠNG III: PEWEB – HỆ THỐNG BĨC TÁCH THƠNG TIN
T
6
2

SẢN PHẨM DỰA TRÊN TÍNH TỐN ENTROPY .....................29
T
6
2

1. Xây dựng cây HTML........................................................................................ 29
T
6
2

26T

2. Tính tốn Entropy ............................................................................................. 30
T
6

2

26T

CHƯƠNG IV: TỰ ĐỘNG TRÍCH XUẤT THƠNG TIN SẢN
T
6
2

PHẨM TRÊN WEB ỨNG DỤNG KỸ THUẬT SIMHASH .........39
T
6
2

1. Bài tốn trích xuất thơng tin sản phẩm từ các website thương mại .................................... 39
T
6
2

T
6
2

2. Kỹ thuật xác định vị trí các vùng mơ tả sản phẩm sử dụng Simhash.................................. 41
T
6
2

T
6

2

2.1. Các trang web thương mại và cây DOM..................................................................42
T
6
2

T
6
2

2.2. Kỹ thuật Simhash dùng trong phát hiện các văn bản trùng lặp .................................44
T
6
2

T
6
2

2.3. Sử dụng Simhash để tìm các cây con tương tự nhau trong cây DOM .......................44
T
6
2

T
6
2

2.4. Xây dựng cây quyết định cho quá trình lọc kết quả .................................................47

T
6
2

T
6
2

3. Cài đặt hệ thống bóc tách thơng tin sản phẩm sử dụng Simhash...................................... 49
T
6
2

T
6
2

3.1. Tìm kiếm các vùng có khả năng chứa thơng tin sản phẩm ........................................49
T
6
2

T
6
2

3.2. Loại bỏ nhiễu ..........................................................................................................51
T
6
2


26T

4. Chương trình bóc tách thơng tin sản phẩm ............................................................... 52
T
6
2

T
6
2

5. Các kết quả thực nghiệm..................................................................................... 55
T
6
2

26T

5. Kết luận và hướng phát triển................................................................................. 58
T
6
2

26T

TÀI LIỆU THAM KHẢO ...............................................................60
T
6
2


T
6
2

-2-


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

DANH MỤC HÌNH
Hình 1: Ví dụ về tính cấu trúc của trang web bán cấu trúc................................ 10
U
T
6
2

T
6
2
U

Hình 2: Ví dụ về bài tốn nhận dạng thực thể ................................................... 11
U
T
6
2

T

6
2
U

Hình 3: Ví dụ về trích xuất nội dung chính của trang Web ................................ 15
U
T
6
2

T
6
2
U

Hình 4: Ví dụ về hệ thống tìm kiếm giá cả ......................................................... 16
U
T
6
2

T
6
2
U

Hình 5: Ví dụ xây dựng cây DOM sử dụng hộp ảo ............................................ 20
U
T
6

2

T
6
2
U

Hình 6: Dạng biểu diễn của trang list page ....................................................... 23
U
T
6
2

T
6
2
U

Hình 7: Dạng biểu diễn của trang detail page ................................................... 23
U
T
6
2

T
6
2
U

Hình 8: Chuyển đổi từ mã HTML sang cây EC ................................................. 24

U
T
6
2

T
6
2
U

Hình 9: Ví dụ giải thuật RoadRunner ................................................................ 28
U
T
6
2

T
6
2
U

Hình 10: Các mơ tả sản phẩm và cây DOM ...................................................... 31
U
T
6
2

T
6
2

U

Hình 11: Q trình tính giá trị đại diện ............................................................. 32
U
T
6
2

T
6
2
U

Hình 12: Một trang web bán máy tính xách tay ................................................. 43
U
T
6
2

T
6
2
U

Hình 13: Các vùng sản phẩm và vị trí của chúng trên cây DOM....................... 43
U
T
6
2


T
6
2
U

Hình 14: Một ví dụ của q trình tính Simhash trên cây tại node T................... 46
U
T
6
2

T
6
2
U

Hình 15: Cây quyết định xác định một vùng có là một vùng sản phẩm hay khơng
U
T
6
2

T
6
2
U

.......................................................................................................................... 48
Hình 16: Giao diện chương trình bóc tách thơng tin sản phẩm ......................... 53
U

T
6
2

T
6
2
U

Hình 17: Sau khi nhập một đường link trang web bán hàng, chương tình tiến
U
T
6
2

hành phần tích cấu trúc của trang web và xây dựng cây DOM tương ứng ........ 54
T
6
2
U

Hình 18: Kết quả sau khi tìm và bóc tách thơng tin từ các vùng chứa thông tin
U
T
6
2

sản phẩm ........................................................................................................... 55
26T
U


-3-


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

ĐẶT VẤN ĐỀ
Nhưng năm gần đây, cùng với sự phát triển mạnh mẽ của hạ tầng cơ sở mạng
cũng như công nghệ lưu trữ Internet đã trở thành một thành phần không thể thiếu
trong đời sống con người. Hàng loạt các ứng dụng dựa trên nền tảng của Internet đã
ra đời để phục vụ cho nhu cầu, lợi ích của con người. Nổi bật lên trong các ứng dụng
đó chính là các ứng dụng liên quan đến thương mại điện tử. Thương mại điện tử ra
đời giúp con người giảm thiểu tối đa thời gian cũng như chi phí khi tham gia giao
dịch hàng hóa. Tuy nhiên cùng với sự phát triển của thơng tin trên Internet thì các
thông tin liên quan đến thương mại điển tử cũng bùng nổ không kém, hàng loạt các
trang web bán hàng trực tuyến cùng với nó là hàng triệu sản phẩm và các thông tin
liên quan đến sản phẩm làm cho con người khó khăn trong việc tìm kiếm. Các câu hỏi:
Sản phẩm nào tốt ? Giá cả cửa hàng nào tốt hơn ? Tìm kiếm thơng tin của sản phẩm ở
đâu ?... làm con người khó khăn khi lựa chọn một sản phẩm cần giao dịch. Giải pháp
cho vấn đề này đó chính là cần có một hệ thống tìm kiếm phục vụ cho nhu cầu tìm
kiếm này của con người các hệ thống này thường được biết đến với tên gọi hệ thống
tìm kiếm giá cả sản phẩm.
Chính từ nhu cầu thực tế đấy, hệ thống tìm kiếm giá cả đã được rất nhiều sự
quan tâm của các bộ máy tìm kiếm (Search Engine) lớn trên thế giới như Google,
Yahoo, Bing… Ngồi các dịch vụ tìm kiếm thơng thường khác, các Search Engine này
đều có các dịch vụ tìm kiếm riêng cho các sản phẩm, hàng hoá được rao bán trực tuyến
trên các website thương mại. Cách thức hoạt động chung của các dịch vụ tìm kiếm sản
phẩm trực tuyến là: sau khi thu thập các trang web của các website thương mại lưu vào
trong kho dữ liệu của mình, các Search Engine tiến hành bóc tách thơng tin liên qua

đến các mặt hàng sản phẩm có trong các trang web đó, và tổ chức lưu trữ dữ liệu đã
được bóc tách một các hợp lý để có thể nhanh chóng đáp ứng các truy vấn từ người
dùng. Những thông tin mà người dùng quan tâm đến một sản phẩm thường là tên sản

-4-


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

phẩm, giá cả, các mô tả chi tiết của sản phẩm, hay địa chỉ rao bán… Nếu như việc thu
thập và tổ chức lưu trữ dữ liệu không phải là vấn đề quá khó khăn đối với các Search
Engine, vì dữ liệu về các sản phẩm trực tuyến chỉ là một phần rất nhỏ so với dữ liệu
toàn bộ dữ liệu Web, thì vấn đề bóc tách thơng tin sản phẩm thực sự đặt ra nhiều thách
thức cho các Search Engine. Có thể nói, chất lượng của các dịch vụ tìm kiếm phụ thuộc
rất nhiều vào chất lượng của q trình bóc tách thơng tin sản phẩm. Chỉ khi có một
phương pháp bóc tách thơng tin sản phẩm thật đầy đủ và chi tiết, thì các Search Engine
mới có thể đem lại kết quả tìm kiếm tốt nhất cho người dùng.
Vấn đề đầu tiên khi tiến hành bóc tách thông tin sản phẩm từ các trang web bán
hàng trực tuyến là xác định vị trí của các phần chứa thơng tin sản phẩm có trên trang
web. Tuy nhiên, đây khơng phải là vấn đề có thể giải quyết một cách dễ dàng. Trên
một trang web bán hàng, ngoài các khu vực chứa thơng tin sản phẩm, cịn có các vùng
thông tin khác như menu, quảng cáo, danh sách danh mục mặt hàng… Các phương
pháp bóc tách sản phẩm cần phải phân biệt được các vùng chứa và không chứa thơng
tin sản phẩm, để có thể khơng phát hiện thiếu hay nhầm lẫn, làm ảnh hưởng tới q
trình bóc tách sau này. Khó khăn mà các Search Engine gặp phải là mỗi website có một
cách trình bày hay bố trí sản phẩm trên trang web riêng, và cách trình bày có thể được
thay đổi một cách thường xuyên. Cộng với việc số lượng các website bán hàng, dẫn
đến số lượng các trang web chứa thông tin sản phẩm, rất lớn thì các Search Engine
thực sự cần một phương pháp khơng những nhanh mà cịn phải hồn tồn tự động để

xác định vị trí các vùng sản phẩm trên các trang web. Do đó, vấn đề này đã được đặt ra
nghiên cứu từ nhiều năm nay.
Bóc tách thơng tin sản phẩm là vấn đề con nằm trong bài tốn bóc tách thơng tin
trên Web nói chung. Từ lâu, bài tốn bóc tách dữ liệu từ Web đã được đặt ra nghiên
cứu để phục vụ cho nhiều mục đích, như để thu thập các bài viết từ các trang báo điện
tử, các thơng tin tài chính… Các phương pháp trích xuất thơng tin Web ít nhiều đều có
thể áp dụng cho bài tốn bóc tách thơng tin sản phẩm. Từ trước tới nay, bóc tách dữ

-5-


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

liệu Web thường là xây dựng các chương trình đặc biệt, gọi là các wrapper, để tìm các
dữ liệu cần và xây dựng một bộ khung để khi áp dụng vào các trang web, ta có thể có
ngay các dữ liệu mong muốn. Việc xây dựng và duy trì wrapper có thể sẽ rất khó khăn,
do đó đã có rất nhiều cải tiến cho việc này. Sau đây là một vài phương pháp và công cụ
tương ứng xây dựng các wrapper, cũng như tính hiệu quả của chúng dựa trên khả năng
tự động của chúng.
-

Ngôn ngữ xây dựng wrapper: hướng tiếp cận này sẽ thiết kế các ngôn ngữ đặc biệt
nhằm hỗ trợ người xây dựng wrapper dễ dàng hơn. Một vài công cụ nổi bật là
Minera[11]. TSIMMIS[15], Web-OQL[3]. Các ngơn ngữ này có thể được sử dụng
để thay thế các ngơn ngữ lập trình.

-

Các cơng cụ dựa HTML: Hướng tiếp cận này nhằm xây dựng các công cụ dựa vào

các đặc tính về cấu trúc vốn có của các văn bản HTML để trích xuất dữ liệu. Trong
q trình tiền xử lý, các cơng cụ sử dụng hướng tiếp cận này, như W4F[27],
XWRAP[21], hoặc RoandRunner[10] sẽ biến đổi các văn bản thành các cây mà
phản ánh được tính phân cấp của văn bản HTML.

-

Các cơng cụ sử dụng các kỹ thuật xử lý ngôn ngữ tự nhiên: Trong hướng tiếp cận
này, các công cụ RAPIER[6], SRV[14], WHISK[31],… xây dựng các luật bóc tách
thơng tin trong các văn bản ngôn ngữ tự nhiên bằng các sử dụng các kỹ thuật NLP,
chẳng hạn như lọc, gán nhãn, và đánh thẻ từ vựng ngữ nghĩa. Hướng tiếp cận này
thường thích hợp để xử lý các văn bản có cú pháp chuẩn.

-

Các công cụ wrapper qui nạp: trong hướng tiếp cận này, các luật bóc tách dựa vào
các dấu hiện phân cách được xây dựng từ một tập học mẫu. Các công cụ wrapper
qui nạp, như WIEN[18], SoftMealy[16], và STALKER[23], sẽ thích hợp với văn
bản HTML hơn là các cơng cụ sử dung kỹ thuật NLP, bởi vì chúng phụ thuộc vào
các đặc tính định dạng tạo nên cấu trúc của dữ liệu cần tìm, hơn là các rằng buộc về
ngơn ngữ.

-6-


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

-


Các công cụ sử dụng mẫu: Ý tưởng của hướng tiếp cận này là tìm trong trang web
các mẩu dữ liệu mà khớp với cấu trúc của các đối tượng cần quan tâm. Sau đó,
bằng cách sử dụng các thuật tốn như của các cơng cụ wrapper qui nạp, các công cụ
sử dụng mẫu, như NoDoSe[1], và DeByE[19] sẽ xác định các đối tượng có cấu trúc
giống với cấu trúc cho trước trên các trang web.
Một tiêu chí quan trọng khi so sánh các phương pháp bóc tách thông tin là mức

độ tự động của các phương pháp. Trong hướng tiếp cận ngôn ngữ xây dựng wrapper,
người phát triển cần phải viết một lượng lớn code, để xây dựng chương trình bóc tách
các đối tượng cần quan tâm. Do đó, người phát triển phải kiểm tra các văn bản và tìm
các thẻ HTML cần cho quá trình xác định biên của các đối tượng một cách thủ công.
Trong khí đó, mặc dù có mức độ tự động hố cao hơn, các công cụ dựa HTML chỉ thực
sự hiệu quả khi có sự nhất quả của các thẻ HTML trong các trang web. Điều này khó
có thể xảy ra với số lượng trang web lớn. Trong các hướng tiếp cận NLP, wrapper qui
nạp, và sử dụng mẫu, người phát triển chỉ phải cung cấp các mẫu thử cho quá trình xây
dựng wrapper. Do đó, các cơng cụ này được coi là bán tự động.
Có thể thấy rằng, các phương pháp bóc tách dữ liệu ở trên khơng hồn tồn tự
động: chúng đều cần ít nhất một giai đoạn cần sự can thiệp của người phát triển. Điều
này sẽ là không khả thi khi áp dụng để xử lý một tập dữ liệu lớn như các trang web.
Vấn đề cần đặt ra là phải tìm một hướng tiếp cận khác mà q trình bóc tách dữ liệu
của nó khơng cần đến bất cứ tác động từ người phát triển.
Trong luận văn này, tác giả sẽ đề xuất một phương pháp hồn tồn tự động để
xác định các vùng chứa mơ tả sản phẩm có trên một trang web bán hàng. Phương pháp
này dựa vào hướng tiếp cận đã có của tác giả Phan Xuân Hiếu và các tác giả khác[32],
trong q trình xây dựng một hệ thống lấy thơng tin sản phẩm, có tên là PEWeb.
Hướng tiếp cận này tận dụng tính chất rất thường gặp của các trang web bán hàng, đó
là các vùng chứa sản phẩm trong trang web thường có cách trình bày giống hoặc gần
giống nhau. Đây là đặc tính quan trọng, giúp ta có thể dễ dàng xác định các vùng sản

-7-



Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

phẩm trên trang web. Tuy có cùng hướng tiếp cận, nhưng phương pháp của chúng tôi
khác với phương pháp của PEWeb. Chúng tôi đề xuất sử dụng một hàm băm đặc biệt,
được gọi là Simhash, để tìm các vùng chứa mô tả sản phẩm. Simhash đã từng được sử
dụng để tìm các đối tượng có các thuộc tính tương tự nhau, chẳng hạn như các văn bản
trùng lặp. Chúng tôi đã biến đổi hàm Simhash để áp dụng cho bài toán xác định các
vùng chứa sản phẩm trên trang web. Chúng tơi chọn Simhash vì sử dụng kỹ thuật này
không những đem lại kết quả cao và tốc độ xử lý nhanh mà cịn khơng phụ thuộc vào
một cấu trúc văn bản HTML cụ thể nào nên không cần có xử lý nào từ phía người phát
triển, hay nói cách khác, nó hồn tồn tự động. Do đó, giải pháp này đã giải quyết được
các khó khăn mà các Search Engine gặp phải mà đã nêu ở trên. Chi tiết của phương
pháp do chúng tôi đề xuất sẽ được trình bày kỹ hơn trong luận văn này.
Luận văn gồm 4 chương nội dung được mô tả sơ bộ dưới đây:
-

Chương 1: Trong chương này, chúng tôi khái quát bài tốn trích xuất thơng
tin cho dữ liệu bán cấu trúc.

-

Chương 2: Chúng tơi trình bày một số phương pháp sử dụng trong bài tốn
trích xuất thơng tin cho dữ liệu.

-

Chương 3: Chúng tôi giới thiệu PEWeb, một hệ thống bóc tách thơng tin sản

phẩm hồn tồn tự động

-

Chương 4: Chúng tơi trình bày phương pháp của chúng tơi để xác định và
lấy thông tin sản phẩm từ các trang web thương mại.

-8-


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

CHƯƠNG I: KHÁI QT BÀI TỐN TRÍCH XUẤT THƠNG
TIN CHO DỮ LIỆU BÁN CẤU TRÚC
Chủ đề chính của khóa luận là áp dụng bài tố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ả. Chương này sẽ giới thiệu bài
tốn trích xuất thơng tin nói chung và bài tốn trích xuất thơng tin cho dữ liệu bán
cấu trúc nói riêng, từ đó đưa ra một số ứng dụng của bài tốn trích xuất thơng tin cho
dữ liệu bán cấu trúc, đồng thời cũng giới thiệu về phương pháp đánh giá khả năng
trích xuất thơng qua độ hồi tưởng (R), độ tin cậy (P).

1. Bài tốn trích xuất thơng tin
1.1. Giới thiệu bài tốn
Trích xuất thơng tin bài tốn nhận dạng những thành phần thông tin cụ thể
của một văn bản, những thành phần này chính là hạt nhân tạo nên nội dung ngữ nghĩa
của văn bản đó [17].
Ví dụ: Với một báo cáo thời tiết có thể trích xuất được thông tin về các vùng,
thời gian, nhiệt độ cao hay thấp. Với một trang web về kinh doanh sản phẩm trực
tuyến có thể trích xuất được thơng tin về tên sản phẩm, thuộc tính của sản phẩm và

giá của sản phẩm đó.

1.2. Dữ liệu của bài tốn
Dữ liệu thơng thường được chia thành 3 dạng cơ bản:
• Dữ liệu không cấu trúc: Dữ liệu không cấu trúc thường dùng để chỉ dữ
liệu ở dạng tự do và không cần có cấu trúc định nghĩa sẵn ví dụ như:
ngơn ngữ tự nhiên.

-9-


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

• Dữ liệu có cấu trúc: Dữ liệu có cấu trúc thường dùng để chỉ dữ liệu lưu trữ
trong các hệ quản trị cơ sở dữ liệu quan hệ như MS SQL server hay
MySQL, trong đó các thực thể và các thuộc tính được định nghĩa sẵn.
• Dữ liệu bán cấu trúc: Là dữ liệu có cấu trúc nhưng khơng hồn tồn tường
minh, nó khơng tn theo những cấu trúc, cách thức cấu trúc của bảng và
các mô hình
dữ liệu trong cơ sở dữ liệu nhưng nó chứa những thẻ , những đánh dấu tới
những phần tử ngữ nghĩa riêng biệt của các bản ghi và các trường riêng
biệt bên trong dữ liệu .
Các trang web thông thường là một dạng tiêu biểu của dữ liệu bán cấu trúc,
những thành phần có cấu trúc trong trang web đó là dữ liệu được lấy từ tầng cơ sở
dữ liệu (có cấu trúc) bên dưới và hiện thị trên web thơng qua các thẻ HTML…

Hình 1: Ví dụ về tính cấu trúc của trang web bán cấu trúc
Hình 1 mơ tả dữ liệu bán cấu trúc về trang sản phẩm, dữ liệu này chứa tên các
sản phẩm, giá sản phẩm và các thông tin chi tiết về sản phẩm. Các thông tin ứng với


- 10 -


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

từng sản phẩm được mô tả dưới dạng mã HTML đã định trước. Dữ liệu này được lấy
từ tầng cơ sở dữ liệu (có cấu trúc) bên dưới và hiển thị trên trang web thông qua các
thẻ HTML. Đây chính là thành phần có cấu trúc của trang web.

2. Các hướng tiếp cận trong bài tốn trích xuất thơng tin
Các bài tốn trích xuất thơng tin thơng thường được tiếp cận theo dữ liệu
mà bài tốn đó xử lý. Vì vậy có những dạng bài tốn như sau:
• Dữ liệu có cấu trúc
Đối với dữ liệu có cấu trúc, việc trích xuất thơng tin là khá đơn giản. Vì các
thơng tin đã được biểu diễn theo những định dạng chuẩn của bảng, thực thể.. nên có
thể lấy được những thông tin cần thiết một các dễ dàng dựa vào những truy vấn.
Ví dụ: dữ liệu có cấu trúc được lưu trữ trong hệ quản trị cơ sở dữ liệu MS
SQL, MySQL có thể trích xuất được những thơng tin cần thiết dựa vào các lệnh
SQL như SELECT, JOIN.
• Dữ liệu khơng cấu trúc

Hình 2: Ví dụ về bài tốn nhận dạng thực thể
Đối với dữ liệu khơng cấu trúc thì có một số bài tốn về trích xuất thông tin

- 11 -


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash

Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

như nhận dạng và trích xuất thực thể: tên người, tên tổ chức…
Để giải quyết bài tốn trích xuất thực thể thì có nhiều cách tiếp cận như
HMM, SVM hay CRF…ngồi ra cịn một giải thuật khá nổi tiếng đó là giải thuật
DIPRE - Dual Iterative Pattern Relation Expansion của BRin [28] trong việc trích
xuất cặp thực thể quan hệ tên sách và tác giả đối với trang amazon.com.
• Dữ liệu bán cấu trúc
Web là dữ liệu điển hình trong dữ liệu bán cấu trúc. Trích xuất thơng tin web
đó là vấn đề trích xuất các thành phần thơng tin mục tiêu từ những trang Web.
Một chương trình hay một luật trích xuất thường được gọi là một wrapper.
Phương pháp trích xuất này có nhiều hướng tiếp cận như sử dụng cây DOM.
Phương pháp này sẽ phân tích mã nguồn HTML dưới dạng một cây các node, mỗi
node là một thẻ HTML, q trình trích xuất thơng tin sẽ dựa vào đường đi từ gốc đến
node chứa thông tin cần trích xuất.

3. Bài tốn trích xuất thơng tin cho dữ liệu bán cấu trúc
3.1. Vấn đề đặt ra với bài tốn
Trích xuất thơng tin cho dữ liệu bán cấu trúc.
Bài tốn trích xuất thơng tin cho dữ liệu bán cấu trúc là rất hữu dụng bởi vì
nó cho phép chúng ta thu được và tích hợp dữ liệu từ nhiều nguồn để cung cấp cho
những dịch vụ giá trị gia tăng như : thu được những thông tin Web một cách tùy ý, hệ
thống tìm kiếm giá cả, hay meta-search. Ngày càng nhiều các công ty, các tổ chức phổ
cập các thơng tin ở trên Web, thì khả năng trích xuất dữ liệu từ các trang Web đó
ngày càng trở nên quan trọng.
Bài toán này đã được bắt đầu nghiên cứu vào giữa những năm của thập niên
1990 bởi nhiều công ty và các nhà nghiên cứu.

- 12 -



Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

3.2. Một số phương pháp trích xuất thơng tin cho dữ liệu bán cấu trúc
Như ta đã nói về một số hướng tiếp cận ở mục 2 đối với dữ liệu bán cấu trúc
thì bài tốn trích xuất có một số phương pháp điển hình như:
• Phương pháp thủ công
Quan sát một trang Web và mã nguồn của nó, người lập trình sẽ tìm một vài
mẫu và viết chương trình để trích xuất các dữ liệu mục tiêu. Để làm đơn giản hơn
cho người lập trình, một vài ngôn ngữ miêu tả mẫu và các giao diện người dùng đã
được xây dựng. Tuy nhiên với phương pháp này thì khơng thể làm việc với một số
lượng lớn các trang[2].
• Wrapper qui nạp
Đây là phương pháp bán tự động. Nó được đề xuất vào khoảng năm 19951996. Trong phương pháp này thì một tập hợp các luật trích xuất được học từ một bộ
các trang đã được gán nhãn bằng tay. Sau đó các luật này sẽ được dùng để trích xuất
các thành phần dữ liệu từ những trang có định dạng tương tự. Một số giải thuật tiêu
biểu như: Stalker[5], WIEN[13] (được sử dụng trong máy tìm kiếm lycos).
• Phương pháp tự động
Được đề xuất trong năm 1998, phương pháp này tự động tìm các mẫu hoặc các
cấu trúc để trích xuất thơng tin từ những trang cho trước. Vì phương pháp này khơng
cần đến sự gán nhãn bằng tay nên nó có thể trích xuất được dữ liệu từ một lượng
khổng lồ các trang; một số giải thuật tiêu biểu như RoadRunner[10], bootstrapping[2].

3.3. Phương pháp đánh giá
Để đánh giá chất lượng phương pháp trích xuất thơng tin cho dữ liệu bán
cấu trúc người ta thường sử dụng một số độ đo như độ hồi tưởng (R), độ tin cậy (P).
Giả sử sau khi sử dụng bài toán trích xuất cho một tập dữ liệu gồm n tài
liệu. Kết quả trích xuất được là m tài liệu.Kết quả trích xuất đúng là q tài liệu khi đó
độ hồi tưởng R và độ chính xác P sẽ được tính theo công thực (1) và (2).


- 13 -


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

R=

q
×100%
n

(1)

R=

q
×100%
m

(2)

Ví dụ:
Nếu tập dữ liệu cần trích xuất là 100 (tài liệu).
Dữ liệu trích xuất được là: 97 (tài liệu).
Dữ liệu trích xuất đúng là: 90 (tài liệu) .

90
R = ×100% =

90%
100
90
R = ×100% =
92, 78%
97
3.4. Ứng dụng của bài tốn trích xuất thơng tin cho dữ liệu bán cấu trúc
• Nhận dạng và trích xuất nội dung chính của trang Web
Với một trang web ngồi những thành phần mang thơng tin chính thì cịn
những thành phần ít có ý nghĩa về mặt thơng tin như quảng cáo, các menu.... Việc
nhận dạng và trích xuất nội dung chính của trang web giúp giảm thiểu việc lưu trữ
thông tin và tối ưu kết quả trả về trong các máy tìm kiếm vì máy tìm kiếm chỉ phải
lưu nội dung chính của trang web và tìm kiếm trong nội dung chính này. Các giải
thuật được đề xuất như ContentExtractor và FeatureExtractor của Debnath[29], [30].

- 14 -


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

Hình 3: Ví dụ về trích xuất nội dung chính của trang Web
•

Hệ thống tìm kiếm giá cả sản phẩm

Hệ thống cho phép người sử dụng so sánh được giá cả của sản phẩm mà họ
muốn mua. Hệ thống này phải duyệt qua các trang web kinh doanh sản phẩm để
trích xuất các thơng tin hữu dụng về sản phẩm.


- 15 -


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

Hình 4: Ví dụ về hệ thống tìm kiếm giá cả

- 16 -


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

CHƯƠNG II: MỘT SỐ PHƯƠNG PHÁP SỬ DỤNG TRONG BÀI
TỐ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 tố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 [17] và biểu thức chính qui. Chương này cũng đề cập đến hai
giải thuật trong bài tố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 đó.

1. Trích xuất thơng tin dựa vào cây DOM
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. Ví dụ về một bảng được lấy văn bản HTML:
<TABLE>

<TBODY>

Dạng biểu diễn cây DOM của mã HTML

<TR>
<TD>Shady Grove</TD>
<TD>Aeolian</TD>
</TR>
<TR>
<TD>Over the River,

- 17 -


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

Charlie</TD>
<TD>Dorian</TD>
</TR>
</TBODY>
</TABLE>

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. 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ư <li>,
<hr>,

) 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ụ: <tr> … <td> … </tr> … </td>,
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

- 18 -


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

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ã 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.

- 19 -


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

Hình 5: Ví dụ xây dựng cây DOM sử dụng hộp ảo
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 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.
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:

- 20 -


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

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

2. Trích xuất thơng tin dựa theo các mẫu biểu thức chính qui
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ố HTML. Cho
một tập 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:
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), (A)? cũng là một biểu
P

P

thức chính qui, trong đó (A|B) tức là A hoặc B và (A)? tức là (A| ε).
P

P

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 đó
P


P

(A)* = { ε , A, AA, AAA,…}.
P

P

Chúng ta cũng sử dụng (A)+ để chỉ A(A)*. Nếu biểu thức chính qui khơng có
P

P

P

- 21 -

P


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009

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. 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 q trình này, dữ liệu có thể được trích xuất.

Ví dụ: Với mã HTML như sau:
<head>
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
<title>Tinh tong cua cac so tu 1 den n</title>
</head>
Để 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: <head>.*?<title>(#text)</title>

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
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.
-

List Page: là trang chứa đựng một vài danh sách của các đối tượng. Hình 6
giới thiệu một list page. Có hai dạng trang list, đó là trang list bố trí theo
chiều ngang 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.

-

Detail Page: là trang chỉ giới thiệu một đối tượng đơn. Ví dụ hình 7 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

- 22 -


Tự động trích xuất thơng tin sản phẩm trên Web ứng dụng kỹ thuật Simhash
Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009


của sản phẩm như: tên, ảnh, giá, thông số kỹ thuật, thời gian bảo hành.

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

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à

- 23 -