LUẬN VĂN TỐT NGHIỆP 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 LÀ
CÁC TỪ GHÉP

Giáo viên hướng dẫn :
Sinh viên thực hiện : 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 là các t ghép
Nguyn Th Thanh Hà - 0112215 1 Nguyn Trung Hiu - 0112216
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 ã
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 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


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 là các t ghép
Nguyn Th Thanh Hà - 0112215 3 Nguyn Trung Hiu - 0112216
NHN XÉT CA GIÁO VIÊN PHN BIN
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
……………………………………………………………………………………
…………………………………………………………………………………....
……………………………………………………………………………………
Ngày…… tháng……nm 2005
Ký tên

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 là các t ghép
Nguyn Th Thanh Hà - 0112215 4 Nguyn Trung Hiu - 0112216
C LC
DANH SÁCH CÁC BNG...................................................................................8
DANH SÁCH CÁC HÌNH V..............................................................................8
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

4.2 Vn  bng mã ting Vit.........................................................................27

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 là các t ghép
Nguyn Th Thanh Hà - 0112215 5 Nguyn Trung Hiu - 0112216
4.3 Các khó khn khác.....................................................................................27
Chng 3: TÁCH T TNG........................................................................29
1. Tách t trong Ting Anh .................................................................................29
2. Tách t trong Ting Vit .................................................................................29
2.1 Mt sc m chính v t ting Vit [2.2]..............................................29
2.1.1 Ting...................................................................................................29
2.1.2 T .......................................................................................................30
2.2 Tách t tng ting Vit .........................................................................30
3. Các phng pháp tách t ting Vit.................................................................30
3.1 fnTBL (Fast Transformation-based learning) [3.1].....................................30
3.1.1 Mô t...................................................................................................30
3.1.2 Áp dng tách t ting Vit...................................................................31
3.2 Longest Matching [1.4]..............................................................................37
3.3 Kt hp gia fnTBL và Longest Matching.................................................37
Chng 4: LP CH MC ..................................................................................38
1. Khái quát v h thng lp ch mc...................................................................38
2. Phng pháp lp ch mc [1.1]........................................................................38
2.1 Xác nh các t ch mc.............................................................................38
2.2 Các phng pháp tính trng s ca t........................................................40
2.2.1 Tn s tài liu nghch o....................................................................40
2.2.2  nhiu tín hiu (The Signal – Noise Ratio) ......................................40
2.2.3 Giá tr phân bit t (The Term Discrimination Value) .........................42
2.3 Lp ch mc tng cho tài liu ting Anh................................................43
3. Lp ch mc cho tài liu ting Vit..................................................................45
4. Tp tin nghch o tài liu ...............................................................................46
4.1 Phân bit gia tp tin nghch o và tp tin trc tip..................................46

1. Cu trúc lu tr d liu....................................................................................64
1.1 Tp tin lu ni dung tài liu.......................................................................64
1.1.1 Cu trúc DTD / XSD...........................................................................64
1.1.2 Tài liu XML ......................................................................................66
1.2 Tp tin sau khi tách t tài liu....................................................................67
1.2.1 Cu trúc DTD / XSD...........................................................................67
1.2.2 Tài liu XML ......................................................................................68
1.3 Tp tin cha các t không th hin ni dung ca vn bn (stop list)...........70
1.3.1 Cu trúc DTD / XSD...........................................................................70
1.3.2 Tài liu XML ......................................................................................71
1.4 Tp tin ch mc o ( Inverted ).................................................................71
1.4.1 Cu trúc DTD / XSD...........................................................................71
1.4.2 Tài liu XML ......................................................................................73
1.5 Tp tin sau khi tách t câu hi....................................................................74
1.5.1 Cu trúc DTD / XSD...........................................................................74
1.5.2 Tài liu XML ......................................................................................75
1.6 Tp tin cha các t ca câu hi sau khi loi b các t trong danh sách
StopList...........................................................................................................76
1.6.1 Cu trúc DTD / XSD...........................................................................76
1.6.2 Tài liu XML ......................................................................................77
1.7 Tp tin cha các t trong câu hi và các tài liu liên quan..........................77
1.7.1 Cu trúc DTD / XSD...........................................................................77

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 là các t ghép
Nguyn Th Thanh Hà - 0112215 7 Nguyn Trung Hiu - 0112216
1.7.2 Tài liu XML ......................................................................................79
1.8 Tp tin cha  tng quan gia câu hi và các tài liu.............................80
1.8.1 Cu trúc DTD / XSD...........................................................................80
1.8.2 Tài liu XML ......................................................................................82
2. Chi tit các lp i tng ................................................................................83

Nguyn Th Thanh Hà - 0112215 8 Nguyn Trung Hiu - 0112216
DANH SÁCH CÁC BNG
ng 1-1 So sánh IRS vi các h thng thông tin khác ..........................................................17
ng 4-1 Cách tp tin nghch o lu tr...............................................................................47
ng 4-2 Cách tp tin trc tip lu tr...................................................................................47
ng 4-3 Thêm mt tài liu mi vào tp tin nghch o.........................................................48
ng 5-1 Danh sách các Actor...............................................................................................50
ng 5-2 Danh sách các UseCase..........................................................................................50
DANH SÁCH CÁC HÌNH V
Hình 1-1 Môi trng ca h tìm kim thông tin.....................................................................13
Hình 1-2 Tng quan v chc nng ca mt h tìm kim thông tin..........................................14
Hình 2-1 H tìm kim thông tin tiêu biu...............................................................................18
Hình 3-1 Quá trình hc..........................................................................................................35
Hình 3-2 Giai n xác nh t cho tài liu mi.....................................................................36
Hình 4-1 Các tc sp theo th t ....................................................................................39
Hình 4-2 Quá trình chn t làm ch mc................................................................................45
Hình 5-1 S Use-case ca h thng...................................................................................49
Hình 5-2 S các lp th hin.............................................................................................51
Hình 5-3 S các lp x lý.................................................................................................52
Hình 5-4 S Use-case tách t............................................................................................53
Hình 5-5 S tun t tách t...............................................................................................53
Hình 5-6 S cng tác tách t.............................................................................................54
Hình 5-7 S lp tách t.....................................................................................................54
Hình 5-8 S use-case lp ch mc.....................................................................................55
Hình 5-9 S tun t to mi ch mc ................................................................................56
Hình 5-10 S tun t cp nht ch mc ............................................................................57
Hình 5-11 S cng tác to mi ch mc ............................................................................58
Hình 5-12 S cng tác cp nht ch mc...........................................................................59
Hình 5-13 S lp lp ch mc ...........................................................................................60
Hình 5-14 S use-case tìm kim .......................................................................................61

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 là các t ghép
Nguyn Th Thanh Hà - 0112215 10 Nguyn Trung Hiu - 0112216
U
Trong thi i bùng n thông tin nh hin nay, thông tin c lu tr trên máy
tính ngày càng nhiu do ó vic tìm kim thông tin chính xác là nhu cu thit yu i
i mi ngi trong mi lnh vc. Internet hin nay ã tr thành mt kho t liu khng
 mà vic tìm kim thông tin trên kho t liu này cn phi c h tr bi các công c
tìm kim (search engine) tt. Các h thng tìm kim thông tin thông dng nh Google,
Yahoo Search ã áp ng c phn nào nhu cu ó ca mi ngi. Tuy nhiên, các h
thng này c xây dng  x lý và tìm kim các vn bn ting Châu Âu, chúng cha
tht s phù hp cho các vn bn ting Vit. Do ó nhu cu phi có mt công c tìm
kim “hiu” và x lý tt các vn bn tíng Vit.
Các h tìm kim thông tin u phi thc hin giai n lp ch mc (indexing)
cho vn bn  trích các t ch mc (index term) biu din tt nht ni dung ca vn
n. Giai n này ph thuc vào ngôn ng ca vn bn và phng pháp x lý tng
ngôn ngó. Hin nay cha có nhiu h thng tìm kim thông tin trên kho tài liu
ting Vit có khai thác các c trng ca ting Vit cho vic lp ch mc.
Vì vy mc tiêu ca lun vn này nhm xây dng mt h thng tìm kim thông
tin bng ting Vit có s dng các kt qu ca x lý ngôn ng t nhiên tng  xác
nh c các ch mc là các t (word) hay t ghép (compound word) ca ting Vit.

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 là các t ghép
Nguyn Th Thanh Hà - 0112215 11 Nguyn Trung Hiu - 0112216
Phn 1 : TÌM HIU LÝ THUYT
Chng 1: NG QUAN V TÌM KIM THÔNG TIN
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 t s vn  trong vic tìm kim thông tin:

Hiu n gin  thng tìm kim thông tin là mt h thng h tr cho ngi
 dng tìm kim thông tin mt cách nhanh chóng và d dàng. Ngi s dng có
tha vào nhng câu hi, nhng yêu cu (dng ngôn ng t nhiên) và h thng s tìm
kim trong tp các tài liu (dng ngôn ng t nhiên) ã c lu tr tìm ra nhng

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 là các t ghép
Nguyn Th Thanh Hà - 0112215 13 Nguyn Trung Hiu - 0112216
tài liu có liên quan, sau ó s sp xp các tài liu theo mc  liên quan gim dn và
tr v cho ngi s dng.
3. Các thành phn ca mt h tìm kim thông tin [1.1]
m: tp các tài liu (DOCS) ã c lu tr trong kho d liu, tp các yêu cu
(REQS) ca ngi dùng, và mt s phng pháp tính  tng quan (SIMILAR) 
xác nh các tài liu áp ng cho các yêu cu.
Hình 1-1 Môi trng ca h tìm kim thông tin
Theo lý thuyt thì mi liên h gia các câu hi và các tài liu có th so sánh mt
cách trc tip. Nhng trên thc t thì u này không thc vì các câu hi và các tp
tài liu u  dng vn bn, ch có con ngi c vào thì thy ngay c mi liên h
gia chúng, nhng ây ch là mt h thng máy móc không th suy lun nh con
ngi c. Chính vì th xác nh c mi liên h gia các câu hi và các tp tài
liu phi qua mt bc trung gian.

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 là các t ghép
Nguyn Th Thanh Hà - 0112215 14 Nguyn Trung Hiu - 0112216
Hình 1-2 Tng quan v chc nng ca mt h tìm kim thông tin
Trc ht chuyn i các câu hi thành các t riêng bit  biu hin cho ni
dung ca câu hi gi là ngôn ng ch mc (Indexing language - LANG). Tách t trong
các tp tài liu và lp ch mc cho tài liu. Lúc này có th so sánh trc tip gia các t
a câu hi và các t ch mc ca tp tài liu. Và tó ta s d dàng hn  xác nh
 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 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ng này ang c áp dng nhiu cho công vic nhn dng và chun óan
nh.
4.4  tr li câu hi (QAS)
 tr li câu hi cung cp vic truy cp n các thông tin bng ngôn ng t
nhiên. Vic lu tr c s d liu thng bao gm mt s lng ln các vn  liên
quan n các lnh vc riêng bit và các kin thc tng quát. Câu hi ca ngi dùng có
th dng ngôn ng t nhiên. Công vic ca h tr li câu hi là phân tích câu truy
n ca ngi dùng, so sánh vi các tri thc c lu tr, và tp hp các vn  có liên
quan li a ra câu tr li thích hp.
Tuy nhiên, h tr li câu hi ch còn ang th nghim. Vic xác nh ý ngha
a ngôn ng t nhiên dng nh vn là chng ngi ln  có th s dng rng rãi h
thng này.

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 là các t ghép
Nguyn Th Thanh Hà - 0112215 17 Nguyn Trung Hiu - 0112216
4.5 So sánh IRS vi các h thng thông tin khác
IRS DBMS QAS MIS
Tìm kim
i dung
trong các tài
liu.
Các phn t
có kiu d
liu ã c
nh ngha.
Các s kin
rõ ràng.

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 là các t ghép
Nguyn Th Thanh Hà - 0112215 18 Nguyn Trung Hiu - 0112216
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]
t h thng thông tin tiêu biu nh sau:
Hình 2-1 H tìm kim thông tin tiêu biu
 thng tìm kim thông tin gm có 3 b phn chính : b phn phân tích vn
n, b phn lp ch mc, b phn so khp và sp xp các tài liu tr v.

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 là các t ghép
Nguyn Th Thanh Hà - 0112215 19 Nguyn Trung Hiu - 0112216
(1)  phn phân tích vn bn: b phn này có nhim v phân tích các vn
n thu thp c thành các t riêng bit. Tng t, khi ngi dùng nhp câu truy vn
thì câu truy vn cng c phân tích thành các t riêng bit.
(2)  phn lp ch mc : các t trích c t các vn bn thu thp c s
c b phn này la chn  làm các t ch mc. Các t ch mc phi là các t th
hin c ni dung ca vn bn.
(3)  phn so khp và sp xp các tài liu tr v: Các t trích c t câu
truy vn và các t ch mc ca vn bn sc so khp vi nhau  tìm ra các tài liu
liên quan n câu truy vn. Mi tài liu có mt  tng quan vi câu hi. Các tài liu
này sc sp xp theo  tng quan gim dn và tr v cho ngi s dng.
2. t s mô hình  xây dng mt h tìm kim thông tin [1.2]
c tiêu ca các h thng tìm kim thông tin là tr v các tài liu càng liên
quan n câu hi càng tt. Vì th ngi ta ã a ra rt nhiu mô hình tìm kim nhm
tính toán mt cách chính xác  tng quan này. Sau ây là mt s mô hình tìm kim
 bn:
2.1 Mô hình không gian vector
Mô hình không gian vector tính toán  tng quan gia câu hi và tài liu bng
cách nh ngha mt vector biu din cho mi tài liu, và mt vector biu din cho câu

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)
df
j
: s tài liu có cha t t
j
idf
j
=
10
log
j
d
df
trong ó d là tng s tài liu
Vector c xây dng cho mi tài liu gm có n thành phn, mi thành phn là
giá tr trng sã c tính toán cho mi t trong tp tài liu. Các t trong tài liu
c gán trng s tng da vào tn s xut hin ca chúng trong tp tài liu và s
xut hin ca mi t trong mt tài liu riêng bit. Trng s ca mt t tng nu tó
xut hin thng xuyên trong mt tài liu và gim nu tó xut hin thng xuyên

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 là các t ghép
Nguyn Th Thanh Hà - 0112215 21 Nguyn Trung Hiu - 0112216
trong tt c các tài liu.  tính trng s ca t th t

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
c tính nh sau:
SC(Q,D
i
) =
ij
1
w*
n
qj
j
d
=
∑
2.2 Tìm kim Boolean
Mô hình tìm kim Boolean khá n gin. Câu hi a vào phi  dng biu thc
Boolean. Ngha là phi tha:
Ø Ng ngha rõ ràng
Ø Hình thc ngn gn
Do các t hoc xut hin hoc là không xut hin, nên trng s w

, d
5
}. Phng pháp này có mt s khuyt 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
Ø 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 vi câu hi.
Mô hình tìm kim Boolean m rng ra i nhm h tr vic sp xp (ranking)
t qu tr v da trên ý tng c bn là ánh trng s cho mi t trong câu hi và
trong tài liu. Gi s mt câu hi yêu cu (t
1
OR t
2
) và mt tài liu D có cha t
1
vi
trng s w
1
và t
2
vi trng s w
2
. Nu w
1
và w

) =
2
= 1.414
a SC vào khong [0,1], SC c tính nh sau:
SC( Q
t1 v t2
, d
i
) =
22
12
(w) (w)
2
+
Công thc này gi s là câu hi ch có toán t OR . i vi toán t AND, thay
vì tính khong cách ti gc, ta s tính khong cách n m (1,1). Câu hi nào càng
n n m (1,1) thì nó càng tho yêu cu ca toán t AND:
SC(Q
t1 ^ t2
, d
i
) = 1-
22
12
(1-w ) (1 w )
2
+−
2.4  rng trong vic thêm vào trng s ca câu hi
u câu hi có trng s là q
1

)
2.4.1  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
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:

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 là các t ghép
Nguyn Th Thanh Hà - 0112215 24 Nguyn Trung Hiu - 0112216
SC(D, Q
( q i v q j )
) =
1
p p pp
p
i i jj
pp
ij
qw
qq
qw

+

+


SC(D, Q
( q i ^ q j )
) = 1 -