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

1LỜ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


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

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

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ữ

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ó

đồ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

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

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


• 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


 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ặ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

độ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


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]


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):

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 đá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

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

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

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ứ


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