MỤC LỤC
LỜI MỞ ĐẦU................................................................................................4
PHẦN I: MỞ ĐẦU........................................................................................6
1. Tính cấp thiết của luận văn.....................................................................6
2. Mục đích, nhiệm vụ của luận văn...........................................................7
2.1 Mục đích của luận văn............................................................................7
2.2 Nhiệm vụ của luận văn............................................................................7
3. Phạm vi nghiên cứu..................................................................................7
4. Nội dung luận văn....................................................................................8
PHẦN II: NỘI DUNG..................................................................................9
CHƯƠNG I: GIỚI THIỆU BỘ CÔNG CỤ TÌM KIẾM THÔNG TIN.......9
1.1 Khái niệm bộ công cụ tìm kiếm thông tin............................................9
1.2 Bộ công cụ tìm kiếm thông tin trên mạng..........................................13
1.3 Mô hình bộ công cụ tìm kiếm thông tin truyền thống......................18
1.4 cấu trúc dữ liệu trong tổ chức và tìm kiếm thông tin.......................20
1.4.1 Bảng băm.............................................................................................20
1.4.1.1 Khái niệm hàm băm........................................................................20
1.4.1.2 Khái niệm bảng băm......................................................................22
1.4.1.3 Giải quyết xung đột........................................................................23
1.4.2 Cây cân bằng nhiều đường B - Tree..................................................27
1.4.2.1 Định nghĩa cây B - Trees................................................................27
1.4.2.2 Cây B* - Tree.................................................................................29
1.4.2.3 Cây B
+
- Tree..................................................................................29
1
1.4.2.4 Cây B
Link
– Trees.............................................................................31
1.4.2.5 Lựa chọn phương pháp dữ liệu tần số.............................................32
CHƯƠNG II: CÁC CÔNG CỤ TÌM KIẾM CƠ BẢN.............33

PHẦN III: KẾT LUẬN...............................................................................90
1. Kết quả đạt được trong luận văn.......................................................90
2. Hướng phát triển trong tương lai......................................................91
TÀI LIỆU THAM KHẢO..........................................................................94
PHỤ LỤC.....................................................................................................98
3
DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ
TIẾNG ANH
Thuật ngữ tiếng anh Tiếng Việt Viết tắt
CONTENT INDEX Chỉ mục nội dung
CRAWLER Bộ thu hồi
COLLECTION ANALYSIS MODULE Mô đun phân tích tập
hợp
MATCHING PROCESS Quá trình đối sánh
FULL - TEXT INDEX Chỉ mục toàn văn bản
HASHING SCHEME Sơ đồ băm
REVLEVANCE Mức độ liên quan
INDEX Bảng chỉ mục
INVERTED FILE Tập tin đảo
INVERTED INDEX Chỉ mục ngược
INFORMATION RETRIEVAL Hệ thống tìm kiếm IR
PAGERANK
STRUCTURE INDEX Cấu trúc bảng chỉ mục
S EARCH ENGINE Hệ tìm kiếm
SIGNATURE FILE
STANDFORD WEBBSE
QUERY FORMULATION PROCESS Biểu diễn truy vấn
QUERY ENGINE Công cụ truy vấn
Uniform Resource Location
Địa chỉ một trạm trên

của tổ chức là những thuộc tính căn bản của mọi hệ thống kinh tế - xã hội.
Hệ thống càng phát triển tức là càng có nhiều yếu tố tạo thành mối quan hệ
giữa chúng càng phức tạp do đó lượng thông tin càng phong phú. Chính vì
vậy mà ngày nay cùng với sự phát triển của Công nghệ Thông tin cũng như
sự phát triển nhanh chóng của mạng máy tính toàn cầu và sự bùng nổ thông
tin, các kho dữ liệu số đã được hình thành ở khắp mọi nơi và không ngừng
gia tăng về dung lượng, nhưng thông tin thì vẫn luôn là cần thiết thậm chí
thiếu với họ. Các kho dữ liệu này ẩn chứa một hàm lượng thông tin vô cùng
lớn. Nhưng vấn đề đặt ra là làm thế nào để “khai thác, tìm kiếm” tổng hợp
kho thông tin đó để cho nó trở nên hiệu quả và có giá trị đối với người dùng.
Những thông tin này được lưu trữ và biểu diễn ở rất nhiều dạng khác nhau
như văn bản, âm thanh, hình ảnh vv... có thể nói : “khối lượng dữ liệu khổng
lồ mà người sử dụng có thể truy xuất nếu không được tổ chức lưu trữ tốt và
kèm theo một phương thức xử lý hiệu quả để có thể khai thác và tìm kiếm
lượng thông tin trong đó thì chúng cũng chỉ là những thông tin chết chứ
không mang lại chút lợi ích nào cả ”.
Để giải quyết vấn đề này, người ta đã xây dựng các hệ thống tìm kiếm
thông tin. Nó giúp con người tìm kiếm và chọn lọc ra những tài liệu có chứa
thông tin cần thiết. Do người sử dụng luôn yêu cầu kết quả tìm kiếm chính
6
xác, đầy đủ và với các vận tốc tìm kiếm nhanh nên các hệ thống tìm kiếm
thông tin luôn được nghiên cứu và phát triển cùng với các kỹ thuật, thuật
toán tìm kiếm hiệu quả và tối ưu nhất.
Luận văn “Bộ công cụ tìm kiếm thông tin trên mạng ” không đặt mục
tiêu chính là xây dựng một hệ thống hoàn chỉnh, mà trình bày phần lý thuyết
để đảm bảo cho một hệ thống tìm kiếm. Với hy vọng là tìm hiểu các chiến
thuật, thuật toán để tổ chức một bộ công cụ tìm kiếm tối ưu, đưa ra đáp ứng
người dùng với thời gian ngắn nhất và các kết quả có độ liên quan tới truy
vấn cao nhất và có nhiều lựa chọn để người dùng có thể can thiệp vào hệ
thống.

liệu phù hợp nhất trong tập tài liệu nguồn ngày càng trở nên khó khăn đối
với con người và máy tính.
8
2. Mục đích , nhiệm vụ của luận văn
2.1. Mục đích của luận văn:
Luận văn tập chung nghiên cứu các mô hình tìm kiếm thông tin truyền
thống và mô hình tìm kiếm thông tin trên mạng bên cạnh đó cũng tập chung
nghiên cứu và phân tích các đặc tính cấu trúc chung của một mô hình tìm
kiếm thông tin dựa trên cơ sở lý thuyết.
2.2. Nhiệm vụ của luận văn:
Luận văn phải thực hiện được các nhiệm vụ sau:
2.2.1.Nghiên cứu về bộ công cụ tìm kiếm thông tin .
2.2.2.Nghiên cứu các mô hình bộ công cụ tìm kiếm thông tin truyền
thống.
2.2.3.Nghiên cứu các mô hình bộ công cụ tìm kiếm thông tin trên
mạng.
3. Phạm vi nghiên cứu
Kết quả đề tài là bước đầu nghiên cứu, tổng hợp các vấn đề lý thuyết
tron bài toán “Bộ công cụ tìm kiếm thông tin trên mạng”. Dựa vào mô hình
lý thuyết để tiến hành cài đặt một số chức năng hỗ trợ cho việc thiết kế bộ
công cụ tìm kiếm trên mạng.
4. Nội dung luận văn :
Luận văn gồm 3 chương
CHƯƠNG 1: GIỚI THIỆU BỘ CÔNG CỤ TÌM KIẾM THÔNG TIN
Gồm các nội dung sau :
1. Kh¸i niÖm bé c«ng cô t×m kiÕm th«ng tin
9
3. M« h×nh bé c«ng cô t×m kiÕm th«ng tin truyÒn thèng
4. M« h×nh bé c«ng cô t×m kiÕm th«ng tin trªn m¹ng
5. CÊu tróc d÷ liÖu trong tæ chøc lu tr÷ vµ t×m kiÕm th«ng tin

liệu có chứa thông tin cần thiết. Một số tài liệu “tìm kiếm được” thỏa mãn
yêu cầu của người sử dụng gọi là các tài liệu phù hợp hay tài liệu liên quan
(relevanl document). Một hệ thống tìm kiếm hoàn hảo sẽ chỉ tìm và đưa ra
các tài liệu liên quan mà không đưa ra các tài liệu không liên quan. Tuy
nhiên các hệ thống này không tồn tại bởi các thể hiện tìm kiếm là không đầy
đủ mà mức độ liên quan phụ thuộc vào quan điểm chủ quan của từng người.
11
Hai ngi s dng cú th a ra cựng mt truy vn vi mt h thng tỡm
kim thụng tin v sau ú s cú nhng ỏnh giỏ khỏc nhau v mc liờn
quan trờn cỏc ti liu ó tỡm c.
Tỡm kim trờn cỏc thụng tin núi chung gii quyt cỏc vn nh biu
din, lu tr, t chc v truy cp n cỏc mc thụng tin. Vic t chc v
biu din thụng tin giỳp ngi s dng d dng truy cp thụng tin m mỡnh
quan tõm. Nhng mụ t c im thụng tin yờu cu ca ngi s dng
khụng phi d dng. Vỡ th, h thng tỡm kim thụng tin bao gm ba quỏ
trỡnh c bn sau: Biu din ni dung cỏc ti liu, biu din yờu cu ca
ngi s dng v so sỏnh hai biu din ny.
Hình 1: Quy trình tìm kiếm thông tin
12
Bài toán thông tin
Văn bản
Biểu diễn
Truy vấn Văn bản đã chỉ số hoá
So sánh
Biểu diễn
Các văn bản được
tìm kiếm
Phản hồi
Quá trình biểu diễn tài liệu được gọi là quá trình chỉ số hóa
(indexing). Quá trình này có thể lưu trữ thực sự các tài liệu trong hệ thống,

bị lỗi trong số hàng nghìn đối tượng được tìm kiếm là không thực hiện được.
Tuy nhiên, với một hệ thống khôi phục thông tin, các đối tượng tìm kiếm có
thể không chính xác và cho phép các lỗi nhỏ. Nguyên nhân chính của sự
khác nhau này là việc khôi phục thông tin luôn xử lý với văn bản ngôn ngữ
tự nhiên thường không có cấu trúc và không thể rõ nghĩa. Nói cách khác, hệ
thống khôi phục dữ liệu (như một cơ sở dữ liệu quan hệ ) xử lý dữ liệu có
cấu trúc và ngữ nghĩa đã được xác định. Việc khôi phục dữ liệu không giải
quyết vấn đề trong khôi phục thông tin về một chủ đề hoặc một lĩnh vực cụ
thể. Để đạt được hiệu quả đáp ứng thông tin yêu cầu của người dùng, hệ
thống IR phải bằng cách nào “hiểu” được các nội dung của thông tin (các
văn bản) trong một tập hợp và sắp xếp chúng theo mức độ phù hợp với truy
vấn. Sự “hiểu biết” về nội dung văn bản này bao gồm sự trích chọn cú pháp
và ngữ nghĩa thông tin từ văn bản và sử dụng thông tin này để so khớp với
thông tin người dùng. Cái khó là không chỉ hiểu để trích chọn thông tin này
như thế nào mà còn là hiểu cách sử dụng nó để quyết định mối liên quan như
thế nào. Do vậy khái niệm mức độ liên quan (revlevance) cũng là một phần
quan trọng trong tìm kiếm tất cả các tài liệu liên quan với một truy vấn
người dùng mặc dù việc tìm kiếm có thể đưa ra một tài liệu không thích hợp.
14
Vậy, khôi phục thông tin là một quá trình nhận dạng, xác định và chỉ
ra các tài liệu liên quan dựa trên mô tả yêu cầu thông tin của người sử dụng.
Việc tìm kiếm các tài liệu dựa trên nội dung thực sự của văn bản mà không
phụ thuộc vào các từ khóa gắn với văn bản đó. Các công cụ văn bản nổi
tiếng hiện nay như Google, Altaavista, Yohoo,... là những hệ tìm kiếm đưa
ra danh sách các văn bản theo độ quan trọng của câu hỏi đưa vào, Để xây
dựng một hệ tìm kiếm văn bản có hiệu quả cao, trước hết các văn bản và
truy vấn ở dạng ngôn ngữ tự nhiên phải được tiền xử lý và chuẩn hóa.
Một mô hình của quá trình thiết lập truy vấn được chuẩn hóa thành
hai vấn đề: Đầu tiên là chọn các ternm truy vấn và thứ hai là lựa chọn các
phép toán truy vấn. Dưới đây em đưa ra hai mô hình chi tiết cho bộ công cụ

đều đồng ý rằng các trang Web có hiệu lực hiện nay, với kích thước trung
bình của mỗi trang khoảng 5Kb tới 10Kb thì ta cũng có ít nhất là 10Tb dữ
liệu, các tỷ lệ của các trang Web còn kinh khủng hơn, kích thước của trang
Web sẽ tăng lên gấp đôi trong vòng hai năm và tỷ lệ đó sẽ tiếp tục tăng
trong hai năm tiếp theo.
Xong bên cạnh các trang vừa được tạo ra thì các trang đang tồn tại
cũng luôn luôn được cập nhật, chẳng hạn, theo dõi hơn nửa triệu trang trong
các miền như “.com” thì phải có đến 40% các trang được thay đổi hàng
ngày. Cộng với kích thước rất lớn và tỷ lệ thay đổi liên tục của các trang
16
M« dule
Ph©n
tÝch tËp
hîp
WW
W
Module
LËp chØ
môc
C«ng cô
t×m
kiÕm
S¾p xÕp
Ng­êi sö dông
§iÒu khiÓn
Thu Håi
Kho l­u tr÷ trang
Thu håi
Truy vÊn KÕt qu¶
B¶ng chØ môc :

S¾p xÕp
Ng­êi sö dông
§iÒu khiÓn
Thu Håi
Kho l­u tr÷ trang
Thu håi
Truy vÊn KÕt qu¶
B¶ng chØ môc :
TiÖn
Ých
Ph¶n håi
CÊu
tróc
V¨n
B¶n
Hình 2 : Bộ công cụ tìm kiếm trang Web
Ở hình trên em đưa ra mô hình tổng quan của một bộ công cụ tìm
kiếm Web. Mọi bộ công cụ đều sử dụng một mô đun Crawler để thu hồi tài
liệu cung cấp cho các hoạt động của nó. Bộ thu hồi là một nhóm các chương
trình thay mặt bộ công cụ để duyệt các trang Web, tương tự như một người
sẽ kết nối để đi đến các trang khác, nhóm chương trình có đầu vào là một
tập các giá trị khởi đầu URL mà các trang của nó sẽ được tìm kiếm từ Web.
Bộ thu hồi trích các giá trị URL xuất hiện trong mỗi trang Web tìm kiếm
được và gửi tới mô đun bộ điều khiển thu hồi. Mô đun này xác định liên kết
nào được thăm tiếp theo, để cung cấp thông tin này tới các Crawlers (một
vài chức năng cuả mô đun bộ điều khiển thu hồi có thể được thực hiện bởi
chính các Crawler). Bộ thu hồi lưu các trang tìm kiếm được vào trong một
kho lưu trữ trang (Page Repostory). Bộ thu hồi tiếp tục thăm các trang Web
cho tới khi nguồn tài nguyên cục bộ bị cạn kiệt.
Khi bộ công cụ tìm kiếm đã trải qua ít nhất một chu kỳ thu hồi

trang đã thăm dựa theo thời gian xây dựng bảng chỉ mục. Bộ nhớ đệm này
hỗ trợ cho việc đưa ra các trang kết quả một cách nhanh chóng và cung cấp
các tiện ích tìm kiếm cơ bản. Một vài hệ thống, giống như Internet Archive
đã duy trì một số lượng rất lớn các trang và lưu trữ chúng lâu dài. Vấn đề
lưu trữ cũng phải được xem xét một cách cẩn thận.
Mô đun “công cụ truy vấn” (Query Engine) có nhiệm vụ nhận và tìm
kiếm các yêu cầu từ người sử dụng. Bộ công cụ sẽ dựa vào bảng chỉ mục và
19
thỉnh thoảng là các kho lưu trữ trang. Bởi kích thước lớn của Web thêm vào
nữa khi người sử dụng chỉ đưa vào một hoặc là hai từ khóa thì sẽ nhận được
một tập rất lớn các trang kết quả. Do vậy phải có một môđun Ranking thực
hiện việc sắp xếp kết quả sao cho các kết quả ở gần đầu sẽ giống với nội
dung đang được tìm kiếm hơn. Môđun truy vấn được quan tâm một cách đặc
biệt, bởi vì: Với các kỹ thuật truyền thống ta chỉ dựa vào sự đo lường về độ
tương quan giữa văn bản trong tập tài liệu. Trong khi đó, đối với bộ công cụ
tìm kiếm Web, các truy vấn thì rất nhỏ còn tập dữ liệu thì lại rất lớn, nó đã
ngăn chặn sự đánh giá về độ tương quan dựa trên phép tính gần đúng từ việc
lọc số lượng các trang không liên quan ra khỏi kết quả tìm kiếm.
1.3 Mô hình bộ công cụ tìm kiếm thông tin truyền thống
Vào những năm 70, khi các mô hình tìm kiếm thông tin chủ yếu được
xử lý với các truy vấn không có cấu trúc thì các hệ thống truy vấn tự động đã
mở thành một sự kiện. Nguyên tắc hoạt động của các hệ thống truy vấn tự
động là chỉ số hóa và thiết lập công thức truy vấn, kết quả đưa ra là một biểu
diễn có ý nghĩa gần với thực của văn bản, loại bỏ các từ không theo quy tắc
trong ngôn ngữ tự nhiên đến mức có thể. Sau đây em đưa ra một mô hình
tổng quát của hệ thống tìm kiếm thông tin truyền thống. 20
21

Tài liệu
Từ không nằm
trong StopList
Từ đã
chuẩn hoá
Từ, trọng
số
Tập tài liệu
liên quan
Từ truy vấn
Tập tài liệu
thu hồi đư
Tập tài liệu
đã sắp xếp
Tập tài liệu
tìm kiếm
Truy
vấn
Truy vấn
Hình 3 : Mô hình bộ công cụ tìm kiếm truyền thống
Khi xây dựng cơ sở dữ liệu, nội dung của tập tài liệu được tách thành
các từ. Các từ này được so sánh với Stoplist - một danh sách các từ không
được lập chỉ mục (nó không có giá trị nội dung trong nhận dạng văn bản, ví
dụ a, an, the, about....). Các từ không nằm trong Stoplist sẽ được chiết lọc để
lấy gốc (stemming). Các từ có thể thống kê tần suất xuất hiện để hỗ trợ cho
việc sắp xếp các tài liệu thu hồi được. Cuối cùng các từ cùng với các thông
tin kết hợp với chúng (ví dụ: định danh tài liệu, định danh trường nằm trong
tài liệu và các giá trị thống kê...vv) được dặt vào kho cơ sở dữ liệu. Kho cơ
sở dữ liệu có thể bao gồm các cặp giá trị định danh tài liệu và các từ khóa.
Cấu trúc này được gọi là tập tin đảo (Inverted File).

i
được tính theo công thức:
( )
mxxH
ii
mod=
Với m là một số nguyên tố phù hợp, chữ phù hợp ở đây mang ý nghĩa
là một số nguyên tố lớn.
Hệ số
α
= n/m được gọi là hệ số tải với n là số khóa trong tập L. Giá trị
này càng nhỏ thì khả năng hai khóa khác nhau có cùng một giá trị băm càng
nhỏ (hiện tượng này được gọi là xung đột).
Hàm băm h được gọi là một hàm băm hoàn hảo nếu nó thỏa mãn tính
chất vì mọi x
i
, x
j
thuộc L ta có: h(x
i
) = h(x
j
) khi v à ch ỉ khi x
i
= x
j
. Tính chất
này đảm bảo không xảy ra đụng độ như đã nói ở trên, dễ thấy rằng để thỏa
mãn điều kiện này thì trước hết phải có
α

h(54) = 54 mod 13 = 2 => T [2] = 54
h(79) = 79 mod 13 = 1 => T [1] = 79
h(198) = 198 mod 13 = 3 => T [3] = 198
Ta gọi h là hàm băm (hash function), T là bảng băm (hash table) và
h(i) là giá trị băm của i
24
Nếu tập A có thêm phần tử {14} thì ta có
h(14) = 14 mod 13 = 1⇒ T[1] =14
Như vậy 79 và 14 sẽ chiếm cùng một phần tử T[1]. Từ đây ta có hai
hướng để giải quyết, thứ nhất là tránh xung đột bằng cách xây dựng hàm
băm hoàn hảo hoặc cũng có thể tránh xung đột bằng cách mở rộng kích
thước bảng băm. Thứ hai là chấp nhận xung đột và áp dụng một số giải pháp
giải quyết xung đột. Như phần trên đã chứng minh, hướng thứ nhất thực hiện
rất phức tạp và có thể vẫn xảy ra xung đột, nên sang phần sau em sẽ trình
bày hướng giải quyết thứ hai.
1.4.1.3 Giải quyết xung đột
* Phương pháp Chaining: Phương pháp này cho ta thấy khá đơn giản, mỗi
phần tử của bảng băm được gắn với một danh sách liên kết, các bản ghi có
cùng giá trị băm của khóa được đặt vào danh sách liên kết đó. Chaining dễ
dàng trong việc cài đặt, mặt khác danh sách liên kết trong bảng băm thường
là ngắn, nên việc tìm kiếm, chèn xóa được thực hiện một cách nhanh chóng.
Thông thường để thuận tiện trong việc tìm kiếm cũng như xóa, bổ
xung, danh sách được sắp xếp theo thứ tự tăng dần của các khóa ( nếu các
khóa có thể so sánh được).

Null
Null
Null
25
Hình 4: Cấu trúc bảng băm