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ự

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ả
Nội dung trích xuất từ tài liệu:
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.01TÓ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ĩ kthu 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 Đ U1. 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 nghơ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 tph 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 nluô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 uk 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 thm 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 hth 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 uqu 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 ngd 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. TSVõ 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ênc 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 unà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 sd 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ơ sd 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èmtheo 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 och m c và tìm ki m; tìm hi u các phương pháp Hash index, Bitmap Index, Btree Indexvà 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 utrú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 ngvi 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. 23. Đ 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ìmki 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 ithu 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 chm c ph c v công tác tìm ki m thông tin (Hash Index, Bitmap Index, Btree Index), tr ngtâ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 ntrê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 unh 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ươngphá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ápl 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 utrú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 tcá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ănLu 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 NCHƯƠNG 2: TRIE - C U TRÚC D LI U TÌM KI M CHU I KÝ TCHƯƠ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ìmki 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ênDesktop ñ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 TIN1.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] ...