1
B GIÁO DC VÀ ĐÀO TO
ĐI HC ĐÀ NNG
ĐNG TH ÁNH PHƯNG
NGHIÊN CU NG DNG
CU TRÚC D LIU TRIE
CHO TÌM KIM CHUI KÝ T
Chuyên ngành : KHOA HC MÁY TÍNH
Mã s : 60.48.01
TÓM TT LUN VĂN THC SĨ K THUT
Đà Nng - Năm 2012
2
Công trình ñưc hoàn thành ti
ĐI HC ĐÀ NNG
Ngưi hưng dn khoa hc: PGS.TS. VÕ TRUNG HÙNG
Phn bin 1: TS. NGUYN THANH BÌNH
Phn bin 2: TS. NGUYN MU HÂN
Lun văn ñưc bo v ti Hi ñng chm Lun văn tt nghip thc sĩ k
thut hp ti Đi hc Đà Nng vào ngày 03 tháng 03 năm 2012.
Có th tìm hiu lun văn ti:
• Trung tâm Thông tin - Hc liu, Đi hc Đà Nng
• Trung tâm Hc liu, Đi hc Đà Nng
1
M ĐU
1. Lý do chn ñ tài
Gn ñây, h thng kho d liu ngày càng ñưc m rng và ñóng vai trò quan trng
hơn ñi vi ngưi ra quyt ñnh; hu ht các truy vn ñi vi mt kho d liu ln rt
phc tp và lp ñi lp li; kh năng tr li nhng truy vn hiu qu là mt vn ñ mà
nhi u h thng ñang hưng ñn. Làm th nào ñ! tăng tc ñ, ci thin hiu sut truy vn
luôn là câu h"i ln và không ng#ng tìm kim li gii ñáp ti ưu. Hin nay có rt nhi u
k thut ñưc áp d$ng nh%m tăng hiu qu truy vn, m&i k thut ñ u có nhng th
mnh riêng, TRIE là mt cu trúc d liu ñang ñưc tri!n khai s' d$ng trong các h
thng tìm kim ln hin ti bi nhi u tính năng ưu vit giúp ñ(y nhanh tc ñ và hiu
qu c)a quá trình truy vn.
Trưc th*c trng ñó, tôi chn nghiên cu và th*c hin ñ tài “Nghiên cu ng
dng cu trúc d liu TRIE cho tìm kim chui ký t” dưi s* hưng dn c)a PGS. TS
Võ Trung Hùng. Đ tài phát tri!n s+ giúp cho sinh viên nói riêng và nhng ngưi nghiên
cu v Công ngh thông tin nói chung có thêm tài liu h& tr tri!n khai cu trúc d liu
này ph$c v$ cho công tác tìm kim chu&i ký t* bên cnh các cu trúc d liu ñang s'
d$ng hin nay trong mt s h qun tr cơ s d liu ln, ñc bit là các h qun tr cơ s
d liu mã ngun m.
2. Mc tiêu và nhim v nghiên c u
M$c tiêu c)a ñ tài là cu trúc d liu Trie ñưc tìm hi!u và trình bày c$ th! kèm
theo vic ng d$ng trong MariaDB.
Nhim v$ nghiên cu bao gm phn nghiên cu lý thuyt v các phương pháp to
ch, m$c và tìm kim; tìm hi!u các phương pháp Hash index, Bitmap Index, Btree Index
và nghiên cu cu trúc d liu Trie, các bin th! c)a Trie, các thao tác cơ bn trên cu
trúc d liu này. D*a trên các nghiên cu lý thuyt ñó, ñ tài ñưa ra ñưc tài liu Ting
vit v cu trúc d liu Trie ph$c v$ cho vic hc tp và nghiên cu.
2
3. Đ!i tư#ng và ph$m vi nghiên c u
Đi tưng nghiên cu c)a ñ tài gm: Cơ s lý thuyt v các phương pháp tìm
kim, truy xut d liu, ch, m$c và các k thut lp ch, m$c ph$c v$ tìm kim, các gii
thut liên quan ñn cu trúc d liu TRIE.
Phm vi nghiên cu v h thng tìm kim thông tin nói chung và các k thut lp ch,
m$c ph$c v$ công tác tìm kim thông tin (Hash Index, Bitmap Index, Btree Index), trng
tâm ñi sâu tìm hi!u cu trúc d liu TRIE, các bin th! Trie nén và các thao tác căn bn
trên Trie, Trie nén.
4. Phương pháp nghiên c u
Đ tài ñưc tri!n khai b%ng các phương pháp nghiên cu sau: Phương pháp tài liu
nh%m thu thp, phân tích và t-ng hp tài liu liên quan ñn vn ñ lý thuyt, phương
pháp mô hình hóa và phương pháp th*c nghim.
5. Ý nghĩa khoa hc và th'c ti(n c)a ñ tài
Kt qu nghiên cu có th! làm tài liu tham kho cho vic tìm hi!u các phương pháp
lp ch, m$c ph$c v$ tìm kim và so sánh hiu qu gia chúng, ñc bit là tài liu v cu
trúc d liu Trie ph$c v$ tìm kim. Ngoài ra, phn nghiên cu lý thuyt s+ cung cp mt
cách nhìn t-ng quát v h thng tìm kim, các phương pháp tìm kim.
6. B! cc lu*n văn
Lun văn ñưc trình bày cơ bn bao gm 3 chương chính.
CHƯƠNG 1: T0NG QUAN V1 TÌM KI2M THÔNG TIN TRÊN VĂN B4N
CHƯƠNG 2: TRIE - C5U TRÚC D6 LI7U TÌM KI2M CHU8I KÝ T9
CHƯƠNG 3: TRIE TÌM KI2M TRÊN CƠ S: D6 LI7U MARIADB
3
CHƯƠNG 1: T,NG QUAN V- TÌM KIM THÔNG TIN TRÊN
VĂN B.N
Trong chương này chúng tôi s+ trình bày khái quát v tìm kim thông tin
(Retrieval Information) và cu trúc cũng như phương thc hot ñng c)a h thng tìm
kim. Bên cnh ñó chúng tôi s+ gii thiu mt s h thng tìm kim trên Internet và trên
Desktop ñang ph- bin hin nay. Cui chương, chúng tôi s+ trình bày mt s ñánh giá và
ñnh hưng cho vic ng d$ng mã ngun m.
1.1. TÌM KIM THÔNG TIN
1.1.1. Khái quát v tìm ki/m thông tin
[1],[2],[3]
1.1.2. Mô hình tìm ki/m
[2]
Hình 1.1. Mô hình tìm kim
[2]
Hình 1.1 mô t mt mô hình tìm kim thông tin trong ñó “front-end process” là các
bưc x' lý liên quan ñn phn chương trình tương tác tr*c tip vi ngưi s' d$ng, ñi u
khi!n vic giao tip vi ngưi s' d$ng; “back-end process” là các x' lý liên quan ñn
phn chương trình ph$ tr phía sau, thưng ñưc ñt trên máy ch). Query parser phân
tích cú pháp truy vn và Search engine interface là giao din c)a máy tìm kim. Hình v+
này miêu t nhim v$ tương ng vi nhim v$ c)a B thu thp thông tin, B lp ch, m$c
và B tìm kim thông tin ñã ñưc nêu phía trên.