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

  • Số trang: 30 |
  • Loại file: PDF |
  • Lượt xem: 16 |
  • Lượt tải: 0
nganguyen

Đã đăng 34173 tài liệu

Mô tả:

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 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 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 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  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  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  Để 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 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 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  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  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  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 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 Hình 3: Luồng thông điệp giữa các thành phần trong mạng 13  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 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 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 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 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  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
- Xem thêm -