MỤC LỤC
Hình 1.1: Thu hồi thông tin bằng công cụ Google 12
Hình 1.2: Trích rút thông tin tỷ số bóng đá từ LivesCore 13
Hình 2.1:Thuật toán tìm thông tin dạng bảng 22
Hình 2. 3: Thủ tục trích rút thông tin từ bảng 25
Hình 2.4: Ví dụ về cây DOM 27
Hình 2.5: Các cây DOM và cây đặc trưng ST 29
Hình 2.6:Ví dụ về SST 32
Hình 2.7: Thuật toán đánh dấu các vùng nhiễu 36
Hình 2.8:Một SST đã được đơn giản 38
Hình 2.9: Thủ tục MapSST 39
Hình 2.10: Thủ tục SSTWebSite 40
Hình 2.11: Một minh họa cho các đỉnh gộp và các vùng dữ liệu 43
Hình 2.12: Thuật toán đối sánh cây đơn giản 44
Hình 2.13: Cây thẻ HTML cho các data record 46
Hình 2.14: Thực hiện hợp đỉnh và so sánh 47
Hình 2.15: Thuật toán so sánh đỉnh của cây dựa trên khoảng cách soạn thảo 48
Hình 2.16: Thủ tục so sánh gộp của các đỉnh 49
Hình 2.17: Mô tả một vùng dữ liệu 50
Hình 2.18: Thuật toán tìm tất cả các vùng dữ liệu trong một cây thẻ HTML 53
Hình 2.19: Thủ tục xác định các vùng dữ liệu có thể có của đỉnh 54
Hình 2.20: Thủ tục kiểm tra vùng dữ liệu con có nằm trong vùng mức cha 55
Hình 2.21: Thủ tục tạo cây mẫu biểu diễn thông tin các bản ghi dữ liệu 56
Hình 2.22 Chèn cây khi hai đỉnh kề có đối sánh 58
Hình 2.24: Không thể thực hiện chèn 59
Hình 2.25: Cây thẻ html cần tách thông tin 60
Hình 2.26: Cây mẫu biểu diễn thông tin trong một vùng 61
Hình 2.27: Tách các trường thông tin từ cây mẫu 62
1
Hình 3.1: Giao diện chính của hệ thống 63
Hình 3.2: Giao diện tách thông tin dạng bảng 64

Hình 2.27: Tách các trường thông tin từ cây mẫu 62
3
Hình 3.1: Giao diện chính của hệ thống 63
Hình 3.2: Giao diện tách thông tin dạng bảng 64
Hình 3.5: Trang web tỷ giá ngoại tệ của ngân hàng Vietcombank 67
Hình 3.7: Biểu đồ tỷ giá ngoại tệ 69
4
LỜI NÓI ĐẦU
Với tốc độ phát triển nhanh chóng, Internet và World Wide Web
(WWW ) ngày càng ảnh hưởng sâu rộng đến mọi mặt của đời sống, khoa
học, kinh tế, chính trị, văn hóa, xã hội,…Theo số liệu thống kê năm 1995,
số người truy cập Internet thường xuyên chỉ đạt khoảng 33 triệu người, đến
năm 2000 thì con số này là 150 triệu người, đến năm 2005 số người thường
xuyên truy cập Internet lên đến 850 triệu người và đến năm 2007 thì con số
này là xấp xỉ 1.2 tỷ người. Hơn nữa, với doanh số tối thiểu giao dịch hàng
năm đạt 1.5 ngàn tỷ USD, Internet đã thực sự trở thành một phần thiết yếu
của cuộc sống hiện đại.
Trong đó, việc tận dụng các nguồn thông tin từ Internet là một điều
hết sức quan trọng, bởi vì với thời đại công nghệ thông tin hiện nay, ai nắm
bắt được thông tin thì người đó có cơ hội thành công rất lớn. Phương pháp
lấy thông tin trên mạng thông dụng nhất hiện nay là tìm kiếm theo từ khóa
được cung cấp bởi Google, Yahoo,…Tuy nhiên, việc trả về quá nhiều địa
chỉ làm cho quá trình lựa chọn những thông tin cần thiết trở nên vô cùng
khó khăn và tốn nhiều thời gian. Đối với người dùng, việc có được nhiều
thông tin không phải là điều quan trọng nhất, mà tính kịp thời, đầy đủ và
chính xác của thông tin mới là yếu tố quyết định.
Internet, với hàng tỉ trang web, hàng triệu cơ sở dữ liệu thông tin về
nhiều lĩnh vực: khoa học, kinh tế, chính trị, xã hội , được coi là “mỏ thông
tin” vĩ đại nhất trong lịch sử loài người. Tuy nhiên, những thông tin này lại
nằm rải rác ở nhiều nơi, khiến việc thu thập, lưu trữ để rồi sau đó tiến hành

6
thông tin trong các lĩnh vực thông tin mới nên các hệ thống này vẫn còn ít
được sử dụng rộng rãi.
Mục đích của đề tài là nghiên cứu các kỹ thuật trích rút thông tin để
từ đó xây dựng một hệ thống tự động trích chọn thông tin dạng bảng từ các
Web site. Dữ liệu được ghi ra file dạng HTML, từ dạng dữ liệu này ta hoàn
toàn có thể sử dụng các công cụ sẵn có để chuyển đổi tiếp sang dạng dữ
liệu nào đó phù hợp với nhu cầu sử dụng, chẳng hạn dạng bảng tính của
Excel, dạng cơ sở dữ liệu của SQL, dạng DOC,…
Xây dựng ứng dụng trích chọn thông tin tỷ giá ngoại tệ trên web site
của ngân hàng Vietcombank, dữ liệu được lưu trữ trong cơ sở dữ liệu SQL,
từ đó người dùng có thể vẽ biểu đồ biến động giá cả của từng loại ngoại tệ
theo từng tháng để có thể hỗ trợ cho việc phân tích, đánh giá và đầu tư
thích đáng.
Đồ án được chia thành 3 chương với nội dung như sau:
Chương 1: Tổng quan về trích rút thông tin
Chương 2: Các kỹ thuật trích rút thông tin
Chương 3: Cài đặt thuật toán, thiết kế, xây dựng chương trình.
Em xin chân thành cảm ơn thầy giáo đã hướng dẫn, giúp đỡ em trong
quá trình làm đồ án!
7
CHƯƠNG 1: TỔNG QUAN VỀ TRÍCH RÚT THÔNG TIN• Khái niệm khai phá dữ liệu
• Khái niệm trích rút thông tin
• Các hệ trích rút-tách thông tin
• Kết luận
Chương này sẽ đưa ra những khái niệm cơ bản liên quan đến trích rút
thông tin, đồng thời tìm hiểu khả năng ứng dụng trích rút thông tin trong

lớp (classification), hồi quy (regression),…
9
Những ứng dụng điển hình của khai phá dữ liệu:
• Tài chính và thị trường chứng khoán (finance & stock market): phân
tích tình hình tài chính và dự báo giá của các loại cổ phiếu trong thị
trường chứng khoán,…
• Phân tích dữ liệu và hỗ trợ ra quyết định (data analysis and decision
support)
• Text mining & Webmining: khai thác văn bản và các trang Web,
tóm tắt văn bản, tìm kiếm thông tin,…
• Tin – sinh: tìm kiếm, đối sánh các quan hệ gen và thông tin di
truyền, mối liên hệ giữa một số hệ gen và một số bệnh di truyền,…
• Điều trị y học (medical treatment): mối liên hệ giữa triệu chứng,
chẩn đoán và phương pháp điều trị (chế độ dinh dưỡng, thuốc men,
…)
1.2 KHÁI NIỆM TRÍCH RÚT THÔNG TIN
Cho đến nay chưa có một định nghĩa chuẩn nào về trích rút thông tin,
tuy nhiên đối với nhiều nhóm nghiên cứu về trích rút thông tin họ đã đưa ra
khái niệm ban đầu về trích rút thông tin theo các hướng tiếp cận riêng của
họ. Nhìn một cách tổng quát, các khái niệm này đều có một số điểm giống
nhau thể hiện nét đặc trưng riêng của trích rút thông tin so với các ngành
khoa học khác. Ta có thể hiểu khái niệm về trích rút thông tin như sau:
Trích rút thông tin (Information Extraction-IE) là một quá trình
nhằm xác định và trích rút ra các thông tin cần thiết trên các văn bản tài
liệu cho trước.
Ta cần phân biệt sự khác biệt giữa hai kỹ thuật: kỹ thuật trích rút
thông tin IE và kỹ thuật thu hồi thông tin (Information Retrieval-IR) ví dụ
10
như các chương trình tìm kiếm thông tin trên Internet như là Google,
Yahoo,…

để mô hình các dữ liệu tuần tự. Mỗi trạng thái bỏ qua một số dấu hiệu
(token) tùy theo một số phân bố cố định. Sự chuyển đổi giữa các trạng thái
cũng tuân theo một số phân bố cố định. Khi sử dụng HMM cho trích rút
thông tin (IE), các trạng thái chính là các trường cần trích rút. Ví dụ có các
trạng thái khởi đầu và kết thúc cho mỗi trường và một trạng thái cho trường
hợp không có trường nào (trạng thái nền). Có các thuật toán hiệu quả cho
việc sinh ra dãy trạng thái liên tiếp cho một tài liệu cho trước. HMM có thể
được sử dụng trong IE bằng cách xác định một chuỗi trạng thái phù hợp
nhất cho việc xác định cấu trúc toàn bộ tài liệu cho trước, và sau đó tách
các biểu tượng (Symbol) tương ứng với các trường mà chúng ta muốn tách.
HMM mô hình một quá trình sinh các dãy biểu tượng từ một số trạng
thái ban đầu, việc sinh các biểu tượng được chỉ định bởi trạng thái đó và
việc chuyển đổi sang trạng thái kế tiếp. Quá trìnhh cứ tiếp tục cho đến khi
đạt tới trạng thái kết thúc. Tương ứng với mỗi tập trạng thái là một phân bố
xác suất thông qua một tập các chuyển đổi tới trạng thái kế tiếp. Các xác
suất này được học trong giai đoạn huấn luyện. Thuật toán lập trình động
Viterbi được sử dụng để tìm ra chuỗi trạng thái phù hợp nhất từ một HMM
cho trước và một chuỗi các biểu tượng. Mỗi trường khác nhau sử dụng một
HMM riêng.
14
Mỗi mô hình có 2 trạng thái, trạng thái nền và trạng thái đích. Trạng
thái đích sinh ra các trường mà ta cần trích rút.
Một trong những nhược điểm của việc sử dụng HMM cho IE là nó
khó mô hình cho một token có nhiều tính chất hoặc ý nghĩa khác nhau.
1.3.2 Rapier [11]
Rapier dựa trên việc học quy nạp từ các luật chi tiết đến các luật tổng
quát để xây dựng tập các luật dùng để trích rút các trường trong các tài liệu
đầu vào.
Rapier không dùng các thẻ đầu và cuối để xác định vị trí các trường
cần trích rút mà sử dụng việc học đối với các chuỗi ký tự chứa trường cần

tin trả về khá đầy đủ nhưng độ chính xác không cao vì có thêm các thông
tin dư thừa. Sau đó thuật toán được cải tiến nhờ sử dụng độ gia tăng. Nó lặp
lại việc áp dụng cho tập huấn luyện và với mỗi lần trọng số tương ứng với
mỗi mẫu thay đổi để nhấn mạnh các mẫu mà trên đó bộ học đã thực hiện
kém chất lượng ở lần học trước.
1.3.4 (LP)
2
[3]
(LP)
2
học các quy tắc tượng trưng cho việc xác định các thẻ đầu và
cuối. Giống như BWI, nó xác định các thẻ đầu và cuối của các trường một
cách riêng biệt. Các thẻ đầu cuối này không gồm N thẻ phía trước và N thẻ
phía ngay sau thông tin cần tách tạo ra khung chữ nhật bề rộng 2*N (Một
thẻ trong (LP)
2
có thể là một thẻ HTML, cũng có thể là một ký hiệu cách
16
dòng, một từ, một số, một chuỗi ký tự, một từ viết hoa, một từ viết thường,
… )
(LP)
2
cũng dựa trên việc quy nạp từ các luật chi tiết đến các luật
tổng quát sao cho các luật tổng quát bao phủ càng nhiều mẫu càng tốt.
Giống như Rapier, (LP)
2
duy trì một vùng luật gồm k luật tốt nhất.
Các luật được tổng quát hóa trong các vòng lặp sau sẽ được thay thế các
luật tồi nhất trong vùng k luật nếu như luật tổng quát hóa này cho phép bao
phủ nhiều mẫu hơn.

đã được triển khai thử nghiệm trong thực tế. Mỗi hệ ứng dụng đều có đặc
trưng riêng cho phép trích rút thông tin khá hiệu quả trên một số lĩnh vực
cụ thể mà hệ áp dụng. Tuy nhiên khi áp dụng cho các thông tin gồm nhiều
dạng khác nhau: dạng cấu trúc, dạng bán cấu trúc và dạng ngôn ngữ tự
nhiên thì các hệ thống này còn chưa hiệu quả. Một số hệ yêu cầu người
dùng phải có hiểu biết khá sâu sắc về trích rút thông tin thì mới có thể khai
thác tốt hệ thống bởi vì họ phải đưa ra những mẫu huấn luyện chính xác
cho hệ thống, khi mà trên thực tế nhiều người dùng không biết, hoặc không
muốn hiểu sâu về hệ thống, họ mong muốn có một giao diện đơn giản, dễ
sử dụng và kết quả thu về nhanh chóng và chính xác.
18
CHƯƠNG 2: CÁC KỸ THUẬT TRÍCH RÚT THÔNG TIN

• Thuật toán trích rút thông tin tự động từ các bảng và danh sách
của nhóm K.Lerman
• Kỹ thuật loại bỏ nhiễu sử dụng cây SST (Site Style Tree) của
nhóm Lan Yi.
• Kỹ thuật trích rút thông tin dựa trên so sánh cây của nhóm Bing
Liu.
• Kết luận
19
2.1 THUẬT TOÁN TRÍCH RÚT THÔNG TIN TỰ ĐỘNG TỪ CÁC
BẢNG VÀ DANH SÁCH CỦA NHÓM K.LERMAN
2.1.1 Một số khái niệm cơ bản
a. Khái niệm phần phân tách (separator)
Phần phân tách (separator) là các ký hiệu dùng để phân cách trang
Web thành các vùng dữ liệu riêng biệt.
Separator được định nghĩa là một hoặc nhiều thẻ HTML liên tục
hoặc bất kỳ một ký tự kết thúc câu nào ngoại trừ tập “,.(-)’%” và dấu cách
“SPACE”. Tập này được chọn theo kinh nghiệm. Đôi khi một dấu gạch

các dữ liệu trả về từ các truy vấn cơ sở dữ liệu. Thuật toán ta
xây dựng cần tìm trang web mẫu để loại bỏ nó trong các trang
web thông tin, điều này sẽ giúp giảm phạm vi tìm kiếm thông
tin của thuật toán. Như vậy sẽ giảm được đáng kể thời gian
tìm kiếm.
- Các vùng thông tin thường chứa trong các bảng nằm trong
cùng nhất, nghĩa là trong nó không còn chứa bảng con nào
khác. (các bảng này thường có số hàng và số cột lớn hơn 2)
- Các vùng thông tin không thể trùng nhau trong các trang web
khác nhau.
21
2.1.3 Trình bày thuật toán
Có thể thấy hầu hết các Website hiện nay đều có cấu trúc dạng bảng
để phân chia trang Web thành các vùng khác nhau như : vùng quảng cáo,
vùng tiêu đề, vùng thông tin,…Nhiệm vụ của chúng ta là cần tách ra vùng
thông tin.
Thuật toán trích rút thông tin dạng bảng như sau:
Hình 2.1:Thuật toán tìm thông tin dạng bảng
Dòng 1: Tải các file về từ những địa chỉ liên kết do người dùng chọn
hoặc nhập vào.
Dòng 2: Tìm và loại bỏ các trang web mẫu.
Dòng 3: Tìm kiếm các bảng trong cùng.
Dòng 4: Trích rút thông tin trong các bảng trả về từ hàm
FindDeepestTable();
22
Procedure FindDataTable(urls)
1. pages ← LoadFile(urls);
2. pages ← TemplateReplace(pages);
3. tables ← FindDeepestTable(pages);
4. ExtractDataTable(tables);

11 if ( n = N AND length(s) >= 3 )
12 add(s, templatePage)
13 end if
14 s = null;
15 end if
16 end for
17 foreach Page in pages
18 Page ← DeleteTemplate(Page, templatePage);
End TemplateReplace
Dòng 1: Trang web mẫu phải có kích thước nhỏ hơn hoặc bằng kích
thước của tất cả các trang đầu vào. Vì vậy ta chọn trang web có kích thước
nhỏ nhất để tìm kiếm trang web mẫu.
Dòng 3: Khai báo một chuỗi ký tự, nếu nó xuất hiện trong tất cả các
trang thì chuỗi đó thuộc trang web mẫu.
Dòng 4: tìm lần lượt từng token trong page.
Dòng 5, 6, 7 và 8: thực hiện nối các token thành chuỗi chừng nào
chúng còn thỏa mãn điều kiện cùng xuất hiện trong tất cả các trang, chuỗi
(dãy) token này chắc chắn được sinh ra từ trang web mẫu.
Dòng 10: đếm số lần xuất hiện của s trong tất cả các trang (N là số
lượng trang Web).
Dòng 11 và 12: Nếu s chứa ít nhất 3 token và s xuất hiện trong tất cả
các trang thì thêm s vào trang web mẫu (điều kiện 3 token dựa trên kết quả
thực nghiệm của nhóm K.Lerman).
Dòng 14: trả s lại null cho lần tìm tiếp theo.
Dòng 17 và 18: Xóa phần trùng lặp (do trang web mẫu sinh ra) trong
tất cả các trang web đầu vào.
24
Thuật toán trích rút dữ liệu trong các bảng ExtractDataTable() sẽ
trích rút các thông tin cần thiết từ các bảng trong cùng. Thuật toán được mô
tả như sau: