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

Download miễn phí Đồ án Xây dựng ứng dụng dựa trên mạng ngang hàng



MỤC LỤC
MỤC LỤC 1
LỜI CẢM ƠN 3
MỞ ĐẦU 4
Chương 1: TỔNG QUAN VỀ MẠNG CHIA SẺ FILE NGANG HÀNG 6
1.1. Giới thiệu về mạng ngang hàng (peer to peer – P2P) 6
1.1.1. Khái niệm cơ bản 6
1.1.2. Đặc điểm của các mạng ngang hàng 7
1.1.3. Tiện ích mạng P2P mang lại. 7
1.1.4. Những khó khăn trong thiết kế mạng ngang hàng 8
1.1.5. Phân loại các ứng dụng mạng ngang hàng 9
1.2. Mô hình mạng P2P 9
1.2.1. Mô hình tập trung 9
1.2.2. Mô hình phân tán. 12
1.3. Ưu, nhược điểm của P2P 13
1.3.1. Ưu điểm 13
1.3.2. Nhược điểm 14
1.4. Một số ứng dụng chia sẻ file ngang hàng 14
1.4.1. Hoạt động của Napster 15
1.4.2. Hoạt động của Gnutella 16
1.4.3. So sánh Gnutella và Napster 17
1.5. Một số nghiên cứu lý thuyết 18
Chương 2: MÔ TẢ MỘT SỐ PHƯƠNG PHÁP, 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 20
2.1. Tổ chức chỉ mục tìm kiếm 20
2.2. Tạo chỉ mục 20
2.3. Tìm kiếm dựa trên chỉ mục 22
2.4. Xếp hạng kết quả tìm kiếm 23
Chương 3: GIẢI PHÁP XÂY DỰNG ỨNG DỤNG 26
3.1. Khái quát ý tưởng 26
3.2. Cấu trúc chỉ mục 29
3.3. Đánh giá giải pháp 31
Chương 4: CÀI ĐẶT CHƯƠNG TRÌNH 33
4.1. Mô tả về thư viện mã nguồn mở Lucene 33
4.1.1. Khái quát về Lucene 33
4.1.2. Tổ chức chỉ mục logic của Lucene 34
4.1.3. Xây dựng và khai thác chỉ mục trong Lucene 35
4.2 Tổ chức chương trình 36
4.2.1. Khối chức năng cơ bản 36
4.2.2. Khối giao diện người dùng. 40
4.2.3. Khối giao tiếp ngang hàng. 42
4.2.4. Sơ đồ lớp của chương trình. 44
Chương 5: KẾT QUẢ THỰC HIỆN CHƯƠNG TRÌNH 45
5.1. Tìm kiếm theo nội dung 45
5.2. Theo dõi trạng thái chia sẻ và nội dung tài liệu 48
KẾT LUẬN VÀ CÁC HƯỚNG PHÁT TRIỂN 51
Phụ lục: MÃ NGUỒN MỘT SỐ LỚP QUAN TRỌNG 52
TÀI LIỆU THAM KHẢO 67
 
 





Để tải tài liệu này, vui lòng Trả lời bài viết, Mods sẽ gửi Link download cho bạn ngay qua hòm tin nhắn.

Ket-noi - Kho tài liệu miễn phí lớn nhất của bạn


Ai cần tài liệu gì mà không tìm thấy ở Ket-noi, đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:


ở hình dưới đây. Các khối có thể cùng kích thước hay được phân chia theo cấu trúc nội dung: đoạn tài liệu (paragraph), tệp tài liệu (file),
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
2.3. Tìm kiếm dựa trên chỉ mục
Dựa trên hệ thống chỉ mục được tổ chức theo cấu trúc file đảo ngược, thuật toán tìm kiếm thường tuân theo 3 bước sau:
Tìm kiếm trên bảng từ vựng: Tách, phân tích xâu truy vấn thành các từ đơn hay các cụm từ. Thực hiện tìm kiếm các từ, cụm từ này trên bảng từ vựng.
Thu thập danh sách thông tin vị trí của các từ, cụm từ tìm được sau bước một thông qua bảng vị trí.
Xử lý các thông tin thu thập được từ bước hai và tạo ra danh sách kết quả tìm kiếm.
Do bảng từ vựng được sắp xếp theo thứ tự từ điển nên thao tác tìm kiếm trên đó mất một chi phí cỡ O(logn) bằng cách sử dụng thuật toán tìm kiếm nhị phân. Bước thứ hai của thuật toán đơn giản chỉ là thu thập lại danh sách về thông tin vị trí của các từ đơn lẻ xuất hiện trong truy vấn thỏa mãn kết quả tìm kiếm trên bảng từ vựng. Bước thứ ba tương đối phức tạp trong trường hợp phải tìm kiếm cho các cụm từ. Khi đó người ta phải tổ chức tìm kiếm đồng thời trên các danh sách ứng với các từ đơn có mặt trong cụm. Bằng phương pháp trộn nhiều danh sách được sắp theo thứ tự vị trí người ta có thể tìm được những chuỗi tuần tự các từ theo đúng thứ tự trong cụm. Trong trường hợp chỉ mục có sử dụng kỹ thuật đánh địa chỉ khối, ta sẽ phải tiếp tục duyệt tuần tự bên trong nội dung của nhiều khối thu được từ các danh sách thông tin về vị trí để tìm ra những cụm thỏa mãn. Các xấp xỉ được đánh giá bằng lý thuyết cũng như các kết quả thực nghiệm cho thấy việc sử dụng chỉ mục theo cấu trúc file đảo ngược đem lại một thời gian tìm kiếm cũng như kích thước cần lưu trữ tăng theo kích thước file văn bản với một tốc độ chậm hơn tốc độ tăng của hàm tuyến tính. Điều này là không thể đạt được khi thực hiện tạo chỉ mục theo các cấu trúc khác.
2.4. Xếp hạng kết quả tìm kiếm
Khi tiến hành truy vấn tìm kiếm theo nội dung một tập hợp văn bản cho trước (gọi là thư viện) thì người dùng không chỉ muốn nhận về danh sách kết quả tìm kiếm mà họ còn muốn danh sách này phải được sắp xếp theo một tiêu chí nào đó. Tiêu chí này chính là độ liên quan (relevance) giữa các kết quả với truy vấn tìm kiếm do người dùng đưa ra. Việc này quy về 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. Bài toán này đã được nghiên cứu khá chi tiết và toàn diện trong lĩnh vực truy xuất thông tin. Trong mục này, chúng tui sẽ trình bày tóm lược nội dung của một thuật toán xác định độ liên quan nổi tiếng và hiện đang được sử dụng rộng rãi. Đó là thuật toán TF-IDF [12].
Xét bài toán trong trường hợp đơn giản: ta xem mỗi truy vấn q gồm một tập hợp các từ khóa ki . Với một văn bản D bất kỳ thuộc thư viện C thì ta có:
R(q) = Σ R(ki) (2.3.1)
Trong đó R(q) là độ liên quan của q với D còn R(ki) là độ liên quan của từ khóa ki với D.
Nếu một từ khóa ki xuất hiện nhiều lần hơn từ khóa kj trong văn bản D thì khi chỉ xét trong phạm vi văn bản D ta có thể nói rằng từ khóa ki mang ý nghĩa quan trọng hơn từ khóa kj. Hay trong phần lớn các trường hợp ta có thể rút ra rằng từ khóa ki có ảnh hưởng tới nội dung của văn bản D lớn hơn hay R(ki) > R(kj). Vậy 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) (tf viết tắt của term frequency).
Mặt khác nếu ta xét trên phạm vi toàn bộ thư viện C chứ không chỉ trong văn bản D nữa thì có một vấn đề khác nảy sinh. Nếu một từ khóa k xuất hiện trong văn bản D và cũng xuất hiện trong nhiều văn bản khác thuộc C thì ta có thể thấy từ khóa k không còn mang tính đặc trưng cho văn bản D nữa. Lúc này không chỉ có văn bản D mà từ khóa k còn liên quan tới nội dung của nhiều văn bản khác nữa. Khái quát điều này ta có thể suy ra nếu 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. Để định lượng cho tính chất này, đối với từ khóa ki ta đưa vào tham số idf(i) được tính như sau:
idf(i) = log(N/ni) (2.3.2)
Trong đó N là số văn bản có trong C và 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 (idf viết tắt của inverse document frequency).
Từ hai nhận xét quan trọng trên ta có thể rút ra rằng:
R(ki) = tf(i) * idf(i) (2.3.3)
Từ hai công thức (2.3.1) và (2.3.3) ta có thể suy ra 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)) (2.3.4)
Như vậy ta có thể 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ị này 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. Đó chính là nội dung của thuật toán TF-IDF .
Chương 3: GIẢI PHÁP XÂY DỰNG ỨNG DỤNG
3.1. Khái quát ý tưởng
Trong mục này chúng tui sẽ đưa ra giải pháp 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 (viết tắt là tài liệu). Ứng dụng cần đảm bảo 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.
Luồng thông điệp giữa các thành phần trong mạng.
Để thực hiện được ba chức năng lớn nêu trên chương trình sẽ được tách thành hai thành phần triển khai ở hai phía: phía các điểm nút và phía máy chủ tìm kiếm. Nhiệm vụ của thành phần triển khai trên máy chủ tìm kiếm:
Tổ chức xây dựng và cập nhật chỉ mục tìm kiếm.
Tiếp nhận truy vấn từ các điểm nút, tìm kiếm dựa trên chỉ mục và trả về danh sách kết quả.
Nhiệm vụ của thành phần triển khai tại các điểm nút:
Gửi tới máy chủ tìm kiếm các yêu cầu đăng nhập vào và đăng xuất ra khỏi hệ thống chia sẻ file ngang hàng.
Tiếp nhận yêu cầu của người dùng và gửi đến máy chủ tìm kiếm các thông báo chia sẻ hay dừng chia sẻ các file được lưu trữ tại các điểm nút.
Tiếp nhận truy vấn do người dùng nhập, gửi đến máy chủ tìm kiếm và tổ chức hiển thị kết quả trả về.
Tiếp nhận và gửi yêu cầu tải tài liệu kết quả của người dùng tới điểm nút đích. Đóng vai trò là phía client trong hoạt động tải tài liệu.
Tiếp nhận yêu cầu tải tài liệu được chia sẻ trên máy cục bộ và đóng vai trò một server cung cấp tài liệu cho các điểm nút khác.
Vấn đề cơ bản và khó khăn nhất của một hệ thống tìm kiếm theo nội dung là tổ chức tạo chỉ mục cho các tài liệu đồng thời duy trì việc cập nhật cho hệ thống chỉ mục này. 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 và đăng xuất khỏi hệ thống. Bởi vì đó là ba sự kiện dẫn đến việc thay đổi thông tin liên quan tới tính tồn tại của một tài liệu trong mạng chia sẻ file ngang hàng. Bài toán đặt ra là phải tiến hành cập nhật hệ thống chỉ mục tập trung nằm trên máy chủ tìm kiếm cho tất cả các tài liệu được lưu trữ phân tán, rải rác trên các điểm nút. Để giải quyết bài toán này, chúng tui đề xuất giải pháp phân chia việc việc cập nhật chỉ mục làm hai bước. Bước đầu tiên được thực hiện tại các điểm nút và bắt đầu khi có một trong ba sự kiện nói trên xảy ra. Sau khi bước này kết thúc, các điểm nút thông báo tới máy chủ tìm kiếm để thực hiện bước thứ hai là cập nhật trực tiếp vào hệ thống chỉ mục tập trung. Chi tiết hơn, với mỗi sự kiện xảy ra ở phía điểm nút ta sẽ thực hiện như sau:
Với sự kiện một tài liệu được chia sẻ: Bước đầu tiên, điểm nút sẽ tạo chỉ mục cho tài liệu được chia sẻ. Kết thúc bước này, bảng chỉ mục nhỏ của tài liệu này được chuyển lên cho máy chủ tìm kiếm. Tại máy chủ tìm kiếm, bước thứ hai là trộn bảng chỉ mục nhỏ này với bảng chỉ mục tập trung hiện thời để tạo ra một bảng chỉ mục tập trung mới.
Với sự kiện dừng chia sẻ một tài liệu: Điểm nút sẽ thực hiện bước đầu tiên và xác định được định danh của tài liệu sẽ dừng chia sẻ. Định danh này được chuyển lên cho máy chủ tìm kiếm. Máy chủ tìm kiếm sẽ tiến hành xóa bỏ các thông tin chỉ mục liên quan đến tài liệu này trong bảng chỉ mục tập trung.
Đăng xuất khỏi hệ thống: Hành động này của một điểm nút tương đương với việc dừng chia sẻ tất cả các tài liệu hiện đang được chia sẻ trên điểm nút đó. Sau bước đầu tiên, điểm nút cần chuyển tới cho máy chủ tìm kiếm định danh của chính nó và công việc của máy chủ tìm kiếm là tìm và xóa bỏ mọi thông tin chỉ mục liên quan đến các tài liệu được chia sẻ nằm trên điểm nút này.
Ngoài ra chúng ta cần quan tâm tới một sự kiện nữa xảy ra khi người dùng trên một điểm nút tiế...
Music ♫

Copyright: Tài liệu đại học © DMCA.com Protection Status