Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

1


LỜI CẢM ƠN


Em xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy giáo tiến sĩ Hà
Quang Thụy và thầy Nguyễn Trí Thành, khoa Công nghệ, ĐHQG Hà nội đã hướng
dẫn và động viên em rất nhiều trong quá trình làm luận văn.
Em xin cảm ơn các Thầy Cô trong khoa Công nghệ, Đại học Quốc Gia Hà
Nội, và nhóm Xemina "Máy tìm kiếm VietSeek" thuộc bộ môn Các Hệ thống Thông tin,
khoa Công nghệ, những người đã giúp đỡ cho em trong suốt quá trình học tập và
nghiên cứu.
Cuối cùng, em xin bày t
ỏ lòng biết ơn tới gia đình và các bạn bè đã giúp đỡ,
động viên em rất nhiều trong suốt quá trình học tập.



Hà Nội ngày 28/05/2003
Sinh viên





Đặng Thanh Hải
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek

Khóa luận tốt nghiệp đại học Đặng Thanh Hải

2


TÓM TẮT NỘI DUNG


Do kích thước khổng lồ của dữ liệu Web, việc xây dựng cũng như tích hợp các
yếu tố khai phá dữ liệu Web vào công cụ tìm kiếm trên mạng Internet đang thu hút
được sự quan tâm rất lớn của rất nhiều nhà nghiên cứu. Khóa luận đề cập tới vấn đề
cải tiến chất lượng và tốc độ của máy tìm kiếm bằng việc nghiên cứu bài toán phân lớp
trong máy tìm kiếm.
Nội dung chính của khóa lu
ận trình bày cấu trúc cũng như mô hình hoạt động
của modul đánh chỉ mục trong máy tìm kiếm VietSeek, các kỹ thuật cơ bản và các
thuật toán thông dụng liên quan đến quá trình khai phá dữ liệu Web trong máy tìm
kiếm, mà cụ thể là bài toán phân lớp trang văn bản Web. Đặc biệt khóa luận tập trung
vào giải pháp phân lớp theo phương pháp Bayes thứ nhất. Xuất phát từ công thức (3.8)
[1], khóa luận đề xuất các công thức (3.15), (3.16) và chứng minh tính đúng đắn của
chúng, với giả
thiết về tính độc lập của các biến cố. Đi kèm với giải pháp phân lớp
Bayes là các đề xuất nhằm giải quyết vấn đề tính ngưỡng cho các lớp.
Khóa luận đã tích hợp thành công các đề xuất này vào máy tìm kiếm VietSeek
và thu được kết quả rất khả quan.
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

3
PHẦN MỞ ĐẦU


Ngày nay sự phát triển vượt bậc của công nghệ thông tin, đặc biệt là sự ra đời
và phát triển như vũ bão của mạng Internet đã tạo ra một cuộc cách mạng trong mọi
lĩnh vực đời sống xã hội. Có thể nói rằng Internet là một thế giới ảo với vô vàn các
thông tin về mọi mặt của đời sống kinh tế, chính trị, xã hội được trình bày dưới dạng
văn bản, hình ảnh, âm thanh,
Internet luôn biến đổi không ngừng cả về kích thước lẫn nội dung. Đến nay
không có một ai biết được chính xác kích thước của Internet là bao nhiêu, có bao
nhiêu Website và bao nhiêu trang Web. Bên cạnh đó, thông tin trong chính các trang
Web cũng được cập nhật liên tục. Theo kết quả nghiên cứu , hơn 500.000 trang Web
trong hơn 4 tháng thì 23% các trang thay đổi hàng ngày, và khoảng hơn 10 ngày thì
50% các trang trong tên miền đó biến mất, nghĩa là địa chỉ URL của nó không còn tồn
tại nữa [2].
Một điều thực tế là kh
ối lượng dữ liệu tăng lên gấp nhiều lần, nhưng tỷ lệ các
thông tin có ích so với khối lượng dữ liệu đó lại giảm đi rất nhiều. Theo thống kê, 99%
của thông tin Web là vô ích với 99% người dùng Web [2]. Rõ ràng với một khối lượng
khổng lồ dữ liệu được lưu trữ trên Internet thì vấn đề tìm kiếm thông tin có ích đang
trở thành một vấn đề nghiên cứu có tính thời sự cao. Ngườ
i dùng không thể tự tìm
kiếm địa chỉ trang Web chứa thông tin mà mình cần, do vậy đòi hỏi cần phải có một
trình tiện ích quản lý nội dung của các trang Web và cho phép tìm thấy các địa chỉ
trang Web có nội dung giống với yêu cầu của người tìm kiếm. Hiện nay, trên thế giới
có một số máy tìm kiếm thông dụng như Yahoo, Google, Alvista, đã được xây dựng
và triển khai nhằm đáp ứng nhu cầu tìm kiếm thông tin của người dùng.
Mặc dù
đã đáp ứng ứng được phần lớn nhu cầu tìm kiếm thông tin của người
dùng, tuy nhiên hầu hết các máy hiện nay mới chỉ hỗ trợ việc tìm kiếm theo từ khóa,
mà chưa xét đến vấn đề ngữ nghĩa của các từ cần tìm kiếm. Với việc tìm kiếm bằng
cách đối sánh các từ khóa, kết quả tìm kiếm có thể không bao gồm tất cả các tài liệu

như ý muốn của ngườ
i dùng (do vấn đề từ đồng nghĩa). Thậm chí các tài liệu tìm thấy
có thể không liên quan đến yêu cầu của người dùng (do vấn đề từ đa nghĩa).
Mặc khác các máy tìm kiếm thông dụng hiện nay đều chưa có chức năng lưu
trữ và phân tích tiểu sử của người dùng, để từ đó có khả năng hỗ trợ tốt hơn với từng
lớp người dùng. Cụ thể, gi
ả sử chúng ta có các trang Web về các vấn đề Tin học, Thể
thao, Kinh tể-Xã hội và Xây dựng Căn cứ vào nội dung của các tài liệu mà khách
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

4
hàng xem hoặc tải về, sau khi phân lớp chúng ta sẽ biết khách hàng hay tập trung vào
nội dung gì, từ đó chúng ta sẽ bổ sung thêm nhiều các tài liệu về các nội dung mà
khách hàng quan tâm.
Từ những nhu cầu thực tế trên, phân lớp và tìm kiếm trang Web vẫn là bài
toán hay, có tính thời sự cao, cần được phát triển và nghiên cứu hiện nay.
Đề tài khóa luận tốt nghiệp ‘Thuật toán phân lớp văn bản Web và thực
nghiệm trong máy tìm kiếm VietSeek (Vinahoo)’ cũng không nằm ngoài mục đ
ích
trên.
Ngoài phần mở đầu và phần kết luận, nội dung của khóa luận được tổ chức
thành 4 chương với nội dung chính như sau:
Chương 1, với tên gọi Máy tìm kiếm VietSeek, nhằm mục đích giới thiệu một
cách chi tiết cấu trúc cũng như cơ chế hoạt động của các máy tìm kiếm VietSeek.
Ngoài ra, phần đầu của chương còn giới thiệu tổng quát về cấu trúc chung củ
a các máy
tìm kiếm đang được sử dụng rộng rãi hiện nay.
Chương 2 có tên gọi là Khai phá dữ liệu Web trong máy tìm kiếm. Nội dung
chính của chương trình bày các kỹ thuật cơ bản liên quan dến bài toán khai phá dữ liệu

Web trong máy tìm kiếm.
Chương 3, tích hợp giải pháp phân lớp trang văn bản vào máy tìm kiếm
VietSeek, giới thiệu các thuật toán điển hình được áp dụng để giải quyết bài toán phân
lớp văn bản. Trong đ
ó đặc biệt tập trung vào giải pháp phân lớp theo phương pháp
Bayes thứ nhất. Các công thức đề xuất (3.15) và (3.16), cùng với quá trình chứng minh
tính đúng đắn của chúng được trình bày một cách chi tiết trong chương này. Đi kèm
với giải pháp phân lớp Bayes là các đề xuất nhằm giải quyết vấn đề tính ngưỡng cho
các lớp. Phần cuối của chương giới thiệu quá trình tích hợp giải pháp phân lớp trang
văn bản vào máy tìm kiếm VietSeek.
Chương 4 vớ
i tựa đề Kết qủa thực nghiệm và đánh giá sẽ giới thiệu các kết
quả thực nghiệm thu được khi tiến hành tích hợp giải pháp phân lớp văn bản Web vào
máy tìm kiếm VietSeek. Sau đó đưa ra các đánh giá về các công thức đề xuất dựa trên
kết quả thực nghiệm.


Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

5
Chương 1. MÁY TÌM KIẾM VIETSEEK

1.1. Giới thiệu máy tìm kiếm VietSeek
Hiện nay, trên thế giới có một số máy tìm kiếm thông dụng như Yahoo,
Google, Alvista, đã được xây dựng và triển khai nhằm đáp ứng nhu cầu tìm kiếm
thông tin ngày càng lớn của người dùng.
Máy tìm kiếm là một hệ thống được xây dựng có khả năng tiếp nhận các yêu
cầu tìm kiếm từ phía người dùng (thường là một tập các từ khoá), phân tích nội dung
câu truy vấn và tiến hành tìm kiếm trong cơ sở d

ữ liệu đã được xây dựng sẵn từ trước.
Kết quả trả về cho người sử dụng bởi máy tìm kiếm là tập hợp các trang Web liên
quan hoặc có chứa các từ khóa xuất hiện trong câu truy vấn.
Đối với các máy tìm kiếm, vấn đề biểu diễn dữ liệu là rất quan trọng. Biểu
diễn các trang Web như thế nào để vừa có khả năng lưu trữ được một số l
ượng khổng
lồ các trang Web, vừa cho phép máy tìm kiếm thực hiện việc tìm kiếm nhanh chóng
và chính xác.
Cấu trúc điển hình của một máy tìm kiếm được mô tả như trong hình (1.0 )
Trong thực tế thì mỗi máy tìm kiếm lại có các sửa đổi riêng theo cách riêng, tuy nhiên
về cơ bản vẫn dựa trên các bộ phận được mô tả trong hình (1.0 )


Kho trang web
Bé t×m
duyÖt


Hình 1.0. Mô hình cấu trúc hoạt động của máy tìm kiếm
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

6
Bộ dò tìm trang Web (Crawler): Hầu hết các máy tìm kiếm hoạt động dựa
vào các bộ dò tìm trang Web, là các chương trình có kích thước nhỏ đảm nhận chức
năng cung cấp dữ liệu (các trang web) cho máy tìm kiếm hoạt động. Bộ dò tìm trang
Web thực hiện công việc duyệt web. Hoạt động của nó tương tự như hoạt động của
con người khi truy cập web là dựa vào các mối liên kết để đi từ trang web này tới trang
web khác.
Modul đánh chỉ mụ

c (Indexer) thực hiện việc khảo sát tất cả các từ khóa
trong từng trang web có trong kho trang Web, và ghi lại các địa chỉ URL của các trang
web có chứa mỗi từ. Kết quả sinh ra một bảng chỉ mục rất lớn gọi là chỉ mục ngược.
Nhờ có bảng chỉ mục này, máy tìm kiếm cung cấp tất cả các địa chỉ URL của các trang
web khi có yêu cầu: Khi cho một từ khóa bất kỳ thì qua bảng chỉ mục, máy tìm kiếm
s
ẽ nhận được tất cả các địa chỉ URL của các trang web có chứa từ khóa đó.
Bộ phân tích tập (Collection Analysis Module) hoạt động dựa vào thuộc
tính của bộ truy vấn (Query Engine). Ví dụ nếu bộ truy vấn chỉ đòi hỏi việc tìm kiếm
hạn chế trong một số Website đặc biệt, hoặc giới hạn trong một tên miền thì công việc
sẽ nhanh và hiệu quả hơn nếu tồn t
ại một bảng chỉ mục các Website mà trong đó mỗi
tên miền được gắn với một danh sách các trang Web thuộc miền đó. Công việc như thế
được thực hiện bởi bộ phân tích tập.
Bộ truy vấn chịu trách nhiệm nhận các yêu cầu của người sử dụng. Bộ phận
này hoạt động thường xuyên dựa vào bảng chỉ mục và thỉnh thoảng dựa vào kho trang
Web. Do số lượ
ng các trang web là rất lớn, và trong thực tế thì người sử dụng chỉ đưa
vào khoảng một hoặc vài từ khoá, cho nên tập kết quả thường rất lớn. Vì vậy bộ xếp
hạng (Rangking) có chức năng sắp xếp kết quả thành một danh sách các trang web
theo thứ tự giảm dần về độ liên quan (theo máy tìm kiếm) tới vấn đề mà người sử dụng
đang quan tâm, và sau đó hiển thị danh sách kế
t quả tìm được cho người sử dụng.
VietSeek là một trong số ít các máy tìm kiếm tiếng Việt đã được xây dựng và
đưa vào sử dụng hiện nay (như PanVietNam của NetNam, HoaTieu của Vương Quang
Khải). VietSeek được phát triển dựa trên ASPSeek, là một phần mềm mã nguồn mở,
bởi nhóm Vinahoo (ban đầu do Bùi Quang Minh thực hiện ) trong khuôn khổ của đề
tài QG-02-02 và công ty TTVNOnline [7]. Là một máy tìm kiếm trên Internet với tất
cả các đặc tính mong muốn từ phía người dùng, VietSeek được vi
ết bằng ngôn ngữ

C++, sử dụng thư viện STL, và kết hợp giữa hệ quản trị cơ sở dữ liệu MySQL và các
file nhị phân cho mục đích lưu trữ. VietSeek bao gồm ba modul chính: modul đánh chỉ
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

7
mục (indexer), modul tìm kiếm chạy ngầm (search deamon), và modul CGI chạy ở
phía người dùng.
• Modul đánh chỉ mục
Modul này sẽ lần theo các Web site, tải về các trang Web mà nó bắt gặp, phân
tích và lưu trữ nội dung các trang Web đó trong một cấu trúc dữ liệu đặc biệt(một số
dữ liệu được lưu trữ trong cơ sỡ dữ liệu MySQL, số còn lại được lưu trong các file nhị
phân được gọi là “file delta” ở th
ư mục “/usr/local/aspseek/var”). Khi không còn trang
Web nào để đánh chỉ số, modul này sẽ sắp xếp các file delta và trộn nội dung trong các
file delta vào cơ sỡ dữ liệu MySQL để xây dựng chỉ số ngược. Modul đánh chỉ mục hỗ
trợ các giao thức HTTP, HTTPS và có thể phân tích được các tài liệu full text cũng
như các tài liệu HTML. Hầu hết các chức năng của modul index đều được điều khiển
bởi nội dung file cấu hình “vinaseek.conf”.
• Modul tìm kiế
m
Modul tìm kiếm chạy ngầm để lắng nghe và trả lời các câu truy vấn đến từ
modul đầu cuối “s.cgi”. Modul phía người dùng (s.cgi) nhận kết quả tìm kiếm, định
dạng và hiện thị kết quả tìm kiếm dưới dạng trang Web.




Hình 1.1. Giao diện một trang kết quả tìm kiếm của máy tìm kiếm Vietseek
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek

Khóa luận tốt nghiệp đại học Đặng Thanh Hải

8
1.2. Một số tính chất của máy tìm kiếm VietSeek
VietSeek được tối ưu hóa để có thể làm việc với nhiều Website, và có thể tiến
hành tìm kiếm trên hàng triệu trang Web. Người sử dụng có thể yêu cầu VietSeek tìm
kiếm các từ, cụm từ, sử dụng các ký tự đại diện cũng như các phép toán Logic. Dưới
đây là một số tính năng của máy tìm kiếm VietSeek:

 Khả năng đánh chỉ mục và tìm kiếm trên hàng triệ
u trang tài liệu
 Kết quả tìm kiếm trả về rất tốt, được sắp xếp theo độ liên quan đến câu truy vấn
 Khả năng tìm kiếm nâng cao
Người sử dụng có thể yêu cầu máy tìm kiếm VietSeek tìm kiếm không chỉ một
từ mà có thể là một cụm từ. Để tìm kiếm một cụm từ, người dùng chỉ cần thêm dấu mở
ngoặc và đóng ngoặc vào cụm từ
đó. Ví dụ, ‘many years ago’. Nếu người dùng biết
chính xác cụm từ cần tìm, nhưng lại quên một từ trong cụm từ đó thì có thể sử dụng
dấu (*) để thay thế cụm từ đó. Bởi vậy câu truy vấn sẽ là: “many * ago” .
Người dùng có thể sử dụng biểu thức tìm kiếm logic để yêu cầu tìm kiếm.
Biểu thức logic có thể được kết hợp dựa trên các phép toán logic như AND, OR, và
các dấu ngoặc. Ví dụ, (some OR any) AND (days OR months OR years).
Người dùng cũng có thể loại trừ các từ không muốn xuất hiện trong kết quả
tìm kiếm bằng cách đặt dấu “-“ trước các từ đó.Với câu truy vấn dạng này, các trang
Web chứa các từ đó sẽ bị loại bỏ khỏi kết quả tìm kiếm. Ví dụ:
search engine –prorietary
Đặc tính tìm kiếm theo khuôn mẫu cho phép tìm các tài liệu chứa các từ phù
hợp với khuôn mẫu được xác định trướ
c. Ký tự “?” đại diện cho một ký tự bất kỳ, ký
tự “*” đại diện cho một chuỗi các ký tự bất kỳ. Ví dụ, để tìm kiếm tất cả các tài liệu có

chứa các từ bắt đầu bằng ‘provider’ ta đánh:
provider*
VietSeek cho phép người dùng giới hạn việc tìm kiếm trong một vài site cụ
thể. Ví dụ để tìm kiếm tất cả các tài liệu có chứa từ ‘bubble’ trong site
www.mysite.org
người dùng đánh câu truy vấn:
bubble site: www.mysite.org

bubble site: mysite.org
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

9
bubble –site: mysite.org site: www.fotech.edu.vnn.vn
Cuối cùng người sử dụng có thể tiến hành tìm kiếm tất cả các trang Web chứa
các liên kết tới các trang Web đặc biệt khác. Ví dụ:
link: www.aspseek.org


 Hỗ trợ các giao thức HTTP,HTTPS,HTTP proxy, FTP proxy
 Hỗ trợ hai loại tài liệu full text và html
 Sử dụng đa tuyến
Modul đánh chỉ mục tải về các tài liệu từ nhiều Website và modul tìm kiếm có
khả năng xử lý nhiều câu truy vấn đồng thời. Đặc điểm này sẽ giúp chúng ta cải thiện
tốc độ của modul đánh chỉ mục vì trong trường hợp sử dụng chỉ
một luồng, phần lớn
thời gian được dành cho việc chờ dữ liệu từ mạng.

Nhân tố làm chậm tốc độ của modul đánh chỉ mục chính là việc phải tìm các
máy chủ phục vụ tên miền nhiều lần. Để tránh điều này, quá trình tìm kiếm không

đồng bộ ( việc tìm kiếm DNS được thực hiện bởi một số tiến trình riêng biệt được xác
định trước ) và bộ nhớ
đệm chứa các ánh xạ từ tên máy sang địa chỉ IP được triển khai
trong máy tìm kiếm VietSeek

 Hỗ trợ các từ dừng ( stopword )
Từ dừng là các từ mà bản thân nó không có ý nghĩa hoàn chỉnh. Ví dụ :’is,
are,at,this’. Việc tìm kiếm trên các từ dừng là hoàn toàn vô nghĩa, bởi vậy các từ dừng
sẽ bị loại bỏ khỏi câu truy vấn. Các từ dừng cũng bị loại bỏ ra khỏi cơ sở
dữ liệu trong
suốt quá trình đánh chỉ mục, bởi vậy cơ sỡ dữ liệu sẽ nhỏ hơn và nhanh hơn. Không có
tập các từ dừng được xây dựng sẵn trong VietSeek, người sử dụng phải xây dựng tập
hợp các từ dừng tương ứng với từng ngôn ngữ và lưu vào file.

 Hỗ trợ việc đoán nhận mã chữ cái
Một số máy chủ b
ị hỏng hoặc do cấu hình sai sẽ không cho máy khách biết bộ
mã chữ cái của tài liệu mà chúng cung cấp. Nếu người quản trị hệ thống tìm kiếm
VietSeek đang đánh chỉ mục các máy chủ này, hay sử dụng VietSeek để đánh chỉ mục
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

10
các máy chủ FTP (giao thức FTP không cho biết thông tin về bộ mã chữ cái), bộ đoán
nhận mã chữ cái có thể được sử dụng để giải quyết điều này. Bộ đoán nhận sẽ sử dụng
các bảng chứa tần số các từ ( được gọi là ‘langmaps’ ) để tìm ra tập chữ cái đúng.

 Hỗ trợ việc sử dụng “robots” của các máy chủ phục vụ Web
Máy tìm kiế
m VietSeek sẽ tiến hành kiểm tra một file đặc biệt trong thư mục

gốc của mày chủ phục vụ Web có tên là “robots.txt”. Nội dung của file “robots.txt”
thông báo cho máy tìm kiếm VietSeek không được thăm một tập hợp các trang Web
cụ thể trên máy chủ này. File “robots.txt” sử dụng giao thức “Robots Exclusion
Protocol”, giao thức này cho phép người quản trị Website có thể xác định máy tìm
kiếm nào không được thăm phần nào của site. Giao thức “Robots Exclusion
Protocol” được miêu tả như sau:
Ví dụ Ý nghĩa
User-agent: *
Disallow:
Dấu (*) có ý nghĩa “bất cứ máy tìm kiếm nào”
User-agent: *
Disallow: /cgi-bin/
Disallow: /tmp/
Disallow:/private/
Tất cả các máy tìm kiếm có thể thăm tất cả các thư mục ngoại
trừ ba thư mục đề cập ở đây
User-agent: BadBot
Disallow: /
Máy tìm kiếm BadBot không được phép thăm bất cứ thư mục
nào.
User-agent: BadBot
Disallow: /

User-agent:*
Disallow : /private/
Riêng máy tìm kiếm BadBot không được phép thăm bất cứ thư
mục nào còn tất cả các máy tìm kiếm còn lại đều có quyền thăm
tất cả các thư mục ngoại trừ thư mục “private”

 Có thể điều khiển việc sử dụng độ rộng băng thông mạng

Nhà quản trị hệ thống VietSeek có thể điều khiển độ rộng băng thông mạng để
modul đánh chỉ mục sử dụng. Chính xác nhà quản trị máy tìm kiếm VietSeek có thể
giới hạn độ rộng băng thông (số byte trên một giây ) được sử dụng bởi modul đánh chỉ
mụ
c trong một ngày xác định.

 Hỗ trợ chế độ đánh chỉ mục không đồng bộ theo thời gian thực
Một số máy tìm kiếm yêu cầu việc tìm kiếm phải dừng lại trong suốt thời gian
cập nhật cơ sở dữ liệu. VietSeek không yêu cầu điều này bằng cách hỗ trợ chế độ thời
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

11
gian thực cho modul đánh chỉ mục. Trong chế độ thời gian thực chúng ta sử dụng một
cơ sở dữ liệu giống hệt cơ sở dữ liệu ban đầu để lưu trữ nỗi dung đã được đánh chỉ số
ngược của các trang Web. Tính năng này sẽ rất có ích khi tiến hành xây dựng một máy
tìm kiếm chuyên biệt cho các trang Web có nội dung thay đổi liên tục ví dụ như các
trang tin trực tuyến. Chú ý r
ằng số lượng tài liệu trong cơ sở dữ liệu thời gian thực bị
giới hạn vào khoảng 1000 tài liệu. Nếu có càng nhiều tài liệu trong cơ sở dữ liệu thời
gian thực thì tốc độ index vào cơ sở dữ liệu chính sẽ càng bị chậm.

 Sắp xếp kết quả trả về theo độ liên qua hoặc theo ngày tháng
Các máy tìm kiếm thường trả về các kết quả liên quan nh
ất trước tiên. Nhưng
nếu muốn tìm kiếm các trang mới nhất, người dùng có thể yêu cầu VietSeek sắp xếp
kết quả trả về theo thời gian thay đổi gần đây nhất, do đó các trang Web bị thay đổi
gần đây nhất sẽ được trình bày đầu tiên.
 Chắt lọc nội dung và tô sáng các từ trong câu truy vấn khi trình bày kết quả tìm
kiếm

Với VietSeek người dùng có thể tùy biến độ dài nội dung tổng quát cho các tài
li
ệu. Mỗi tài liệu tìm thấy đều được đi kèm với một liên kết tới cơ sở dữ liệu của
VietSeek. VietSeek lưu trữ một bản sao được nén của các tài liệu đã được xử lý, do đó
người dùng có thể xem toàn bộ nội dung của trang Web cả trong trường hợp các trang
Web đó đã bị loại bỏ khỏi Website.

 Khả năng nhóm các kết quả theo site
 Hỗ
trợ các trang Web nhân bản (clone- origin)
 Hỗ trợ tìm kiếm tiếng Việt
Tính năng này được phát triển bởi Bùi Quang Minh, bằng việc cài đặt thêm
một số thuật toán nhận dạng các chuẩn tiếng Việt và chuyển tất cả các chuẩn đó về
cùng chuẩn UNICODE

1.3. Cấu trúc máy tìm kiếm VietSeek
Như đã trình bày ở trên, vấn đề biểu diễn dữ liệu trong máy tìm kiếm là rất
quan trọng. Biểu diễn các trang Web nh
ư thế nào để vừa có khả năng lưu trữ được một
số lượng khổng lồ các trang Web, vừa cho phép máy tìm kiếm thực hiện việc tìm
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

12
kiếm nhanh chóng và chính xác. Đối với máy tìm kiếm VietSeek, dữ liệu được tổ
chức, lưu trữ trong cơ sở dữ liệu MySQL và hệ thống file nhị phân xác định.

1.3.1. Cơ sở dữ liệu sử dụng trong máy tìm kiếm VietSeek
• Bảng wordurl: chứa các thông tin về mỗi từ khóa
Tên trường Miêu tả

word bản thân các từ khóa,không phải từ dừng
word_id Số định danh của từ(khóa chính)
urls Thông tin về các site và các url mà từ khóa này xuất hiện.Trường này sẽ
rỗng nếu như kích thước của nó lớn hơn 1000 byte, trong trường hợp này
thông tin sẽ được lưu trữ trong các file nhị phân.
urlcount Số lượng các url có chứa từ khóa này
totalcount Tổng số lần xuất hiện của từ khóa này trong tất cả các tài liệu mà nó xuất
hiện

Trong đó trường wordurl.urls và wordurl1.urls có cấu trúc dữ liệu như sau:
Địa chỉ tương đối Độ dài Miêu tả
0 4 Địa chỉ tương đối của vùng thông tin URL cho site thứ nhất
4 4 Số định danh của site thứ nhất có chứa từ khóa này
8 4 Địa chỉ tương đối của vùng thông tin URL cho site thứ hai
12 4 Số định danh của site thứ hai có chứa từ khóa này

(N-1)*8 4 Địa chỉ tương đối của vùng thông tin URL cho site thứ N
(N-1)*8+4 4 Số định danh của site thứ N có chứ từ khóa này
(N-1)*8+12 4 Địa chỉ tương đối của cuối vùng thông tin URL cho site thứ N.

VÙNG THÔNG TIN URL

0 4 URLID của site thứ nhất có chứa từ khóa
4 2 Số lần xuất hiện của từ khóa trong URLID này
6 2 Vị trí của lần xuất hiện thứ nhất
8 2 Vị trí của lần xuất hiện thứ hai

6+(N-1)*2 2 Vị trí của lần xuất hiện thứ N
Lặp lại các thông tin như trên cho các URL khác có chứa từ khóa này của site thứ nhất


Lặp lại các thông tin trên cho các URL có chứa từ khóa này của các site tiếp theo

• Bảng urlword
Chứa thông tin về tất cả các URL đã hoặc chưa được đánh chỉ số bởi máy tìm
kiếm VietSeek, thỏa mãn một điều kiện đặc biệt nào đó
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

13
Tên trường Miêu tả
url_id Số định danh của URL
site_id Số định danh của site
deleted =1 nếu máy chủ trả về lỗi 404 và tùy chọn “deleteBad” được thiết lập,
hoặc có thể do file “robots.txt” không cho phép được đánh chỉ số trang
Web này
url Nội dung của chính URL
next_index_time Thời điểm tiếp theo cần index, tính theo giây
status =Trạng thái HTTP trả về bởi máy chủ hoặc
=0 nếu trang Web này chưa được đánh chỉ số
crc chuỗi đại diện MD5 của tài liệu
last_modified tiêu đề chứa thông tin về lần thay đổi nội dung gần đây
nhất(Last_Modified) được trả về từ máy chủ phục vụ Web
etag tiêu đề “Etag” được trả về bởi máy chủ
last_index_time thời điểm tiến hành đánh chỉ số cuối cùng
referre Số định danh của URL tham chiếu đầu tiên đến trang Web này
hops độ sâu của URL trong cây siêu liên kết
redir =URLID mới nếu trang Web này bị chuyển hướng nếu không sẽ bằng 0
origin =URLID của trang Web ban đầu nếu trang Web này là một bản sao
=0 nếu trang Web này không phải là bản sao


• Bảng urlwordNN (với NN là các số 00,01, 15)
Bảng này chứa thông tin về các URL đang được đánh chỉ số. Số NN của bảng
chính là URL_ID mod 16

Tên trường Miêu tả
url_id Số định danh của URL
deleted =1 nếu máy chủ trả về lỗi 404 và tùy chọn “deleteBad” được thiết lập,
hoặc có thể do file “robots.txt” không cho phép được đánh chỉ số trang
Web này
wordcount Số lượng các từ khác nhau trong nội dung đã được đánh chỉ số của URL
totalcount Tổng tất cả các từ trong nội dung đã được đánh chỉ số của URL
content-type Tiêu đề “Content-Type” được trả về bởi máy chủ
charset Bộ chữ cái được sử dụng trong nội dung tài liệu, thông tin này được lấy
từ thẻ META
title 128 ký tự đầu tiên trong tiêu đề của trang Web
txt 255 ký tự đầu tiên,không tính các thẻ HTML, trong nội dung của trang
Web
docsize Kích thước của tài liệu
description 100 ký tự đầu tiên trong phần mô tả trang Web
words Nội dung được nén của các URL
hrefs Danh sách đã sắp xếp của các liên kết (URLID) tìm thấy trong phần đã
được đánh chỉ số của trang Web này
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

14
1.3.2. Hệ thống file nhị phân được sử dụng trong máy tìm kiếm VietSeek

 Hệ thống file tạm, delta
Để nâng cao tốc độ của quá trình xây dựng cơ sở dữ liệu chỉ mục ngược cho

tất cả các từ khóa trong toàn bộ các trang Web đã được phân tích bởi bộ dò tìm, máy
tìm kiếm VietSeek sử dụng hệ thống gồm 100 file nhị phân delta để lưu trữ nội dung
đã được phân tích của các trang Web trong mỗi lần thực thi modul đánh chỉ mục.
Một trăm file delta (d00,,d99) trong thư
mục ‘usr/local/aspseek/var/aspseek12’
được dùng để thu thập các thông tin về các URL mới hoặc bị thay đổi cho các từ khóa.
Sau khi tải một Url về, nội dung của nó sẽ được lưu vào 100 file ‘delta’. Chúng ta xem
nội dung của 100 file ‘delta’ như là nội dung mới cần được trộn với nội dung cũ trong
trường ‘wordurl.urls’. Để xây dựng chỉ số ngược chúng ta sẽ dùng nội dung của 100
file ‘delta’ để cập nhật nội dung trường ‘urls’ c
ủa bảng ‘wordurl’ cho các từ xuất hiện
trong 100 file ‘delta’. File ‘delta’ thứ i sẽ chứa các từ khóa thỏa mãn điều kiện
‘(word_ID mod 100)=i’. Các file delta có cấu trúc như sau:

Địa chỉ tương đối Độ dài Miêu tả
0 4 Site_id
4 8 Url_id
8 2 Số lượng các từ khác nhau trong Url_id này
có giá trị “word_id %100” bằng chỉ số của
file
10 4 word_id
14 2 Số lần xuất hiện của từ khóa này trong nội
dung xác định bởi Url_id
16 2 Vị trí thứ nhất của từ

16+(N-1)*2 2 Vị trí cuối cùng của từ
Lặp lại các thông tin trên cho các từ khóa tiếp theo, bắt đầu bằng Word_ID

Lặp lại các thông tin trên cho các URL khác, bắt đầu bằng Site_ID



 Hệ thống file lưu trữ chỉ mục ngược
Với cơ sở dữ liệu chỉ mục ngược của các từ khóa được lưu trữ trong cơ sở dữ
liệu MySQL, quá trình tìm kiếm sẽ được thực hiện một cách nhanh chóng. Tuy nhiên,
kích thước của cơ sở dữ liệu chỉ mục ngược thường rất lớn và vượt quá khả năng lưu
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

15
trữ của hệ quản trị cơ sở dữ liệu MySQL. Để giải quyết khó khăn này, máy tìm kiếm
VietSeek sử dụng thêm hệ thống file nhị phân để lưu trữ cơ sở dữ liệu chỉ mục ngược.
Với việc sử dụng thêm hệ thống file nhị phân này, máy tìm kiếm VietSeek sẽ có khả
năng lưu trữ cơ sở dữ liệu chỉ mục ngượ
c có kích thước không giới hạn.
Cách thức lưu trữ dữ liệu chỉ số ngược trong máy tìm kiếm VietSeek được
điều khiển bởi giá trị tham số CompactStorage. Tùy thuộc vào giá trị của tham số
CompactStorage, chúng ta có hai cơ chế lưu trữ như sau:
1. Cơ chế lưu trữ thông thường
Cơ chế này được sử dụng khi giá trị tham số CompactStorage bằng 0. Với cơ
chế này, n
ếu kích thước dữ liệu chỉ số ngược (nội dung trường urlword.urls) tương
ứng với một từ khóa (word_id) nào đó lớn hơn 10000 byte, thì nó sẽ được lưu trong
một file nhị phân có tên trùng với ‘word_id’ của từ khóa đó,và được đặt trong thư mục
‘/usr/local/aspseek/var/aspseek12/wNN, với NN=’word_id’ % 100.
2. Cơ chế lưu trữ CompactStorage
Được sử dụng khi giá trị tham số CompactStorage bằng 1. Thay vì lưu tr
ữ nội
dung chỉ số ngược (trường “urlword.urls”) của các từ khóa trong một file nhị phân
riêng biệt, modul đánh chỉ mục sẽ kết hợp nội dung tất cả các file nhị phân có trong
thư mục ‘/usr/local/aspseek/var/aspseek12/wNN’ vào ba file nhị phân đặc biệt có tên

là ‘ind’, ‘urls’ và ‘sites’. Cấu trúc của ban file nhị phân này được mô tả như hình (1.2):
• File ‘ind’: dùng để lưu cấu trúc dữ liệu “WordInd” như sau:
struct{
ULONG m_offset;
ULONG m_siteCount;
ULONG m_urlCount;
ULONG m_totalCount;
}WordInd;
• File ‘sites’: dùng để lưu trữ cấu trúc dữ liệu “SiteInd” như sau:
struct{ ULONG m_siteID;
ULONG m_offset;
}SiteInd;
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

16
• File ‘urls’: dùng để lưu trữ vùng thông tin về Url trong nội dung của trường
‘urlword.urls’ cho tất cả các từ khóa, word_id của tất cả các từ khóa này lập thành
một cấp số cộng với công sai là d=100. File ‘urls’ có cấu trúc như sau: (Giả sử file
nằm trong thư mục “ /wNN”)
Địa chỉ tương đối Độ dài Miêu tả
0 4 Url_id trong Site_id1
4 8 Số lần xuất hiện của từ có “word_id”=NN
8 2 Vị trí lần xuất hiện thứ nhất
10 2 Vị trí lần xuất hiện thứ hai

8+(N-1)*2 2 Vị trí lần xuấ hiện cuối cùng của từ
Lặp lại các thông tin như trên cho các Url_ID trong cùng một Site(Site_id1) có chứa từ
khóa “word_id”=NN


Lặp lại các thông tin trên cho một Site khác(site_id2) có chứa từ khóa “word_id”=NN

Lặp lại vùng thông tin URl trên cho từ khóa có “word_id”=NN+100


• Mối liên hệ giữa ba file nhị phân:
















IND
Site_id Offset Site_id Offset Site_id Offset Site_id Offset

Thông tin về vùng Site của từ có Thông tin về vùng Site của từ có
word_id = NN word_id = NN+100
SITES
Url_id Count 1
st

position n th pos Url_id Count 1
st
pos n th pos Url_id

Thông tin về vùng Url của từ có Thông tin về vùng Url của từ có
word_id = NN word_id = NN+100
URLS
Biểu diễn cho từ có word id = NN Biểu diễn cho từ có word id =NN+100
Offset
SiteCount
UrlCount
TotalCoun
t



Hình 1.2. Mối quan hệ giữa ba file nhị phân trong cơ chế CompactStorage
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

17
 File nhị phân ’ ./dev/zero’
Trong quá trình đánh chỉ số các trang Web, máy tìm kiếm VietSeek thường
xuyên thêm mới các Url vào bảng ‘urlword’ và ‘urlwordNN”, hoặc xóa các Url sẵn có
trong hai bảng đó (chỉ có trong quá trình đánh chỉ mục theo cơ chế ‘CompactStorage’)
Do vậy miền không gian các ‘Url_id’ hiện được sử dụng trong bảng ‘urlword’ sẽ
không liên tục. Thông thường khi thêm mới một Url, máy tìm kiếm VietSeek sử dụng
cơ chế tự động tăng khóa của hệ quả
n trị cơ sở dữ liệu MySQL. Nếu số lượng các
trang Web cần đánh chỉ số là rất lớn (khoảng vài triệu trang) thì việc sử dụng cơ chế tự

động tăng khóa của hệ quản trị cơ sở dữ liệu MySQL sẽ không hợp lý, gây ra sữ lãng
phí về tài nguyên ‘url_id’ dùng để cấp cho các trang Web. Trong nhiều trường hợp, có
thể không chèn được các trang Web mới vào cơ sở dữ liệ
u.
VietSeek giải quyết vấn đề trên bằng cách lưu lại tất cả các ulr_id bị đánh dấu
xóa hoặc bị xóa khỏi bảng urlword(urlwordsNN) trong file nhị phân ‘./dev/zero’. File
‘./dev/zero’ chứa cấu trúc ULONG(4 byte). Mỗi bít trong một ULONG được đánh chỉ
số theo thứ tự tăng dần từ phải qua trái. Chỉ số của tất cả các bít trong file nhị phân
này tăng liên tục từ trái sang phải trên tất cả các ULONG(4 byte). Cấu trúc và ch
ức
năng quản lý tài nguyên urlID của file ’./dev/zero’ theo thứ tự được thể hiện thông qua
lớp CDelMap và CDelMapReuse:

Lớp CDelMap
class CDelMap
{
public:
ULONG*m_chunks[DELMAP_SIZE];///<Chứanộidungfile“./dev/zero”
pthread_mutex_t m_mutex; ///< Mutex để đồng bộ hóa các thao tác
trên m_chunks
int m_fd; ///< Số mô tả file “ /dev/zero”
}
Trong cấu trúc m_chunks[DELMAP_SIZE] được mô tả trong hình (1.3), mỗi
bít được gán một chỉ số theo một qui tắc thống nhất, bít có chỉ số thứ ‘
i’ sẽ đại diện
cho ‘Url_id = i’ theo qui tắc sau: Url_id = i sẽ bị đánh dấu xóa trong bảng ‘urlword’
và bảng urlwordsNN tương ứng nếu giá trị của bít thứ ‘i’ bằng 1.
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải


18


















Lớp CDelMapReuse
Lớp CDelMapReuse được thiết kế để tối ưu việc sử dụng không gian “Url_id”
để cấp phát cho các trang Web mới. Bằng cách lưu lại và cập nhật giá trị Url_id nhỏ
nhất đã bị xóa trong file nhị phân “./dev/zero”, VietSeek sẽ sử dụng Url_id nhỏ nhất
này làm khóa định danh cho các trang Web được chèn mới, thay vì sử dụng khóa tự
sinh ra do hệ quản trị c
ơ sở dữ liệu MySQL.
class CDelMapReuse
{
public:
int m_file; //< chỉ số mô tả file “ /dev/zero”

Hình 1.3. Cấu trúc biến thành viên
D
elMa
p
::m chunks
Bít 31 Bit 0 Bít 63 Bit 32
2
15
ULONG (15=DEL_CHUNK_SHIFT –3 –2)

Bít 2*(1<<DEL_CHUNK_SHIFT)
Bít 2*(1<<DEL_CHUNK_SHIFT)+31

m_chunks[DELMAP_SIZE]




















m_chunks
NULL
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

19
long m_length; //< Kích thước dữ liệu trong file “ /dev/zero”
ULONG* m_map;//<Bộ đệm chứa nội dung của file
ULONG m_urlID; //< Miền [ 0, m_urlID) không có Url_id nào bị
xóa hoặc bị đánh dấu xóa
pthread_mutex_t m_mutex; //<mutex dùng để đồng bộ hóa các thao
tác trên bộ đệm
ULONG Get(); ///<Lấy giá trị Url_id nhỏ nhất đã bị xóa, hoặc bị
đánh dấu xóa
void Put(ULONG urlID); ///<Thiết lập giá trị bít tương ứng với
Url_id bằng 1, cập nhật lại giá trị m_urlID
}
1.3.3. Bộ dò tìm trang Web (Crawler) trong máy tìm kiếm VietSeek
Bộ dò tìm trang Web là mộ
t chượng trình có nhiệm vụ dò tìm và tải về các
trang Web mà nó bắt gặp trong quá trình hoạt động. Ban đầu, bộ dò tìm trang Web sẽ
tải về nội dung của một địa chỉ Url ban đầu (Url hạt nhân), phân tích nội dung Url này
qua đó tìm ra tất cả các siêu liên kết trỏ tới các trang Web khác. Tất cả các siêu liên kết
tìm thấy này sẽ được lưu trữ trong một hàng đợi theo một chiến lược nhất định. Sau
khi phân tích xong nội dung mộ
t Url, bộ dò tìm trang Web sẽ tiến hành lấy địa chỉ Url
đầu tiên trong hàng đợi ra để tiếp tục hoạt động. Quá trình này sẽ được thực hiện cho

tới khi thỏa mãn một điều kiện cụ thể nào đó hoặc hàng đợi rỗng, tức là không có địa
chỉ Url nào để tải về. Như vậy có thể kết luận rằng bộ dò tìm trang Web là một
chương trình duyệt cây Website theo chiều rộng.
Trong máy tìm kiếm VietSeek, b
ộ dò tìm trang Web có các đặc điểm sau:
 Danh sách các Url hạt nhân được lấy từ lệnh ‘Server’ trong quá trình tải file cấu
hình ‘vinahoo.conf’
 Sử dụng hàng đợi (m_queue) có cấu trúc CSitesQueue
 Mỗi urlID trong hàng đợi được gắn với hai trọng số đánh giá: độ sâu của trang
Web trong cây Website và giá trị thời gian đánh chỉ mục tiếp theo
(next_index_time)
Sơ đồ tổng quát quá trình hoạt động của bộ dò tìm trong máy tìm kiếm VietSeek
được
trình như hình (1.4):
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

20








• Hàng đợi m_queue
Hàng đợi m_queue được khởi tạo với tư cách là một biến thành viên của lớp
‘CMySQLDatabaseI’. Nó là một thể hiện của lớp CSiteQueues và có thể được mô tả
bằng hình (1.5):


















m_first m_last
1 100


m_first m_last
1 100


m_first m_last
1 100
UrlLink
Site_id
Site_id

Site id

C
Sit
eU
rl
m_first
m_last
Hàng đợi các Url thuộc Site_id
m_first m_last
m_current m_currentFail
Hình 1.5. Cấu trúc hàng đợi m_queue
Url id
Url id
url hạt nhân
Tải nội dung
file cấu hình
‘
v
inah
oo.co
nf’
Lưu vào hàng
đợi và cơ sở
d
ữ
li
ệu
Lấy thông tin về
tài liệu tiếp theo

c
ần
đ
ánh
c
hỉ m
ục
Tải trang Web về và
tạo chỉ số xuôi và lưu
vào 100 file
t
ạm
deta
d/sách
hàng đợi m_queue
Hình 1.4. Sơ đồ tổng quát quá trình hoạt động của VietSeek Crawler
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

21
• Chiến lược dò tìm trang Web trong máy tìm kiếm VietSeek
Bộ dò tìm trang Web trong máy tìm kiếm VietSeek có hai chiến lược hoạt
động dựa trên nguyên tắc lưu trữ các urlID trong hàng đợi ‘ m_queue’.
1. Chiến lược thứ nhất
Bộ dò tìm tiến hành dò tìm các trang Web theo độ ưu tiên về giá trị thời gian
đánh chỉ mục tiếp theo (next_index_time). Với chiến lược này, các urlID trong hàng
đợi m_queue được sắp xếp theo thứ tự tăng dần của giá trị
next_index_time. Tại một
thời điểm nào đấy, máy tìm kiếm VietSeek sẽ chọn urlID có giá trị next_index_time bé
nhất trong tất cả các urlID, đang cần được đánh chỉ mục, là trang Web tiếp theo sẽ

được đánh chỉ mục. Đặc trưng của chiến lược phần này có thể được mô tả thông qua
sơ đồ thuật toán lấy urlID tiếp theo từ hàng đợi m_queue để tiến hành đ
ánh chỉ mục
trong hình (1.6)
2. Chiến lược thứ hai
Bộ dò tìm tiến hành dò tìm các trang Web trước tiên theo độ ưu tiên về độ sâu
trang Web và sau đó theo độ ưu tiên về giá trị thời gian đánh chỉ mục tiếp theo
(next_index_time). Trong chiến lược này, các urlID trong hàng đợi m_queue được sắp
xếp theo thứ tự tăng dần của giá trị độ sâu trong cây Website. Trong cùng một độ sâu,
các urlID lại được sắp xếp theo thứ tự t
ăng dần của giá trị next_index_time. Tại một
thời điểm nào đấy, máy tìm kiếm VietSeek sẽ chọn urlID có giá trị next_index_time bé
nhất trong tất cả các urlID thuộc về độ sâu thấp nhất, đang cần được đánh chỉ mục, là
trang Web tiếp theo sẽ được đánh chỉ mục. Đặc trưng của chiến lược thứ hai này phần
nào có thể được mô tả thông qua sơ
đồ thuật toán lấy urlID tiếp theo từ hàng đợi
m_queue để tiến hành đánh chỉ mục trong hình 1.7

1.4. Mô hình hoạt động của máy tìm kiếm VietSeek

1.4.1 Modul đánh chỉ mục các trang Web

 Mô hình mức cao(Hình 1.8)
 Mô hình mức thấp (Hình 1.9)



kết quả
DS các sites
nếu thay đổi

Internet
Index
File cấu hình CSDL
lấy 1 URL
2
3
1
4
Hình 1.8.
Mô hình ho
ạt động mứccaocủa modul index
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

22




























Tải file cấu hình

1.Khởi tạo biến “Hrefs”
2.Khởi tạo biến “ServerD”
1.Khởi tạo biến “resolverList”
2. Tạo cơ sở dữ liệu nếu chưa
tồn tại
3. Lưu nội dung “Hrefs” vào
CSDL, hàng đợi
Hàng đợi
rỗng?
Lấy thông tin tài
liệu tiếp theo để
đánh chỉ số
Tìm thông tin
về Server chứa
tài liệu này
Nội dung mới

khác n/d cũ
thông tin
v
ề t
ài li
ệu
1.Xóa nội dung tài
liệu trong file delta
2.Đánh dấu xóa url
DomainName
Resolving
Tải nội
dung mới
của tài liệu
IP
Phân tích
nội dung
mới
Đọc và phân tích
nội dung cũ từ
CSDL
Lưu nội dung mới
vào

C
S
DL
<Một số
điều kiện>
N

1.Kết hợp nội dung
cũ vào nội dung
mới và lưu vào file
delta
Lưu các siêu liên
kết tìm thấy vào file
nhị phân
010101
File nhị
phân
Database
url
Database
Database
nội dung
url_id
Internet
Request
content
siêu liên k
ết
Từ vựng
Y
Y
N
Y
N
1.Xây dựng dữ liệu chỉ
số ngược
2.Tính hạng tất cả Wp

END
Database
Hàn
g
đ
ợ
i
Hình 1.9. Mô hình hoạt động mức thấp của modul index
Hàn
g
đ
ợ
i
B
ộ
đ
ệ
m từ v
ự
n
g

ResoverList
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

23




























BEGIN
Số lượng các Site chưa
được kết nối trong hàng đợi
< numthreads *4
1.Lấy ra tất cả các url trong bảng “urlword” thỏa mãn điều kiện
: m_maxtime < ”next_index_time” <= now(), sắp xếp theo thứ

tự tăng dần của “next_index_time” và lưu một số lượng nhất
định các Url đầu tiên vào hàng đợi CSQLDatabaseI::m_queue
2.Cập nhật giá trị CSQLDatabaseI::m_maxtime
3.numr <= Số lượng các Url được thêm mới vào hàng đợi
CSQLDatabaseI::m_queue
Y
numr > 0
1.Lọc ra các Url thỏa mãn điều kiện “next_index_time”=maxtime
2.Lưu một số lượng nhất định các Url này vào hàng đợi
3.Cập nhật giá trị CSQLDatabaseI::m_maxtime
Y
Lấy và trả về Url_id đầu tiên trong hàng đợi
CSQLDatabaseI::m_queue
END
Hình 1.6. Chiến lược lấy urlID tiếp theothứ nhất để tiến hành đánh chỉ mục
numthreads
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

24










































Hình 1.7. Chiến lược lấy urlID tiếp theothứ hai để tiến hành đánh chỉ mục
BEGIN
(Số lượng các Site chưa được kết nối
trong hàng đợi < numthreads *4)
AND
(
m
_
maxho
p
s < 65536
)
1.maxtime <= giá trị “next_index_time” lớn nhất trong tất cả
các trang Web có cùng độ sâu bằng m_maxhops, xuất hiện
trong hàng đợi
Y
maxtime < now
1.Lọc ra các Url thỏa mãn điều kiện maxtime<“next_index_time”<=now() và
hops=m_maxhops
2.Sắp xếp theo thứ tự tăng dần của “next_index_time”
3.Lưu một số lượng nhất định các Url đầu tiên vào hàng đợi
CSQLDatabaseI::m_queue
4.Cập nhật giá trị CSQLDatabaseI::m_maxtime
5. numr <= số lượng các Url được thêm vào hàng đợi
Y
Lấy và trả về Url_id đầu tiên trong hàng đợi
CSQLDatabaseI:: m_queue
END
1.Lọc ra các Url thỏa mãn điều kiện “next_index_time”=maxtime và
hops = m_maxhops

2.Lưu một số lượng nhất định các Url này vào hàng đợi
3.Cậ
p
nhật
g
iá trị CSQLDatabaseI::m
_q
ueue
numr > 0
Y
m_maxhops <=m_maxhops+1
numthreads
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải

25
Chương 2. KHAI PHÁ DỮ LIỆU WEB TRONG
MÁY TÌM KIẾM


2.1. Quá trình khai phá dữ liệu Web
Hệ thống các Website trên Internet được xem như là một trung tâm dịch vụ
thông tin toàn cầu rộng lớn, phân tán một cách rỗng rãi, về mọi mặt của đời sống xã
hội như tin tức, quảng cáo, thông tin khách hàng, quản lý tài chính, giáo dục, chính
phủ, thương mại điện tử, và nhiều dịch vụ thông tin khác. Ngoài ra, nội dung các trang
Web cũng bao hàm một tập hợp phong phú, luôn biến đổi không ngừng các siêu liên
kết, các truy xuất trang Web và các thông tin sử d
ụng trang Web. Chính những thông
tin này là nguồn tài nguyên phong phú cho quá trình khai phá dữ liệu (data mining).
Tuy nhiên, dựa trên các đặc điểm được trình bày sau đây, chúng ta thấy rằng hệ thống

các Website còn ẩn chứa rất nhiều thách thức cho quá trình khai phá tri thức:

 Hệ thống trang Web dường như quá lớn để phục vụ một cách có hiệu quả quá
trình xây dựng kho dữ liệu (data warehouse), cũng như quá trình khai phá dữ liệu
(data mining)
Các CSDL truyền thống th
ường có kích thước không lớn lắm và được lưu trữ
tập trung ở một nơi. Trong khi đó kích thước Web rất lớn, tới hàng terabytes và thay
đổi liên tục, không những thế còn phân tán trên rất nhiều máy tính khắp nơi trên thế
giới. Một vài nghiên cứu về kích thước của Web đã đưa ra các số liệu như sau: Hiện
nay trên Internet có khoảng hơn một tỷ các trang Web được cung cấp cho người sử
dụng., giả sử kích thướ
c trung bình của mỗi trang là 5-10Kb thì tổng kích thước của nó
ít nhất là khoảng 10 terabyte[2]. Còn tỷ lệ tăng của các trang Web thì thật sự gây ấn
tượng. Hai năm gần đây số các trang Web tăng gấp đôi và còng tiếp tục tăng trong hai
năm tới. Nhiều tổ chức và xã hội đặt hầu hết những thông tin công cộng của họ lên
Web. Như vậy việc xây dựng một kho dữ liệu (datawarehouse) để l
ưu trữ, sao chép
hay tích hợp các dữ liệu trên Web là gần như không thể

 Độ phức tạp của trang Web lớn hơn rất nhiều so với những tài liệu văn bản
truyền thống khác
Các dữ liệu trong các CSDL truyền thống thì thường là loại dữ liệu đồng nhất
(về ngôn ngữ, định dạng,…), còn dữ liệu Web thì hoàn toàn không đồng nhất. Ví dụ về