BỘ GIÁO DỤC VÀ ĐÀO
TẠO
TẬP ĐOÀN BƯU CHÍNH VIỄN THÔNG
VIỆT NAM
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
NGUYỄN QUANG HUY

NGHIÊN CỨU SEARCH ENGINE VÀ CÁC
THUẬT TOÁN ĐỐI SÁNH MẪU CHO HỆ THỐNG
TÌM KIẾM THÔNG TIN TRÊN MẠNG

CHUYÊN NGÀNH:
TRUYỀN DỮ LIỆU VÀ MẠNG MÁY TÍNH

MÃ SỐ: 60.48.15

TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT

HÀ NỘI - 2010
Luận văn được hoàn thành tại:
Học viện Công nghệ Bưu chính Viễn thông
Tập đoàn Bưu chính Viễn thông Việt Nam
1.2.1 Máy tìm kiếm thông thường 2
1.2.2 Máy siêu tìm kiếm - Meta Search Engine 2
1.3 Mô hình của seach engine 3
1.3.1 Bộ tìm duyệt Crawler 3
1.3.2 Kho dữ liệu Repository 7
1.3.3 Bộ lập chỉ mục Indexer 8
1.3.4 Phân hạng trang (Page Rank) 11
1.4 Search Engine điển hình 12
1.4.1 Sự ra đời 12
1.4.2 Cấu trúc của máy tìm kiếm Google 12
1.4.3 Cấu trúc dữ liệu chính 13
1.4.4 Document Index 14
1.4.5 Danh mục từ Lexicon 14
1.4.6 Các danh sách hit 14
1.4.7 Đánh chỉ mục cho web (indexing the web) 15
1.4.8 Tìm kiếm 15
1.4.9 Hệ thống xếp hạng 16
CHƯƠNG II: CÁC THUẬT TOÁN ĐỐI SÁNH MẪU CHO HỆ THỐNG TÌM KIẾM
THÔNG TIN TRÊN MẠNG 17
2.1 Giới thiệu một số thuật toán đối sánh mẫu điển hình 18
2.1.1 Thuật toán Brute Force 18
2.1.2 Thuật toán Knuth Morris Pratt 19
2.1.3 Thuật toán Boyer-Moore 21
2.2 So sánh các thuật toán 22
CHƯƠNG III: THỬ NGHIỆM XÂY DỰNG MÁY TÌM KIẾM 23
3.1 Giới thiệu 23
3.2 Xây dựng cấu trúc dữ liệu 23
3.2.1 Lớp Catalog 23
3.2.2 Lớp Word 23
3.2.3 Lớp File 24

sử dụng.
Do sự hữu ích của các công cụ tìm kiếm thông tin trên Internet nên
tôi lựa chọn đề tài “Nghiên cứu Search Engine và các thuật toán đối
sánh mẫu cho hệ thống tìm kiếm thông tin trên mạng”, với mục đích là
nghiên cứu cấu trúc, cơ chế hoạt động của một Search Engine, và một số
thuật toán đối sánh mẫu. Tiếp đó là xây dựng một máy tìm kiếm hoạt động
theo cơ chế chung của một Search Engine.

1
CHƯƠNG 1: TỔNG QUAN VỀ SEARCH ENGINE

1.1 Giới thiệu chung
Máy tìm kiếm Search Engine nguyên thuỷ là một phần mềm
nhằm tìm ra các trang trên mạng Internet có nội dung theo yêu cầu
người dùng dựa vào các thông tin mà người sử dụng cung cấp qua từ
khoá tìm kiếm. Máy tìm kiếm sẽ truy tìm trong cơ sở dữ liệu của nó và
trả về danh mục các trang Web có chứa từ khoá mà người sử dụng đưa
vào ban đầu.
Thuật ngữ “Search Engine” được dùng chung để chỉ 2 hệ
thống tìm kiếm: Một do các chương trình máy tính tự động tạo ra
(Crawler-Based Search Engines) và dạng thư mục Internet do con
người quản lý (Human-Powered Directories). Hai hệ thống tìm kiếm
này tìm và lập danh mục website theo 2 cách khác nhau.
Crawler-Based Search Engines: Các máy tìm kiếm loại này
chúng sử dụng các chương trình máy tính, được gọi là Robots,
Spiders, hay Crawlers để lần tìm các trang trên mạng, rồi tự động phân
tích các trang lấy về và đưa vào cơ sở dữ liệu của nó. Khi có một yêu

siêu tìm kiếm sẽ gửi từ khóa đến các Search Engine khác một cách
đồng loạt và nhận về các kết quả tìm được. Nhiệm vụ còn lại của máy
siêu tìm kiếm là phân tích và phân hạng lại các kết quả tìm được. 3
1.3 Mô hình của seach engine
1.3.1 Bộ tìm duyệt Crawler
Bộ tìm duyệt Crawler thu thập các trang trên Internet rồi
chuyển cho bộ đánh chỉ mục Indexer. Crawler xuất phát từ tập các
URL ban đầu S
0
. Đầu tiên nó sắp xếp các phần tử trong tập S
0
vào một
hàng đợi, sau đó lấy dần các URL theo thứ tự và tải về các trang tương
ứng, Crawler trích tất cả các URL có trong các trang vừa tải về rồi lại
đưa vào hàng đợi. Quá trình trên tiếp tục cho đến khi Crawler quyết
định dừng lại. Do số lượng các trang tải về rất lớn và tốc độ thay đổi
nhanh chóng của Web nên xuất hiện những vấn đề cần giải quyết:
- Lựa chọn các trang để tải về.
- Cách cập nhật các trang: Crawler phải xem xét trang nào nên
ghé thăm lại trang nào không.
- Song song hoá quá trình dò tìm trang web: Các Crawlers
song song phải được bố trí một cách hợp lý sao cho một Crawler
không ghé thăm các trang mà một Crawler khác đã thăm.
1.3.1.1 Page selection (lựa chọn các trang)
Bộ tìm duyệt Crawler tải về các trang theo thứ tự trang nào
“quan trọng” sẽ tải về trước. Như vậy ta phải tìm hiểu cách mà
Crawler xác định mức độ quan trọng của các trang.

1
là trang có thứ hạng cao nhất, lần lượt đến
R
2
,… . Gọi R
1
, …,R
K
là các trang hot. Trong số k trang được Crawler
ghé thăm chỉ có m trang (mk) sẽ được sắp thứ hạng cao hơn hoặc
bằng trang R
k

- Crawl & Stop with Threshold: vẫn giả sử rằng bộ Crawler ghé thăm
k trang. Tuy nhiên lúc này đích quan trọng G đã được cho sẵn, và bất
cứ trang nào có độ quan trọng lớn hơn G thì đều được coi là trang
hot. 5
- Độ đo thứ hạng (Ordering Metrics): Một Crawler lưu giữ những
URLs mà nó đã ghé thăm trong quá trình dò tìm vào một hàng đợi.
Sau đó nó lựa chọn một URL trong hàng đợi cho lần ghé thăm tiếp
theo. Ở mỗi lần lựa chọn thì Crawler chọn URL u có giá trị Ordering
cao nhất để ghé thăm. Độ đo thứ hạng (Ordering Metric) được thiết
lập dựa vào một trong các độ đo khác. Ví dụ nếu ta đang thực hiện tìm
những trang có giá trị IB(P) cao, thì ta sẽ lấy giá trị IB
’
(P) làm độ đo
thứ hạng, trong đó P là trang mà được trang u trỏ tới.

được cập nhật. Người ta nói rằng tập B “cập nhật” hơn (“fresher”) tập
A. Thêm nữa nếu tập A được cập nhật một ngày trước đây, tập B được
cập nhật một năm trước đây thì ta nói tập A hiện hành hơn (“more
current”) tập B, dẫn đến khái niệm tuổi “age”:
Dựa trên khái niệm trực giác này chúng ta đưa ra định nghĩa
freshness và age như sau:
+ Freshness: Đặt S={e
1
,…,e
n
} là tập hợp N trang đã được
Crawler tải về. Freshness được định nghĩa như sau:
freshness của trang e
i
tại thời điểm t là




1
0
),( t
i
eF
+ Age: Để biết được “tuổi” của một tập chúng ta định nghĩa
khái niệm “age” như sau:
“age” của trang e
i
tại thời điểm t là



7
1.3.2 Kho dữ liệu Repository
Bộ phận page Repository là một hệ thống lưu trữ có khả năng mở
rộng. Hệ thống này quản lý một tập lớn các trang web. Nó thực hiện
hai chức năng chính: chức năng thứ nhất, cho phép Crawler lưu trữ
các trang web. Thứ hai, nó phải cung cấp API truy cập hiệu quả để bộ
Indexer và bộ Collection Analysis có thể sử dụng để lấy các trang từ
kho dữ liệu.
1.3.2.1 Các yêu cầu đối với repository
- Một Repository quản lý một tập các đối tượng dữ liệu “data
object” lớn.
- Có khả năng mở rộng
- Có cách truy cập kép (dual access mode): Truy nhập ngẫu nhiên
được sử dụng để nhanh chóng nhận về trang web và gán cho mỗi trang
một định danh duy nhất. Truy cập tuần tự được sử dụng để nhận về
tập hợp hoàn chỉnh, hay vài tập hợp con lớn.
- Cố thể cập nhật khối lượng lớn.
- Loại bỏ những trang không còn tồn tại.
- Kho dữ liệu được thiết kế phân tán (Distributed Repository).
1.3.2.2 Nguyên tắc phân tán trang
Các trang có thể được gán cho các nút dựa trên một số nguyên tắc
khác nhau. Như nguyên tắc phân tán đồng bộ (Uniform distribution),
tất cả các nút được xử lý đồng nhất. Một trang có thể được gán cho
một nút bất kỳ trong hệ thống. Các nút sẽ chứa các phần của tập hợp 8
các trang tuỳ theo khả năng lưu trữ của nút. Ngược lại, với cách phân
tán băm (hash distribution) việc định vị các trang vào các nút dựa trên

Link Index: tạo chỉ mục liên kết, các đoạn web đã duyệt được
biểu diễn dưới dạng đồ thị với các đỉnh và các cạnh.
Text Index: Phương pháp đánh chỉ mục dựa theo nội dung (text-
based) là một phương pháp quan trọng để định danh các trang có liên
quan đến yêu cầu tìm kiếm.
Chỉ mục kết hợp: Số lượng và kiểu của các chỉ mục Utility
được quy định bởi bộ Collection Analysis tuỳ thuộc vào chức năng
của bộ máy truy vấn và kiểu thông tin mà modul Ranking sử dụng.
1.3.3.1 Các bước lập chỉ mục
Bước 1: Xác định các mục từ, khái niệm có khả năng đại diện
cho văn bản sẽ được lưu trữ.
Bước 2: Xác định trọng số cho từng mục từ, trọng số này là giá
trị phản ánh tầm quan trọng của mục từ đó trong văn bản
1.3.3.2 Xác định mục từ quan trọng
Ta xác định mục từ của một văn bản dựa vào chính nội dung
của văn bản đó, hoặc tiêu đề hay tóm tắt nội dung của văn bản đó. 10
Thông thường việc lập chỉ mục tự động bắt đầu bằng việc khảo
sát tần số xuất hiện của từng loại từ riêng rẽ trong văn bản.
Đặc trưng xuất hiện của từ vựng có thể được định bởi “thứ hạng
- tần số” (Rank_Frequency)
Các bước để xác định một mục từ quan trọng
+ Cho một tập hợp n tài liệu, thực hiện tính toán tần số xuất
hiện của các mục từ trong tài liệu đó.
Ký hiệu F
ik
(Frequency): là tần số xuất hiện của mục từ k
trong tài liệu i

nguyên gốc bằng cách loại bỏ tiền tố, hậu tố, và các biến thể khác của
từ như từ ở dạng số nhiều, quá khứ,
1.3.3.4 Cấu trúc của chỉ mục đảo
Sau khi phân tích các trang web, và thực hiện tách các từ,
chuẩn hoá các từ về dạng nguyên gốc, loại bỏ các từ stop word. Ta thu
được một danh mục các từ mỗi từ được gắn kèm danh sách các trang
chứa từ đó. Danh mục này gọi là chỉ mục đảo (inverted index)
1.3.4 Phân hạng trang (Page Rank)
Sergey Brin và Lawrence Page đã đưa ra một phương pháp nhằm
giúp cho công việc tính toán hạng trang. Phương pháp này dựa trên ý
tưởng rằng: nếu có liên kết từ trang A đến trang B thì đó là một sự tiến
cử của trang A đối với trang B. Nếu trang B được nhiều trang “quan
trọng” hơn trỏ đến, còn trang C nào đó được ít trang “quan trọng” trỏ
đến thì B cũng có độ quan trọng hơn C. Giả sử ta có một tập các trang
Web với các liên kết giữa chúng, khi đó ta có một đồ thị với các đỉnh
là các trang Web và các cạnh là các liên kết giữa chúng. 12
1.4 Search Engine điển hình
Trong những Search Engine hiện nay Goole là Search Engine tốt
nhất. Phần này sẽ giới thiệu về google.
1.4.1 Sự ra đời
Google được ra đời năm 1997 bởi hai thành viên sáng lập là
Larry Page và Sergey Brin.
1.4.2 Cấu trúc của máy tìm kiếm Google
Tổng quan về cấu trúc của máy tìm kiếm Google

Hình 1.6: Kiến trúc của máy tìm kiếm Google
Bộ tìm duyệt Crawler: Bộ phận Crawler của Google bao gồm

14
Bigfiles là các file ảo mở rộng ra là hệ thống nhiều file và có
thể đánh địa chỉ được bằng 64 bit số nguyên.
Repository (kho chứa dữ liệu) chứa đầy đủ mã HTML của các
trang web đã được nén. Việc lựa chọn kỹ thuật nén phải dựa trên sự
cân đối giữa tốc độ và tỷ lệ nén.
1.4.4 Document Index
Chỉ mục tài liệu (Document Index-DocID) lưu trữ thông tin
về mỗi tài liệu bao gồm thông tin về trạng thái hiện hành của tài liệu
(Document status), con trỏ tới kho Repository, một thông số kiểm lỗi
Checksum, và nhiều thông số khác. Nếu tài liệu đã được duyệt
(crawled) thì DocID chứa thông tin về tài liệu đó (như địa chỉ URL,
tiêu đề title). Nếu tài liệu chưa được duyệt thì DocID chứa con trỏ đến
danh sách URL (URL list).
1.4.5 Danh mục từ Lexicon
Có một số loại danh mục từ khác nhau, trong đó có một kiểu
là danh mục từ có thể được chứa trong bộ nhớ với giá thành hợp lý.
Danh mục từ được chia thành hai phần một danh sách các từ và một
bảng băm của các con trỏ.
1.4.6 Các danh sách hit
Mỗi hit chứa các thông tin của một từ nào đó trong một tài liệu bao
gồm vị trí, font chữ, và viết hoa hay viết thường. Danh sách hit loại bỏ
hầu hết các khoảng trống trong cả chỉ mục xuôi và chỉ mục ngược. 15
Kích thước một danh sách hit được đặt ở đầu của chính các hit.
Để tiết kiệm không gian, độ dài của danh sách hit được kết hợp với
wordID trong chỉ mục xuôi và kết hợp với docID trong chỉ mục
ngược. Điều này giới hạn từ 5 đến 8 bit. Nếu độ dài của hit vượt quá

Để giới hạn thời gian trả về kết quả, mỗi lần các tài liệu phù
hợp với yêu cầu được trả về, bộ tìm kiếm tự động chuyển đến bước 8.
Có nghĩa là có thể các kết quả tìm kiếm tối ưu phụ được trả về.
1.4.9 Hệ thống xếp hạng
Google lưu trữ nhiều thông tin về tài liệu web. Mỗi trang có các
thông tin như các URL trỏ đến trang đó, và các URL mà trang đó trỏ
đến. Việc xây dựng hàm xếp hạng sao cho không có bất kỳ một thông
tin nào có quá nhiều ảnh hưởng.
Hệ thống tìm kiếm Google có khả năng mở rộng. Google sử
dụng một số kỹ thuật như giải thuật phân hạng trang PageRank,
anchor text, và proximity để nâng cao chất lượng tìm kiếm. 17
CHƯƠNG II: CÁC THUẬT TOÁN ĐỐI SÁNH MẪU CHO HỆ
THỐNG TÌM KIẾM THÔNG TIN TRÊN MẠNG
Để một máy tìm kiếm họat động hiệu quả, ngoài kỹ thuật thu
thập thông tin và tạo chỉ mục cho thông tin, chúng ta cũng cần quan
tâm đến việc sử dụng các thuật toán tối ưu để tìm kiếm dữ liệu.
Dữ liệu trong máy tính được lưu trữ dưới rất nhiều dạng khác
nhau, nhưng phổ biến nhất vẫn là dạng chuỗi. Một phép toán cơ bản
trên chuỗi là đối sánh mẫu (pattern matching), bài toán yêu cầu ta tìm
ra một hoặc nhiều vị trí xuất hiện của mẫu trên một văn bản. Trong đó
mẫu có độ dài m và văn bản có độ dài n (m ≤ n), tập các ký tự được
dùng gọi là bảng chữ cái , có số lượng là .
Để tăng tốc độ tìm kiếm dữ liệu thì đối sánh đa mẫu được sử
dụng. Trong phương pháp đối sánh đơn mẫu thì tại một thời điểm chỉ
có một mẫu được đối sánh. Còn trong phương pháp đối sánh đa mẫu,
tại một thời điểm nhiều mẫu được đồng thời đối sánh.
Việc đối sánh mẫu diễn ra với nhiều lần thử trên các đoạn


19
Đánh giá thuật toán: Trường hợp xấu nhất là tìm đến hết chuỗi
T mà không thấy. Khi đó với n-m+1 vị trí tìm kiếm, ta phải so sánh m
ký tự của chuỗi P với các ký tự tương ứng của chuỗi T. Số lần so sánh:
C
max
=m*(n-m+1). Thông thường m rất nhỏ so với n nên ta có thể coi
C
max
=m*n. Như vậy độ phức tạp thuật toán này là O(m*n).
2.1.2 Thuật toán Knuth Morris Pratt
- Tư tưởng: Thuật toán Knuth Morris Pratt dựa trên thuật toán Brute
Force với ý tưởng tận dụng lại thông tin của lần thử trước cho lần sau.
- Giải thuật:
P: chuỗi mẫu
T: chuỗi ban đầu
+ Giải thuật tính mảng next:
Procedure InitNext;
Begin
Next[0]:= 0;
i := 1;
j := 0;
while i < m
if P[i] = P[j]
{đã so khớp j + 1 ky tự}
Next[i]:= j + 1
i := i + 1
j := j + 1
else if j > 0 then