Nghiên cứu về Search Engine

Chương 1: Các phương pháp thu thập thơng tin
1.1 Sự phát triển của internet và u cầu tìm kiếm thơng tin
Mạng Internet được ra đời từ những năm 1970 với tên ban đầu là
ARPANET, là mạng của bộ quốc phòng Mỹ.Với sự tiện dụng và tính khả thi của
mình mạng ARPANET đã phát triễn mạnh mẽ thu hút sự tham gia của nhiều tổ
chức trên thế giới. Cho tới nay đã có hàng triệu các máy chủ khác nhau tham gia
trong mạng tồn cầu –Internet.

Internet
Server
Workstation
IBM Compatible
Hub
LAN
Server
Workstation
IBM Compatible
Hub
LAN
Server
Workstation
IBM Compatible
Hub
LAN
Server
Workstation
IBM Compatible
Hub
LAN

hình 1: Sự kết nối mạng của các máy tính

THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
Sự thuận tiện của Internet thể hiện ở tiềm năng các dịch vụ sẵn có của nó
như: Telnet, FTP, Web Sự ra đời của Web đánh dấu một bước thay đổi quan
trọng trong sự phát triễn của Internet.Web hay còn gọi là World Wide Web là
một hệ thống các tài liệu liên kết trên các máy khác nhau.Web là hệ thống đa
phương tiện, các tài liệu có thể bao gồm âm thanh, hình ảnh và các phương tiện
truyền thơng khác. Đó là các tài liệu html (Hyper Text Make up Language). Sự
tiện dụng của Web được chứng minh qua thực tế với hàng loạt các cơng ty, tổ
chức tham gia phát triển.
Internet phát triển mạnh mẽ, đi sâu vào mọi lĩnh vực cuộc sống. Sự phát
triển đó làm cho khối lượng thơng tin trên Internet ngày càng trở nên đồ sộ hơn,
con người hầu như có thể nhận được bất cứ thơng tin họ mong muốn. Tuy nhiên
sự phát triển đó cũng làm cho người sử dụng khó khăn hơn trong việc tìm ra vị
trí thơng tin cần thiết cũng như lựa chọn được những thơng tin thích hợp nhất.
Để giải quyết vấn đề trên nhiều cơng ty cung cấp dịch vu Internert đã và đang
phát triển các hệ thống tìm kiếm và đánh giá thơng tin.Các “máy tìm kiếm”-
Search Engine được xây dựng như một cơng cụ để giải quyết các vấn đề đó.
Trong chương này ta nghiên cứu các vấn đề liên quan đến tìm kiếm thơng tin,
đây chính là những cơ sở tốn học cốt yếu để thiết kế lên các Search Engine
phục vụ các u cầu tìm kiếm thơng tin.
1.2 Tìm kiếm thơng tin
1.2.1 Giới thiệu:
Thơng tin là một khái niệm trừu tượng khơng định nghĩa, thơng tin có thể
là âm thanh hình ảnh cũng có thể là sự kiện.Chúng ta phân tích các vấn đề tìm
kiếm thơng tin trên cơ sở dữ liệu dạng text bởi hai ngun nhân:
 Sự hiểu biết về phương pháp này rất hữu dụng và được coi
như là thơng tin nền tảng cho các phát triễn mới hơn
 Sự phát triển hoặc mở rộng phương pháp này là trọng tâm
cho các phương pháp khác
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
Giả sử chúng ta cần tài liệu về một chủ đề, chúng ta biết các từ khóa đặc
trưng cho vấn đề đó, khi đó từ một chuỗi các từ khóa nhập vào u cầu xác định
các tài liệu có chứa chuỗi từ đó. Đây chính là u cầu đặt ra cho các Search
Engine mà chúng ta sẽ nghiên cứu ở chương 2 của luận văn, bây giờ chúng ta sẽ
nghiên cứu những cơ sở khoa học cho việc tìm kiếm đó.
1.2.2 Phương pháp tìm kiếm văn bản cổ điển
Các phương pháp tìm kiếm gắn liền với cách biễu diễn các chỉ mục của
các tài liệu, vì vậy chúng ta sẽ xem xét chúng song song nhau:
a.Qt tồn bộ tài liệu:
Phương pháp trực tiếp nhất để xác định tài liệu có chứa một chuỗi kí tự
cần tìm kiếm cụ thể là tìm kiếm tồn bộ tài liệu. Một thuật tốn đơn giản để thực
hiện điều này:
 Xuất phát từ ký tự đầu tiên trong tài liệu, trích ra một chuỗi
con bắt đầu từ kí tự đó, so sánh chuỗi con này với chuỗi nguồn cần so
sánh
 Nếu có sự khác biệt dịch chuỗi con của tài liệu một kí tự sang
bên phải của tài liệu
 Lặp lại cho tới khi tìm được chuỗi con thỏa mãn hoặc duyệt
hết tài liệu, kết luận chuỗi con khơng có trong tài liệu
Thuật tốn trên đơn giản nhưng rất chậm. Nếu m là chiều dài chuỗi cần
tìm kiếm và n là chiêu dài của văn bản thì số phép so sánh tối đa mà thuật tốn
cần thực hiện là m*(n-m) phép so sánh. Đã có rất nhiều cải tiến cho phương
pháp này: thực hiện tiền sử lý chuỗi cần tìm kiếm nhằm tăng số bước dịch
chuyển sau mỗi lần so sánh, hoặc sử dụng Automate trạng thái so sánh một lúc
nhiều xâu. Các thuật tốn này đều khơng u cầu chi phí khơng gian tuy nhiên
mỗi khi tài liệu cập nhật, thay đổi thì chúng lại phải đánh lại chỉ mục từ đầu vì
vậy, phương pháp qt tồn bộ chỉ thích hợp để tạo chỉ mục các tài liệu văn học
hoặc thiết kế cho các phần cứng chun dụng
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
b.Sử dụng tệp ký hiệu
Phương pháp này sử dụng một file kí hiệu đối với mỗi tài liệu được tạo
chỉ mục. Có nhiều phương pháp tạo file kí hiệu đã được đè xuất. Phương pháp
đơn giản nhất có thể kể đến là Bitstring. Mỗi một tài liệu cần tạo chỉ mục cho
ứng với một chuỗi bít xác định sự xuất hiện của các từ trong tài liệu.Giả sử trong
tài liệu có từ t gồm nhiều kí tự, nếu chúng ta quan tâm đến s kí tự đầu tiên của từ
này thì ứng với mỗi kí tự quan tâm biểu diễn nó bằng một chuỗi bít có độ dài là
s, một cách đơn giản là cho tương ứng mã ASCII của kí tự đó với một chuỗi bit
nhị phân có chiều dài s, như vậy ứng với một từ trong tài liệu ta có thể biểu diễn
bằng s chuỗi bit nhị phân, mỗi chuỗi có độ dài w định trước.Ví dụ quan tâm tới 3
kí tự đầu tiên trong các từ sau ta có. Các ký tự đầu tiên có mã ASCII dạng octal
như bảng sau:
Từ Ký tự thứ nhất Kí tự thứ hai Kí tự thứ ba
Nor
Her
Hunger
Eased
116
150
150
145
157
145
165
141
162
162
156
163
Sử dụng hàm chuyển f(c) =
)8mod(
2
c
chuyển các ký tự trên dưới dạng các
chuỗi nhị phân có chiều dài 8 bit:

Từ Chuyển thành các chuỗi bit nhị phân
Nor
Her
Hunger
01 000 000
00 000 001
00 000 001
10 000 000
00 100 000
00 100 000
00 000
100
00 000
100
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
Eased 00 100 000 00 000 010 00 100
000
00 001
000

Khơng có sự phân biệt các từ giống nhau trong tài liệu, điều này có nghĩa
là: các từ giống nhau trong tài liệu có chung một giá trị bit. Thơng thường trước
khi tạo file kí hiệu các từ trong tài liệu được phân tích loại bỏ các từ vơ nghĩa,
chuẩn hóa các từ biến dạng về từ gốc, khi đó ta có tập các thuật ngữ (term). Mỗi
câu truy vấn được phân tích như một tài liệu, sự so sánh xảy ra trên các chuỗi bít
đã tạo theo quy tắc trên
Để giảm thời gian xử lý tìm kiếm trong các file ký hiệu người ta đề xuất
phương pháp Bitslice. ý tưởng của phương pháp này là tạo file ký hiệu cho tồn
bộ cơ sở dữ liệu text. ( Cơ sở dữ liệu text là cơ sở dữ liệu chứa các tài liệu dạng
text, mỗi bản ghi có thể coi là một danh sách các từ thuộc một tài liệu trong cơ
sở dữ liệu). Giả sử ta có N tài liệu trong một cơ sở dữ liệu, với mỗi từ có xuất
hiện trong các tài liệu ta xây dựng một chuỗi bit có chiều dài là N (các slice),
chuỗi bít thứ i xác định sự có mặt của từ đó trong tài liệu thứ i của cơ sở dữ liệu.
Phương pháp Bitslice trở nên khơng thích hợp đối với cơ sở dữ liệu lớn,
giả sử một cơ sở dữ liệu text có hàng triệu bản ghi, thì chiều dài các chuỗi bit
(slice) trong file ký hiệu là rất lớn. Phương pháp Blocked Signature File được
phát triễn để giải quyết vấn đề trên. Theo phương pháp này mỗi một bit trong
các bitslice thể hiện sự xuất hiện của từ mà nó biễu diễn trong một nhóm các tài
liệu được xác định trước. Vấn đề dặt ra ở đây là: đối với u cầu tìm kiếm các
tài liệu chứa tất cả các từ trong một câu truy vấn (Disconjunctive query) một
khối có thể thỏa mãn u cầu tìm kiếm nhưng khơng có tài liệu nào trong khối
thỏa mãn u cầu tìm kiếm đó. Chúng ta có thể giảm tình trạng này bằng cách
sắp xếp các tài liệu vào nhiều khối khác nhau, cùng một tài liệu có thể thuộc
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
khối 1, khơi 2, Giả sử mỗi từ xuất hiện trong tài liệu cần biểu diễn bởi một
chuỗi bit có chiều dài là w, trong ph c ó K block chứa từ đó, thế thì sẽ có
k
w

side trong tệp kí hiệu biễu diễn từ này. Phưương pháp Block File Signature ơng
pháp đề xuất ở trên chỉ có thể giảm phần nào sai sót (false match) chứ khơng
đảm bảo chắc chắn sai xót sẽ khơng xảy ra. Chúng ta xem xét một mơ hình tốn
học áp dụng cho việc đánh giá mức độ chính xác trong phương pháp tạo file kí
hiệu. Giả sử một văn bản có t thuật ngữ khác nhau, ứng với mỗi thuật ngữ ta
dùng s chuỗi bít để tạo tệp kí hiệu, mỗi chuỗi bít có chiều dài là w, Khi đó ta cần
xác định s*t chuỗi bít cho tệp kí hiệu. Gọi p(w,s,t) là giá trị định khả năng một
tài liệu thỏa mãn u cầu truy vấn khi tìm trong tệp ký hiệu, nhưng khơng phải
là tài liệu thỏa mãn. Dựa vào các tính tốn khoa học ta có
P(w,s,t) =
 
s
ts
w
*
)
1
1(1 

Ví dụ: một tài liệu có 150 thuật ngữ khác nhau, mỗi thuật ngữ được biễu
diễn bởi 8 chuỗi bit, mỗi chuỗi có chiều dài là 5000, sử dụng cơng thức trên ta
có thể tính mức độ sai lệch trong kết quả tìm kiếm là:
100000
1
.
c.Sử dụng file nghịch đảo
Khác với phương pháp sử dụng tệp ký hiệu, phương pháp sử dụng tệp
nghịch đảo ( inverted file ) tạo ra các danh sách các từ khóa có trong cơ sở dữ
liệu, các câu truy vấn được xử lý bằng cách so sánh với danh sách các từ khóa
này rồi tìm ra các tài liệu chứa các từ khóa thỏa mãn câu truy vấn. Một file
nghịch đảo bao gồm hai phần: danh sách các từ khóa được index chứa trong tài
liệu và danh sách trỏ tới các tài liệu chứa các từ khóa đó. Để thu gọn kích thước
file nghịch đảo các tài liệu trong cơ sở dữ liệu được gán một định danh duy nhất
(docID), các liên kết tới tài liệu chỉ đơn giản là lưu các định danh của tài liệu
tương ứng. Q trình tạo ra các tệp nghịch đảo bao gồm 3 bước:
 Document File: Xác định các từ trong tài liệu sẽ được index, đây là
các từ có ý nghĩa, từ khóa, loại bỏ các từ khơng cần thiết, chứa đựng ít thơn tin:
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
các giới từ, các liên từ, các thẻ trong trang hrml khi đó ta được tập các từ vựng
(vocabulary)
 Dictionary: Thống kê tần suất xuất hiện và vị trí của các từ trong
tập từ vựng ở trên, sắp xếp chúng lại theo một trật tự hợp lý có ý nghĩa
 Invertion list: Kết hợp hai bước trên tạo ra các file nghịch đảo chứa
các liên kết tới các tài liệu chứa các từ khóa đã xác định ở trên.
Khác với phương pháp tệp ký hiệu, khơng có sự sai khác khi tìm kiếm
trên các file nghịch đảo (false match) lý do là các từ khóa xuất hiện trong các file
nghịch đảo chính xác như trong tài liệu, liên kết được xác định tường minh nên
khơng có sự nhầm lẫn. Nhiều nghiên cứu về hai phương pháp file nghịch đảo và
file kí hiệu cho thấy cùng với một câu truy vấn phương pháp file nghịch đảo cho
kết quả tìm chính xác, nhanh hơn phương pháp tệp kí hiệu, sử dụng phương
pháp nén thơng tin, kích thước file nghịch đảo cũng nhỏ hơn kích thước tệp ký
hiệu, do đó phương pháp sử dụng file nghịch đảo đang được phát triễn và sử
dụng ở hầu hết các Search Engine hiện nay.
d.Tìm kiếm theo mơ hình vec tơ phân nhóm
Phương pháp tìm kiếm theo mơ hình vectơ dựa trên ý tưởng biễu diễn các
tài liệu dưới dạng các vec tơ, các thành phần của véc tơ là các từ khóa sẽ được
index, giá trị của các thành phần đánh giá độ quan trọng của từ khóa thường là
tần suất xuất hiện của nó trong tài liệu hoặc được tính tốn theo một cơng thức
nào đó. Theo cách thức trên một cơ sở dữ liệu text có n tài liệu, m từ khóa được
biễu diễn bằng một ma trận a có kích thước m*n ( n véc tơ mỗi véc tơ có m
chiều). Giá trị phần tử a
ij
thể hiện độ quan trọng của từ khóa.
Một ví dụ đơn giản: ta có cơ sở dữ liệu các 7 tiêu đề sách:

Tài liệu
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
1:
2:
3:
4:
5:
6:
7:
Infant & Toddler First Aid
Babies & Children’s Room (For your home)
Child Safety at Home
Your Baby’s Health and Safety: From Infant to
Toddler
Baby Proofing Basics
Your Guide to Easy Rust Proofing
Beanie Babies Collector’s Guide

Các từ gạch chân được xác định làm các từ khóa, ta có danh sách các từ
khố:



Từ khố



T1
T2
T3
Bab(y, ies)
Child(ren’s)
Guide
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
T4
T5
T6
T7
T8
T9
Health
Home
Infant
Proofing
Safety
Toddler




Khi đó một ma trận biễu diễn cho cơ sở dữ liệu trên với a
ij
là tần xuất xuất
hiện các từ khóa là:
~
0001001
0001100
0110000
0001001
0000110
0001000
1100000
0000110
1011010






























A
Trong cơ sở dữ liệu trên mỗi từ khóa chỉ xuất hiện một lần, tuy nhiên
trong các cơ sở dữ liệu lớn số lần xuất hiện của một từ khóa có thể rất nhiều lần,
để nhất qn các phương pháp xử lý người ta đưa ma trận trên về một dạng
chuẩn nào đó, ở đây ta dùng dạng chuẩn Euclide để chuẩn hóa các véc tơ ứng
với các tài liệu, ma trận hợp thành các véc tơ đó là các ma trận được chuẩn
hóa.Giả sử véc tơ x=(x
1
,x
2,
,x
n
) khi đó chuẩn Euclide của véc tơ này được xác
định như sau:
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN



m
i
i
T
xxxx
1
2
2

áp dụng chuẩn trên ta có ma trân được chuẩn hóa tương ứng với ma trận
đang xét là:































0004472.0007071.0
0004472.05774.000
07071.07071.00000
0004472.0007071.0
00005774.05774.00
0004472.0000
7071.07071.000000
00005774.05774.00
7071.007071.04472.005774.00
A

Cũng như hai phương pháp trước (tệp nghịch đảo và tệp kí hiệu) các tài
liệu sử dụng mơ hình véc tơ cũng có bước tiền xử lý các tài liệu để xác định các
từ khóa, nò bao gồm các cơng việc: loại bỏ các từ khơng cần thiết, quy chuẩn
các từ đồng âm, các từ biến dạng của từ gốc việc xử lý hiệu quả vấn đề này cần
có những thuật tốn cụ thể khơng nằm trong vấn đề nghiên cứu của luận văn.
Các câu truy vấn tìm kiếm cũng được biễu diễn dưới dạng một véc tơ việc
tìm ra các tài liệu thỏa mãn u cầu chỉ đơn giản là so sánh độ gần nhau giữa các
vec tơ trong ma trận biễu diễn của cơ sở dữ liệu. Giả sử biểu diễn được một câu
truy vấn dưới dạng q=(q
1
, q
2
, q
3
, , q
n
)
Độ gần của câu truy vấn q, với tài liệu thứ j trongcơ sở dữ liệu được tính
theo cơng thức





m
i
i
m
i
ij
m
i
iij
T
j
j
qa
qa
qaj
qa
1
2
1
2
1
22
cos


THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN

Xem chi tiết: Nghiên cứu về Search Engine