Luận văn:Nghiên cứu ứng dụng cấu trúc dữ liệu Trie cho tìm kiếm chuỗi ký tự

Chia sẻ: Nhung Thi | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST

Báo xấu

129
lượt xem 15
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo luận văn - đề án 'luận văn:nghiên cứu ứng dụng cấu trúc dữ liệu trie cho tìm kiếm chuỗi ký tự', luận văn - báo cáo, thạc sĩ - tiến sĩ - cao học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn:Nghiên cứu ứng dụng cấu trúc dữ liệu Trie cho tìm kiếm chuỗi ký tự

1 B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG Đ NG TH ÁNH PHƯ NG NGHIÊN C U NG D NG C U TRÚC D LI U TRIE CHO TÌM KI M CHU I KÝ T Chuyên ngành : KHOA H C MÁY TÍNH Mã s : 60.48.01 TÓM T T LU N VĂN TH C SĨ K THU T Đà N ng - Năm 2012
2 Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Ngư i hư ng d n khoa h c: PGS.TS. VÕ TRUNG HÙNG Ph n bi n 1: TS. NGUY N THANH BÌNH Ph n bi n 2: TS. NGUY N M U HÂN Lu n văn ñư c b o v t i H i ñ ng ch m Lu n văn t t nghi p th c sĩ k thu t h p t i Đ i h c Đà N ng vào ngày 03 tháng 03 năm 2012. Có th tìm hi u lu n văn t i: • Trung tâm Thông tin - H c li u, Đ i h c Đà N ng • Trung tâm H c li u, Đ i h c Đà N ng
1 M Đ U 1. Lý do ch n ñ tài G n ñây, h th ng kho d li u ngày càng ñư c m r ng và ñóng vai trò quan tr ng hơn ñ i v i ngư i ra quy t ñ nh; h u h t các truy v n ñ i v i m t kho d li u l n r t ph c t p và l p ñi l p l i; kh năng tr l i nh ng truy v n hi u qu là m t v n ñ mà nhi u h th ng ñang hư ng ñ n. Làm th nào ñ tăng t c ñ , c i thi n hi u su t truy v n luôn là câu h i l n và không ng ng tìm ki m l i gi i ñáp t i ưu. Hi n nay có r t nhi u k thu t ñư c áp d ng nh m tăng hi u qu truy v n, m i k thu t ñ u có nh ng th m nh riêng, TRIE là m t c u trúc d li u ñang ñư c tri n khai s d ng trong các h th ng tìm ki m l n hi n t i b i nhi u tính năng ưu vi t giúp ñ y nhanh t c ñ và hi u qu c a quá trình truy v n. Trư c th c tr ng ñó, tôi ch n nghiên c u và th c hi n ñ tài “Nghiên c u ng d ng c u trúc d li u TRIE cho tìm ki m chu i ký t ” dư i s hư ng d n 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à nh ng ngư i nghiên c u v Công ngh thông tin nói chung có thêm tài li u h tr tri n khai c u trúc d li u này ph c v cho công tác tìm ki m chu i ký t bên c nh các c u trúc d li u ñang s d ng hi n nay trong m t s h qu n tr cơ s d li u l n, ñ c bi t là các h qu n tr cơ s d li u mã ngu n m . 2. M c tiêu và nhi m v nghiên c u M c tiêu c a ñ tài là c u trúc d li u Trie ñư c tìm hi u và trình bày c th kèm theo vi c ng d ng trong MariaDB. Nhi m v nghiên c u bao g m ph n nghiên c u lý thuy t v các phương pháp t o ch m c và tìm ki m; tìm hi u các phương pháp Hash index, Bitmap Index, Btree Index và nghiên c u c u trúc d li u Trie, các bi n th c a Trie, các thao tác cơ b n trên c u trúc d li u này. D a trên các nghiên c u lý thuy t ñó, ñ tài ñưa ra ñư c tài li u Ti ng vi t v c u trúc d li u Trie ph c v cho vi c h c t p và nghiên c u.
2 3. Đ i tư ng và ph m vi nghiên c u Đ i tư ng nghiên c u c a ñ tài g m: Cơ s lý thuy t v các phương pháp tìm ki m, truy xu t d li u, ch m c và các k thu t l p ch m c ph c v tìm ki m, các gi i thu t liên quan ñ n c u trúc d li u TRIE. Ph m vi nghiên c u v h th ng tìm ki m thông tin nói chung và các k thu t l p ch m c ph c v công tác tìm ki m thông tin (Hash Index, Bitmap Index, Btree Index), tr ng tâm ñi sâu tìm hi u c u trúc d li u TRIE, các bi n th Trie nén và các thao tác căn b n 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 c u sau: Phương pháp tài li u nh m thu th p, phân tích và t ng h p tài li u liên quan ñ n v n ñ lý thuy t, phương pháp mô hình hóa và phương pháp th c nghi m. 5. Ý nghĩa khoa h c và th c ti n c a ñ tài K t qu nghiên c u có th làm tài li u tham kh o cho vi c tìm hi u các phương pháp l p ch m c ph c v tìm ki m và so sánh hi u qu gi a chúng, ñ c bi t là tài li u v c u trúc d li u Trie ph c v tìm ki m. Ngoài ra, ph n nghiên c u lý thuy t s cung c p m t cách nhìn t ng quát v h th ng tìm ki m, các phương pháp tìm ki m. 6. B c c lu n văn Lu n văn ñư c trình bày cơ b n bao g m 3 chương chính. CHƯƠNG 1: T NG QUAN V TÌM KI M THÔNG TIN TRÊN VĂN B N CHƯƠNG 2: TRIE - C U TRÚC D LI U TÌM KI M CHU I KÝ T CHƯƠNG 3: TRIE TÌM KI M TRÊN CƠ S D LI U MARIADB
3 CHƯƠNG 1: T NG QUAN V TÌM KI M 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 ki m thông tin (Retrieval Information) và c u trúc cũng như phương th c ho t ñ ng c a h th ng tìm ki m. Bên c nh ñó chúng tôi s gi i thi u m t s h th ng tìm ki m trên Internet và trên Desktop ñang ph bi n hi n nay. Cu i chương, chúng tôi s trình bày m t s ñánh giá và ñ nh hư ng cho vi c ng d ng mã ngu n m . 1.1. TÌM KI M 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 ki m [2] Hình 1.1 mô t m t mô hình tìm ki m thông tin trong ñó “front-end process” là các bư c x lý liên quan ñ n ph n chương trình tương tác tr c ti p v i ngư i s d ng, ñi u khi n vi c giao ti p v i ngư i s d ng; “back-end process” là các x lý liên quan ñ n ph n 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 v n và Search engine interface là giao di n c a máy tìm ki m. Hình v này miêu t nhi m v tương ng v i nhi m v c a B thu th p thông tin, B l p ch m c và B tìm ki m thông tin ñã ñư c nêu phía trên.
4 1.2. M T S PHƯƠNG PHÁP L P CH M C CHO TÌM KI M CHU I KÝ [3], [4] T - VĂN B N 1.2.1. Hash Index 1.2.2. Btree Index 1.2.3. Bitmap Index 1.3. M T S H TH NG TÌM KI M HI N CÓ 1.3.1. Công c tìm ki m trên m ng internet 1.3.2. Công c tìm ki m trên máy tính cá nhân 1.4. K T LU N VÀ ĐÁNH GIÁ Trong chương này chúng ta ñã tìm hi u nh ng ñi m cơ b n c a thông tin và các hình th c lưu tr c a chúng trên máy tính. Chương này cũng nghiên c u cơ b n các phương pháp tìm ki m thông tin ñã và ñang ñư c ng d ng trong lĩnh v c tài li u ñi n t . Đ c bi t, nghiên c u các phương pháp l p ch m c ph c v cho tìm ki m chu i ký t - văn b n, ñi n hình là phương pháp Hash Index, Btree Index và Bitmap Index. Thông qua vi c tìm hi u các phương pháp l p ch m c này, ñ tìm ra ñư c nh ng h n ch khi thao tác trên các phương pháp ñó, và ñ xu t tìm hi u phương pháp m i kh c ph c ñư c các h n ch y nhưng v n ñ m b o k th a ñư c các ñ c tính tích c c ñã có. C u trúc m i ñư c ñ xu t là Trie, ñư c trình bày c th trong chương sau. Bên c nh ñó còn tìm hi u c u trúc c a h th ng tìm ki m và tìm hi u m t s công c tìm ki m trên Internet và trên Desktop ñang phát tri n ng d ng hi n nay. Qua nh ng ki n th c ñó, chúng ta cơ b n ñã n m ñư c nh ng lý thuy t v lĩnh v c tra c u tìm ki m thông tin, n m ñư c m t s ñ c ñi m c a các ng d ng tìm ki m mà các hãng s n xu t l n ñã phát tri n. T ñó, t ng h p ñư c nh ng lý thuy t c n thi t nh t cho vi c xây d ng m t ng d ng tương t hay k th a thư vi n mã ngu n m ñ phát tri n theo ñúng quy chu n.
5 CHƯƠNG 2: TRIE - C U TRÚC D LI U TÌM KI M CHU I KÝ T Trong chương 1, chúng ta ñã tìm hi u nh ng ki n th c t ng quát liên quan ñ n tìm ki m thông tin trên văn b n và các phương pháp l p ch m c ñã ñư c s d ng, m i phương pháp có m t s ưu ñi m và h n ch nh t ñ nh; Trong chương này, chúng ta s tìm hi u v m t c u trúc d li u m i: Trie. C u trúc này ñư c s d ng k t h p v i các c u trúc ñã ñư c l p ch m c trư c ñây nh m kh c ph c nh ng h n ch ñã nêu. 2.1. C U TRÚC D LI U TRIE [5], [6] TRIE, phát âm là “try”, là t xu t phát t ch retrieval, ngư i phát minh ra nó là Edward Fredkin; là m t c u trúc d li u s d ng ký s trong khóa ñ t ch c và tìm ki m. M c dù trong th c t chúng ta có th s d ng r t nhi u h cơ s ñ phân tích các khóa bên trong các ký s , ví d chúng ta có th ch n các s t nhiên (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) ho c các ký t trong b ng ch cái Ti ng Anh (a – z, A – Z). Gi s các ph n t trong t ñi n c n tìm ki m là h sơ Sinh viên có ch a các trư ng như: Tên SV, chuyên ngành h c, ngày sinh, Mã s . Trong ñó, trư ng khóa là “Mã s ”, ñư c bi u di n b ng chín ký s th p phân t 1 ñ n 9. Đ th hi n ví d này, gi s r ng t ñi n ch có năm ph n t . Trư ng Tên và Mã s c a m i năm ph n t ñư c hi n th như hình bên dư i:
6 TÊN MÃ S Hoa 951-94-1654 Thanh 562-44-2169 Anh 271-16-3624 Vy 278-49-1515 Phong 951-23-7625 Hình 2.1. Năm ph n t trong t ñi n [6] Chúng ta phân chia thành 3 nhóm, nh ng ph n t có Mã s b t ñ u b ng ký s “2”; nh ng ph n t b t ñ u b ng ký s “5” và nhóm cu i cùng g m các ph n t b t ñ u b ng ký s 9. Nh ng nhóm nào có nhi u hơn m t ph n t thì s ñư c phân chia s d ng ký s ti p theo trong khóa ñ phân bi t. Vi c phân chia này s ñư c ti p t c cho ñ n khi m i nhóm ch còn duy nh t m t ph n t . K t qu quá trình phân chia trên ñư c mô t trong m t Tree có 10 ñư ng nhánh như hình dư i. Hình 2.2: Trie cho các ph n t hình 2.1 [7]
7 2.2. TÌM KI M TRONG TRIE 2.2.1. Khóa có chi u dài gi ng nhau Đ tìm ki m m t Trie cho m t ph n t v i khóa c a nó, chúng ta b t ñ u t g c và duy t d n xu ng phía dư i cho ñ n khi h t Trie ho c cho ñ n khi nút ñang duy t là m t nút lá. 2.2.2. Khóa có chi u dài khác nhau Trong ví d trên, t t c các phím có cùng s ký s , là 9 ký s . Trong các ng d ng th c t , có th s g p m t s trư ng h p mà các khóa khác nhau có s ký s khác nhau, thông thư ng, chúng ta s thêm ký s ñ c bi t (thư ng là #) vào cu i m i khóa. 2.3. CHI U CAO C A TRIE [6], [7] Trong trư ng h p x u nh t, t nút g c ñ n nút lá, m i ký s trong khóa ph i duy t qua m t nút nhánh. Khi ñó chi u cao c a Trie là t i ña, và là s ký s c a khóa c ng 1. Trong trư ng h p này, Trie mã s ñư c minh h a ví d trên có chi u cao là 10. 2.4. YÊU C U KHÔNG GIAN VÀ C U TRÚC NÚT [6] 2.5. CHÈN M T PH N T VÀO TRIE Đ chèn m t ph n t A v i khóa là K vào trong m t Trie thì vi c ñ u tiên ta ph i ti n hành tìm ki m trên Trie xem ñã có t n t i ph n t v i khóa K này chưa. N u trie ñã ch a ph n t v i khóa ñó, ta ti n hành thay th ph n t hi n hành v i ph n t A. N u Trie không ch a ph n t A v i khóa K, thì ph n t A s ñư c ñưa vào Trie b ng cách s d ng các th t c sau: Trư ng h p 1, th t c chèn n u k t qu tìm ki m cho khóa K k t thúc t i m t nút lá X b t kỳ, thì sau ñó, khóa c a ph n t t i X và khóa K s ñư c s d ng ñ xây d ng m t nhánh con m i thay th cho ph n t X.
8 Trong trư ng h p 2, th t c chèn khi k t qu tìm ki m ph n t A v i khóa K trong Trie k t thúc b i vi c duy t h t trie t i m t nút nhánh X b t kỳ nào ñó và không tìm th y k t qu . Lúc này chúng ta ch th c hi n m t thao tác ñơn gi n là thêm vào m t nút con (là m t nút lá) t i v trí nút X. Nút lá ñư c thêm vào chính là ph n t A v i khóa K. 2.6. LO I B M T PH N T KH I TRIE Đ lo i b m t ph n t A v i khóa K, vi c ñ u tiên chúng ta ph i tìm ki m ph n t v i khóa K này trong Trie. N u không có ph n t v i khóa K trong Trie thì m i vi c không có gì ñ th c hi n. Vì th , ta gi ñ nh r ng Trie chúng ta ñang thao tác có ch a ph n t A v i khóa K. Các nút lá X ñư c tìm th y ch a ph n t A s b lo i b và chúng ta xét duy t l i các nút nhánh trên ñư ng d n t nút lá X quay v nút g c c a Trie. S có m t s nút nhánh b lo i b n u chúng ch ch a duy nh t m t ph n t trong ñó. Vi c này ñư c l p l i cho ñ n khi chúng ta g p m t nút nhánh không b lo i b ho c cho ñ n khi chúng ta ñã ti n hành lo i b c nút g c c a Trie. Chúng ta hãy xem ví d minh h a t i hình 2.4 2.7. TRIE NÉN VÀ CÁC BI N TH Chúng ta quan sát trie c a hình 2.2. Trong Trie này, có m t vài nút nhánh (ñó là B, D, F), các nút này ch có m t nhánh duy nh t. Chúng ta có th c i thi n th i gian và không gian lưu tr c a Trie b ng cách lo i b t t c các nút nhánh mà ch có duy nh t m t nhánh con này. Trie k t qu thu ñư c t thao tác này ñư c g i là Trie nén. Khi các nút nhánh ch có m t con thì chúng s ñư c di chuy n kh i Trie. Ta c n lưu tr l i t t c nh ng thông tin này ñ ñ m b o vi c t ch c t ñi n ñư c chính xác. Các thông tin này ñư c lưu tr trong ba lo i c u trúc trie nén ñư c mô t dư i ñây.
9 2.7.1. Trie nén ki u s 2.7.2. Trie nén lư t b 2.7.3. Trie nén v i thông tin c nh 2.7.4. Yêu c u không gian c a Trie nén 2.8. TÌM KI M TI N T VÀ M T S NG D NG 2.9. K T LU N Trong chương này, tôi ñã nghiên c u và tìm hi u các v n ñ lý thuy t liên quan ñ n c u trúc d li u Trie khá c th bao g m nh ng ki n th c chung t ng quát v c u trúc Trie và nh ng thao tác cơ b n trên c u trúc d li u này. Qua vi c ñánh giá và so sánh v i các c u trúc d li u trư c, các phương pháp l p ch m c ñã ñư c s d ng, lu n văn tìm ra ñư c m t s ñi m h n ch c a c u trúc này và ñ xu t các bi n th nén c a trie. Qua chương này, ngư i ñ c có th có ñư c ki n th c cơ b n nh t v Trie, hư ng d n t ng bư c vi c th c hi n các thao tác khi s d ng c u trúc này, ñánh giá hi u su t c a c u trúc nói chung và các thao tác nói riêng.
10 CHƯƠNG 3: NG D NG TRIE TÌM KI M TRONG MARIADB Trong n i dung chương 2, chúng ta ñã tìm hi u sơ lư c v c u trúc Trie và nh ng thao tác cơ b n trên Trie. C u trúc này hi n ñang ñư c ng d ng ngày càng nhi u trên toàn th gi i, ñ c bi t trong vi c lưu tr và x lý v i các kho d li u l n. H qu n tr cơ s d li u mã ngu n m ngày càng ñư c nhi u ngư i l a ch n do nh “tính m ” cho ngư i dùng. Trong s ñó, không th không k ñ n MySQL v i c ng ñ ng ngư i s d ng r ng kh p và nh ng tính năng h tr ưu vi t. T khi ngư i sáng l p ra MySQL r i b Sun, c ng ñ ng ngư i s d ng MySQL trên toàn th gi i b t ñ u ti p c n v i MariaDB, m t nhánh r c a MySQL v i nh ng tính năng k th a hoàn toàn c a MySQL và ñư c tích h p thêm nhi u tính năng m i nh m kh c ph c nh ng h n ch c a các phiên b n MySQL trư c ñó. MariaDB cũng là m t h cơ s d li u mã ngu n m hoàn toàn mi n phí cho ngư i dùng, ngoài nh ng c u trúc d li u ñư c b trí như v i MySQL, MariaDB còn k t h p thêm nhi u c u trúc m i nh m t i ưu hóa quá trình truy v n d li u ñ phù h p v i nh ng kho d li u l n. M t trong các c u trúc ñư c s d ng là Trie (ñã trình bày chương 2). 3.1. MÔ T NG D NG Đ làm rõ hơn cho nh ng n i dung liên quan ñ n Trie ñã ñư c trình bày trong chương trư c, trong chương này, chúng ta s ti n hành nghiên c u ng d ng c u trúc khá m i này(c u trúc Trie) trong các truy v n c a h cơ s d li u MariaDB. Ch n MariaDB cho vi c ng d ng Trie vì ñây là m t h cơ s d li u mã ngu n m hoàn toàn mi n phí, ñang ñư c s d ng r ng rãi và d n thay cho MySQL v n ñã chi m ñư c r t nhi u tình c m c a c ng ñ ng ngư i s d ng trên toàn th gi i. Ngoài ra, ñ kh c ph c m t s l i h n ch trong quá trình s d ng MySQL. MariaDB ñã có r t nhi u c i ti n
11 m i trong tính năng h tr , t c ñ và kh năng truy v n d li u mà m t trong nh ng phát tri n ghi nh n là s d ng tích h p c u trúc d li u Trie h tr full-text-search. Theo ñó, n i dung sau ñây s trình bày nh ng ki n th c cơ b n v h cơ s d li u MariaDB, cách cài ñ t và l y mã ngu n t MariaDB trên môi trư ng Ubuntu. Đ làm rõ hơn cho c u trúc Trie ñã minh h a trong chương 2, sau khi cài ñ t thành công, d a trên vi c nghiên c u mã ngu n c a MariaDB, chúng ta s xác ñ nh c u trúc Trie ñư c ng d ng trong MariaDB như th nào và cài ñ t ra sao ñ ti n hành t i ưu hóa các thao tác truy v n ngay trên h cơ s d li u này. Qua ñó, chúng ta s bi t ñư c c u trúc Trie ñư c cài ñ t như th nào trong th c ti n. 3.2. MARIADB [7] 3.2.1. Gi i thi u chung [7] MariaDB, m t nhánh r c a MySQL, là m t máy ch cơ s d li u cung c p các ch c năng thay th cho MySQL. MariaDB ñư c xây d ng b i m t s các tác gi ban ñ u c a MySQL v i s h tr t c ng ñ ng các nhà phát tri n ph n m m mi n phí và mã ngu n m . Ngoài các ch c năng c t lõi c a MySQL, MariaDB cung c p m t t p h p phong phú các tính năng c i ti n bao g m công c lưu tr thay th , t i ưu hóa máy ch và các b n vá l i. Phiên b n MariaDB ñư c tung ra h i tháng 11/2008 b i Monty Widenius, ngư i ñ ng sáng l p ra MySQL. Widenius ñã công b s phát tri n c a r nhánh MariaDB ngay sau khi r i b ch c v là ngư i duy trì cho MySQL c a Sun. Cùng lúc nhà l p trình này ñã sáng l p ra Monty Program AB, m t công ty m i ñ ñưa r nhánh này ra th trư ng.
12 Hình 3.1. Trang ch MariaDB MariaDB là m t nhánh c a MySQL, m t trong nh ng h qu n tr cơ s d li u ph bi n nh t trên th gi i. T các d án nh phát tri n trên Web cho m t s trang Web n i ti ng và uy tín, MySQL ñã t ch ng minh b n thân m t cách v ng ch c, ñang tin c y, nhanh chóng và th t s là m t gi i pháp h u hi u cho vi c s p x p và lưu tr d li u. 3.2.2. Các phiên b n phát tri n 3.3. TRIE TÌM KI M TRONG MARIADB 3.4. CÀI Đ T TH NGHI M 3.4.1. Cài ñ t 3.4.1.1. Thu th p mã ngu n Như ñã gi i thi u, MariaDB là m t phiên b n ñư c r nhánh t MySQL, ñư c sáng l p b i nh ng ngư i m t th i là tác gi c a MySQL. Ngư i sáng l p hàng ñ u là Monty Widenius_ngư i ñã sáng l p ra MySQL và Monty Program AB Ngư i dùng kh p m i nơi trên th gi i có th truy c p vào ñ a ch http://mariadb.org/ ñ tìm hi u, h c h i và t i v b cài ñ t cũng như mã ngu n c a MariaDB cùng v i t t c các phiên b n ñư c phát hành.
13 Ngoài ch c năng h tr download cái gói cài ñ t khác nhau trên các môi trư ng khác nhau, http://mariadb.org/ còn có nhi u h tr khác cho ngư i dùng trong quá trình cài ñ t và ti p c n v i vi c s d ng, khai thác mã ngu n trên MariaDB. Hình 3.7. Trang download mariadb ñây, ngư i dùng có th l a ch n các phiên b n phát tri n phù h p v i yêu c u c a h , các h ñi u hành h tr Generic Linux, Linux Package, Solaris, Source code, Windows. Các gói h tr g m source tar.gz file, gzipped tar file, MSI Package, Zip file và RPM Package; CPU 64-bit ho c 32-bit. Khi ñã l a ch n gói download v i h ñi u hành phù h p, chúng ta ti n hành cài ñ t MariaDB, có th tham kh o mã ngu n ñ phát tri n. Các phiên b n t ñư c phát tri n t 5.1 ñ n 5.3 cũng có s h tr tương ng như nhau. Cách cài ñ t tương t như khi s d ng MySQL, ngư i dùng có th tham kh o t i file Install-source ho c install-win- source trong gói ñư c l a ch n t i v Hình 3.8. File Install-Source và Install-Win-Source
14 3.4.1.2. Cài ñ t th c thi Phiên b n MariaDB m i nh t là 5.3 hi n ñã có b n beta phát hành vào tháng 7/2011, tuy nhiên ch y n ñ nh và nhi u tính năng ưu vi t, ngư i dùng có th t i b n m i nh t này t i http://downloads.askmonty.org/mariadb/5.3/ ho c t i các phiên b n cũ là MariaDB 5.2 t i http://downloads.askmonty.org/mariadb/5.2/ hay phiên b n ñ u tiên 5.1 t i http://downloads.askmonty.org/mariadb/5.1/. Hình 3.9. Các gói cài ñ t c a phiên b n MariaDB 5.2 Trong m i phiên b n ñ u có nhi u gói ñ cài ñ t, b n c n ch n l a gói cài ñ t nào phù h p v i yêu c u c a mình .MariaDB ch y u ñư c khai thác trên các h ñi u hành mã ngu n m , b n thân nó cũng là mã ngu n m nên không ñư c cài ñ t theo ki u Wizard. Cài Mariadb trên Ubuntu có th dùng nhóm l nh sau: shell> groupadd mysql shell> useradd -g mysql mysql shell> cd /usr/local shell> gunzip < /path/to/mysql-VERSION-OS.tar.gz | tar xvf - shell> ln -s full-path-to-mysql-VERSION-OS mysql shell> cd mysql
15 shell> chown -R mysql . shell> chgrp -R mysql . shell> scripts/mysql_install_db --user=mysql shell> chown -R root . shell> chown -R mysql data shell> bin/mysqld_safe --user=mysql & Và ti n hành thay th phiên b n Mariadb b n ñang s d ng trong câu l nh cho phù h p. Sau khi hoàn t t vi c cài ñ t, chúng ta có th can thi p vào mã ngu n ñê nghiên c u, trích l c và phát tri n chương trình riêng. V i các c u trúc d li u ñư c t ch c s d ng, ngư i dùng s ñ c và trích l c ñ l a ch n nh ng ño n mã c n cho quá trình làm vi c c a mình. Chúng ta s ti n hành vi c download và cài ñ t th ngi m ñ i v i phiên b n MariaDB 5.2. S d ng máy o ch y h ñi u hành Ubuntu phiên b n 10.10 ñ download và cài ñ t như sau: - Dùng l nh ch y l y khóa c n thi t (apt –key) - Thêm l nh yêu c u c a h th ng vào file Source.list - C p nh p các gói - Ti n hành cài ñ t MariaDB trên ubuntu - Cài các gói h tr và khai thác
16 Hình 3.10. Mã ngu n ñư c m b ng Dev-C 3.4.2. Th nghi m Đ th ngh m, chúng ta ti n hành cài ñ t trên h ñi u hành Ubuntu 10.10, mariaDB 5.2. C u trúc d li u Trie ñây ñư c s d ng như m t Trie index và tích h p trong ch c năng Full-Text-Search. Sau khi cài ñ t, kh i ñ ng: sudo /etc/init.d/mysql restart, Màn hình thành công n u có l nh báo Hình 3.11. Kh i ñ ng MariaDB Trong ph m vi lu n văn, ch d ng l i th nghi m tìm ki m m t chu i trong Trie trong MariaDB, c u trúc Trie ñư c xây d ng lưu tr b ng m t danh sách các nút liên k t v i nhau, chúng ta ti n hành tìm ki m m t chu i trong danh sách các nút này.
17 Hình 3.12. Mã ngu n MariaDB ñư c s d ng sau khi cài ñ t thành công Sau khi cài ñ t thành công và can thi p vào mã ngu n c a MariaDB, ta ti n hành tìm hi u vi c ng d ng c u trúc d li u Trie trong MariaDB. Trong h qu n tr cơ s d li u MariaDB, c u trúc d li u Trie ñư c s d ng tích h p trong ch c năng full-text-search. Vi c ng d ng Trie cơ b n mô t như sau: C u trúc c a node Kh i t o Trie Phân b m t m ng con tr s s d ng
18 Phân b 1 nút m i và ñánh d u ñó là nút g c c a Trie So sánh, ñ i chi u chu i ñang truy v n và chu i t i nút, tr v 1 n u tìm th y, ngư c l i tr v 0. V i c u trúc ñư c xây d ng cơ b n như trình bày trên, Trie h tr ch c năng full- text-search trong MariaDB, phát huy tên tu i MySQL ñư c ñông ñ o ngư i s d ng trên th gi i s d ng. K t qu th nghi m trên MariaDB, v i d li u c th . T o cơ s d li u “vidu” v i b ng “staff”. Staff bao g m các trư ng: pk_id, firstname, lastname, age, details. Hình 3.13. T o cơ s d li u và b ng d li u