Báo cáo Xây dựng ứng dụng dựa trên mạng ngang hàng

Nội dung text: Báo cáo Xây dựng ứng dụng dựa trên mạng ngang hàng

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG NGÀNH CÔNG NGHỆ THÔNG TIN ====== ISO 9001:2000 BÁO CÁO ĐỒ ÁN TỐT NGHIỆP Tên đề tài: Xây dựng ứng dụng dựa trên mạng ngang hàng Giáo viên hướng dẫn: TS. Phạm Hồng Thái CN. Lương Việt Nguyên Sinh viên thực hiện : Nguyễn Thị Hoa Lớp: CT 702 Mã số sinh viên: 10401
2. NỘI DUNG CHÍNH I. Mục đích của đề tài. II. Kỹ thuật tạo chỉ mục cho tài liệu và tìm kiếm dựa trên chỉ mục . III. Giải pháp xây dựng ứng dụng. IV. Cài đặt chƣơng trình. V. Kết luận và hƣớng phát triển. 1
3. I. MỤC ĐÍCH CỦA ĐỀ TÀI  Tìm hiểu về mạng ngang hàng.  Xây dựng một chương trình ứng dụng chia sẻ file trong mạng ngang hàng theo kiến trúc lai ghép cung cấp khả năng tìm kiếm theo nội dung đối với các tài liệu thuần văn bản. 2
4. II. KỸ THUẬT TẠO CHỈ MỤC CHO TÀI LIỆU VÀ TÌM KIẾM DỰA TRÊN CHỈ MỤC 1. Tổ chức chỉ mục tìm kiếm.  Tìm kiếm một cách hiệu quả trên file văn bản.  Xâu truy vấn bao gồm một tập hợp các từ hoặc cụm từ.  Nhiệm vụ của thao tác tìm kiếm là trả về danh sách các file mà nội dung của chúng có chứa các từ, cụm từ trong xâu truy vấn. 3
5.  Phương pháp thực hiện quét một lần trên các file văn bản và lưu lại danh sách các thành tố có trong file, các thông tin đi kèm với mỗi thành tố .  Các thông tin này sẽ được tổ chức theo một cấu trúc dữ liệu riêng và được gọi là chỉ mục. 2. Tạo chỉ mục.  Có ba phương pháp chủ yếu để tạo chỉ mục dựa trên việc sử dụng các cấu trúc: file đảo ngược, mảng hậu tố và file chữ ký.  File đảo ngược là một cấu trúc dùng để tạo chỉ mục bằng phương pháp hướng từ. 4
6.  Cấu trúc file đảo ngược bao gồm hai thành phần cơ bản: bảng từ vựng và bảng vị trí. Hình 1: Tạo chỉ mục theo cấu trúc file đảo ngược. 5
7.  Để giảm kích thước lưu trữ bảng vị trí ta dùng kỹ thuật đánh địa chỉ khối. Hình 2: Tạo chỉ mục theo cấu trúc file đảo ngược sử dụng kỹ thuật đánh địa chỉ khối 6
8. 3. Tìm kiếm dựa trên chỉ mục Thuật toán tìm kiếm chia làm 3 bước:  Tìm kiếm trên bảng từ vựng.  Thu thập danh sách thông tin vị trí của từ, cụm từ tìm được sau bước 1 thông qua bảng vị trí.  Xử lý các thông tin thu thập được và tạo ra danh sách kết quả tìm kiếm. 7
9. 4. Xếp hạng kết quả tìm kiếm  Tiêu chí để sắp xếp kết quả tìm kiếm chính là độ liên quan giữa các kết quả với truy vấn tìm kiếm do người dùng đưa ra.  Bài toán xác định độ liên quan giữa một truy vấn q với các tài liệu trong một thư viện C cho trước.  Thuật toán xác định độ liên quan: Thuật toán TF-IDF(Term Frequency – Inverse Document Frequency) 8
10.  Xét bài toán đơn giản: truy vấn q gồm một tập hợp các từ khóa ki. Văn bản D bất kỳ thuộc thư viện C thì ta có: R(q) = Σ R(ki) (1) * R(q) là độ liên quan của q với D. * R(ki) là độ liên quan của từ khóa ki với D.  Xét trong phạm vi văn bản D: Tần suất xuất hiện của một từ khóa trong văn bản tỉ lệ thuận với độ liên quan của nó với văn bản đó.  Đại lượng tần suất xuất hiện này của từ khóa ki được gọi là tf(i). 9
11.  Xét trên pham vi toàn bộ thư viện C: từ khóa k xuất hiện trong càng nhiều văn bản thuộc C thì độ liên quan của nó đến D phải càng nhỏ hay R(k) tỉ lệ nghịch với số văn bản trong C có chứa từ khóa k.  Tham số idf(i) được tính như sau: idf(i) = log(N/ni) (2) * N là số văn bản có trong C * ni là số văn bản trong C có chứa ki. * idf(i) sẽ tăng khi ni giảm nghĩa là có ít văn bản trong C chứa ki. 10
12.  Từ (1) và (2) R(ki) = tf(i) * idf(i) (3)  Từ (1) và (3) công thức ước lượng độ liên quan của truy vấn q với một văn bản D thuộc C như sau: R(q) = Σ (tf(i) * idf(i)) (4)  Sắp xếp các văn bản thuộc C theo thứ tự giảm dần của đại lượng R(q).  Nếu đặt một ngưỡng dưới đối với giá trị R(q) thì ta sẽ lọc ra được một danh sách các tài liệu kết quả có độ liên quan với q giảm dần. 11
13. III. GIẢI PHÁP XÂY DỰNG ỨNG DỤNG 1. Khái quát ý tƣởng Ứng dụng thực hiện được 3 chức năng lớn sau:  Cho phép người dùng tại các điểm nút khi tham gia vào mạng có thể tiến hành chia sẻ và dừng chia sẻ các tài liệu nằm trên máy của mình.  Cho phép người dùng có thể đưa ra những truy vấn để tìm kiếm theo nội dung các tài liệu hiện đang được chia sẻ trên phạm vi toàn mạng.  Cho phép người dùng tải về các tài liệu được chia sẻ nằm trên một điểm nút khác. 12
14. Hình 3: Luồng thông điệp giữa các thành phần trong mạng 13
15.  Trong khuôn khổ một ứng dụng chia sẻ file ngang hàng, có ba sự kiện xảy ra ở phía các điểm nút đòi hỏi phải tiến hành cập nhật hệ thống chỉ mục là: * Chia sẻ một tài liệu. * Dừng chia sẻ một tài liệu. * Đăng xuất khỏi hệ thống.  Người dùng trên một điểm nút tiến hành cập nhật lại file tài liệu mà nội dung của nó đã có sự thay đổi tính từ lần chia sẻ đầu tiên hoặc từ lần cập nhật cuối cùng.  Máy chủ tìm kiếm sẽ tiến hành cập nhật chỉ mục tập trung trong điều kiện tương tranh. 14
16. Hình 4: Hoạt động của cơ chế cập nhật chỉ mục và tìm kiếm dựa trên chỉ mục. 15
17. 2. Cấu trúc chỉ mục  Các trường thông tin liên quan đến định danh của tài liệu: * session_id * document_id  Các trường thông tin liên quan đến việc định vị tài liệu: * IP_address * path  Các trường thông tin liên quan đến việc tìm kiếm nội dung của tài liệu: * name * content 16
18. 3. Đánh giá giải pháp  Ưu điểm: * Giúp phân chia công việc cập nhật chỉ mục cho cả hai phía – các điểm nút và máy chủ tìm kiếm – nhằm bảo đảm khai thác tốt hơn tài nguyên của mạng. * Theo dõi sự tồn tại của các tài liệu chia sẻ trên mạng.  Nhược điểm: Nguy cơ quá tải với máy chủ tìm kiếm.  Khắc phục: * Nâng cấp khả năng xử lý và mở rộng băng thông đầu vào của máy chủ tìm kiếm. * Cách giảm tỉ lệ kích thước chỉ mục của một tài liệu. 17
19. IV. CÀI ĐẶT CHƢƠNG TRÌNH 1. Mô tả về thƣ viện mã nguồn mở Lucene a. Khái quát về Lucene Hình 5: Nhiệm vụ, chức năng của thư viện Lucene [8]. 18
20.  Nhiệm vụ của Lucene: * Tạo chỉ mục cho các tài liệu để xây dựng nên hệ thống chỉ mục. * Tiếp nhận các xâu truy vấn của người dùng, thực hiện tìm kiếm dựa trên hệ thống chỉ mục đã có và trả về kết quả. b. Tổ chức chỉ mục logic của Lucene  Document  Field  Term 19
21. c. Xây dựng và khai thác chỉ mục trong Lucene  Lớp IndexWriter  Lớp IndexReader  Lớp QueryParser  Lớp IndexSearcher 2. Tổ chức chƣơng trình a. Khối chức năng cơ bản  Bộ phận triển khai phía máy chủ tìm kiếm bao gồm: * Lớp Server * Lớp ServerThread  Bộ phận triển khai tại phía điểm nút bao gồm: * Lớp ClientPeer * Lớp Indexer 20
22. b. Khối giao diện ngƣời dùng  Cửa sổ giao diện chính của chương trình (Lớp MainWindow). Hình 6: Cửa sổ giao diện chính của chương trình 21
23. Hình 7: Hộp thoại chọn tài liệu chia sẻ. 22
24.  Cửa sổ tìm kiếm (Lớp SearchWindow) Hình 8: Cửa sổ giao diện tìm kiếm 23
25. b. Khối giao tiếp ngang hàng  Lớp FileServer  Lớp FileServerThread  Lớp FilePeerThread c. Sơ đồ lớp của chƣơng trình 24
26. V. KẾT LUẬN VÀ CÁC HƢỚNG PHÁT TRIỂN Kết luận  Trình bày tổng quan về mạng chia sẻ file ngang hàng. Một số phương pháp, kỹ thuật tạo chỉ mục và tìm kiếm dựa trên chỉ mục cũng đã được giới thiệu nhằm mục tiêu áp dụng chúng để xây dựng một ứng dụng chia sẻ file ngang hàng có khả năng tìm kiếm theo nội dung.  Giải pháp để xây dựng một ứng dụng như vậy đã được đề xuất dựa trên cơ chế cộng tác trong việc quản lý, cập nhật hệ thống chỉ mục giữa máy chủ tìm kiếm và các điểm nút.  Xây dựng được chương trình thử nghiệm. 25
27. Các hướng phát triển:  Đưa vào các kiến thức trong lĩnh vực xử lý ngôn ngữ tự nhiên và sử dụng các phương pháp xếp hạng kết quả tìm kiếm tiên tiến nhất nhằm làm tăng chất lượng tìm kiếm, bám sát hơn nữa yêu cầu của người dùng.  Tiến hành cài đặt bổ sung một số thư viện để hỗ trợ cho chương trình thử nghiệm ban đầu có thể phân tích thêm nhiều định dạng văn bản (doc, pdf, ), từ đó mở rộng khả năng tìm kiếm trên nhiều loại văn bản khác nhau.  Cải tiến theo hướng tổ chức trong mạng không chỉ có một mà nhiều máy chủ tìm kiếm được kết nối với nhau và trao đổi thông tin chỉ mục cũng như hỗ trợ nhau trong việc đáp ứng các truy vấn. Giúp tăng khả năng mở rộng của mạng. 26
28. TÀI LIỆU THAM KHẢO [1] Napster Home Page. [2] Gnutella Development Home Page. [3] Freenet Home Page. [4] ICQ Home Page. [5] SETI@ Home Page. [6] Lucene Home Page. [7] Beverly Yang and Hector Garcia-Molina, “Comparing Hybrid Peer-to- Peer Systems”. Stanford University, USA. [8] Erik Hatcher and Otis Gospodnetic, “Lucene in Action”, Manning Publications Co, 2005. [9] F.Cuenca-Acuna and T.Nguyen, “Text-based content search and retrieval in ad hoc p2p communities”, Technical Report DCS-TR-483, Rutgers University, 2002. 27
29. [10] J. Heaps. Information Retrieval – Computational and Theoretical Aspects. Academic Press, 1978. [11] Juan Ramos, “Using TF-IDF to Determine Word Relevance in Document Queries ”, Department of Computer Science – Rutgers University, 2003. [12] Kian Pokorny, “Peer to Peer Networking and Filesharing”, CSI 490 Senior Semina, 2004. [13] Ramesh Subramanian and Brian D. Goodman, “Peer to Peer Computing: The Evolution of a Disruptive Technology”, Idea Group, 2005. [14] R.A. Baeza-Yates and B.A. Ribeiro-Neto, “Modern Information Retrieval.” ACM Press Series / Addision Wesley, New York, 1999. [15] Songmei Han, Bijit Hore, Ilya Issenin, Sean McCarthy and Shannon Tauro, “HollyShare: Peer-to-Peer File Sharing Application”, Final Report, 2001. [16] Stephanos Androutsellis-Theotokis and Diomidis Spinellis, A Survey of Peer-to-Peer Content Distribution Technologies, ACM Computing Surveys, December 2004. [17] V.Kalogeraki, D.Gunopulos and D. Zeinalipour-Yazti, “A local search mechanism for peer-to-peer network”, In Proc. Of the 11th International Conference on Information Knowledge Managament, 2002. 28
30. Em xin chân thành cảm ơn! 29