BÀI GI NG TH VI N S
Ư Ệ Ố
Ả
CH
NG 3:
ƯƠ
Ỉ Ụ
Ệ
Ả CH M C TÀI LI U VĂN B N
Ỗ TS. Đ QUANG VINH
HÀ N I - 2013 Ộ
N I DUNG
Ộ
I. T NG QUAN V TH VI N S DL Ề Ư Ệ Ố Ổ
II. MÔ HÌNH HÌNH TH C CHO TH VI N S DL Ứ Ư Ệ Ố
III. CH M C TÀI LI U Ỉ Ụ Ệ
IV. TÌM KI M THÔNG TIN Ế
V. CÁC CHU N S D NG TRONG TH VI N S Ẩ Ử Ụ Ư Ệ Ố
Ầ Ệ Ề
22
VI. TH C HÀNH H PH N M M TH VI N S GREENSTONE Ự Ư Ệ Ố
III.
Ỉ Ụ
Ệ
Ả CH M C TÀI LI U VĂN B N
ể ỉ ụ ị
i h n t ớ ạ ố
(từ đ nh n d ng đ i v i ch m c): là m t ạ ậ ộ ố ớ ch và s , nh ng gi i đa ư ố ự ữ s ự ố 3.1 M Đ UỞ Ầ Đ nh nghĩa 3.1 ự ạ ủ ố ự
dãy c c đ i c a các ký t i đa 4 ký t và t 256 ký t B ng 3.1 - CSDL TREC
ả S tài li u N 741856 ố
333338738 ệ S thu t ng F ậ ữ ố
S thu t ng riêng bi t n ữ ậ ố ệ 535346
S con tr ch m c f 134994414 ỏ ỉ ụ ố
33
Kích th c t ng (MB) 2070.29 ướ ổ
ả ữ ệ Ả ỗ
ệ ấ Ch m c ủ ị (Đ Trung Tu n): ể
ỉ ụ là b ng d li u hay ị c u trúc d li u dùng đ xác đ nh v trí c a các dòng trong t p ị ấ theo đi u ki n nào đó 3.2 CH M C T P Đ O IFID Ỉ Ụ Ệ Đ nh nghĩa 3.2 ữ ệ ệ
ỉ ụ là
m t cách tìm ki m thông tin
ỉ ụ là m t c ch nh m đ nh v thu t ng ữ ộ ơ ế ằ ậ ị ị
c trong văn b n
(ch m c t p đ o IFID) ỉ ụ ệ ố ớ ả ộ
ừ ể ư
ị ộ ị cho tr ị ữ ộ ứ i t ỏ ớ ấ ả ộ ấ
ệ ủ ỏ ả ộ
ượ ữ ệ ệ ấ ộ
ỏ
44
ề Đ nh nghĩa 3.3 (Folk M.J., Zoellick B., Riccardi G.): Ch m c ế Đ nh nghĩa 3.4 : Ch m c ả ướ Đ nh nghĩa 3.5 : Đ i v i m i m t thu t ậ ỗ ng trong t đi n, m t IF ch a m t danh sách đ o (IL) l u tr ộ ữ ả m t danh sách con tr t t c xu t hi n c a thu t ng đó trong ữ ậ văn b n chính, trong đó m i m t con tr trong th c t là s tài ố ự ế ỗ c coi là m t danh li u mà thu t ng đó xu t hi n. IL đôi khi đ ụ ụ sách m c l c và các con tr là m c l c nhiên nh t, g n t ấ ỉ ụ ự ầ ươ ứ
ng pháp ch m c t ố ậ ụ ụ ươ ủ Đây là ph ỉ ụ ụ ụ ớ ề ộ ớ
ng ng v i ch m c c a m t cu n sách và v i cách dùng m c l c truy n th ngố
ệ B ng 3.2 - Văn b n m u; m i dòng là m t tài li u ỗ ộ ả ả ẫ
TÀI LI U Ệ VĂN B NẢ
Information retrieval is searching and indexing 1
2 Indexing is building an index
3 An inverted file is an index
55
4 Building an inverted file is indexing
B ng 3.3 - IF đ i v i văn b n c a b ng 3.2
ố ớ
ữ
ả ủ ả IL(tài li u; v trí) ị ệ (2;4), (3;1), (3;5), (4;2) (1;5) (2;3), (4;1) (3;3), (4;4) (2;5), (3;6) (1;6), (2;1), (4;6) (1;1)
(3;2), (4;3)
(1;3), (2;2), (3;4), (4;5)
(1;2)
ả Thu t ngậ an and building file index indexing information inverted is retrieval searching
Số 1 2 3 4 5 6 7 8 9 10 11
(1;4)
66
Đ nh nghĩa 3.6: Đ h t ị
ỉ ụ là tính chính xác đ nh n d ng v trí c a thu t ng ữ ộ ậ ị
đ i v i văn b n c a b ng 3.2
(Tài li u; t ) ừ ệ <4; (2;4), (3;1), (3;5), (4;2)> <1; (1;5)> <2; (2;3), (4;1)> <2; (3;3), (4;4)> <2; (2;5), (3;6)> <3; (1;6), (2;1), (4;6)> <1; (1;1)>
<4; (1;3), (2;2), (3;4), (4;5)>
ộ ạ (granularity) c a m t ch m c ể ậ ạ ứ ừ ố ớ ủ ủ ả ủ ả
B ng 3.4 - IF m c t ả Thu t ngậ ữ an and building file index indexing information inverted<2; (3;2), (4;3)> is retrieval<1; (1;2)>
Số 1 2 3 4 5 6 7 8 9 10 11 searching
<1; (1;4)>
77
Xây d ng ch m c t p đ o IFID ỉ ụ ệ ả ự
Xây d ng ch m c là m t trong nh ng nhi m v thách th c ỉ ụ ự ữ ụ ứ ệ ộ
nh t ph i đ ả ươ ấ ng đ u khi xây d ng m t CSDL. ự ầ ộ
đây, ta đ c p đ n bài toán xây d ng ch m c t p đ o IFID, Ở ỉ ụ ệ ề ậ ự ế ả
vì đây là d ng ch m c thi t th c nh t đ i v i c hai truy v n ỉ ụ ạ ế ấ ố ớ ả ự ấ
BQ và RQ.
Quá trình xây d ng ch m c đ ỉ ụ ự ượ c coi là s đ o văn b n. T ừ ự ả ả
đi n The Concise Oxford Dictionary đ nh nghĩa “ ể ị s đ o là đ o ự ả ả
i, đ o v trí, tr t t ho c quan h bình th l n trên d ộ ướ ả ị ậ ự ặ ệ ườ ” và ng
88
đây đúng là đi u ph i làm đ t o l p ch m c. ể ạ ậ ỉ ụ ề ả
Xét văn b n m u b ng 3.2 ẫ ở ả ả
M i tài li u c a văn b n ch a m t s thu t ng ch m c và ữ ỉ ụ ệ ủ ộ ố ứ ả ậ ỗ
m i m t thu t ng ch m c xu t hi n m t s dòng. Quan ữ ỉ ụ ệ ở ộ ố ậ ấ ỗ ộ
c bi u di n v i m t ma tr n t n su t, trong đó h có th đ ệ ể ượ ậ ầ ể ễ ấ ộ ớ
m i m t c t t ng ng ộ ộ ươ ứ ng ng v i m t t ớ ộ ừ ỗ , m i m t hàng t ộ ỗ ươ ứ
i hàng và c t b t kỳ là t n su t v i m t tài li u và s ch a t ệ ớ ố ứ ạ ộ ộ ấ ấ ầ
ch đ nh b i c t đó. Ma tr n t n su t đ i v i văn b n c a t ủ ừ ỉ ấ ố ớ ậ ầ ở ộ ả ị
99
c trình bày b ng 5.1 c a b ng 3.2 đ ủ ả ượ ở ả
Thu t ngậ
ữ
information retrieval
searching
indexing
building
index inverted file
1
1
1
-
1
-
-
-
-
2
-
-
-
1
1
1
-
-
3
-
-
-
-
-
1
1
1
4
-
-
-
1
1
-
1
1
1010
B ng 5.1 - Ma tr n t n su t đ i v i văn b n c a b ng 3.2 ả ủ ả ấ ố ớ ậ ầ ả
B ng 5.2 - Chuy n v t ng đ ể ị ươ ả ươ ủ ấ ủ ả ậ ầ
ng c a ma tr n t n su t c a b ng 5.1
Tài li uệ
Số Thu t ngậ ữ
1 2 3 4
1 information 1 - - -
2 retrieval 1 - - -
3 searching - - - -
4 indexing 1 1 - 1
5 building - 1 - 1
6 index - 1 1 -
7 inverted - - 1 1
1111
8 file - - 1 1
GI Ả I THU T 5.1 Đ O DANH SÁCH MÓC N I Ố Ậ Ả
1. S n xu t m t ch m c đ o đ i v i m t CSDL tài li u ỉ ụ ả ố ớ ệ ấ ộ ả
ạ
ừ ể ỗ /* Pha 1 - t p h p các xu t hi n thu t ng */ ợ đi n r ng S. ấ ữ ệ ậ
Đ i v i m i m t tài li u Dd trong CSDL, 1 ≤ d ≤ N, ộ /* Kh i t o */ ở ạ 2. T o ra m t c u trúc t ộ ấ ậ ộ ố ớ ệ
d , phân tích cú pháp nó thành các thu t ng ch m c ữ ỉ ụ
ỗ a. Đ c Dọ ậ
˛ b. Đ i v i m i m t thu t ng ch m c t ữ ỉ ụ ố ớ ậ ộ ỗ Dd
d
ậ ầ ữ
ố ớ ế
ế
i. Cho fd,t là t n su t c a thu t ng t trong D
ấ ủ
ii. Tìm ki m S đ i v i t
iii. N u t không có trong S, chèn nó
iv. Thêm m t nút l u tr
1212
ng ng v i thu t ng t t ươ ứ ữ ậ ớ
3. /* Pha 2 - đ u ra c a IF */ ầ ủ
Đ i v i m i m t thu t ng 1 ≤ t ≤ N ố ớ ữ ậ ộ ỗ
a. B t đ u m t m c vào IF m i ớ ộ ắ ầ ụ
b. Đ i v i m i m t
t,
ụ thêm
a. N u yêu c u, nén m c vào IF ụ ế ầ
b. Thêm m c vào IF này vào IF.
ầ
(đ c và phân tích cú pháp văn b n) ụ Th i gian đ o T yêu c u là: ả ọ ả
1313
(ghi IF nén) ờ T = Btr + Ftp + I(td + tr)
Hình 5.1 - C u trúc d li u bi u di n IF đ i v i văn b n c a b ng 3.2 ễ ả ủ ả ố ớ ữ ệ ể ấ
information
1
1
retrieval
1
2
searching
1
4
indexing
1
6
4
6
2
1
buiding
2
3
4
1
index
2
5
3
6
inverted
3
2
4
3
file
3
3
4
4
1414
3.3 CH M C T P KÝ S SFID Ỉ Ụ Ệ
ả ệ ố ớ
Ố ồ ố ữ
ươ
ấ ể ỉ ụ ộ ế ắ ỗ ộ ố
ệ ộ
: S truy c p SF có th đ ự ố
c tăng nhanh ể ượ ậ ậ bitslicing, t c là k thu t ỹ ứ ậ ỹ
1515
T p ký s bitslice ằ ể ị B ng 3.5 – Mã hoá ch ng lên c a tài li u 2 đ i v i SF ủ Ký s thu t ng Thu t ngậ ữ ậ 0001 0000 1100 0100 indexing 0100 0100 0001 0000 is 0101 0011 0000 0000 building 0000 0100 0100 1100 an 1100 1000 0010 0000 index 1101 1111 1111 1110 Ký s bloc ố T p ký s SF: là m t ph ng pháp xác su t đ ch m c văn ộ ố ệ b n. M i m t tài li u có m t ký s liên k t, m t xâu bit b t ộ ệ ả n i dung tài li u theo m t nghĩa nào đó ộ ệ h n b ng cách dùng k thu t ơ chuy n v ma tr n bit ậ
3.4 SO SÁNH CÁC PH ƯƠ Ỉ Ụ NG PHÁP CH M C
Ph ỉ ụ ệ ỉ ụ ệ ả ố
ươ là hai ph ng pháp ch m c t p đ o IFID và ch m c t p ký s SFID ng pháp ch m c chính tài li u trong th vi n s . ư ệ ố ỉ ụ ươ ệ
ậ ệ ỉ ụ Ở ầ ứ
Quy lu t ch m c tài li u trong DL : ạ
c ch m c và t c đ truy v n. IF nén là ph ệ ố ơ ộ
ệ
h u h t các ng ế t h n SF trong ph m vi c a c hai kích d ng, IF th c hi n t ủ ả ụ ự ng pháp ch th ỉ ươ ấ ố ỉ ụ ướ m c h u ích nh t m t CSDL l n các tài li u văn b n có đ dài ụ ữ ộ ả ớ ộ ấ có th thay đ i. ể ổ
3.5 CÁC MÔ HÌNH NÉN IFID
3.5.1 Đ t v n đ ặ ấ ề
ng pháp mã hoá đ nén IFID ả ươ ể
c ệ ủ ộ ể ượ
1616
Kh o sát các mô hình và ph CSDL tài li u trong th vi n s . ư ệ ố Chìa khoá c a bài toán nén là nh n xét m i m t IL có th đ ỗ ậ l u tr nh m t dãy s nguyên tăng d n. ư ữ ư ộ ầ ố
3.5.2 Mô hình nén toàn c cụ
Mô hình không tham s ố Mô hình Bernoulli toàn c cụ
3.5.3 Các mô hình nén c c bụ ộ
1717
Mô hình hyperbol c c b ụ ộ Mô hình Bernoulli c c bụ ộ Mô hình Bernoulli l chệ Mô hình nén n i suy ộ
ệ ủ
ằ
S bit/con tr 3.5.4 Hi u năng c a các mô hình nén ch m c ỉ ụ ỏ ố ớ ỏ B ng 3.9 - Nén IF b ng s bit/con tr đ i v i TREC ố ố
1918
ả Mô hình Mô hình toàn c cụ Đ n nguyên ơ Nh phân ị Bernoulli
g
d 20.00 12.30 6.63 6.38
1818
Mô hình c c bụ ộ Hyperbol Bernoulli Bernoulli l chệ N i suy 5.89 5.84 5.44 5.18 ộ
NH N XÉT : Ậ
ự ụ ộ
ụ ệ ề ờ ng th c hi n nén t ả ơ
ứ ạ ướ ặ
ỉ ụ ặ
t h n mô Các mô hình c c b có xu h ố ơ ướ hình toàn c c và không hi u qu h n v th i gian x lý đòi ử ệ ng cài đ t ph c t p i mã, vì chúng có xu h h i trong khi gi ả ỏ h n. Đ i v i m c đích th c hành, mô hình nén ch m c phù ự ụ ơ ố ớ h p nh t là ph ng pháp Bernoulli c c b , cài đ t dùng k ỹ ụ ộ ươ ấ ợ thu t mã hoá Golomb ậ
3.6 CÁC HI U NG
ữ (case folding)
Ệ Ứ G p d ng ch ộ ạ Truy g c t ố ừ (stemming)
1919
(stop word) T b qua ừ ỏ
TÀI LI U THAM KH O Ả Ệ
1. Đ Quang Vinh (2009), ỗ ế , Th vi n s - Ch m c và Tìm ki m ư ệ ố ỉ ụ
Nxb Đ i h c Qu c gia Hà N i. ạ ọ ộ ố
ậ ở
2. Lourdes T.D. (2006), Th vi n s và truy c p m tài li u l u ệ ư ư ệ ố trữ, Nguy n Xuân Bình và nnk biên d ch, UNESCO, Hà N i. ộ ễ ị
3. Arms W.Y. (2003), Digital Libraries, MIT Press, Cambridge.
4. Fox E.A. (2000), Advanced Digital Libraries, Virginia
Polytechnic Institue and State University.
5. Lesk M. (2005), Understanding Digital Libraries, 2nd Edition,
Morgan Kaufmann, San Francisco.
2020
6. Witten I.H., Bainbridge D. (2003), How to Build a Digital
Library, Morgan Kaufmann, San Francisco.
K T THÚC !
Ế
TRÂN TR NG CÁM N !
Ơ
Ọ
2121
