BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
……………………………………..

MỤC LỤC
MỤC LỤC......................................................................................................... 2
DANH MỤC CÁC TỪ VIẾT TẮT .................................................................. 4
DANH MỤC BẢNG......................................................................................... 5
DANH MỤC HÌNH .......................................................................................... 6

LUẬN VĂN THẠC SĨ KHOA HỌC

MỞ ĐẦU........................................................................................................... 8
U

CHƯƠNG 1. TỔNG QUAN VỀ TRUY XUẤT THÔNG TIN ..................... 10
1.1. Khái niệm truy xuất thông tin............................................................... 10
1.2. Quá trình truy xuất thông tin ................................................................ 13
1.2.1. Giai đoạn tiền xử lý........................................................................ 15
1.2.2. Giai đoạn thu thập .......................................................................... 20

XÂY DỰNG HỆ THỐNG TRUY XUẤT THÔNG TIN

1.3. Các hướng tiếp cận giải quyết bài toán truy xuất thông tin.................. 22
1.4. Đánh giá hiệu quả truy xuất thông tin .................................................. 22
1.4.1. Độ chính xác và độ bao phủ........................................................... 23
1.4.2. Độ chính xác trung bình................................................................. 25
1.4.3. Độ đo F và độ đo E ........................................................................ 26

NGÀNH: CÔNG NGHỆ THÔNG TIN
MÃ SỐ:

TRẦN THỊ HOÀNG THẢO

1.4.4. Các tiếp cận đánh giá lấy người dùng làm trung tâm .................... 28
1.5. Một số hệ thống truy xuất thông tin ..................................................... 29
1.6. Kết chương............................................................................................ 34
CHƯƠNG 2. CÁC CÔNG CỤ TRUY XUẤT THÔNG TIN CƠ BẢN ........ 35
2.1. Lập chỉ mục .......................................................................................... 35
2.2. Xếp hạng ............................................................................................... 43

Người hướng dẫn khoa học: TS. LÊ THANH HƯƠNG

2.2.1. Tổng quan các mô hình truy xuất thông tin ................................... 43
2.2.2. Các mô hình lôgíc .......................................................................... 46
2.2.3. Các mô hình đại số ......................................................................... 52
2.2.4. Các mô hình xác suất ..................................................................... 56
2.3. Kết chương............................................................................................ 61

HÀ NỘI 2006


3

4

Truy xuất thông tin

CHƯƠNG 3. CƠ CHẾ HOẠT ĐỘNG CỦA LUCENE................................. 62

Truy xuất thông tin


DANH MỤC CÁC TỪ VIẾT TẮT

3.1. Giới thiệu Lucene ................................................................................. 62

BIR

Binary Independence Retrieval: truy xuất độc lập nhị phân

3.2. Lập chỉ mục .......................................................................................... 63

CLM

Coordination Level Matching: đối sánh mức đồng hạng

3.2.1. Khung nhìn lôgíc của chỉ mục ....................................................... 64

GVSM

Generalized Vector Space Model: mô hình không gian véctơ suy rộng

3.2.2. Cấu trúc chỉ mục ............................................................................ 65

idf

Inverse Document Frequency: nghịch đảo tần số văn bản

3.2.3. Inverted index................................................................................. 73

IR


Information Retrieval: truy xuất thông tin

3.2.4. Chiến lược lập chỉ mục .................................................................. 77

LSI

Latent Semantic Indexing: lập chỉ mục ngữ nghĩa tiềm ẩn

3.3. Tìm kiếm............................................................................................... 78

tf

Term Frequency: tần số thuật ngữ

3.3.1. Mô hình không gian véctơ ............................................................. 78

tf – idf

Phương pháp tần số kết hợp của tf và idf

3.3.2. Xếp hạng ........................................................................................ 81

TREC

Text REtrieval Conference : hội nghị truy xuất văn bản

VSM

Vector Space Model: mô hình không gian véctơ


3.4. Kết chương............................................................................................ 84
CHƯƠNG 4. CHƯƠNG TRÌNH VÀ KẾT QUẢ THỰC NGHIỆM ............. 85
4.1. Kiến trúc hoạt động của chương trình .................................................. 85
4.2. Kết quả thực nghiệm............................................................................. 87
4.3. Kết chương............................................................................................ 94
CHƯƠNG 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN CỦA LUẬN VĂN 95
5.1. Kết luận................................................................................................. 95
5.2. Hướng phát triển của luận văn.............................................................. 96
TÀI LIỆU THAM KHẢO............................................................................... 98
TÀI LIỆU THAM KHẢO CHÉO................................................................. 100

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Trần Thị Hoàng Thảo

Luận văn thạc sĩ


5

6

Truy xuất thông tin

Truy xuất thông tin

DANH MỤC BẢNG


DANH MỤC HÌNH

Bảng 1-1 Số thứ tự các hệ thống trong biểu đồ .............................................. 31

Hình 1-1 Quy trình truy xuất thông tin nói chung (nguồn: [1])...................... 13

Bảng 3-1 Ví dụ các tệp chỉ mục ...................................................................... 66

Hình 1-2 Khung nhìn lôgíc của tài liệu thông qua các giai đoạn tiền xử lý

Bảng 3-2 Ví dụ các tệp chỉ mục ...................................................................... 67

(nguồn: [1]) ..................................................................................................... 15

Bảng 3-3 Ví dụ các tệp chỉ mục ...................................................................... 69

Hình 1-3 Văn bản A ban đầu .......................................................................... 16

Bảng 3-4 Ví dụ chỉ mục ghép ......................................................................... 71

Hình 1-4 Văn bản A sau khi phân tích............................................................ 16

Bảng 4-1 So sánh kết quả lập chỉ mục của chương trình và Google Desktop 88

Hình 1-5 Văn bản A sau khi loại các từ trong danh sách stopword của Smart

Bảng 4-2 Các loại truy vấn được thử nghiệm ................................................. 90

......................................................................................................................... 17


Bảng 4-3 So sánh hiệu quả truy vấn của chương trình và Google Desktop ... 91

Hình 1-6 Văn bản A sau khi lấy gốc từ........................................................... 18
Hình 1-7 Ví dụ đồ thị độ chính xác-độ bao phủ trung bình............................ 24
Hình 1-8 Các tài liệu được thu thập so với các tài liệu có liên quan (nguồn:
[5]) ................................................................................................................... 27
Hình 1-9 Biểu đồ so sánh tính chính xác của một số hệ thống IR.................. 30
Hình 1-10 Biểu đồ so sánh tính hiệu quả của một số hệ thống IR ................. 30
Hình 1-11 Biểu đồ so sánh một số hệ thống IR .............................................. 31
Hình 2-1 Tần số tập hợp (cf) và tần số tài liệu (df) thể hiện khác nhau ......... 37
Hình 2-2 Ví dụ các giá trị idf .......................................................................... 38
Hình 2-3 Một ví dụ tạo nhãn với mỗi khối logic có D = 2 từ, kích thước nhãn
F = 12 bit, m = 4 bit ........................................................................................ 39
Hình 2-4 Cấu trúc File dạng SSF .................................................................... 40
Hình 2-5 Minh hoạ một Inverted File ............................................................. 42
Hình 3-1 Quy trình lập chỉ mục với Lucene ................................................... 63
Hình 3-2 Khung nhìn lôgíc của một chỉ mục Lucene..................................... 65
Hình 3-3 Chỉ mục không được tối ưu hoá gồm 3 phân đoạn, chứa 24 tài liệu
......................................................................................................................... 68
Hình 3-4 Ví dụ minh hoạ định dạng chỉ mục của Lucene (nguồn: [4]).......... 74

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Trần Thị Hoàng Thảo

Luận văn thạc sĩ



7

8

Truy xuất thông tin

Hình 3-5 Một sơ đồ lập chỉ mục Lucene......................................................... 78

Truy xuất thông tin

MỞ ĐẦU

Hình 3-6 Minh họa độ tương tự côsin............................................................. 79

Ngày nay, sự phát triển mạnh mẽ của công nghệ thông tin dẫn tới dung

Hình 4-1 Kiến trúc hoạt động của chương trình ............................................. 85

lượng dữ liệu được lưu trên máy tính gia tăng nhanh chóng. Trong những tập

Hình 4-2 Phần client thực hiện tìm kiếm ........................................................ 87

dữ liệu khổng lồ đó ẩn chứa hàm lượng thông tin vô cùng lớn. Vấn đề đặt ra

Hình 4-3 Biểu đồ độ chính xác giữa chương trình và Google Desktop ......... 89

là làm thế nào khai thác được khối thông tin đó để nó trở nên có ích đối với

Hình 4-4 Biểu đồ R-Precision của chương trình (R = 10) .............................. 93


người dùng.

Hình 4-5 Biểu đồ so sánh thời gian thực hiện giữa chương trình với Google
Desktop............................................................................................................ 93

Những tiến bộ đạt được về lý thuyết và công nghệ trong lĩnh vực xử lý
thông tin đã giải quyết được phần nào nhu cầu nêu trên, chẳng hạn, các bài
toán trong xử lý văn bản như tìm kiếm, phân loại, phân cụm văn bản.
Information Retrieval (tạm dịch là truy xuất thông tin) là một trong số các
vấn đề rất được quan tâm hiện nay. Đây là vấn đề khó, ngay cả với những hệ
thống tìm kiếm phổ biến trên mạng Internet như Google, Altavista, Yahoo thì
vẫn còn nhiều hạn chế. Có thể liệt kê các hạn chế thường gặp như sau: thứ
nhất là với mỗi truy vấn, hệ thống thường trả về tập kết quả gồm hàng nghìn
tài liệu, thậm chí còn lớn hơn nhiều, khiến người dùng phải mất nhiều thời
gian để đọc nội dung của từng tài liệu nhằm tìm thông tin mà họ quan tâm;
thứ hai là vấn đề tìm kiếm theo trọng số của từ khoá, ví dụ nếu người dùng
đưa ra truy vấn “software engineering” với mong muốn rằng từ “software” có
ưu tiên cao hơn từ “engineering” thì nhiều khi không nhận được kết quả như
ý; thứ ba là vấn đề sắp xếp các tài liệu trả về theo độ liên quan với truy vấn.
Ngày càng nhiều tổ chức và cá nhân có nhu cầu tìm kiếm thông tin
trong tập dữ liệu đặt trên một máy tính hoặc một mạng máy tính. Yêu cầu đặt
ra là cần có những hệ thống truy xuất thông tin chạy trên Desktop với hiệu
quả và độ chính xác cao. Trong luận văn này, chúng tôi tập trung nghiên cứu
cơ sở lý thuyết truy xuất thông tin và xây dựng thử nghiệm một hệ thống
truy xuất thông tin cho phép tìm kiếm các tài liệu mang nội dung tiếng

Trần Thị Hoàng Thảo

Luận văn thạc sĩ


Trần Thị Hoàng Thảo

Luận văn thạc sĩ


9

10

Truy xuất thông tin

Anh chứa trong một máy tính. Hệ thống được xây dựng dựa trên thư viện
mã nguồn mở truy xuất thông tin Lucene.

Truy xuất thông tin

CHƯƠNG 1. TỔNG QUAN VỀ TRUY XUẤT THÔNG TIN
Mục đích của chương này là giới thiệu tóm tắt về vấn đề truy xuất

Nội dung luận văn gồm 5 chương :

thông tin:

• Chương 1: trình bày tổng quan về truy xuất thông tin, các bước cần

9 Truy xuất thông tin là gì?

thực hiện trong quá trình truy xuất thông tin, các phương pháp đánh giá

9 Các bước thực hiện trong quá trình truy xuất thông tin


hiệu quả truy xuất thông tin và so sánh một số hệ thống truy xuất thông

9 Các phương pháp đánh giá hiệu quả truy xuất

tin trên thế giới.

9 So sánh một số hệ thống truy xuất thông tin

• Chương 2: trình bày các công cụ truy xuất thông tin quan trọng là lập
chỉ mục và sắp xếp kết quả tìm kiếm.
• Chương 3: giới thiệu và trình bày cơ chế lập chỉ mục và tìm kiếm của
thư viện mã nguồn mở Lucene.
• Chương 4: trình bày kiến trúc hoạt động của chương trình và kết quả
thực nghiệm.
• Chương 5: kết luận và hướng phát triển tiếp theo của luận văn.

1.1. Khái niệm truy xuất thông tin
Thuật ngữ truy xuất thông tin (Information Retrieval – IR), phát biểu
bởi Rijsbergen [12] , thường được định nghĩa một cách rộng và không chặt
chẽ. Do vậy, thường có sự nhập nhằng giữa các lĩnh vực truy xuất dữ liệu
(data retrieval), truy xuất tài liệu (document retrieval), truy xuất thông tin và
truy xuất văn bản (text retrieval). Một định nghĩa đây đủ, dễ hiểu, tránh được
sự nhầm lẫn đó được đưa ra bởi Lancaster [19] : Một hệ thống truy xuất thông
tin không cho người dùng biết (ví dụ như thay đổi tri thức của người dùng) về
chủ đề mà họ yêu cầu. Nó chỉ đơn thuần cho biết sự tồn tại (hoặc không tồn
tại) và vị trí của các tài liệu có liên quan tới yêu cầu của người dùng. Trong
thực tế nghiên cứu, có thể định nghĩa truy xuất thông tin như sau [7] :
Truy xuất thông tin là việc tìm kiếm tài liệu ở trạng thái phi cấu trúc
(thường là văn bản) thoả mãn một nhu cầu thông tin nào đó từ các

tập hợp lớn (thường là trên các máy chủ cục bộ hoặc trên mạng).
Hành động đó xác định rõ cốt lõi của IR. Hàng ngày, có hàng trăm triệu
người thực hiện truy xuất thông tin mỗi khi họ sử dụng một máy tìm kiếm
web hoặc tìm kiếm trong hộp thư điện tử của mình. IR đang nhanh chóng trở
thành hình thức truy nhập thông tin vượt trội, vượt qua dạng tìm kiếm kiểu cơ
sở dữ liệu truyền thống.
IR là lĩnh vực khoa học máy tính chuyên về lý thuyết và thực hành việc
tìm kiếm thông tin. Do văn bản là phương tiện phổ biến nhất được sử dụng để

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Trần Thị Hoàng Thảo

Luận văn thạc sĩ


11

12

Truy xuất thông tin

Truy xuất thông tin

biểu diễn và phân bố thông tin một cách hiệu quả, hầu hết các nghiên cứu IR
đều tập trung vào việc tìm kiếm trong các tập hợp tài liệu dạng văn bản.
Như hàm ý của thuật ngữ IR, nhiệm vụ chính của IR là tìm kiếm thông
tin thoả mãn nhu cầu thông tin của người dùng. Người sử dụng của một hệ

thống IR quan tâm nhiều tới việc thu nhận thông tin về một chủ đề hơn là thu
thập dữ liệu phù hợp với một câu truy vấn cho trước. Trái lại, truy xuất dữ
liệu chỉ nhằm mục tiêu cung cấp các tập hợp thông tin "vừa khít" với các từ
khoá của một câu truy vấn.
IR có lịch sử lâu dài giống như lịch sử của việc lưu trữ thông tin, vào
khoảng 4000 năm. Cùng với sự phát triển của lượng thông tin được lưu trữ,
con người phải phát triển ngày càng nhiều phương thức để tổ chức lượng
thông tin đó để phục vụ cho việc truy xuất về sau. Quá trình phát triển đó
được tóm lược như dưới đây [14] .
Phương pháp đầu tiên là hệ thống bảng chữ cái. Các tài liệu cần được
sắp xếp theo cách này, khi mà số lượng tác phẩm văn học Hy Lạp tăng lên
buộc các thủ thư của thư viện Alexandria phải nghĩ ra một cách tổ chức các
tác phẩm, vào thế kỷ thứ 3 trước Công nguyên. Mục lục là một ví dụ khác về
các công cụ ban đầu của IR, nó trở nên thiết yếu khi mà các tác phẩm văn học
gia tăng theo số lượng trang. Một ví dụ khác về IR thủa ban đầu là chỉ mục
(index). Danh mục đầu tiên là những mảnh giấy da dê nhỏ, chứa đầu đề (title)
và đôi khi tác giả của tác phẩm.
Trong khoảng 20 năm cuối thế kỷ 20, lĩnh vực IR phát triển tốt dựa trên
những mục đích cơ bản của nó là lập chỉ mục văn bản và tìm kiếm các tài liệu
có ích trong một tập hợp. Ngày nay, nghiên cứu trong IR bao gồm việc mô
hình hóa, phân loại văn bản, kiến trúc hệ thống, giao diện người dùng, trực
quan hóa dữ liệu, lọc, ngôn ngữ…
Một trong những dạng IR ban đầu là Memex được mô tả bởi Vanevar
Bush. Ngoài ra còn có kết quả của Warren Weaver. Warren Weaver tập trung
vào việc xử lý ngôn ngữ, coi đó là nền tảng của IR. Hơn nữa, sự phát triển của
IR hiện đại được củng cố cùng sự phát triển của Trí tuệ nhân tạo. Trong khi
chờ đợi, Trí tuệ nhân tạo chỉ được sử dụng trong một số phần của IR. Thuật

ngữ IR được Moer đặt ra vào năm 1952. Các hệ thống thương mại đầu tiên
được phát triển từ năm 1975 trở về sau. Chúng được sử dụng chủ yếu trong

các thư viện. Cuối cùng, kể từ năm 1993, IR được phổ biến rộng rãi nhờ vào
sự phát triển và tầm quan trọng ngày càng lớn của World Wide Web. Sự phát
triển của World Wide Web dẫn đến sự gia tăng khổng lồ về số lượng các tài
liệu, đòi hỏi phải có những kỹ thuật IR hiệu quả.
Trước khi xuất hiện World Wide Web, hầu hết các hệ thống lưu trữ và
truy xuất thông tin đều được sử dụng riêng bởi những người lập chỉ mục và
tìm kiếm chuyên nghiệp. Thông thường, những người tìm kiếm chuyên
nghiệp hoạt động như những “phương tiện tìm kiếm trung gian” cho các
người dùng cuối hoặc các khác hàng. Họ cố gắng tìm hiểu trong một cuộc đối
thoại tương tác với hệ thống và khách hàng xem nhu cầu của khách hàng là gì
và thông tin này nên được sử dụng như thế nào để tìm kiếm thành công.
Những người dùng chuyên nghiệp khác với người dùng không chuyên bởi họ
biết về tập hợp tài liệu, họ biết cách thức các tài liệu được biểu diễn trong hệ
thống và họ biết cách sử dụng các toán tử tìm kiếm Boolean để giới hạn số
lượng tài liệu được thu thập.
Nhiều hệ thống IR hiện đại được thiết kế cho những người dùng không
biết rõ về tập hợp tài liệu, sự biểu diễn của các tài liệu và cách sử dụng các
toán tử Boolean. Những hệ thống như vậy cần đáp ứng những yêu cầu chính
sau đây. Thứ nhất, người dùng có thể nhập (các) câu, (các) cụm từ, (các) từ
vào hệ thống mà không cần phải nhập các toán tử. Điều này thường được hiểu
là một hệ thống IR toàn văn bản (full text), hệ thống này tự động lập chỉ mục
tất cả các từ trong một tài liệu. Thứ hai, hệ thống có thể xếp hạng các tài liệu
thu thập được bằng cách đánh giá mức độ hoặc khả năng có ích đối với người
dùng. Thứ ba, hệ thống có thể hỗ trợ việc tự động biến đổi câu lệnh tìm kiếm
theo phản hồi của người dùng. Yêu cầu thứ ba có thể không quan trọng như
hai yêu cầu kia.
Một hệ thống IR là một chương trình phần mềm lưu trữ và quản lý
thông tin về các tài liệu. Hệ thống trợ giúp người dùng tìm kiếm thông tin họ
cần. Nó cho biết về sự tồn tại và vị trí của các tài liệu có thể chứa thông tin


Trần Thị Hoàng Thảo

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Luận văn thạc sĩ


13

14

Truy xuất thông tin

cần thiết. Có thể một số tài liệu được đề xuất sẽ thoả mãn nhu cầu thông tin
của người dùng. Những tài liệu đó được gọi là các tài liệu có liên quan. Một
hệ thống IR hoàn hảo sẽ chỉ thu thập những tài liệu có liên quan và bỏ qua
những tài liệu không liên quan. Tuy nhiên, sẽ không thể tồn tại những hệ
thống như vậy bởi các câu lệnh tìm kiếm thường không đầy đủ và độ liên
quan (relevance) phụ thuộc vào ý kiến chủ quan của người dùng. Hai người
dùng có thể đưa ra cùng truy vấn giống nhau cho một hệ thống IR nhưng lại
có cách đánh giá độ liên quan khác nhau đối với các tài liệu được thu thập.
Hệ thống IR theo một nghĩa nào đó, phải “thông dịch” nội dung của các
phần tử thông tin (các tài liệu) trong một tập hợp và xếp hạng chúng theo mức
độ liên quan tới câu truy vấn của người dùng. Việc “thông dịch” một nội dung
tài liệu bao gồm việc chắt lọc thông tin cú pháp và ngữ nghĩa từ văn bản tài
liệu và sử dụng thông tin này để đối sánh với yêu cầu thông tin của người
dùng. Khó khăn không chỉ là việc phải biết cách chắt lọc thông tin mà còn là
phải biết cách sử dụng nó để lựa chọn độ liên quan. Do đó, quan điểm về độ

liên quan là trọng tâm của IR. Thực tế, mục tiêu chính của một hệ thống IR là

Truy xuất thông tin

Quá trình truy xuất thông tin diễn ra theo nhiều giai đoạn. Hình 1-1 thể
hiện mô hình hệ thống truy xuất thông tin nói chung, được đưa ra bởi Baeza
và cộng sự [1] .
Trước khi bắt đầu quá trình thu thập, cần xác định cơ sở dữ liệu văn
bản (text database): tập tài liệu được sử dụng, các thao tác được thực hiện
trên văn bản và mô hình văn bản (ví dụ như cấu trúc văn bản và những phần
tử có thể được thu thập). Các thao tác văn bản (text operation) biến đổi các
tài liệu ban đầu và sinh ra một khung nhìn lôgíc (logical view) của chúng.
Tiếp theo là quá trình xây dựng chỉ mục (indexing) cho văn bản nhằm
tăng tốc độ truy nhập trong giai đoạn truy xuất. Có nhiều loại cấu trúc chỉ
mục nhưng phổ biến nhất là Inverted Files.
Khi tập tài liệu đã được đánh chỉ mục, có thể bắt đầu quá trình thu thập.
Đầu tiên, người sử dụng xác định yêu cầu của mình (user need), yêu cầu này
sẽ được phân tích (parse) và biến đổi (transformed) bằng các thao tác xử lý

thu thập tất cả các tài liệu có liên quan tới một truy vấn của người dùng đồng
thời thu thập ít nhất có thể các tài liệu không liên quan [1] .

đã được áp dụng đối với văn bản. Tiếp theo, các thao tác truy vấn (query

1.2. Quá trình truy xuất thông tin

được xử lý (searching) để nhận được các tài liệu được thu thập (retrieved
documents).

User Interface

Text
User
Need
User
Feedback

Query

Text Operations
Indexing

Database
Manager

Searching

Index

feedback). Trong chu trình như vậy, hệ thống sử dụng các tài liệu được chọn

Ranking

Retrieved
Docs

bởi người dùng để cải thiện đổi công thức truy vấn. Truy vấn đã được biến
đổi này sẽ biểu diễn tốt hơn nhu cầu thực sự của người dùng.
Tóm lại, trong quá trình truy vấn, hệ thống IR chắt lọc các phần thông

Hình 1-1 Quy trình truy xuất thông tin nói chung (nguồn: [1] )


Trần Thị Hoàng Thảo

được, người dùng có thể đánh dấu một tập con các tài liệu thực sự đáng quan
tâm và khi đó sẽ khởi đầu một chu trình phản hồi của người dùng (relevance

Inverted
file
Text
Database

Ranked
Docs

Trước khi chuyển tới người dùng, các tài liệu thu thập được sẽ được
xếp hạng (ranking) theo mức độ liên quan (likelihood relevance). Khi nhận

Logical View
Query
Operations

operations) có thể được áp dụng để tạo nên truy vấn thật sự. Sau đó, truy vấn

Luận văn thạc sĩ

tin có thể sẽ đáp ứng được nhu cầu thông tin được phát biểu bởi người dùng.

Trần Thị Hoàng Thảo

Luận văn thạc sĩ



15

16

Truy xuất thông tin

Truy xuất thông tin

Quá trình này thường được chia thành hai giai đoạn, tiền xử lý (pre-

từ (word), nhưng cũng có thể là một gốc từ (stem), một cụm danh từ hoặc một

processing) và thu thập (retrieval). Giai đoạn truy xuất có thể lặp đi lặp lại

cụm từ (phrase). Gốc từ là một từ được rút gọn thành gốc của nó sau khi loại

nếu như người dùng muốn tinh chỉnh các kết quả truy xuất.

bỏ các phụ tố: ví dụ, ‘system2’ và ‘component_123’ sẽ trở thành ‘system’ và
‘component’ sau bước lấy gốc từ. Giả thiết cơ bản (đôi khi bị nghi ngờ) nằm

1.2.1. Giai đoạn tiền xử lý

sau việc lấy gốc từ là không có sự khác biệt đáng kể về ý nghĩa giữa các từ có

1.2.1.1. Tiền xử lý tài liệu
Trong giai đoạn tiền xử lý, hệ thống IR tạo ra biểu diễn bên trong của
thông tin trong từng tài liệu thông qua quy trình đánh chỉ mục. Trước hết, tập

tài liệu văn bản được tiền xử lý bằng một số phương pháp thao tác văn bản tự
động như phân tích từ vựng (lexical analysis), loại bỏ từ dừng (stopword
removing), lấy gốc từ (stemming) từ dạng văn bản đơn giản (plain text) của
tài liệu. Kết quả nhận được là tập các từ (term) hay còn được hiểu là các khái
niệm (concept), được coi là khung nhìn lôgíc (logical view [1] ) của tài liệu.

chung một gốc. Một cụm từ chứa ít nhất hai từ liên tiếp có nghĩa rõ ràng, ví
dụ ‘office application’ hoặc ‘Hanoi University of Technology’. Nếu có thể,
những từ khóa (keyword) được chỉ định một cách thủ công, mô tả nội dung
của tài liệu cũng có thể được dùng cho việc lập chỉ mục (ví dụ Google).
Phân tích từ vựng

Là quá trình biến đổi các ký tự trong tài liệu thành một tập các từ được
đề cử để chọn làm từ chỉ mục bằng cách xử lý các chữ số, dấu nối, các ký
hiệu chấm câu và chữ viết hoa viết thường.
CHAPTER 1
PREAMBLE
1.1 Humanity stands at a defining moment history. We are confronted with a
perpetuation of disparities between and within nations, a worsening of poverty,
hunger, ill health and illiteracy, and the continuing deterioration of the ecosystem
on which we depend for out well-being.

Hình 1-3 Văn bản A ban đầu
chapter 1 preamble 1 1 humanity stands at a defining moment history we
are confronted with a perpetuation of disparities between and within
nations a worsening of poverty hunger ill health and illiteracy and the
Hình 1-2 Khung nhìn lôgíc của tài liệu thông qua các giai đoạn tiền xử lý
(nguồn: [1] )

Hình 1-4 Văn bản A sau khi phân tích


Trong luận văn này, chúng tôi sẽ dùng thuật ngữ tiếng Anh “term” để

Bước đầu tiên là lọc ra các ký tự không mong muốn và ký hiệu (các thẻ

nói tới “từ” nhằm phân biệt với các thuật ngữ khác. Một term có thể là một

HTML, dấu chấm câu, các con số…). Tiếp theo, văn bản cần được chia thành

Trần Thị Hoàng Thảo

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Luận văn thạc sĩ


17

18

Truy xuất thông tin

Truy xuất thông tin

các thẻ (token, còn gọi là từ khóa) sử dụng khoảng trắng phân tách và các ký

được thực hiện sau khi ta đã lập chỉ mục song toàn bộ tài liệu và bảng


tự kết thúc câu. Việc này không đơn giản vì các từ trong các văn bản không

chỉ mục đang được lưu trong bộ đệm bộ nhớ chính. Khi đó ta thực

phải lúc nào cũng được phân tách rõ ràng (ví dụ, nếu văn bản là I can’t go thì

hiện việc duyệt trên bảng băm để tìm các từ dừng, thêm chúng vào

có thể xem dấu nháy là một dấu phân tách từ để có hai từ là can và t, hoặc có

danh sách danh sách từ dừng và loại phần tử chứa từ đó khỏi bảng

thể không coi nó là dấu phân tách và xem là một từ can’t, hoặc có thể mở

băm.

rộng dạng liên kết thành hai từ can và not và sử dụng khoảng trắng để phân
tách.

Lấy gốc từ

Lấy gốc từ là quá trình thu gọn một từ về dạng ngữ pháp gốc của nó.
Nhằm xác định và nhóm các từ có chung ngữ nghĩa sao cho người dùng

Loại bỏ từ dừng

Việc loại bỏ từ dừng có ý nghĩa làm giảm kích cỡ của cấu trúc chỉ mục.
Đây là bước tiền xử lý nhằm loại bỏ những từ có tần suất xuất hiện cao trong
hầu hết các tài liệu mà lại không mang nội dung có ý nghĩa. Những từ như
vậy được gọi là từ dừng (stopword), bao gồm các mạo từ, giới từ, liên từ,

chẳng hạn như a, the. It, of, could… Một ví dụ về danh sách các từ dừng trong
tiếng Anh có tại: />
không phải xác định quá cụ thể trong truy vấn. Ví dụ: computes, computing,
computer có gốc là comput .
chapter 1 preambl 1 1 human stand defin moment histori confront perpetu dispar
nation worsen poverti hunger ill health and illiteraci continu deterior ecosystem
depend well be

Hình 1-6 Văn bản A sau khi lấy gốc từ
Việc lấy gốc từ trước khi xây dựng chỉ mục có ưu điểm là làm giảm

chapter 1 preamble 1 1 humanity stands defining moment history
confronted perpetuation disparities nations worsening poverty hunger ill
health illiteracy continuing deterioration ecosystem depend well being

kích thước chỉ mục và cho phép truy xuất các tài liệu với nhiều dạng biến tố

Hình 1-5 Văn bản A sau khi loại các từ trong danh sách stopword của Smart

các tài liệu có chứa từ computations và computing ). Một phương pháp lấy

Quá trình loại bỏ từ dừng có thể được chia thành hai loại :
•

gốc từ nhanh và phổ biến là giải thuật của Porter (1980), giải thuật này áp

Từ cần loại bỏ nằm trong danh sách từ dừng, quá trình này sẽ được
thực hiện trong phần nhận dạng từ, có nghĩa là từ này sẽ không thể đi

•


của cùng một từ (ví dụ, khi tìm kiếm với từ computation, kết quả sẽ bao gồm

dụng tập các quy tắc đối với hậu tố của một từ nhằm loại bỏ nó.
Như vậy, giai đoạn tiền xử lý tài liệu tập trung vào việc chắt lọc tập các

qua bộ nhận dạng từ và vì thế chúng không được lập chỉ mục.

khái niệm mô tả cho từng tài liệu. Các khái niệm đó thường được gán trọng số

Từ cần loại bỏ không nằm trong danh sách từ dừng nhưng nó xảy ra

riêng, thể hiện độ liên quan của chúng đối với chủ đề của tài liệu. Thông

quá thường xuyên trong tập tài liệu của ta (từ quá thường xuyên ở đây

thường, nếu một term xuất hiện càng nhiều lần trong một tài liệu và ít xuất

có nghĩa là nó xuất hiện vượt quá một ngưỡng qui định của ta, ví dụ

hiện hơn trong các tài liệu khác của tập hợp thì nó càng là ký hiệu mô tả tốt

như có mặt trên 80% số lượng File, hoặc trên 200 file), quá trình này

hơn cho tài liệu đó. Những tiêu chí khác như vị trí của từ khóa, phần lôgíc mà

Trần Thị Hoàng Thảo

Luận văn thạc sĩ


Trần Thị Hoàng Thảo

Luận văn thạc sĩ


19

20

Truy xuất thông tin

Truy xuất thông tin

từ đó nó đã được chắt lọc hoặc độ dài của tài liệu có thể được dùng để tính

1.2.2. Giai đoạn thu thập

toán trọng số của khái niệm liên quan trong tài liệu.

1.2.2.1. Xử lý truy vấn
Nhu cầu thông tin của người dùng được phát biểu bằng một yêu cầu

1.2.1.2. Lập chỉ mục
Bước lập chỉ mục sử dụng các term mô tả khung nhìn lôgíc của các tài

(request), là đầu vào của hệ thống IR. Một yêu cầu có thể được viết ở dạng

liệu để xây dựng chỉ mục. Như trên đã nêu, cấu trúc chỉ mục phổ biến nhất là

ngôn ngữ tự nhiên, là một tập các từ khóa với từ vựng giới hạn, hoặc có thể


Inverted Files, trong đó tập tài liệu được biến đổi thành một tập các term kèm

được phát biểu với các toán tử Boolean. Bước lấy yêu cầu là bước quan trọng

theo một danh sách tương ứng các tài liệu mà chúng xuất hiện. Trong một

trong quá trình truy xuất. Hệ thống IR có cách biểu diễn bên trong của riêng

Inverted File, mỗi term trỏ tới một danh sách tất cả các tài liệu mà nó xuất

nó đối với yêu cầu.

hiện. Cấu trúc chỉ mục như vậy đóng vai trò rất quan trọng vì nó "cho phép

Ở bước đầu trong giai đoạn truy xuất, hệ thống IR thực hiện các thao
tác xử lý đối với truy vấn của người dùng tương tự như đối với các tài liệu

tìm kiếm nhanh trên tập dữ liệu lớn" [1] .
Quy trình này có thể được thực hiện thủ công (đòi hỏi sức người nên

ban đầu trong quá trình tiền xử lý. Các thao tác xử lý văn bản là những

rất tốn kém) hoặc tự động bằng cách tách các term từ văn bản của phần tử

phương thức chính được dùng để biểu diễn những nhu cầu của người dùng, và

thông tin, sử dụng một thủ tục dựa trên thông kê hoặc ngôn ngữ.

đây là điểm khác biệt chủ yếu của truy xuất thông tin với truy xuất dữ liệu


Một số term có thể biểu diễn tốt hơn chủ đề của tài liệu. Do đó, mỗi

(trong truy xuất dữ liệu không có thao tác xử lý lôgíc đối với truy vấn ban đầu

term có thể được gán một trọng số thể hiện tầm quan trọng của nó trong tài

trước khi thực hiện tìm kiếm). Kết quả nhận được là một danh sách các từ, đó

liệu. Như vậy, cấu trúc chỉ mục bao gồm một tập các term đã được xử lý, kèm

chính là biểu diễn bên trong của nhu cầu thông tin của người dùng.

theo một danh sách các tài liệu chứa chúng và trọng số của chúng. Trọng số
của một term trong một tài liệu có thể chỉ đơn giản là số lần xuất hiện của

1.2.2.2. Tìm kiếm
Trong giai đoạn tìm kiếm, mỗi term thu được từ thao tác xử lý văn bản

chúng trong tài liệu. Tần số càng lớn thì tầm quan trọng của nó càng lớn. Điều

được dùng để xác định, thông qua tập chỉ mục, một danh sách các tài liệu mà

này được gọi là gán trọng số theo tần số từ (term frequency weighting – tf).

trong đó nó xuất hiện. Nếu có nhiều từ xuất hiện trong truy vấn thì bước tìm

Số lượng tài liệu mà một term xuất hiện trong đó cũng có thể được sử dụng

kiếm sẽ trả về hợp của các tài liệu thu thập được theo tất cả các từ hoặc một


làm yếu tố trong việc gán trọng số. Một term xuất hiện trong càng nhiều tài

số từ, tùy theo kiểu truy vấn. Tóm lại, tìm kiếm là quá trình đối sánh

liệu thì khả năng phân biệt của nó đối với càng tài liệu càng kém. Điều này

(matching) các term trong các tài liệu với các term trong truy vấn.

gọi là tần số tài liệu đảo ngược (inverse document frequency – idf). Lược đồ

Cụ thể, hệ thống IR thực hiện đối sánh giữa truy vấn với từng biểu diễn

gán trọng số tf-idf được sử dụng phổ biến trong các hệ thống truy xuất văn

của tài liệu để đánh giá độ liên quan của nó với nhu cầu thông tin. Kết quả đối

bản.

sánh có thể là phù hợp tuyệt đối hoặc một phần, nhưng do tính không rõ ràng
vốn có của quá trình truy xuất nên phù hợp một phần ngày càng được ưa

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Trần Thị Hoàng Thảo

Luận văn thạc sĩ



21

22

Truy xuất thông tin

chuộng hơn, do vậy đối sánh tuyệt đối không được xét trong luận văn. Trong
trường hợp đối sánh một phần, các tài liệu thường được chuyển tới người
dùng theo thứ tự giảm dần của độ liên quan. Mục đích của việc đối sánh một
phần là để trình bày các tài liệu có liên quan với nhu cầu thông tin ở phần đầu

Truy xuất thông tin

1.3. Các hướng tiếp cận giải quyết bài toán truy xuất
thông tin
Nhìn chung, có hai loại nghiên cứu và kỹ thuật chính trong IR là : dựa
trên ngữ nghĩa (semantic) và dựa trên thống kê (statistical) [3] . Các hướng
tiếp cận dựa trên ngữ nghĩa thực hiện việc phân tích ngữ nghĩa và cú pháp ở

tiên trong danh sách được xếp hạng.

một mức độ nào đó; nói cách khác là mô phỏng khả năng hiểu văn bản ngôn
1.2.2.3. Xếp hạng
Cuối cùng, mọi tài liệu thu thập được sẽ được đánh giá theo độ liên
quan của chúng đối với truy vấn. Thông thường, đánh giá này phụ thuộc vào
một giải thuật xếp hạng, giải thuật này tính toán ra kết quả là một con số thực
cho từng tài liệu. Tài liệu ứng với một số giá trị càng lớn thì càng được xem là
có khả năng liên quan nhiều hơn. Tiếp theo, các tài liệu được thu thập sẽ được
trả về theo thứ tự giảm dần theo kết quả của giải thuật xếp hạng. Nhờ vậy,

người dùng có cơ hội để xem xét kỹ hơn các tài liệu liên quan nhất, nằm ở
phần trên trong thứ tự sắp xếp, so với các tài liệu không liên quan. Do đó, giải
thuật xếp hạng được xem là phần cốt yếu của một hệ thống IR.

ngữ tự nhiên mà một người dùng có thể đưa ra ở một mức nào đó (có thể là
rất khiêm tốn). Trong các hướng tiếp cận dựa trên thống kê, các tài liệu được
thu thập hay được xếp hạng cao là những tài liệu phù hợp nhất với truy vấn
theo một số độ đo thống kê. Trong luận văn, chúng tôi tập trung vào các
hướng giải quyết bài toán IR dựa trên thống kê.
Các hướng tiếp cận dựa trên thống kê được chia thành ba loại là: mô
hình truy xuất Boolean (Boolean Retrieval Model), mô hình không gian véctơ
(Vector Space Model) và mô hình xác suất (Probabilistic Model). Truy xuất
Boolean dựa trên lôgíc mệnh đề (propositional). Trong mô hình không gian
véctơ, các tài liệu và các truy vấn được biểu diễn dưới dạng các véctơ trong
không gian các từ khoá được đánh chỉ mục và sự tương quan giữa một tài liệu

1.2.2.4. Phản hồi về độ liên quan
Như trên đã nêu, quá trình truy xuất có thể lặp đi lặp lại, nếu hệ thống

đối với một truy vấn được tính bằng khoảng cách hình học giữa chúng. Trong

IR nhận được phản hồi của người dùng, ví dụ như đánh giá về độ liên quan

mô hình xác suất, xác suất mà một tài liệu có liên quan với một truy vấn được

của các tài liệu được xếp hạng cao nhất. Thông tin này có thể được dùng để

tính bằng cách phát triển các giả định về sự phân bố của các từ khoá trong các

cải thiện biểu diễn của nhu cầu thông tin, và tính được kết quả xếp hạng tốt


tài liệu có liên quan và không liên quan trong chỉ mục.

hơn cho các tài liệu. Chẳng hạn, các phần tử xuất hiện trong các phần tử được
thu thập trước đó, đã được xác định là có liên quan với truy vấn của người
dùng, được bổ sung vào truy vấn ban đầu. Quá trình này được gọi là phản hồi
về độ liên quan, rất có ích để cải thiện hiệu quả truy xuất. Tuy nhiên, trong
luận văn, chúng tôi không xem xét quá trình này.

1.4. Đánh giá hiệu quả truy xuất thông tin
Như trên đã nêu, vì các hệ thống IR phải xử lý nhu cầu thông tin được
mô tả một cách gần đúng của người dùng nên kết quả của một quá trình truy
xuất thông tin không phù hợp tuyệt đối với nhu cầu thông tin, mà được xếp
hạng theo độ liên quan. Việc đánh giá độ chính xác của kết quả được gọi là
đánh giá truy xuất thông tin. Bên cạnh những độ đo hiệu suất quan trọng của

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Trần Thị Hoàng Thảo

Luận văn thạc sĩ


23

24

Truy xuất thông tin


phần mềm nói chung thì hiệu suất truy xuất là vấn đề then chốt của một hệ
thống IR.

Truy xuất thông tin

Nhược điểm của hai độ đo này là thực tế thì việc kiểm tra tất cả các tài
liệu của tập kết quả là không có thật. Tuy nhiên, điều này đối lập với thực tiễn

Việc đánh giá IR được thực hiện bằng cách truy vấn một tập hợp tham

sử dụng, trong đó người dùng chỉ xem một phần của tập tài liệu đã thu thập,

khảo đã chuẩn hóa. Những tập tham khảo này gồm một tập các tài liệu, một

xếp hạng theo độ liên quan. Do đó, các giá trị độ chính xác và độ bao phủ

tập các yêu cầu thông tin ví dụ và các tập hợp tài liệu có liên quan tương ứng.

biến đổi khi người dùng tiến hành kiểm tra các tài liệu được thu thập. Cách

Những tài liệu có liên quan ứng với các yêu cầu thông tin mẫu được xác định

thức phổ biến để biểu diễn sự biến đổi đó, nói cách khác là biểu diễn hiệu quả

bởi chuyên gia.

truy xuất là sử dụng đồ thị độ bao phủ-độ chính xác [22] , trong đó độ chính

Đối với một chiến lược thu thập đã biết, các tài liệu được thu thập sẽ


xác P(r) ứng với các giá trị khác nhau của độ bao phủ, r.

được so sánh với tập các tài liệu có liên quan, đã được xác định bởi chuyên

Để vẽ đồ thị đó, độ chính xác được tính dựa trên 11 mức chuẩn của độ

gia. Độ tương tự giữa hai tập được định lượng bằng tiêu chuẩn đánh giá của

bao phủ là 0%, 10%, 20%,... 100%. Ví dụ, độ chính xác của các tài liệu được

tập kiểm tra và được xem là chất lượng của chiến lược IR đang xét.

thu thập được tính tới khi hệ thống IR trả về 10% số lượng các tài liệu có liên
quan. Nếu đạt tới độ bao phủ 10% với tài liệu thứ hai của tập tài liệu được thu

1.4.1. Độ chính xác và độ bao phủ
Hiệu quả của một hệ thống IR thể hiện khả năng đáp ứng của kết quả
truy xuất đối với một yêu cầu thông tin. Các độ đo hiệu quả truy xuất phổ
biến là độ chính xác (precision) và độ bao phủ (recall) [23] [25] . Cả hai độ
đo đều dựa trên các đánh giá của người dùng theo quá trình truy xuất. Độ

thập thì độ chính xác ứng với mức này sẽ là 50%. Đối với mức bao phủ 0%,
độ chính xác đạt được thông qua một thủ tục nội suy. Mức bao phủ của một
yêu cầu ví dụ có thể khác với 11 mức bao phủ chuẩn, khi đó cũng cần phải sử
dụng thủ tục nội suy nhưng cách này ít được dùng để đánh giá hệ thống IR.

chính xác (P) là tỷ lệ tài liệu được thu thập có liên quan, nó cho biết khả năng
thu thập những tài liệu được xếp hạng trên cùng mà phần lớn là có liên quan.
Độ bao phủ (R) là tỷ lệ tài liệu có liên quan được thu thập, nó cho biết khả

năng tìm kiếm tất cả các tài liệu có liên quan trong tập hợp. P và R lần lượt
được tính theo công thức (1-1 và (1-2 :
A
B
A
R=
C

(1-1)

P=

(1-2)

trong đó, A là số lượng tài liệu có liên quan được thu thập, B là số
lượng tài liệu được thu thập và C là số lượng tài liệu thực sự có liên quan.
Hình 1-7 Ví dụ đồ thị độ chính xác-độ bao phủ trung bình

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Trần Thị Hoàng Thảo

Luận văn thạc sĩ


25

26


Truy xuất thông tin

Các giá trị độ chính xác và độ bao phủ, kết quả của việc tính trung bình
nhiều truy vấn, thường được dùng để so sánh hiệu suất của các hệ thống IR.

Truy xuất thông tin

ích để quan sát hoạt động của một chiến lược truy xuất đối với từng truy vấn
trong tập kiểm tra.
Để so sánh hai giải thuật, có thể sử dụng biểu đồ độ chính xác. Biểu đồ

Những đồ thị độ chính xác-độ bao phủ trung bình như vậy mang lại cái nhìn

độ chính xác là một biểu đồ R-Precision đối với nhiều truy vấn.

tốt hơn cho hiệu quả truy xuất tổng thể.

RPA / B (i ) = RPA (i ) − RPB (i )

(1-3)

1.4.2. Độ chính xác trung bình
Thông thường, trong một hệ thống IR, độ chính xác quan trọng hơn độ
bao phủ nếu như người dùng muốn tìm câu trả lời cho một truy vấn chứ
không phải tất cả các câu trả lời có thể có. Độ bao phủ có thể quan trọng khi
người dùng cần biết tất cả các thông tin có liên quan về một chủ đề. Trong các
hệ thống IR thông thường, độ bao phủ có thể được tăng lên khi số lượng các
phần tử được thu thập tăng lên, trong khi đó độ chính xác lại có khả năng
giảm đi. Vì lý do này, các kỹ thuật cải thiện độ bao phủ sẽ tác động tới độ

chính xác và ngược lại. Cần phải có sự cân bằng giữa các kỹ thuật đó để điều
chỉnh hiệu quả truy xuất.
Thực tế, độ chính xác và độ bao phủ không đủ để đánh giá các hệ thống
IR. Ví dụ, nếu có hai hệ thống, mỗi hệ thống thu thập được 10 tài liêu, 5 tài
liệu có liên quan và 5 tài liệu không liên quan, nhưng cả hai đều có độ chính
xác là 0.5, nhưng một hệ thống có 5 tài liệu đầu tiên có liên quan và 5 tài liệu
tiếp theo không liên quan thì tốt hơn một hệ thống có 5 tài liệu đầu tiên không
liên quan và 5 tài liệu tiếp theo có liên quan (bởi lẽ người dùng sẽ không hài

trong đó, RPA (i) và RPB (i ) lần lượt là các giá trị R-Precision của giải
thuật truy xuất A và B đối với truy vấn thứ i.
• RPA/B = 0: cả hai giải thuật đều có hiệu quả truy xuất ngang nhau đối
với truy vấn thứ i.
• RPA/B > 0: giải thuật A có hiệu quả truy xuất tốt hơn đối với truy vấn
thứ i.
• RPA/B <0: giải thuật B có hiệu quả truy xuất tốt hơn đối với truy vấn
thứ i.
Độ đo được sử dụng phổ biến nhất là độ chính xác trung bình (mean
average precision – MAP). Độ đo MAP tính độ chính xác tại mỗi điểm trong
bảng xếp hạng mà ở đó tìm thấy một tài liệu có liên quan, sau đó lấy trung
bình của các giá trị đó (và cuối cùng là trung bình đối với tất cả các truy vấn).

1.4.3. Độ đo F và độ đo E
Độ đo F (F-measure) kết hợp độ chính xác và độ bao phủ để lấy trung
bình điều hòa của chúng.

lòng nếu phải kiểm tra những tài liệu không liên quan trước). Do đó, cần có
những phép đo kết hợp độ chính xác và độ bao phủ có xét tới thứ tự các tài
liệu được thu thập.


Trong đó r(j) là độ bao phủ và P(j) là độ chính xác của tài liệu thứ i

Một hướng tiếp cận là sử dụng độ đo R-Precision. Cách tiếp cận này sử

trong tập hợp. Các giá trị của F(j) nằm trong khoảng [0,1], bằng 0 nếu không

dụng độ chính xác thứ R trong bảng xếp hạng các kết quả ứng với một truy

có tài liệu có liên quan nào được thu thập và bằng 1 nếu tất cả các tài liệu

vấn, với R là tổng số các tài liệu có liên quan đã biết. Giá trị thu được có lợi

được thu thập đều có liên quan. Hơn nữa, F(j) nhận giá trị cao khi và chỉ khi

Trần Thị Hoàng Thảo

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Luận văn thạc sĩ


27

28

Truy xuất thông tin

Truy xuất thông tin


cả độ chính xác và độ bao phủ đều cao, điều này biểu thị sự cân bằng tốt giữa

IR khác nhau đối với cùng một tập hợp sử dụng cùng truy vấn, sau đó kết hợp

độ chính xác và độ bao phủ.

tất cả các tài liệu có liên quan và thực hiện đánh giá độ liên quan dựa trên tập

Độ đo E (E-measure) là sự khái quát của độ đo F, cho phép nhấn mạnh
độ chính xác so với độ bao phủ hoặc ngược lại.

này.

1.4.4. Các tiếp cận đánh giá lấy người dùng làm trung tâm
Những hướng đánh giá đã nêu đều dựa trên giả thiết rằng tập các tài
liệu có liên quan đối với một truy vấn không phụ thuộc vào người dùng. Tuy

Tham số b do người dùng xác định phản ánh độ quan trọng của độ

nhiên, những người dùng khác nhau, chẳng hạn có trình độ tri thức khác nhau,

chính xác và độ bao phủ. Với giá trị tham số b = 1, độ đo E bằng với độ đo F

có thể có quan điểm khác nhau về những tài liệu có liên quan đối với nhu cầu

(độ chính xác và độ bao phủ được có trọng số ngang nhau). Giá trị b > 1 biểu

thông tin của họ. Để giải quyết yêu cầu đánh giá hiệu suất liên quan tới nhu


thị rằng độ chính xác có trọng số lớn hơn, trong khi đó nếu b < 1 thì nghĩa là

cầu của người dùng, một số phương pháp đã được đưa ra.
Tỷ lệ mới (novelty ratio) là tỷ lệ các tài liệu được thu thập và đánh giá

độ bao phủ có trọng số lớn hơn.
Hình 1-8 thể hiện sự phân bố của các tài liệu được thu thập đối với các
tài liệu có liên quan. Ở phía trái của hình, phần giao giữa hai hình tròn là phần

là có liên quan bởi người dùng mà họ không biết về chúng trước đó; nó đo
khả năng tìm kiếm thông tin mới về một chủ đề.

mà một hệ thống IR cần được cực đại hóa. Ở phía phải, số lượng các tài liệu

Tỷ lệ bao phủ (coverage ratio) là tỷ lệ những tài liệu có liên quan được

cần được cực đại hóa nằm ở góc dưới bên trái và góc trên bên phải. Hai góc

thu thập mà người dùng đã biết trước khi tìm kiếm trên tổng số các tài liệu có

còn lại sẽ mang giá trị 0 trong một hệ thống IR lý tưởng.

liên quan. Độ đo này có ích khi người dùng muốn xác định những tài liệu mà

Toàn bộ tập
tài liệu
Các tài liệu
có liên quan

Các tài

liệu được
thu thập

không được thu thập
liên và không liên
quan
quan
có
liên được thu thập
và có liên quan
quan
được thu thập

không được thu thập
và không liên quan

họ đã thấy trước đó.
Sự nỗ lực của người dùng (user effort) đo khối lượng công việc người
dùng cần thực hiện để phát biểu các truy vấn, theo dõi việc tìm kiếm và xem

không được thu thập
nhưng có liên quan

không được thu thập

xét đầu ra.
Thời gian đáp ứng (response time) là khoảng thời gian tính từ lúc nhận
truy vấn của người dùng tới lúc hệ thống đưa ra kết quả.

Hình 1-8 Các tài liệu được thu thập so với các tài liệu có liên quan (nguồn: [5]

Đối với các tập văn bản lớn trên Web, rất khó để tìm tổng số các tài
liệu có liên quan. Trong những trường hợp như vậy, một giải pháp là lấy mẫu
trên tập hợp và thực hiện đánh giá độ liên quan dựa trên các tài liệu mẫu. Một

Hình thức trình bày (form of presentation) là tầm ảnh hưởng của hình
thức đầu ra đối với khả năng sử dụng các tài liệu thu thập được của người
dùng.
Độ bao phủ tập hợp (collection coverage) đo quy mô chứa bất kỳ/tất cả

ý tưởng khác là áp dụng các giải thuật truy xuất khác nhau hoặc các hệ thống

các phần tử có liên quan trong tập tài liệu.

Trần Thị Hoàng Thảo

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Luận văn thạc sĩ


29

30

Truy xuất thông tin

1.5. Một số hệ thống truy xuất thông tin


5

Hiện nay, có rất nhiều hệ thống truy xuất thông tin phục vụ tìm kiếm

4.5

4

của các cá nhân hoặc tổ chức cũng đang gia tăng. Đáp ứng với nhu cầu đó,
một thế hệ các công cụ tìm kiếm trên máy tính mới đang phát triển mạnh mẽ.
Trong luận văn, chúng tôi sẽ xây dựng thử nghiệm một hệ thống truy xuất

Kết quả đánh giá tính chính xác

kiếm trên web như Google, AltaVista đã và đang rất phổ biến. Bên cạnh đó,
nhu cầu tìm kiếm thông tin trên một máy tính hoặc trên một mạng máy tính

4.5
4.2

thông tin trên máy tính và trên mạng Internet hoặc Intranet. Các hệ thống tìm

thông tin cho phép tìm kiếm dựa trên các tài liệu mang nội dung tiếng Anh có

3.5

3.5
3.2

3.2


2.8
2.6

2.2

1.5

0.5

của UW E-Business Corsontium năm 2005 [8] . UW E-Business Corsontium

0
1

2

3

4

tiêu chí con có liên quan tới mục tiêu của tiêu chí chính. Chúng tôi chỉ xem

8

9

10

11


12

4.4

4.5
4.2

• Tính chính xác: tiêu chí này đánh giá tính chính xác của kết quả tìm

4

kiếm cũng như những nhân tố giúp cho người dùng tìm thấy thông tin

Chúng tôi vẽ biểu đồ so sánh tính chính xác (Hình 1-9), biểu đồ so sánh

7

5

xét hai tiêu chí là tính chính xác và tính hiệu quả:

suất hoạt động của máy tính.

6

Hình 1-9 Biểu đồ so sánh tính chính xác của một số hệ thống IR

trong khoảng từ 1 (kém nhất) tới 5 (tốt nhất), việc cho điểm được dựa trên các


3.8
3.6

3.6
Kết quả đánh giá tính hiệu quả

chỉ mục. Công cụ tốt nhất là công cụ không gây ảnh hưởng tới hiệu

5

Các hệ thống tìm kiếm trên máy tính

thực hiện đánh giá các hệ thống theo sáu tiêu chí, mỗi tiêu chí được chi điểm

bao gồm việc sửa dụng bộ nhớ, thời gian lập chỉ mục hay kích thước

2.6
2.4

2

một số ứng dụng tìm kiếm thống tin trên máy tính dựa vào kết quả đánh giá

• Tính hiệu quả: tiêu chí này đánh giá hiệu quả về kỹ thuật của công cụ

3.2

2.5

1


mong muốn.

3.2

3

trong một máy tính. Vì vậy, trong mục này chúng tôi sẽ trình bày và so sánh

3.5

3.4

3.33

3.4

3

3

3

2.5
2

2

1.8


1.5

1

tính hiệu quả (Hình 1-10) và biểu đồ so sánh tổng thể (Hình 1-11) của 12 hệ

0.5

thống tìm kiếm trên máy tính. Trong đó, các hệ thống được đánh số từ 1 đến

0
1

2

3

4

5

6

7

8

9

10


11

12

Các hệ thống tìm kiếm trên máy tính

12 như trong Bảng 1-1.

Trần Thị Hoàng Thảo

Truy xuất thông tin

Hình 1-10 Biểu đồ so sánh tính hiệu quả của một số hệ thống IR

Luận văn thạc sĩ

Trần Thị Hoàng Thảo

Luận văn thạc sĩ


31

5
4.5

Truy xuất thông tin

Sau đây, chúng tôi trình bày các hệ thống theo thứ tự giảm dần của kết

4.35
3.9

4
Kết quả đánh giá

32

Truy xuất thông tin

3.8

3.5

quả đánh giá tổng thể.
3.5

3.4 3.265 3.25

3

3

Copernic Desktop Search được đánh giá là công cụ tìm kiếm trên máy
2.9

2.9

tính tốt nhất. Copernic rất dễ sử dụng và cho hiệu quả tìm kiếm, sắp xếp kết
2.2


2.5

2.1

2
1.5

quả trả về cao. Copernic có khả năng lập chỉ mục động, nghĩa là cập nhật chỉ
mục theo mỗi sự biến đổi của các tệp tài liệu. Theo kết quả đánh giá,

1

Copernic được điểm cao nhất về tính chính xác và đứng thứ hai về tính hiệu

0.5
0
1

2

3

4

5

6

7


8

9

10

11

12

MSN Toolbar Suite chỉ đứng sau Copernic về tính chính xác và được

Các hệ thống tìm kiếm trên máy tính

Hình 1-11 Biểu đồ so sánh một số hệ thống IR
Bảng 1-1 Số thứ tự các hệ thống trong biểu đồ
Số thứ tự

Hệ thống IR

quả.

Phiên bản

điểm khá cao về tính hiệu quả. Có một nhược điểm là nó không hỗ trợ các tệp
định dạng PDF. Để có thể lập chỉ mục các tệp PDF, người dùng phải cài đặt
công cụ IFilter.
Likasoft Archivarius 3000 được đánh già là có hiệu quả hoạt động cao
nhất và tính chính xác khá cao. Nó cho thời gian lập chỉ mục lần đầu nhanh


1

Copernic Desktop Search

1.5 Beta

2

MSN Toolbar Suite

2.0 Beta

nhất trong số các hệ thống được xét và việc sử dụng bộ nhớ gần như rất thấp

3

Likasoft Archivarius 3000

3.14

khi không phải hoạt động nhiều. Nó hỗ trợ tìm kiếm thư điện tử với khả năng

4

Ask Jeeves

1

tương thích rộng rãi, từ Outlook và Outlook Express tới Eudora, Thunderbird


5

Yahoo! Desktop Search

1.1 Beta

và Lotus Notes/Domino. Đặc biệt, nó có chức năng tìm kiếm từ xa, ứng dụng

6

Google Desktop

1

hoạt động như một máy chủ Web nhỏ, cho phép người dùng tìm kiếm thông

7

dtSearch Desktop

6.5

tin trong máy tính thông qua trình duyệt web. Tuy nhiên, nó không hỗ trợ lập

8

diskMETA Pro

1.0.1


chỉ mục các tệp ảnh hay âm thanh.

9

Enfish Professional

6.1

10

ISYS Desktop

6

11

Blinkx

3

12

HotBot Desktop

Beta

Ask Jeeves là ứng dụng rất nhỏ và hiệu quả, tính hiệu quả được đánh
giá là chỉ đứng sau Likasoft Archivarius 3000 và Copernic. Tuy nhiên, phần
hỗ trợ định dạng tệp tài liệu còn hạn chế, nó không hỗ trợ các tệp dạng ảnh và

âm thanh.
Yahoo Desktop Search có thể lập chỉ mục nội dung lưu lại của
chương trình tin nhắn Yahoo Messenger, các file ảnh. Yahoo chỉ đứng sau

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Trần Thị Hoàng Thảo

Luận văn thạc sĩ


33

34

Truy xuất thông tin

Truy xuất thông tin

Copernic về tính hiệu quả và được điểm khá cao về tính chính xác. Tuy nhiên,

Blinkx có độ chính xác trên mức trung bình nhưng rất hạn chế về tính

Yahoo không hỗ trợ lập chỉ mục động và sắp xếp kết quả trả về theo độ liên

hiệu quả. Thời gian lập chỉ mục của nó rất lớn. Blinkx chiếm một phần đáng

quan.


kể bộ nhớ. Do đó, thời gian tìm kiếm cũng rất chậm.
Google Desktop là sản phẩm tìm kiếm trên máy tính rất dễ sử dụng của

HotBot Desktop là một hệ thống nhỏ gọn và có một số tính năng riêng.

Google, có giao diện tương tự hệ thống tìm kiếm trên Web của Google.

Nó cho phép người dùng liên kết các từ khoá với trang web tuỳ ý (chẳng hạn

Google Desktop được đánh giá là có tính chính xác đứng thứ 4 và tính hiệu

“eb <từ khoá>” để tìm kiếm trên trang web www.ebay.com). Nhưng giao diện

quả đứng thứ 6.

của nó phức tạp, khó sử dụng. HotBot Desktop được đánh giá thấp nhất cả về

dtSearch Desktop được đánh giá cao về tính chính xác. Nó hỗ trợ tìm
kiếm mờ và theo ngữ âm, các từ khoá ký tự đại diện và boolean, phân biệt
chữa hoa chữ thường khi lập chỉ mục. Nó có hai nhược điểm nổi bật là giao
diện khó sử dụng và tệp chỉ mục chứa nhiều phần tử không phải là ký tự do
bộ lập chỉ mục coi hầu hết các tệp nhị phân đều là tệp văn bản.
diskMETA Pro là chương trình đơn giản nhất nhưng kèm theo sự hạn
chế về chức năng. Nó không hỗ trợ tìm kiếm thư điện tử. Việc sắp xếp kết quả
tìm kiếm cũng hạn chế. Tuy vậy, diskMETA Pro có tính chính xác rất cao. Nó
có tính năng từ điển có thể xác định một từ, chẳng hạn như “criterion” từ một
từ khoá “criteria”, đây là tính năng mà hầu hết các công cụ tìm kiếm trên máy
tính khác không có.
Enfish Professional có hiệu quả hoạt động khá cao. Nó cho phép

người dùng tuỳ biến giao diện. Nhưng độ chính xác của Enfish Professional
không cao.

tính chính xác và tính hiệu quả.

1.6. Kết chương
Trong chương này, chúng tôi đã trình bày tổng quan về truy xuất thông
tin. Quá trình truy xuất thông tin bao gồm hai giai đoạn là tiền xử lý tài liệu
và tìm kiếm thông tin theo yêu cầu của người dùng trong tập tài liệu đã xử lý.
Trong đó, quan trọng nhất là bước lập chỉ mục tài liệu và sắp xếp độ liên quan
của từng tài liệu đối với yêu cầu tìm kiếm. Để đánh giá hiệu quả truy xuất
thông tin, có thể áp dụng nhiều độ đo, bao gồm các tiếp cận hướng hệ thống
và các tiếp cận lấy người dùng làm trung tâm. Trong những chương tiếp theo,
chúng tôi sẽ đi sâu vào lập chỉ mục và các hướng tiếp cận truy xuất thông tin.
Tiếp đó, chúng tôi sẽ trình bày cơ chế lập chỉ mục và tìm kiếm của thư viện
mã nguồn mở Lucene. Cuối cùng là kết quả xây dựng chương trình thử
nghiệm dựa trên Lucene.

ISYS Desktop là một hệ thống linh hoạt. Nó hỗ trợ lập chỉ mục nhiều
ngôn ngữ, hỗ trợ nhiều ứng dụng thư điện tử như Compuserve, Eudora và
VIM. Nó cũng có ưu điểm trong việc tăng cường tính chính xác của việc tìm
kiếm. Nó có bộ kiểm tra chính tả, tìm kiếm lôgíc mờ và định dạng ngày tháng
thông minh (chẳng hạn tìm “1/1/05” từ “Jan. 1, 2005”). Nhưng giao diện của
nó quá phức tạp và khó sử dụng.

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Trần Thị Hoàng Thảo


Luận văn thạc sĩ


35

36

Truy xuất thông tin

Truy xuất thông tin

CHƯƠNG 2. CÁC CÔNG CỤ TRUY XUẤT THÔNG TIN CƠ

đồ gán trọng số này được gọi là tần số term và ký hiệu là tft,d, với phần chỉ số

BẢN

dưới biểu thị cho term và tài liệu. Tuy nhiên, nếu có n thể hiện của một term

Trong chương này, chúng tôi trình bày về các công cụ truy xuất thông
tin quan trọng là lập chỉ mục và sắp xếp kết quả tìm kiếm. Đối với lập chỉ
mục, chúng tôi trình bày và so sánh hai cấu trúc chỉ mục là Signature Files và
Inverted Files. Về xếp hạng tập tài liệu trả về, chúng tôi trình bày và so sánh
một số mô hình truy xuất thông tin dựa trên thống kê, gồm ba loại: các mô

trong một tài liệu thì cũng không thực sự có nghĩa là tài liệu đó có tầm quan
trọng gấp n lần so với một tài liệu khác chỉ chứa một thể hiện của term đó. Do
vậy, đã có những nghiên cứu đáng chú ý tập trung vào các hàm trọng số thay
vì dựa vào số lượng các thể hiện của một term. Trong đó, hàm loga khá phổ

biến, hàm này gán trọng số theo công thức:
(2-1)

hình lôgíc, các mô hình đại số và các mô hình xác suất.

2.1. Lập chỉ mục

wft,d =

1 + log tf t ,d

tf t,d > 0

0

nếu tft,d <= 0

Đối với một tài liệu d, tập các trọng số (xác định bởi các hàm gán trọng
số tf hoặc wf nêu trên, hay bất kỳ hàm gán trọng số nào có ánh xạ số lượng

2.1.1.1. Gán trọng số
Trong mục này, chúng tôi trình bày về tiêu chuẩn đánh giá tầm quan

các thể hiện của t trong d thành một giá trị thực) có thể được xem là một

trọng của một term trong tài liệu nhằm mục đích xếp hạng độ phù hợp của các

véctơ, trong đó mỗi phần tử ứng với từng term phân biệt. Từ góc nhìn của

tài liệu đối với truy vấn có chứa term đó. Một tài liệu càng chứa nhiều term


một tài liệu, được gọi là mô hình túi từ (bag of words mode), thì thứ tự chính

của một truy vấn thì càng có khả năng liên quan tới truy vấn đó. Xét khái

xác của các term trong một tài liệu được bỏ qua. Khung nhìn véctơ chỉ thể

niệm một truy vấn văn bản tự do (free text query): là một truy vấn trong đó

hiện thông tin về số lượng các thể hiện. Do vậy, tài liệu “Mary is quicker than

các term được nhập một cách tự do vào giao diện tìm kiếm mà không có một

John” cũng giống với tài liệu “John is quicker than Mary” theo cách nhìn này.

toán tử tìm kiếm nào (chằng hạn như các toán tử Boolean). Loại truy vấn này,

Tuy nhiên, về mặt trực giác thì hai tài liệu mà các biểu diễn véctơ của chúng

đặc biệt phổ biến trên web, được nhìn nhận đơn giản là một tập các term. Khi

tương tự nhau thì cũng tương tự về mặt nội dung.

đó, một cơ chế tính độ liên quan được sử dụng để tính độ tương tự. Độ tương
tự chính là tổng (trên tất cả các term của truy vấn) của các độ phù hợp giữa
từng term với tài liệu. Độ phù hợp giữa một term với một tài liệu được thể
hiện qua trọng số tf và idf.

Tần số tài liệu - idf


Tần số term dạng thô nêu trên có nhược điểm là tất cả các term đều
được xem là quan trọng ngang nhau khi đánh giá độ liên quan đối với một
truy vấn. Mà thực tế thì có những term có ít hoặc không có vai trò gì trong
việc đánh giá này. Để giải quyết vấn đề này cần có một cơ chế để làm giảm

Tần số term - tf

Thật vậy, mỗi term trong một tài liệu được gán một trọng số, phụ thuộc

ảnh hưởng của một term, nếu nó xuất hiện quá nhiều lần trong bất kỳ tài liệu

vào số lượng các thể hiện của term đó trong tài liệu. Phương pháp đơn giản

nào, đối với quyết định về độ liên quan. Ý tưởng tức thời là giảm các trọng số

nhất là gán trọng số bằng với số lần xuất hiện của term t trong tài liệu d. Lược

của những term có tần suất tập hợp cao: tổng số các thể hiện của một term

Trần Thị Hoàng Thảo

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Luận văn thạc sĩ


37


38

Truy xuất thông tin

Truy xuất thông tin

trong một tập tài liệu. Tuy nhiên, phù hợp hơn cả là sử dụng tần số tài liệu dft,
được định nghĩa là số lượng các tài liệu có chứa term t trong tập tài liệu. Lý
do sử dụng df thay vì cf được minh họa trong
Hình 2-1, trong đó cho thấy tần số tập hợp (cf) và tần số tài liệu (df) có thể rất
khác nhau. Cụ thể là các giá trị cf cho cả ferrari và insurance là tương đối

Hình 2-2 Ví dụ các giá trị idf

bằng nhau nhưng các giá trị df của chúng lại khác nhau đáng kể. Điều này cho
thấy rằng số ít những tài liệu có chứa từ ferrari là có chứa nó với tần số cao,
bởi vậy cf của nó cao nhưng df thì thấp. Về mặt trực giác thì những term như
vậy phải được xử lý một cách khác biệt: số ít các tài liệu có chứa ferrari phải
nhận giá trị tăng độ quan trọng (boost) cao hơn đáng kể so với giá trị tăng độ
quan trọng mà nhiều tài liệu có chứa từ insurance nhận được.

Gán trọng số tf-idf

Kết hợp các biểu thức tần số tf và idf để sinh ra trọng số kết hợp cho
từng term trong mỗi tài liệu. Lược đồ gán trọng số tf-idf gán cho term t một
trọng số trong tài liệu d theo công thức sau:
(2-3)
Như vậy, trọng số tf-idft,d gán cho term t một trọng số trong tài liệu d có
giá trị:
1. lớn nhất khi t xuất hiện nhiều lần trong một số lượng nhỏ tài liệu


Hình 2-1 Tần số tập hợp (cf) và tần số tài liệu (df) thể hiện khác nhau
Tần số tài liệu df của một term được sử dụng để tính trọng số của term

2. thấp hơn khi t xuất hiện ít trong một tài liệu hoặc xuất hiện trong nhiều
tài liệu (vì vậy thể hiện độ liên quan thấp)
3. thấp nhất nếu t xuất hiện trong gần như tất cả các tài liệu.
Cũng có thể thay tf bằng một số hàm khác như hàm wf trong công thức

đó. Ký hiệu tổng số tài liệu trong một tập hợp là N, tần số idf (inverse
document frequency) của một term t được định nghĩa như sau:

(2-3), chẳng hạn:
(2-4)
Như vậy, có thể coi mỗi tài liệu là một véctơ mà mỗi phần tử ứng với

(2-2)

một term, cùng với một trọng số cho từng phần tử được tính theo công thức
Do đó, tần số idf của một term ít xuất hiện thì cao trong khi tần số idf
của một term xuất hiện nhiều sẽ thấp. Hình 2-2 minh họa một ví dụ về idf
trong một tập hợp gồm 1,000,000 tài liệu, trong ví dụ này lôgarit có cơ số 10.

(2-4) hoặc phổ biến hơn là công thức (2-3). Dạng véctơ này đóng vài trò chủ
yếu trong việc tính và xếp hạng độ liên quan.
Có hai kỹ thuật lập chỉ mục chính là : Inverted Files (còn gọi là
Inverted Index) và Signature Files. Trong đó, Inverted Files là kỹ thuật được
sử dụng phổ biến nhất. Sau đây, chúng tôi trình bày và so sánh hai kỹ thuật
lập chỉ mục này.


Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Trần Thị Hoàng Thảo

Luận văn thạc sĩ


39

40

Truy xuất thông tin

2.1.1.2. Signature Files
Signature Files sử dụng phương pháp mã hoá chồng nhau để tạo ra

Truy xuất thông tin

được phương pháp Signature báo là chứa đựng từ tìm kiếm chia cho khối đó
nhưng thực tế không chứa từ tìm kiếm.

nhãn (signature) cho tập tài liệu. Diễn tả cụ thể của phương pháp này đó là

Signature Files là một ma trận nhị phân F x N, để xác xuất False drop

mỗi tài liệu sẽ được chia thành các khối logic, mỗi khối chứa đựng D từ phân

là nhỏ nhất thì mỗi hàng trong ma trận này sẽ chứa đựng khoảng 50% bit 1,


biệt (đây là các từ không nằm trong danh sách từ dừng). Mỗi từ cho ta một

và khi đó Fd = 2 - m .

nhãn từ – kích thước F bít với m bít được thiết lập là 1 còn những bít còn lại

Trong hầu hết các trường hợp ma trận Signature được lưu một cách

là 0. Các nhãn từ được “OR” cùng nhau hình thành nên nhãn khối. Các nhãn

tuần tự theo các hàng, và được gọi là cấu trúc SSF (Sequential Signature

khối nối với nhau tạo ra nhãn tài liệu. Vị trí của m bít được thiết lập là “1”

File).

được quyết định bởi các hàm băm. Có ví dụ tạo nhãn như sau:
Từ

Nhãn

Free

001 000 110 010

text

000 010 101 001


Free text

001 010 111 011

Con trỏ
File

Nhãn F bit
N
Khối
Logic

File văn bản

0 1 ….. 0 1
1
……………..
1

Hình 2-4 Cấu trúc File dạng SSF
Có thể thấy rằng thời gian xử lí đối với phương pháp này là tuyến tính

Hình 2-3 Một ví dụ tạo nhãn với mỗi khối logic có D = 2 từ, kích thước nhãn
F = 12 bit, m = 4 bit
Giả sử nhãn của một khối là B. để kiểm tra một từ có nằm trong tài liệu

với số lượng khoản tin N nằm trong cơ sở dữ liệu, do đó nó sẽ trở nên chậm
chạp đối cơ sở dữ liệu lớn. Vì thế phương pháp Signature chỉ sử dụng tốt
trong một số môi trường như:


không, ta tiến hành xác định nhãn của từ đó, giả sử là W, sau đó thực hiện

• Trên PC nhưng với kích thước dữ liệu trung bình

phép toán logic (W & B) đối với các khối trong tài liệu, nếu (W & B = W) thì

• Trên WORM (Write-Once-Read-Only)

từ có thể nằm trong khối đó.

• Các máy song song

Một khái niệm quan trọng trong Signature Files là xác xuất “false
drop” Fd , đó là xác suất mà phương pháp Signature cho ta những báo động

2.1.1.3. Inverted Files
Signature Files cho phép thu hẹp không gian tìm kiếm nhưng để khẳng

lỗi có nghĩa là từ không nằm trong văn bản nhưng phương pháp này báo từ đó

định chính xác văn bản nào có chứa truy vấn thì vẫn phải thực hiện giải thuật

nằm trong văn bản. Do đó xác suất False drop Fd là xác suất mà một khối

tìm kiếm trực tiếp. Nếu đặt hệ tìm kiếm vào tình huống phải xử lý trên khối
lượng dữ liệu lớn, đồng thời nằm trong một hệ khôi phục thông tin thì thời

Trần Thị Hoàng Thảo

Luận văn thạc sĩ


Trần Thị Hoàng Thảo

Luận văn thạc sĩ


41

42

Truy xuất thông tin

Truy xuất thông tin

gian truy tìm trên cấu trúc dữ liệu Signature Files sẽ quá lớn, không phù hợp

Trong khi truy xuất từ “computer”, trước tiên, nó sẽ được tìm trong tệp

với hoàn cảnh thực tế. Inverted Files là giải pháp trọn vẹn hơn cả về kích

từ điển. Nếu có thì danh sách các posting sẽ được truy nhập và trả về các id

thước kho chỉ mục lẫn tốc độ tìm kiếm.

của những tài liệu tương ứng theo thứ tự giảm dần của trọng số.

Cấu trúc dữ liệu Inverted Files này giúp sử dụng hiệu quả không gian
bộ nhớ đồng thời cho phép tìm kiếm theo từ khoá một cách nhanh chóng. Cấu
trúc này được gọi là chỉ mục đảo (inverted) vì nó dùng các term rút ra từ các
tài liệu đầu vào làm những khoá tìm kiếm thay vì xem các tài liệu là những

thực thể chính. Nói khác đi, thay vì trả lời câu hỏi “những từ nào được chứa
trong tài liệu này ?”, cấu trúc này được tối ưu hoá để đưa ra những câu trả lời
nhanh cho câu hỏi “những tài liệu nào có chứa từ X ?”
Một Inverted File là cơ chế tìm kiếm theo từ (word-oriented) để lập chỉ
mục một tập văn bản nhằm tăng tốc độ tìm kiếm. Một Inverted File thường
gồm một tệp từ điển (dictionary file) và một tệp các posting (postings file).
Một tệp từ điển bình thường chứa một mục ứng với từng term riêng biệt trong
tập tài liệu. Mỗi bản ghi bao gồm chính term đó, tổng số các tài liệu mà nó
xuất hiện, tần số xuất hiện tổng cộng của nó trong toàn bộ tập tài liệu, tần số
idf của nó và một con trỏ trỏ tới bản ghi các posting của nó. Tệp các posting
chứa thông tin về một term trong từng tài liệu mà nó xuất hiện. Thông tin
trong một bản ghi posting thường gồm: (1) tần số (frequency) của term trong
một tài liệu, (2) trọng số của term trong tài liệu, (3) mã tài liệu (document id),
(4) một con trỏ trỏ tới posting tiếp theo của từ đó.
Ví dụ, nếu từ “computer” xuất hiện trong 100 tài liệu của một tập gồm
200 tài liệu thì nó sẽ có một bản ghi trong tệp từ điển. Mỗi bản ghi posting
chứa tần số của từ “computer” trong một tài liệu và trọng số term của từ này
trong tài liệu đó. Trọng số term của nó trong tài liệu thứ j được tính theo công
thức (2-3).

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Hình 2-5 Minh hoạ một Inverted File

Trần Thị Hoàng Thảo

Luận văn thạc sĩ



43

44

Truy xuất thông tin

Truy xuất thông tin

2.2. Xếp hạng

thao tác mô hình hóa có thể ảnh hưởng tới toàn bộ lĩnh vực IR theo

2.2.1. Tổng quan các mô hình truy xuất thông tin

chiều hướng tốt.

2.2.1.1. Sự cần thiết của các mô hình truy xuất thông tin
Bất kỳ mô hình IR nào cũng đặt ra những giả định cơ bản về (1) cách

(3) Các mô hình cũng có thể hữu ích để so sánh các đặc điểm của các
hướng tiếp cận IR khác nhau theo một cách tổng quát. Nếu có thể

thức biểu diễn các tài liệu, (2) cách thức biểu diễn các yêu cầu thông tin và (3)

so sánh các mô hình một cách lý thuyết thay vì thực nghiệm thì sẽ

cách thức đối sánh những biểu diễn đó. Ví dụ, mô hình không gian véctơ giả

giảm được số các thí nghiệm và loại bỏ được những lựa chọn


định rằng mô hình IR có thể được thể hiện ở dạng hình học: các tài liệu và các

không lý giải được về mặt lý thuyết.

yêu cầu thông tin có thể được mô tả như các véctơ, có thể được đối sánh bằng

(4) Mọi tiếp cận IR đều có những giả định cơ bản, thường không rõ

cách tính độ tương tự giữa chúng. Mặc dù IR có truyền thống thực nghiệm

ràng. Các giả định đôi khi sai và nếu vậy thì chúng nên được thay

mạnh mẽ, tầm quan trọng của công việc mang tính lý thuyết trong việc mô

bằng các giả thiết có giá trị hơn.

hình hoá quy trình truy xuất theo phương pháp tính toán ngày càng gia tăng

(5) Một mô hình thường dựa trên một framework lý thuyết được thiết

kể từ thế kỷ 17. Vậy thì những mục tiêu của việc mô hình hoá quy trình IR là

lập tốt. Framework này thường đi kèm với một loạt những kỹ thuật

gì? Sebastiani đã xác định các nguyên nhân sau đây [27] .

nổi tiếng, có thể cung cấp các công cụ đáng tin cậy cho việc thực

(1) Các mô hình là cách nhìn trừu tượng hoá của quy trình truy xuất,


hiện. Ví dụ, các mô hình xác suất mở ra hướng sử dụng các công cụ

độc lập với kiến trúc cụ thể được chọn để lưu trữ dữ liệu, thu thập

thống kê, mô hình không gian véctơ sử dụng tính toán ma trận và

các tài liệu hay nhận và xử lý yêu cầu. Sự trừu tượng hoá dẫn tới sự

hình học, và mô hình lôgíc hướng tới các kỹ thuật suy diễn được

khái quát hoá, một mô hình cung cấp một framework mang tính lý

phát triển khởi đầu cho trí tuệ nhân tạo và lý thuyết cơ sở dữ liệu.

thuyết để suy nghĩ về thao tác của IR. Nhờ vậy, nhiều tiếp cận truy
xuất có thể được mô tả trong một mô hình, và những đặc điểm

2.2.1.2. Phân loại các mô hình truy xuất thông tin
Có ba loại mô hình IR [6] :

chính của một tiếp cận truy xuất trở nên rõ ràng hơn và có thể hiểu

• Các mô hình lôgíc (Logical Models)

rõ hơn.

• Các mô hình không gian véctơ (Vector Space Models)

(2) Các mô hình cung cấp nguyên tắc để phát triển một hệ thống IR.


• Các mô hình xác suất (Probabilistic Models)

Ví dụ, các lý lẽ mang tính lý thuyết có thể được dùng để chứng

Mô hình dựa trên lôgíc nổi tiếng nhất là mô hình truy xuất Boolean.

minh rằng một hệ thống IR nên được xây dựng theo cách này hơn

Truy vấn q có thể được biểu diễn thông qua các term chỉ mục và các toán tử

là cách kia. Ngoài ra, một hệ thống IR có thể được ưa chuộng hơn

đại số Boolean: hội, tuyển và phủ định. Các toán tử lôgíc đó mang ngữ nghĩa

vì nó thể hiện sự khái quát hơn so với các mô hình khác. Do vậy,

lý thuyết tập về mặt trực giác : mỗi term chỉ mục tham chiếu tới một tập các
tài liệu được lập chỉ mục bởi term đó. Toán tử AND giới hạn kết quả truy vấn

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Trần Thị Hoàng Thảo

Luận văn thạc sĩ


45


46

Truy xuất thông tin

Truy xuất thông tin

thành phần giao của hai tập, toán tử OR sinh ra phần hợp nhất và toán tử NOT

dựa trên học máy đó phù hợp với việc lọc hoặc gán nhãn thông tin hơn là truy

cung cấp phần khác nhau giữa các tập. Van Rijsbergen đã trình bày mô hình

xuất thông tin, trong đó bao gồm dữ liệu huấn luyện [6] .

Boolean hơi khác một chút: một tài liệu là có liên quan nếu như truy vấn có
thể được tìm thấy từ tập các term chỉ mục của tài liệu đó sử dụng các luật suy
diễn của phép tính mệnh đề (một tài liệu được biểu diễn bằng công thức mệnh
đề d sẽ được thu thập khi nó thực sự kéo theo q). Tuy nhiên, mô hình truy
xuất này hoàn toàn bỏ qua tính bất định vốn có của IR. Nó là mô hình duy
nhất không dựa trên quan điểm về xếp hạng độ liên quan. Một hàm thu thập

2.2.2. Các mô hình lôgíc
Việc thừa nhận framework lôgíc đã là một hướng đi hấp dẫn cho sự
phát triển của các mô hình IR. Các thuộc tính lý thuyết hoàn toàn xác định
của các mô hình lôgíc cổ điển đã được đón nhận nhưng chúng có những hạn
chế, bởi chúng không có khả năng mô hình hoá tính bất định, một đặc tính
chủ yếu trong bài toán IR.

Boolean sẽ chia tập tài liệu thành hai loại, một loại chứa các tài liệu hỗ trợ

cho truy vấn boolean, chẳng hạn là d → q ; một loại gồm các tài liệu không
hỗ trợ cho công thức boolean. Cả hai loại đều không rõ ràng, không có thứ tự
sắp xếp bên trong.
Trong mô hình không gian véctơ, độ liên quan của một tài liệu d đối
với một truy vấn q được định nghĩa là một phép đo khoảng cách (distance)
trong một không gian nhiều chiều (high-dimensional), bởi vậy các mô hình
không gian véctơ cũng có thể được gọi là các mô hình đại số. Độ đo khoảng
cách thực tế được coi là đơn vị để tính độ đồng dạng (similarity) giữa các truy
vấn và các tài liệu. Để tính được độ đồng dạng này, trước hết cần chiếu các tài
liệu và các truy vấn trong không gian nhiều chiều xác định bởi danh sách các
term chỉ mục.
Các mô hình xác suất cổ điển khai thác sự phân bố khác nhau của các
term trong lớp các tài liệu có liên quan và lớp các tài liệu không liên quan.
Các mô hình này tính các trọng số term truy vấn có quan hệ trực tiếp với tỷ lệ
mà term trong truy vấn xuất hiện trong một tài liệu có liên quan.
Ngoài ba loại mô hình chủ yếu trên, các hệ thống IR cũng có thể dựa
trên mạng nơron hoặc các giải thuật di truyền. Tuy nhiên, các hướng tiếp cận

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

2.2.2.1. Mô hình boolean cổ điển
Mô hình Boolean (Standard Boolean Model) là mô hình truy xuất đơn
giản nhất, được sử dụng trong nhiều hệ thống IR trước đây, mô hình này dựa
trên lý thuyết tập và đại số Bool [16] . Đây là hướng tiếp cận nhị phân, trong
đó các tài liệu được xem là có liên quan (1) hoặc không liên quan (0) tuỳ
thuộc vào việc xuất hiện hay không xuất hiện của term truy vấn trong tài liệu.
Mô hình này sử dụng hệ thống đối sánh chính xác (exact match) trong việc
thu thập và các truy vấn được xây dựng bằng cách kết hợp các term với các

toán tử boolean AND, OR, NOT. Hệ thống trả về tất cả các tài liệu thoả mãn
truy vấn. Khả năng kết hợp các khái niệm trừu tượng (AND) và các từ đồng
nghĩa (OR) của các toán tử Boolean, cùng với thời gian đáp ứng nhanh của
việc tìm kiếm khiến hệ thống IR dựa trên mô hình Boolean trở nên phổ biến.
Tuy đã được sử dụng rộng rãi trong nhiều hệ thống nhưng mô hình
Boolea đã bộc lộ nhiều điểm yếu [21] . Việc truy xuất dựa trên quyết định nhị
phân, một tài liệu hoặc là có liên quan hoặc không liên quan, không có việc
đối sánh một phần ở đây. Mô hình Boolean rất cứng nhắc: AND có nghĩa là
“tất cả”; OR có nghĩa là “bất kỳ”. Các hệ thống Boolean không sử dụng các
trọng số của các term và vì vậy sẽ trả về toàn bộ các tài liệu phù hợp với truy

Trần Thị Hoàng Thảo

Luận văn thạc sĩ


47

48

Truy xuất thông tin

Truy xuất thông tin

vấn dưới dạng một tập không có thứ tự. Hệ quả là người dùng có thể phải

(wildcard) theo phương pháp toán học vững chắc, khiến cho nó trở thành một

thêm hoặc bớt các term hoặc đưa ra cấu trúc truy vấn phức tạp hơn để thu gọn


mô hình mạnh trong các hệ thống truy xuất toàn văn bản.
Tóm lại, mô hình Boolean có những ưu điểm sau:

tập các tài liệu được thu thập về một kích thước có thể kiểm soát được.
Người dùng phải có kiến thức về chủ đề tìm kiếm để cho việc tìm kiếm

• Là mô hình rất đơn giản dựa trên lý thuyết tập.

có hiệu quả, ví dụ như nếu có một từ sai trong một truy vấn có thể khiến cho

• Dễ hiểu và dễ cài đặt.

một tài liệu có liên quan trở thành không liên quan. Ngoài ra, người dùng cần

• Hỗ trợ truy vấn chính xác.

phải có khả năng đặt ra các truy vấn phức tạp, đây là việc không dễ dàng.
Tóm lại, mô hình Boolean cổ điển có những nhược điểm sau:
• Thu thập dựa trên tiêu chuẩn quyết định nhị phân, không có khái niệm
phù hợp một phần. Một tài liệu chỉ có thể được thu thập hoặc không.
• Xây dựng các truy vấn dạng tập hợp thì đơn giản nhưng với các biểu
thức boolean phức tạp thì rất khó.

2.2.2.2. Phương pháp đối sánh ở mức đồng hạng
Một cách để cải thiện những điểm yếu của việc biểu diễn các truy vấn
trong mô hình Boolean là mô hình hoá khả năng liên quan bằng số các phù
hợp ở mức đồng hạng (Coordination Level Matching - CLM). CLM giả định
rằng cả truy vấn và các tài liệu đều được biểu diễn bằng một tập các từ chỉ
mục, như vậy thì truy vấn không có cấu trúc (dạng Boolean) bên trong. Đối


• Kết quả trả về có quá nhiều hoặc quá ít tài liệu.

với CLM, giá trị độ liên quan được định nghĩa là số các term truy vấn không

• Trả về các kết quả không được xếp hạng.

trùng lặp tìm thấy trong tài liệu (thực tế, có thể coi CLM là dạng đơn giản của

Mặc dù có nhiều hạn chế nhưng các mô hình Boolean vẫn còn phổ biến
bởi khả năng điều chỉnh rõ ràng truy vấn. Đây là mô hình dẫn đầu trong các

mô hình không gian véctơ [6] ). Con số này càng lớn thì độ đồng hạng càng
cao.

hệ thống IR thương mại cho tới giữa những năm 1990. Hiện nay, các máy tìm

Hướng tiếp cận này có ưu điểm là tập kết quả được sắp xếp và các tài

kiếm web vẫn sử dụng mô hình này để cho phép nhập truy vấn dạng Boolean.

liệu phù hợp một phần được thu thập, điều này có thể được những người dùng

Ưu điểm của mô hình này là tính trực giác của khái niệm của một tập và ngữ

ít kinh nghiệm ưa thích. Ví dụ, hệ thống IR thương mại Muscat, khẳng định là

nghĩa chính xác của các biểu thức Boolean hình thành nên các truy vấn.

có cơ sở vững chắc dựa trên các mô hình xác suất, đã sử dụng CLM làm tiêu


Thật vậy, thứ nhất, mô hình Boolean đem lại cho người dùng (là
chuyên gia) cảm giác điều khiển hệ thống IR. Người dùng có thể hiểu ngay tại
sao một tài liệu lại được thu thập ứng với một truy vấn. Nếu tập tài liệu kết

chuẩn sắp xếp thứ hai của hệ thống.
Tuy nhiên, các thực nghiệm đánh giá (ví dụ [23] ) cho thấy chất lượng
truy xuất của CLM thấp hơn các mô hình có đánh trọng số term rõ ràng.

quả quá nhỏ hoặc quá lớn thì có thể nhận biết rõ ràng những toán tử nào sẽ
cho một tập kết quả lớn hơn hoặc nhỏ hơn. Thứ hai, mô hình có thể được mở
rộng bằng các toán tử lân cận (proximity) và các toán tử ký tự đại diện

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

2.2.2.3. Phương pháp đối sánh gần gũi (Proximity Matching)
Hầu hết các hệ thống thương mại dựa trên truy xuất Boolean đều có
những tiện ích bổ sung để tăng cường độ chính xác của kết quả truy vấn. Việc

Trần Thị Hoàng Thảo

Luận văn thạc sĩ


49

50

Truy xuất thông tin


Truy xuất thông tin

sử dụng các truy vấn Boolean chuẩn trên các tập tài liệu lớn như WWW là

và cộng sự khẳng định rằng phương pháp này cho các kết quả truy xuất hiệu

không phù hợp vì một truy vấn ngắn thường dẫn tới một tập kết quả khổng lồ.

quả, có thể so sánh với các hệ thống sử dụng thống kê term toàn cục như idf,

Nếu sử dụng phương pháp làm chuẩn truy vấn bằng các thêm các term được

đồng thời thoả mãn việc xếp hạng CLM, vốn được ưa chuộng bởi hầu hết

kết hợp với các toán tử AND thường cho kết quả là một tập rỗng. CLM có thể

người dùng.

giải quyết được phần nào vấn đề nhưng có một phương pháp mạnh hơn là sử
dụng thông tin vị trí của các term chỉ mục. Thông thường, các hệ thống IR sử

2.2.2.4. Các mô hình lý thuyết tập
Các mô hình lý thuyết tập (Set-theoretic) biểu diễn tài liệu dưới dạng

dụng một tệp inverted index của một tập tài liệu. Về cơ bản thì cũng có thể

các tập hợp. Độ tương tự được nhận được từ các phép toán lý thuyết tập thực

ghi lại vị trí của từng term chỉ mục trong một tài liệu. Điều này nghĩa là mỗi


hiện trên các tập đó. Đã có một số đề xuất xây dựng các hệ thống IR trên cơ

thể hiện của một term chỉ mục trong một tài liệu sẽ được ghi lại dưới dạng

sở các mô hình lý thuyết tập nhằm giải quyết vấn đề về tính bất định. Mục

một posting trong chỉ mục, việc này sẽ tăng kích thước chỉ mục lên vài lần.

này sẽ giới thiệu tóm tắt hai mô hình được chọn để thay thế mô hình Boolean.

Nếu có thể có thông tin vị trí của toàn bộ các term chỉ mục, một hệ thống IR

Hai mô hình này đã định nghĩa ngữ nghĩa mới cho các toán tử lý thuyết tập.

có thể tính khoảng cách giữa các term chỉ mục và nhờ vậy sẽ hỗ trợ các truy
vấn chính xác cụm từ (exact phrase) hoặc truy vấn gần gũi (proximity
queries). Truy vấn chính xác cụm từ tìm kiếm các thể hiện chính xác của một
cụm từ, còn truy vấn gần gũi nới lỏng ràng buộc của sự gần kề chặt chẽ và sẽ
thu thập những tài liệu mà các term chỉ mục xuất hiện trong một “cửa sổ”.
Một cải tiến cao hơn là tính độ liên quan dựa trên khoảng cách giữa các
term truy vấn trong tài liệu. Phương pháp này gọi là xếp hạng mật độ bao phủ
(cover density ranking) [15] và đã được cài đặt trong hệ thống IR của trường
đại học Waterloo. Xếp hạng mật độ bao phủ là tiêu chuẩn sắp xếp thứ hai,
được áp dụng sau khi xếp hạng bởi CLM. Phương pháp này đặc biệt phù hợp
với các truy vấn ngắn. Với mỗi tài liệu, các đoạn thoả mãn truy vấn (dạng
Boolean) được xác định. Một đoạn tài liệu được xác định bởi vị trí bắt đầu và
kết thúc trong tài liệu. Các đoạn đó được xếp hạng tỷ lệ ngược lại với độ dài
của chúng theo thứ tự giảm dần. Cuối cùng, điểm của tài liệu được tính bằng
cách lấy tổng điểm của các đoạn. Sự đóng góp của đoạn thứ n được làm giảm

trọng số bởi một thừa số n, thường có giá trị trong khoảng 0.5 đến 1. Clarke

Trần Thị Hoàng Thảo

Luận văn thạc sĩ

Mô hình truy xuất mờ (Fuzzy retrieval)

Một số mô hình IR dựa trên lý thuyết tập mờ [33] đã được đề xuất [25]
. Trong một tập mờ, các phần tử mang một giá trị thành viên chia theo điểm
(gradual membership value). Không giống như các mô hình Boolean, trong
đó các giá trị thành viên term-tài liệu là nhị phân, các giá trị thành viên mờ
nằm trong khoảng từ 0 đến 1. Ưu điểm của cách tiếp cận này là các độ tin cậy
(degrees of belief) có thể mã hoá được. Ví dụ, có thể tính ma trận tương quan
term-term và bổ sung các term có tương quan với các term của một tài liệu cụ
thể vào biểu diễn của tài liệu đó với sự tương quan là giá trị thành viên. Việc
đánh giá một truy vấn trong lôgíc mờ khác theo ngữ nghĩa của các toán tử
giao (AND) và hợp (OR), được biểu diễn là giá trị thành viên nhỏ nhất hoặc
lớn nhất.
Các mô hình tập mờ có ưu điểm so với mô hình không gian véctơ và mô
hình xác suất ở chỗ chúng cung cấp khả năng xếp hạng cho các truy vấn có
cấu trúc.

Trần Thị Hoàng Thảo

Luận văn thạc sĩ