giacmokhongcothat3
New Member
Download Luận văn Một số giải pháp cho bài toán tìm kiếm trong cơ sở dữ liệu Hypertext
Phần mở đầu .2
Chương I. Tổng quan vềwebưmining . 9
1.1 Giới thiệu về cơ sở dữ liệu Fulltext và Hypertext . 9
1.1.1 Cơ sở dữ liệu Fulltext . 9
1.1.2 Cơ sở dữ liệu Hypertext . 12
1.1.3 So sánh đặc điểm của dữ liệu Fulltext và dữ liệu trang web . 15
1.2 Tổng quan về phương pháp biểu diễn văn bản trong cơ sở dữ liệu trang web . 16
1.2.1 Giới thiệu sơ bộ về các phương pháp biểu diễn trang web. 17
1.2.2 Cách tiếp cận theo web site. 19
Kết luận chương một. 28
Chương II. Một số phương pháp biểu diễn trangweb và giải pháp kết hợp. . 29
2.1 Phương pháp biểu diễn trong các máy tìm kiếm. 30
2.1.1 Cấu trúc cơ bản và hoạt động của một máy tìm kiếm. 31
2.1.2 Phương pháp biểu diễn dữ liệu trong các máy tìm kiếm. 34
2.2 Phương pháp biểu diễn trang web theo mô hình vector . 45
2.2.1 Phương pháp biểu diễn vector . 45
2.2.2 Phương pháp biểu diễn trang web theo mô hình vector . 48
2.3 Đề xuất giải pháp biểu diễnvector trong máy tìm kiếm . 55
Kết luận chương 2 . 59
Chương III. máy tìm kiếm vietseek và thử nghiệm Thuật toán tìm kiếm theo nội dung . 61
3.1 Máy tìm kiếm VietSeek . 61
3.1.1 Các đặc điểm cơ bản của Vietseek. 61
3.1.2 Cơ sở dữ liệu của Vietseek. 62
3.2 Đề xuất thuật toán tìm kiếm mới cho máy tìm kiếm VietSeek . 69
3.2.1 Những cơ sở để đề xuất thuật toán . 69
3.2.2 Thuật toán . 71
Kết luận chương 3 . 74
Phần kết luận 75
tài liệu tham khảo
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
liệu fulltext thông th−ờng) không còn phù hợp nữa, hay là hoạt động không hiệu quả.
Một nhu cầu đ−ợc đặt ra là phải xây dựng các ph−ơng pháp biểu diễn mới, hay cải tiến
các ph−ơng pháp biểu diễn dã có cho phù hợp với các điều kiện mới.
Sau đây, chúng tui trình bày chi tiết hai lớp ph−ơng pháp biểu diễn trang web phổ
biến hiện nay để chỉ ra đ−ợc sự thay đổi và cải tiến phù hợp với điều kiện của từng bài
toán tìm kiếm khác nhau. Lớp ph−ơng pháp thứ nhất đ−ợc dùng trong các hệ thống máy
Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext
Phạm Thị Thanh Nam – Luận văn cao học
30
tìm kiếm, trong đó nhấn mạnh ngữ nghĩa của việc liên kết các trang web trong việc tính
hạng của trang web. Trong quá trình tiền xử lý văn bản trang web, hạng của nó đ−ợc
hoàn thiện dần theo công thức tính dần từng b−ớc cho đến khi hoàn thiện hệ thống. Sau
đó, hạng của trang web đ−ợc dùng cho việc hiển thị các trang web kết quả tìm kiếm cho
ng−ời dùng. Lớp thứ hai dựa trên việc phát triển mô hình vector trong biểu diễn dữ liệu
fulltext. Đại diện cho lớp ph−ơng pháp theo h−ớng này đ−ợc Sean Slattery trình bày
[11]. Mỗi trang web đ−ợc t−ơng ứng với một vector biểu diễn. Câu hỏi tìm kiếm đa
dạng và phong phú hơn lớp thứ nhất và kết quả tìm kiếm đ−ợc hiển thị dựa theo "độ gần
nhau" của câu hỏi với các trang web.
2.1 Ph−ơng pháp biểu diễn trong các máy tìm kiếm
Sự phát triển nhanh chóng của mạng Internet và Intranet đã sinh ra một khối
l−ợng lớn các trang web. Cùng với sự phát triển và thay đổi hàng ngày hàng giờ
về nội dung cũng nh− số l−ợng của các trang web trên Internet thì vấn đề tìm kiếm
thông tin đối với ng−ời sử dụng lại ngày càng khó khăn. Một vấn đề cần đ−ợc giải
quyết là: Làm thế nào để tìm ra đ−ợc các trang web có mang thông tin cần thiết trong
số hàng tỷ các trang web? Việc này chỉ có thể thực hiện đ−ợc nhờ vào các máy tìm
kiếm (search engine) hiện đang đ−ợc cung cấp rộng rãi cho mọi ng−ời sử dụng trên
Internet, chẳng hạn nh− Yahoo, Google, Altavista...
Máy tìm kiếm là các hệ thống đ−ợc xây dựng có khả năng tiếp nhận các yêu cầu
tìm kiếm của ng−ời dùng (th−ờng là một tập các từ khoá), sau đó phân tích và tìm kiếm
trong cơ sở dữ liệu đã có sẵn và đ−a ra các kết quả các trang web cho ng−ời sử dụng.
Nh− đã biết, bài toán biểu diễn và tìm kiếm thông tin trên Internet đặt ra nhiều
thách thức. Thứ nhất, tập hợp trang web trên Internet là một tập dữ liệu khổng lồ, phân
tán trên rất nhiều máy tính khắp nơi trên thế giới. Thứ hai, nội dung các trang web
không hoàn toàn đồng nhất, chẳng hạn vấn đề ngôn ngữ trình bày trang web bao gồm
rất nhiều loại ngôn ngữ khác nhau (cả ngôn ngữ diễn tả nội dung lẫn ngôn ngữ lập
trình), nhiều loại định dạng khác nhau (text, HTML, PDF, hình ảnh, âm thanh,...),
Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext
Phạm Thị Thanh Nam – Luận văn cao học
31
nhiều loại từ vựng khác nhau (địa chỉ email (email addresses), các liên kết (links), các
mã nén (zip code), số điện thoại (phone number),...). Và thứ ba là nội dung trang web
thay đổi liên tục và không ai có thể kiểm soát nổi. Các nghiên cứu về kích th−ớc của hệ
thống web đã đ−a ra các số liệu sau đây để minh chứng cho các khó khăn đó [6]. Hiện
nay có khoảng hơn một tỷ các trang web đ−ợc cung cấp cho ng−ời sử dụng, giả sử kích
th−ớc trung bình của mỗi trang web là 5-10 KB, thì kích th−ớc tổng cộng của hệ thống
ít nhất khoảng 10 terabyte. Mặt khác, tốc độ tăng số l−ợng các trang web cũng rất
nhanh, chẳng hạn, trong hai năm gần đây số l−ợng các trang web đã tăng lên gấp đôi.
Ngoài số l−ợng lớn các trang web đ−ợc tạo mới thì các trang web đang tồn tại trên
Internet cũng không ngừng cập nhật thông tin. Theo kết quả nghiên cứu hơn 500.000
trang web trong hơn 4 tháng thì 23% các trang thay đổi hàng ngày. Trong các site mà
tên miền có đuôi .com thì 40% các trang thay đổi hàng ngày, và khoảng 10 ngày thì
50% các trang trong các tên miền đó biến mất, nghĩa là địa chỉ URL của chúng không
còn tồn tại nữa.
Các thách thức trên đây cho thấy việc biểu diễn dữ liệu trong các máy tìm kiếm là
rất quan trọng. Biểu diễn các trang web nh− thế nào để vừa có khả năng l−u trữ đ−ợc
một số l−ợng lớn các trang web đó, vừa cho phép máy tìm kiếm thực hiện việc tìm
kiếm nhanh chóng và chính xác. Tr−ớc hết chúng ta khảo sát cấu trúc cơ bản của máy
tìm kiếm và hoạt động của nó.
2.1.1 Cấu trúc cơ bản và hoạt động của một máy tìm kiếm
Cấu trúc điển hình của một máy tìm kiếm đ−ợc mô tả nh− trong hình 2.1. Trong
thực tế thì mỗi máy tìm kiếm lại có các sửa đổi riêng theo cách riêng, tuy nhiên về cơ
bản vẫn dựa trên các bộ phận đ−ợc mô tả trong hình 2.1.
Bộ tìm duyệt (Crawler): Hầu hết các máy tìm kiếm hoạt động dựa vào các bộ
tìm duyệt là các ch−ơng trình có kích th−ớc nhỏ đảm nhận chức năng cung cấp dữ liệu
(các trang web) cho máy tìm kiếm hoạt động. Bộ tìm duyệt thực hiện công việc duyệt
web. Hoạt động của nó t−ơng tự nh− hoạt động của con ng−ời khi truy cập web là dựa
Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext
Phạm Thị Thanh Nam – Luận văn cao học
32
vào các mối liên kết để đi từ trang web này tới trang web khác. Các bộ tìm duyệt đ−ợc
cung cấp các địa chỉ URL xuất phát, đọc trang web t−ơng ứng, phân tích và tìm ra các
URL có trong các trang web đó. Sau đó bộ tìm duyệt cung cấp các URL kết quả cho bộ
điều khiển tìm duyệt (Crawl Control). Bộ điều khiển tìm duyệt sẽ quyết định xem
URL nào sẽ đ−ợc tìm duyệt tiếp theo và gửi lại kết quả quyết định cho bộ tìm duyệt
(trong một số máy tìm kiếm, bộ tìm duyệt thực hiện luôn chức năng của bộ phận điều
khiển tìm duyệt). Các bộ tìm duyệt cũng chuyển luôn các trang web đã duyệt vào kho
trang web (Page Repository). Sau đó, các bộ tìm duyệt tiếp tục đi thăm các trang web
khác trên Internet cho đến khi các nguồn chứa cạn kiệt.
Bộ tạo chỉ mục (Indexer Module) thực hiện việc khảo sát tất cả các từ khóa
trong từng trang web có trong kho trang web, và ghi lại các địa chỉ URL của các trang
web có chứa mỗi từ. Kết quả sinh ra một bảng chỉ mục rất lớn (thực sự, bảng chỉ mục
giới hạn trong các trang web đã qua bộ tìm duyệt). Nhờ có bảng chỉ mục này, máy tìm
kiếm cung cấp tất cả các địa chỉ URL của các trang web khi có yêu cầu: Khi cho một từ
Kho trang web
Bộ tìm
duyệt
Hình 2.1. Mô hình cấu trúc của máy tìm kiếm
Kho trang web
Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext
Phạm Thị Thanh Nam – Luận văn cao học
33
khóa bất kỳ thì qua bảng chỉ mục, máy tìm kiếm sẽ nhận đ−ợc tất cả các địa chỉ URL
của các trang web có chứa từ khóa đó. Chỉ mục này đ−ợc gọi là chỉ mục nội dung (Text
Index).
Việc tạo chỉ mục cho hệ thống web thực sự là một việc làm rất khó khăn do kích
th−ớc đồ sộ của hệ thống web cũng nh− sự th...
Download miễn phí Luận văn Một số giải pháp cho bài toán tìm kiếm trong cơ sở dữ liệu Hypertext
Phần mở đầu .2
Chương I. Tổng quan vềwebưmining . 9
1.1 Giới thiệu về cơ sở dữ liệu Fulltext và Hypertext . 9
1.1.1 Cơ sở dữ liệu Fulltext . 9
1.1.2 Cơ sở dữ liệu Hypertext . 12
1.1.3 So sánh đặc điểm của dữ liệu Fulltext và dữ liệu trang web . 15
1.2 Tổng quan về phương pháp biểu diễn văn bản trong cơ sở dữ liệu trang web . 16
1.2.1 Giới thiệu sơ bộ về các phương pháp biểu diễn trang web. 17
1.2.2 Cách tiếp cận theo web site. 19
Kết luận chương một. 28
Chương II. Một số phương pháp biểu diễn trangweb và giải pháp kết hợp. . 29
2.1 Phương pháp biểu diễn trong các máy tìm kiếm. 30
2.1.1 Cấu trúc cơ bản và hoạt động của một máy tìm kiếm. 31
2.1.2 Phương pháp biểu diễn dữ liệu trong các máy tìm kiếm. 34
2.2 Phương pháp biểu diễn trang web theo mô hình vector . 45
2.2.1 Phương pháp biểu diễn vector . 45
2.2.2 Phương pháp biểu diễn trang web theo mô hình vector . 48
2.3 Đề xuất giải pháp biểu diễnvector trong máy tìm kiếm . 55
Kết luận chương 2 . 59
Chương III. máy tìm kiếm vietseek và thử nghiệm Thuật toán tìm kiếm theo nội dung . 61
3.1 Máy tìm kiếm VietSeek . 61
3.1.1 Các đặc điểm cơ bản của Vietseek. 61
3.1.2 Cơ sở dữ liệu của Vietseek. 62
3.2 Đề xuất thuật toán tìm kiếm mới cho máy tìm kiếm VietSeek . 69
3.2.1 Những cơ sở để đề xuất thuật toán . 69
3.2.2 Thuật toán . 71
Kết luận chương 3 . 74
Phần kết luận 75
tài liệu tham khảo
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đă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:
ờng xuyên nên các ph−ơng pháp biểu diễn truyền thống (biểu diễn dữliệu fulltext thông th−ờng) không còn phù hợp nữa, hay là hoạt động không hiệu quả.
Một nhu cầu đ−ợc đặt ra là phải xây dựng các ph−ơng pháp biểu diễn mới, hay cải tiến
các ph−ơng pháp biểu diễn dã có cho phù hợp với các điều kiện mới.
Sau đây, chúng tui trình bày chi tiết hai lớp ph−ơng pháp biểu diễn trang web phổ
biến hiện nay để chỉ ra đ−ợc sự thay đổi và cải tiến phù hợp với điều kiện của từng bài
toán tìm kiếm khác nhau. Lớp ph−ơng pháp thứ nhất đ−ợc dùng trong các hệ thống máy
Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext
Phạm Thị Thanh Nam – Luận văn cao học
30
tìm kiếm, trong đó nhấn mạnh ngữ nghĩa của việc liên kết các trang web trong việc tính
hạng của trang web. Trong quá trình tiền xử lý văn bản trang web, hạng của nó đ−ợc
hoàn thiện dần theo công thức tính dần từng b−ớc cho đến khi hoàn thiện hệ thống. Sau
đó, hạng của trang web đ−ợc dùng cho việc hiển thị các trang web kết quả tìm kiếm cho
ng−ời dùng. Lớp thứ hai dựa trên việc phát triển mô hình vector trong biểu diễn dữ liệu
fulltext. Đại diện cho lớp ph−ơng pháp theo h−ớng này đ−ợc Sean Slattery trình bày
[11]. Mỗi trang web đ−ợc t−ơng ứng với một vector biểu diễn. Câu hỏi tìm kiếm đa
dạng và phong phú hơn lớp thứ nhất và kết quả tìm kiếm đ−ợc hiển thị dựa theo "độ gần
nhau" của câu hỏi với các trang web.
2.1 Ph−ơng pháp biểu diễn trong các máy tìm kiếm
Sự phát triển nhanh chóng của mạng Internet và Intranet đã sinh ra một khối
l−ợng lớn các trang web. Cùng với sự phát triển và thay đổi hàng ngày hàng giờ
về nội dung cũng nh− số l−ợng của các trang web trên Internet thì vấn đề tìm kiếm
thông tin đối với ng−ời sử dụng lại ngày càng khó khăn. Một vấn đề cần đ−ợc giải
quyết là: Làm thế nào để tìm ra đ−ợc các trang web có mang thông tin cần thiết trong
số hàng tỷ các trang web? Việc này chỉ có thể thực hiện đ−ợc nhờ vào các máy tìm
kiếm (search engine) hiện đang đ−ợc cung cấp rộng rãi cho mọi ng−ời sử dụng trên
Internet, chẳng hạn nh− Yahoo, Google, Altavista...
Máy tìm kiếm là các hệ thống đ−ợc xây dựng có khả năng tiếp nhận các yêu cầu
tìm kiếm của ng−ời dùng (th−ờng là một tập các từ khoá), sau đó phân tích và tìm kiếm
trong cơ sở dữ liệu đã có sẵn và đ−a ra các kết quả các trang web cho ng−ời sử dụng.
Nh− đã biết, bài toán biểu diễn và tìm kiếm thông tin trên Internet đặt ra nhiều
thách thức. Thứ nhất, tập hợp trang web trên Internet là một tập dữ liệu khổng lồ, phân
tán trên rất nhiều máy tính khắp nơi trên thế giới. Thứ hai, nội dung các trang web
không hoàn toàn đồng nhất, chẳng hạn vấn đề ngôn ngữ trình bày trang web bao gồm
rất nhiều loại ngôn ngữ khác nhau (cả ngôn ngữ diễn tả nội dung lẫn ngôn ngữ lập
trình), nhiều loại định dạng khác nhau (text, HTML, PDF, hình ảnh, âm thanh,...),
Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext
Phạm Thị Thanh Nam – Luận văn cao học
31
nhiều loại từ vựng khác nhau (địa chỉ email (email addresses), các liên kết (links), các
mã nén (zip code), số điện thoại (phone number),...). Và thứ ba là nội dung trang web
thay đổi liên tục và không ai có thể kiểm soát nổi. Các nghiên cứu về kích th−ớc của hệ
thống web đã đ−a ra các số liệu sau đây để minh chứng cho các khó khăn đó [6]. Hiện
nay có khoảng hơn một tỷ các trang web đ−ợc cung cấp cho ng−ời sử dụng, giả sử kích
th−ớc trung bình của mỗi trang web là 5-10 KB, thì kích th−ớc tổng cộng của hệ thống
ít nhất khoảng 10 terabyte. Mặt khác, tốc độ tăng số l−ợng các trang web cũng rất
nhanh, chẳng hạn, trong hai năm gần đây số l−ợng các trang web đã tăng lên gấp đôi.
Ngoài số l−ợng lớn các trang web đ−ợc tạo mới thì các trang web đang tồn tại trên
Internet cũng không ngừng cập nhật thông tin. Theo kết quả nghiên cứu hơn 500.000
trang web trong hơn 4 tháng thì 23% các trang thay đổi hàng ngày. Trong các site mà
tên miền có đuôi .com thì 40% các trang thay đổi hàng ngày, và khoảng 10 ngày thì
50% các trang trong các tên miền đó biến mất, nghĩa là địa chỉ URL của chúng không
còn tồn tại nữa.
Các thách thức trên đây cho thấy việc biểu diễn dữ liệu trong các máy tìm kiếm là
rất quan trọng. Biểu diễn các trang web nh− thế nào để vừa có khả năng l−u trữ đ−ợc
một số l−ợng lớn các trang web đó, vừa cho phép máy tìm kiếm thực hiện việc tìm
kiếm nhanh chóng và chính xác. Tr−ớc hết chúng ta khảo sát cấu trúc cơ bản của máy
tìm kiếm và hoạt động của nó.
2.1.1 Cấu trúc cơ bản và hoạt động của một máy tìm kiếm
Cấu trúc điển hình của một máy tìm kiếm đ−ợc mô tả nh− trong hình 2.1. Trong
thực tế thì mỗi máy tìm kiếm lại có các sửa đổi riêng theo cách riêng, tuy nhiên về cơ
bản vẫn dựa trên các bộ phận đ−ợc mô tả trong hình 2.1.
Bộ tìm duyệt (Crawler): Hầu hết các máy tìm kiếm hoạt động dựa vào các bộ
tìm duyệt là các ch−ơng trình có kích th−ớc nhỏ đảm nhận chức năng cung cấp dữ liệu
(các trang web) cho máy tìm kiếm hoạt động. Bộ tìm duyệt thực hiện công việc duyệt
web. Hoạt động của nó t−ơng tự nh− hoạt động của con ng−ời khi truy cập web là dựa
Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext
Phạm Thị Thanh Nam – Luận văn cao học
32
vào các mối liên kết để đi từ trang web này tới trang web khác. Các bộ tìm duyệt đ−ợc
cung cấp các địa chỉ URL xuất phát, đọc trang web t−ơng ứng, phân tích và tìm ra các
URL có trong các trang web đó. Sau đó bộ tìm duyệt cung cấp các URL kết quả cho bộ
điều khiển tìm duyệt (Crawl Control). Bộ điều khiển tìm duyệt sẽ quyết định xem
URL nào sẽ đ−ợc tìm duyệt tiếp theo và gửi lại kết quả quyết định cho bộ tìm duyệt
(trong một số máy tìm kiếm, bộ tìm duyệt thực hiện luôn chức năng của bộ phận điều
khiển tìm duyệt). Các bộ tìm duyệt cũng chuyển luôn các trang web đã duyệt vào kho
trang web (Page Repository). Sau đó, các bộ tìm duyệt tiếp tục đi thăm các trang web
khác trên Internet cho đến khi các nguồn chứa cạn kiệt.
Bộ tạo chỉ mục (Indexer Module) thực hiện việc khảo sát tất cả các từ khóa
trong từng trang web có trong kho trang web, và ghi lại các địa chỉ URL của các trang
web có chứa mỗi từ. Kết quả sinh ra một bảng chỉ mục rất lớn (thực sự, bảng chỉ mục
giới hạn trong các trang web đã qua bộ tìm duyệt). Nhờ có bảng chỉ mục này, máy tìm
kiếm cung cấp tất cả các địa chỉ URL của các trang web khi có yêu cầu: Khi cho một từ
Kho trang web
Bộ tìm
duyệt
Hình 2.1. Mô hình cấu trúc của máy tìm kiếm
Kho trang web
Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext
Phạm Thị Thanh Nam – Luận văn cao học
33
khóa bất kỳ thì qua bảng chỉ mục, máy tìm kiếm sẽ nhận đ−ợc tất cả các địa chỉ URL
của các trang web có chứa từ khóa đó. Chỉ mục này đ−ợc gọi là chỉ mục nội dung (Text
Index).
Việc tạo chỉ mục cho hệ thống web thực sự là một việc làm rất khó khăn do kích
th−ớc đồ sộ của hệ thống web cũng nh− sự th...