Xây dựng hệ thống tìm kiếm thông tin tiếng Việt dựa trên các chỉ mục có cấu trúc
LỜI CẢM ƠN
Chúng em xin gởi lời cảm ơn chân thành nhất đến thầy Hồ Bảo Quốc, người
đã tận tình hướng dẫn, giúp đỡ chúng em trong suốt thời gian thực hiện luận văn này.
Chúng con cảm ơn Cha, Mẹ và gia đình, những người đã dạy dỗ, khuyến
khích, động viên chúng con trong những lúc khó khăn, tạo mọi điều kiện cho chúng
con nghiên cứu học tập.
Chúng em cảm ơn các thầy, cô trong khoa Công Nghệ Thông Tin đã dìu dắt,
giảng dạy chúng em, giúp chúng em có những kiến thức quý báu trong những năm
học qua.
Cảm ơn chị Lê Thúy Ngọc và các bạn đã tận tình đóng góp ý kiến cho luận
văn của chúng tôi.
Mặc dù rất cố gắng nhưng luận văn của chúng em không tránh khỏi sai sót,
mong nhận được sự thông cảm và góp ý của thầy cô và các bạn.
Tháng 7 năm 2005
Sinh viên
Nguyễn Thị Thanh Hà – Nguyễn Trung Hiếu
Nguyễn Thị Thanh Hà - 0112215 1 Nguyễn Trung Hiếu - 0112216
Xây dựng hệ thống tìm kiếm thông tin tiếng Việt dựa trên các chỉ mục có cấu trúc
NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................
..............................................................................................................................

Nguyễn Thị Thanh Hà - 0112215 3 Nguyễn Trung Hiếu - 0112216
Xây dựng hệ thống tìm kiếm thông tin tiếng Việt dựa trên các chỉ mục có cấu trúc
MỤC LỤC
DANH SÁCH CÁC BẢNG.................................................................................7
DANH SÁCH CÁC HÌNH VẼ............................................................................7
Phần 1 : TÌM HIỂU LÝ THUYẾT.....................................................................11
Chương 1: TỔNG QUAN VỀ TÌM KIẾM THÔNG TIN...............................11
1. Giới thiệu về tìm kiếm thông tin......................................................................11
1.1 Khái niệm về tìm kiếm thông tin...............................................................11
1.2 Một số vấn đề trong việc tìm kiếm thông tin:...........................................11
2. Hệ tìm kiếm thông tin – IRS............................................................................12
3. Các thành phần của một hệ tìm kiếm thông tin [1.1].......................................13
4. So sánh IRS với các hệ thống thông tin khác .................................................14
4.1 Hệ quản trị cơ sở dữ liệu (DBMS)............................................................15
4.2 Hệ quản lý thông tin (IMS).......................................................................15
4.3 Hệ hỗ trợ ra quyết định (DSS)..................................................................15
4.4 Hệ trả lời câu hỏi (QAS)...........................................................................16
4.5 So sánh IRS với các hệ thống thông tin khác............................................16
Chương 2: XÂY DỰNG MỘT HỆ THỐNG TÌM KIẾM THÔNG TIN.......17
1. Kiến trúc của hệ tìm kiếm thông tin. [1.3].......................................................17
2. Một số mô hình để xây dựng một hệ tìm kiếm thông tin [1.2]........................19
2.1 Mô hình không gian vector.......................................................................19
2.2 Tìm kiếm Boolean.....................................................................................21
2.3 Tìm kiếm Boolean mở rộng......................................................................21
2.4 Mở rộng trong việc thêm vào trọng số của câu hỏi...................................22
2.4.1 Mở rộng cho số từ tuỳ ý......................................................................23
2.4.2 Thêm toán tử tự động..........................................................................23
2.5 Mô hình xác suất.......................................................................................24
2.6 Đánh giá chung về các mô hình................................................................24
3. Các bước để xây dựng một hệ tìm kiếm thông tin. [3.2].................................24

2.2.2 Độ nhiễu tín hiệu (The Signal – Noise Ratio).....................................39
2.2.3 Giá trị phân biệt từ (The Term Discrimination Value)........................41
2.3 Lập chỉ mục tự động cho tài liệu tiếng Anh..............................................42
3. Lập chỉ mục cho tài liệu tiếng Việt..................................................................44
4. Tập tin nghịch đảo tài liệu...............................................................................45
4.1 Phân biệt giữa tập tin nghịch đảo và tập tin trực tiếp................................45
4.2 Tại sao sử dụng tập tin nghịch đảo để lập chỉ mục...................................46
Phần 2 : PHÂN TÍCH VÀ THIẾT KẾ...............................................................48
Chương 1: PHÂN TÍCH....................................................................................48
1. Sơ đồ UseCase hệ thống..................................................................................48
2. Sơ đồ Lớp........................................................................................................50
2.1 Sơ đồ các lớp thể hiện...............................................................................50
2.2 Sơ đồ các lớp xử lý...................................................................................51
3. Tách từ.............................................................................................................52
3.1 Sơ đồ UseCase..........................................................................................52
3.2 Sơ đồ Tuần tự............................................................................................52
3.3 Sơ đồ Cộng tác..........................................................................................53
3.4 Sơ đồ Lớp..................................................................................................53
4. Lập chỉ mục.....................................................................................................54
4.1 Sơ đồ UseCase..........................................................................................54
4.2 Sơ đồ Tuần tự............................................................................................55
4.2.1 Tạo mới chỉ mục.................................................................................55
4.2.2 Cập nhật chỉ mục.................................................................................56
Nguyễn Thị Thanh Hà - 0112215 5 Nguyễn Trung Hiếu - 0112216
Xây dựng hệ thống tìm kiếm thông tin tiếng Việt dựa trên các chỉ mục có cấu trúc
4.3 Sơ đồ Cộng tác..........................................................................................57
4.3.1 Tạo mới chỉ mục.................................................................................57
4.3.2 Cập nhật chỉ mục.................................................................................57
4.4 Sơ đồ Lớp..................................................................................................58
5. Tìm kiếm..........................................................................................................59

1.8.2 Tài liệu XML.......................................................................................80
2. Chi tiết các lớp đối tượng................................................................................81
2.1 Các lớp trong quá trình tách từ..................................................................81
2.1.1 Sơ đồ các lớp......................................................................................81
2.1.2 Lớp tách từ ghép..................................................................................82
2.1.3 Lớp tách từ..........................................................................................85
2.1.4 Lớp giao diện tách từ...........................................................................87
2.2 Các lớp trong quá trình lập chỉ mục..........................................................89
Nguyễn Thị Thanh Hà - 0112215 6 Nguyễn Trung Hiếu - 0112216
Xây dựng hệ thống tìm kiếm thông tin tiếng Việt dựa trên các chỉ mục có cấu trúc
2.2.1 Sơ đồ các lớp.......................................................................................89
2.2.2 Lớp lập chỉ mục...................................................................................90
2.2.3 Lớp giao diện tạo mới chỉ mục...........................................................93
2.2.4 Lớp giao diện cập nhật chỉ mục..........................................................95
2.3 Các lớp trong quá trình tìm kiếm..............................................................97
2.3.1 Sơ đồ các lớp.......................................................................................97
2.3.2 Lớp tìm kiếm.......................................................................................97
2.3.3 Lớp giao diện tìm kiếm.....................................................................103
3. Một số màn hình giao diện khác....................................................................108
3.1 Màn hình chính của chương trình...........................................................108
3.2 Màn hình tìm kiếm nhiều câu hỏi...........................................................109
3.3 Màn hình tìm kiếm chính ( giao diện Web)............................................111
3.4 Màn hình trả về các tài liệu tìm được ( giao diện Web)..........................112
3.5 Màn hình chi tiết của một tài liệu ( giao diện Web)................................113
Phần 3 : TỔNG KẾT.........................................................................................114
1. Chương trình thử nghiệm...............................................................................114
2. Đánh giá kết quả đạt được.............................................................................114
3. Hướng phát triển............................................................................................115
TÀI LIỆU THAM KHẢO................................................................................116
1. Sách................................................................................................................116

Hình 5-19 Sơ đồ cộng tác cập nhật chỉ mục........................................................58
Hình 5-20 Sơ đồ lớp lập chỉ mục..........................................................................59
Hình 5-21 Sơ đồ use-case tìm kiếm......................................................................59
Hình 5-22 Sơ đồ tuần tự tìm kiếm........................................................................60
Hình 5-23 Sơ đồ cộng tác tìm kiếm......................................................................61
Hình 5-24 Sơ đồ lớp tìm kiếm..............................................................................62
Hình 6-25 Sơ đồ lớp tách từ..................................................................................82
Nguyễn Thị Thanh Hà - 0112215 8 Nguyễn Trung Hiếu - 0112216
Xây dựng hệ thống tìm kiếm thông tin tiếng Việt dựa trên các chỉ mục có cấu trúc
Hình 6-26 Lớp tách từ ghép.................................................................................82
Hình 6-27 Lớp tách từ...........................................................................................85
Hình 6-28 Lớp giao diện tách từ..........................................................................87
Hình 6-29 Màn hình tách từ.................................................................................88
Hình 6-30 Màn hình chi tiết tách từ.....................................................................89
Hình 6-31 Sơ đồ lớp lập chỉ mục..........................................................................90
Hình 6-32 Lớp lập chỉ mục...................................................................................91
Hình 6-33 Lớp giao diện tạo mới chỉ mục...........................................................93
Hình 6-34 Màn hình tạo mới chỉ mục..................................................................94
Hình 6-35 Lớp Màn hình cập nhật chỉ mục........................................................95
Hình 6-36 Màn hình cập nhật chỉ mục................................................................96
Hình 6-37 Sơ đồ lớp tìm kiếm..............................................................................97
Hình 6-38 Lớp xử lý tìm kiếm..............................................................................98
Hình 6-39 Lớp giao diện tìm kiếm.....................................................................104
Hình 6-40 Màn hình tìm kiếm............................................................................105
Hình 6-41 Xem từ khóa câu hỏi.........................................................................105
Hình 6-42 Xem từ khóa tài liệu..........................................................................106
Hình 6-43 Màn hình chính.................................................................................108
Hình 6-44 Màn hình tìm kiếm nhiều câu hỏi....................................................109
Hình 6-45 Giao diện tìm kiếm trên Web...........................................................111
Hình 6-46 Giao diện các tài liệu trả về sau khi tìm kiếm.................................112

1. Giới thiệu về tìm kiếm thông tin
1.1 Khái niệm về tìm kiếm thông tin
Tìm kiếm thông tin là tìm kiếm trong một tập tài liệu để lấy ra các thông tin mà
người tìm kiếm quan tâm.
1.2 Một số vấn đề trong việc tìm kiếm thông tin:
Kể từ những năm 40, các vấn đề trong việc lưu trữ thông tin và tìm kiếm thông
tin đã thu hút sự chú ý rất lớn. Với một lượng thông tin khổng lồ thì việc tìm kiếm chính
xác và nhanh chóng càng trở nên khó khăn hơn. Với sự ra đời của máy tính, rất nhiều ý
tưởng lớn được đưa ra nhằm cung cấp một hệ thống tìm kiếm thông minh và chính xác.
Tuy nhiên, vấn đề tìm kiếm sao cho hiệu quả vẫn chưa được giải quyết.
Về nguyên tắc, việc lưu trữ thông tin và tìm kiếm thông tin thì đơn giản. Giả sử
có một kho chứa các tài liệu và một người muốn tìm các tài liệu liên quan đến yêu cầu
của mình. Người đó có thể đọc tất cả các tài liệu trong kho, giữ lại các tài liệu liên quan
và bỏ đi các tài liệu không liên quan. Rõ ràng giải pháp này không thực tế bởi vì tốn rất
nhiều thời gian.
Với sự ra đời của máy vi tính tốc độ cao, máy tính có thể “đọc” thay cho con
người để trích ra các tài liệu có liên quan trong toàn bộ tập dữ liệu. Tuy nhiên vấn đề lúc
Nguyễn Thị Thanh Hà - 0112215 11 Nguyễn Trung Hiếu - 0112216
Xây dựng hệ thống tìm kiếm thông tin tiếng Việt dựa trên các chỉ mục có cấu trúc
này là làm sao để xác định được tài liệu nào liên quan đến câu hỏi. Mục đích của một hệ
thống tìm kiếm thông tin tự động là truy lục được tất cả các tài liệu có liên quan đến yêu
cầu.
2. Hệ tìm kiếm thông tin – IRS
Sau đây là định nghĩa về hệ thống tìm kiếm thông tin của một số tác giả: [2.1]
Salton (1989):
“Hệ thống tìm kiếm thông tin xử lý các tập tin lưu trữ và những yêu cầu về thông
tin, xác định và tìm từ các tập tin những thông tin phù hợp với những yêu cầu về thông
tin. Việc truy tìm những thông tin đặc thù phụ thuộc vào sự tương tự giữa các thông tin
được lưu trữ và các yêu cầu, được đánh giá bằng cách so sánh các giá trị của các thuộc
tính đối với thông tin được lưu trữ và các yêu cầu về thông tin.”

tương quan giữa các câu hỏi và tập tài liệu.
4. So sánh IRS với các hệ thống thông tin khác
Hệ thống tìm kiếm thông tin cũng tương tự như nhiều hệ thống xử lý thông tin
khác. Hiện nay các hệ thống thông tin quan trọng nhất là: hệ quản trị cơ sở dữ liệu
(DBMS), hệ quản lý thông tin (MIS), hệ hỗ trợ ra quyết định (DSS), hệ trả lời câu hỏi
(QAS) và hệ tìm kiếm thông tin (IR).
Nguyễn Thị Thanh Hà - 0112215 14 Nguyễn Trung Hiếu - 0112216
Xây dựng hệ thống tìm kiếm thông tin tiếng Việt dựa trên các chỉ mục có cấu trúc
4.1 Hệ quản trị cơ sở dữ liệu (DBMS)
Bất cứ hệ thống thông tin tự động nào cũng dựa trên một tập các mục được lưu
trữ (gọi là cơ sở dữ liệu) cần thiết cho việc truy cập. Do đó hệ quản trị cơ sở dữ liệu đơn
giản là một hệ thống được thiết kế nhằm thao tác và duy trì điều khiển cơ sở dữ liệu.
DBMS tổ chức lưu trữ các dữ liệu của mình dưới dạng các bảng. Mỗi một cơ sở
dữ liệu được lưu trữ thành nhiều bảng khác nhau. Mỗi một cột trong bảng là một thuộc
tính, và mỗi một dòng là một bộ dữ liệu cụ thể. Trong mỗi một bảng có một thuộc tính
duy nhất đại diện cho bảng, nó không được trùng lắp và ta gọi đó là khoá chính. Các
bảng có mối liên hệ với nhau thông qua các khoá ngoại. DBMS có một tập các lệnh để
hỗ trợ cho người sử dụng truy vấn đến dữ liệu của mình. Vì vậy muốn truy vấn đến
CSDL trong DBMS ta phải học hết các tập lệnh này. Nhưng ngược lại nó sẽ cung cấp
cho ta các dữ liệu đầy đủ và hoàn toàn chính xác. Hiện nay DBMS được sử dụng rộng
rãi trên thế giới. Một số DBMS thông dụng : Access, SQL Server, Oracle.
4.2 Hệ quản lý thông tin (IMS)
Hệ quản lý thông tin là hệ quản trị cơ sở dữ liệu nhưng có thêm nhiều chức nhưng
về việc quản lý. Những chức năng quản lý này phụ thuộc vào giá trị của nhiều kiểu dữ
liệu khác nhau. Nói chung bất kỳ hệ thống nào có mục đích đặc biệt phục vụ cho việc
quản lý thì ta gọi nó là hệ quản lý thông tin.
4.3 Hệ hỗ trợ ra quyết định (DSS)
Hệ hỗ trợ ra quyết định sẽ dựa vào các tập luật được học, từ những luật đã học rút
ra những luật mới, sau khi gặp một vấn đề nó sẽ căn cứ vào vào tập các luật để đưa ra
những quyết định thay cho con người.

thủ tục( Tính
tổng, tính
trung bình,
phép chiếu…)
Lưu trữ
Các văn bản
ngôn ngữ tự
nhiên.
Các phần tử
dữ liệu ở dạng
bảng.
Các sự kiện rõ
ràng và các
kiến thức tổng
quát.
Xử lý
Các câu truy
vấn không
chính xác.
Các câu truy
vấn có cấu
trúc.
Các câu truy
vấn không
giới hạn.
Bảng 1-1 So sánh IRS với các hệ thống thông tin khác
Chương 2: XÂY DỰNG MỘT HỆ THỐNG TÌM KIẾM
THÔNG TIN
1. Kiến trúc của hệ tìm kiếm thông tin. [1.3]
Một hệ thống thông tin tiêu biểu như sau:

và t
2
. Vector xây dựng được sẽ gồm
có 2 thành phần: thành phần thứ nhất biểu diễn sự xuất hiện của t
1
, và thành phần thứ hai
biểu diễn cho sự xuất hiện của t
2
. Cách đơn giản nhất để xây dựng vector là đánh 1 vào
thành phần tương ứng nếu từ đó xuất hiện, và đánh 0 nếu từ đó không xuất hiện. Giả sử
tài liệu chỉ gồm có 2 từ t
1
. Ta biểu diễn cho tài liệu này bởi vector nhị phân như sau:
<1,0> Tuy nhiên, biểu diễn như vậy không cho thấy được tần số xuất hiện của mỗi từ
trong tài liệu. Trong trường hợp này, vector nên được biễu diễn như sau: <2,0>
Đối với một câu hỏi đã cho, thay vì chỉ căn cứ so sánh các từ trong tài liệu với
tập các từ trong câu hỏi, ta nên xem xét đến tầm quan trọng của mỗi từ. Ý tưởng chính là
một từ xuất hiện tập trung trong một số tài liệu thì có trọng số cao hơn so với một từ
Nguyễn Thị Thanh Hà - 0112215 19 Nguyễn Trung Hiếu - 0112216
Xây dựng hệ thống tìm kiếm thông tin tiếng Việt dựa trên các chỉ mục có cấu trúc
phân bố trong nhiều tài liệu. Trọng số được tính dựa trên tần số tài liệu nghịch đảo
(Inverse Document Frequency) liên quan đến các từ được cho:
n: số từ phân biệt trong tập tài liệu
tf
ij
: số lần xuất hiện của từ t
j
trong tài liệu D
i
(tần số)

d
ij
: là trọng số của từ t
j
trong tài liệu D
i
Đối với hệ thống tìm kiếm thông tin theo mô hình vector, mỗi tài liệu là một
vector có dạng : D
i
(d
i1
, d
i2
, …, d
in
) . Tương tự, câu truy vấn Q cũng là một vector có
dạng : Q(w
q1
, w
q2
, …, w
qn
)
w
qj
: là trọng số của từ t
j
trong câu truy vấn Q.
Độ tương quan (SC: similarity coeficient) giữa câu truy vấn Q và tài liệu D
i

1
là { d
1
, d
3
, d
5
} và các tài liệu liên quan đến
t
2
là {d
3
, d
5
, d
7
}. Như vậy với phép and, các tài liệu thỏa yêu cầu của người dùng là {d
3
,
d
5
}. Phương pháp này có một số khuyết điểm như sau:
 Các tài liệu trả về không được sắp xếp (ranking)
 Câu hỏi tìm kiếm đòi hỏi phải đúng định dạng của biểu thức Boolean gây
khó khăn cho người dùng
 Kết quả trả về có thể là quá ít hoặc quá nhiều tài liệu
2.3 Tìm kiếm Boolean mở rộng
Mô hình tìm kiếm Boolean không hỗ trợ việc sắp xếp kết quả trả về bởi vì các tài
liệu hoặc thỏa hoặc không thỏa yêu cầu Boolean. Tất cả các tài liệu thỏa mãn đều được
trả về, nhưng không có sự ước lượng nào được tính toán cho sự liên quan của chúng đối

i
) =
2 2
1 2
(w ) (w )+
Với trọng số 0.5 và 0.5, SC(Q,D
i
) =
2 2
(0.5) (0.5)+
=0.707
SC cao nhất nếu w
1
và w
2
đều bằng 1. Khi đó:
SC(Q,D
i
) =
2
= 1.414
Để đưa SC vào khoảng [0,1], SC được tính như sau:
SC( Q
t1 v t2
, d
i
) =
2 2
1 2
(w ) (w )

2 2
1 2
q w q w
q q
+
+
SC(Q
q1 ^ q2
, d
i
) = 1- (
2 2 2 2
1 1 2 2
2 2
1 2
q (1-w ) (1 )q w
q q
+ −
+
)
2.4.1 Mở rộng cho số từ tuỳ ý
Để tính khoảng cách Euclide trong không gian đa chiều, tham số p được sử dụng.
Tham số p chỉ sự biến đổi tầm quan trọng của trọng số trong việc đánh giá độ thích hợp.
Độ tương quan SC tổng quát như sau:
SC(D, Q
( q i v q j )
) =
1
p p p p
p

→ ∞
: chuyển về hệ thống Boolean thông thường (không có trọng số)
Nếu p = 1 : chuyển về hệ thống không gian vector
2.4.2 Thêm toán tử tự động
Các chiến lược tìm kiếm không đòi hỏi người dùng nhận biết các toán tử phức
tạp. Trọng số có thể được gán tự động và tài liệu được sắp xếp bằng cách chèn toán tử
OR vào giữa các từ. Bất kỳ tài liệu nào có chứa ít nhất một từ trong câu hỏi sẽ được sắp
thứ tự với một số điểm lớn hơn 0.
Nguyễn Thị Thanh Hà - 0112215 23 Nguyễn Trung Hiếu - 0112216
Xây dựng hệ thống tìm kiếm thông tin tiếng Việt dựa trên các chỉ mục có cấu trúc
2.5 Mô hình xác suất
Mô hình tìm kiếm xác suất tính toán độ tương quan giữa câu hỏi và tài liệu dựa
vào xác suất mà tài liệu đó liên quan đến câu hỏi. Các lý thuyết về xác suất được áp
dụng để tính toán độ liên quan giữa câu hỏi và tài liệu. Các từ trong câu hỏi được xem là
đầu mối để xác định tài liệu liên quan. Ý tưởng chính là tính xác suất của mỗi từ trong
câu hỏi và sau đó sử dụng chúng để tính xác suất mà tài liệu liên quan đến câu hỏi.
2.6 Đánh giá chung về các mô hình
 Mô hình Boolean được xem là mô hình yếu nhất trong các mô hình bởi vì
như đã trình bày nó còn rất nhiều khuyết điểm.
 Theo kinh nghiệm của Salton và Buckley thì nhìn chung mô hình vector
làm tốt hơn mô hình xác suất.
Luận văn của chúng em sử dụng mô hình không gian vector để xây dựng một
hệ thống tìm kiếm thông tin tiếng Việt.
3. Các bước để xây dựng một hệ tìm kiếm thông tin. [3.2]
3.1 Tách từ tự động cho tập các tài liệu
Đối với tiếng Anh, ta tách từ dựa vào khoảng trắng. Tuy nhiên đối với tiếng Việt,
giai đoạn này tương đối khó khăn. Cấu trúc tiếng Việt rất phức tạp, không chỉ đơn thuần
dựa vào khoảng trắng để tách từ. Hiện nay có rất nhiều công cụ dùng để tách từ tiếng
Việt, mỗi phương pháp có ưu, khuyết điểm riêng. Các phương pháp này sẽ được trình
bày chi tiết hơn ở chương III : Tách từ tự động.