Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt
Lê Th Ngọc - 0012745 5 Đỗ Mỹ Nhung - 0012624
2.2.2 Độ nhiễu tín hiệu (Signal Noise): 25
2.2.3 Giá trị độ phân biệt của mục từ : 25
2.2.4 Kết hợp tần số xuất hiện mục từ và nghịch đảo tần số tài liệu 26
2.3 Lập chỉ mục tự động cho tài liệu 28
3. Lập chỉ mục cho tài liệu tiếng Việt ([III.1], [II.1], [II.2], [II.3], [II.4], [IV.11],
[IV.12]) 29
3.1 Khó khăn cho việc lập chỉ mục tiếng Việt 29
3.2 Đặc điểm về từ trong tiếng Việt và việc tách từ 31
3.2.1 . Đặc điểm về từ trong tiếng Việt: 31
3.2.2 Tách từ 32
3.3 Giải quyết các vấn đề hiển thị của tiếng Việt (vấn đề chính tả) 34
3.3.1 Vấn đề bảng mã 34
3.3.2 Vấn đề dấu thanh 35
3.3.3 Vấn đề dấu tổ hợp ngun âm 36
3.4 Giải quyết các vấn đề về từ của tiếng Việt 37
3.4.1 Luật xác định các từ láy 37
3.4.2 Luật xác định các liên từ 37
3.5 Xây dựng từ điển tiếng Việt 37
Chương 4: BỘ TÌM KIẾM THƠNG TIN – SEARCH ENGINE 40
1. Vì sao ta cần một cơng cụ tìm kiếm (SE) ? 40
2. Các phương thức tìm kiếm 40
2.1 Tìm theo từ khố – Keyword searching 40
2.2 Những khó khăn khi tìm theo từ khố 41
2.3 Tìm theo ngữ nghĩa – Concept-based searching 41
3. Các chiến lược tìm kiếm 42
3.1 Tìm thơng tin với các thư mục chủ đề 42
3.2 Tìm thơng tin với các cơng cụ tìm kiếm 43
3.3 Tối ưu câu truy vấn 43
3.4 Truy vấn bằng ví dụ 44
Chương 5: MỘT SỐ SEARCH ENGINE THƠNG DỤNG TRÊN THẾ GIỚI
VÀ VIỆT NAM 45
1.1 Thư mục của Yahoo, Google 54
1.2 Alltheweb 55
1.3 AltaVista 55
1.4 Lycos 55
1.5 HotBot 55
2. Một số search engine thơng dụng ở Việt Nam 56
2.1 Netnam [IV.12] 56
2.1.1 Phương pháp Netnam SE lập chỉ mục dữ liệu 58
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt
Lê Th Ngọc - 0012745 6 Đỗ Mỹ Nhung - 0012624
2.1.2 Cú pháp tìm kiếm 59
2.1.3 Sử dụng từ khố để lọc các tìm kiếm 61
2.2 Vinaseek ([IV.11]) 65
Phần 2 : THIẾT KẾ VÀ CÀI ĐẶT 67
Chương 6: THIẾT KẾ DỮ LIỆU 67
1. Cơ sở dữ liệu trong SQL 67
2. Hệ thống tập tin 71
Chương 7: THU THẬP THƠNG TIN 72
1. Cấu trúc dữ liệu 72
1.1 Cấu trúc UrlInfo 73
1.2 Cấu trúc StartUrlInfo 74
1.3 Cấu trúc FileRetrieval 75
1.4 Cấu trúc ProjectInfo 75
2. Xử lý của web robot 78
3. Giải quyết các vấn đề của web robot 83
3.1 Tránh sự lặp lại 83
3.2 Tránh làm qúa tải server 83
3.3 Tránh truy xuất đến các dạng tài ngun khơng thích hợp 83
3.4 Tránh các lỗ đen(black holes) 84
3.5 Tránh những nơi cấm robot 84
4. Các thuật tốn phân tích cấu trúc file HTML 84
4.1 Thuật tốn lấy liên kết 84
4.1.1 Thuật tốn ứng dụng cũ đã cài đặt 85
4.1.2 Chọn lựa của ứng dụng mới 89
4.2 Thuật tốn lấy tiêu đề 89
4.3 Thuật tốn lấy nội dung 90
5. Duy trì thơng tin cho CSDL 91
6. Resume project 91
6.1 Ngun tắc resume của ứng dụng cũ
1
92
6.2 Cải tiến của ứng dụng mới 94
Chương 8: LẬP CHỈ MỤC 97
1. Tính trọng số của từ: 97
2. Tập tin nghịch đảo : 98
3. Từ điển chỉ mục 105
4. Q trình stemming 110
Chương 9: TÌM KIẾM THƠNG TIN 113
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt
Lê Th Ngọc - 0012745 7 Đỗ Mỹ Nhung - 0012624
Chương 10: CÁC MODULE ,PACKAGE, LỚP CHÍNH CỦA CHƯƠNG
TRÌNH 115
1. Các module, package của chương trình 115
2. Các lớp đối tượng chính trong từng module 116
2.1 Module DBController 116
2.2 Module ProcessDoc 117
2.3 Module Query 118
2.4 Module SE 119
2.5 Module Webcopy 119
2.6 Module WebcopyGUI 120
Phần 3 : KẾT QUẢ, ĐÁNH GIÁ VÀ HƯỚNG PHÁT TRIỂN 122
1. Kết quả thử nghiệm 122
2. Hoạt động của chương trình 124
2.1 Giao diện quản trị 124
2.1.1 Giao diện chính của quản trị 124
2.1.2 Tạo mới project 125
2.1.3 Tạo mới một StartUrl : 128
2.1.4 Xem từ điển chỉ mục 131
2.1.5 Quản l ý mục từ 132
2.2 Giao diện tìm kiếm 134
3. Đánh giá 136
3.1 Ưu điểm 136
3.2 Khuyết điểm 137
4. Hướng phát triển 137
4.1 Đối với từng module : 137
4.2 Đối với tồn luận văn: 138
DANH SÁCH CÁC BẢNG 139
DANH SÁCH CÁC HÌNH VẼ 140
TÀI LIỆU THAM KHẢO 141
I. Sách, ebook: 141
II. Luận văn, luận án 141
III. Bài báo 142
IV. Website 142
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt
Lê Th Ngọc - 0012745 1 Đỗ Mỹ Nhung - 0012624
MỞ ĐẦU
Trong thời đại ngày nay, thơng tin là nhu cầu thiết yếu đối với mọi người trên
mọi lĩnh vực. Mỗi phút trơi qua hàng triệu triệu trang web được đẩy lên nhằm làm giàu
nguồn tài ngun vơ tận này. Tuy nhiên tồn tại một nghịch lý là dù được ví như thư
viện tồn cầu, internet vẫn khơng thoả mãn nhu cầu thơng tin của con người. Xung
quanh vấn đề này có nhiều ngun nhân nhưng quan trọng nhất là sự thơng hiểu giữa
con người và cơng cụ tìm kiếm trên mạng – search engine – chưa đạt đến mức có thể
giao tiếp tốt với nhau.
Hơn nữa, mỗi search engine sẽ mang đặc thù của ngơn ngữ mà nó hiển thị như
search engine Tiếng Việt phải giải quyết những vấn đề đặc trưng của Tiếng Việt, cụ thể
là vấn đề bảng mã, ngữ pháp trong Tiếng Việt.
Nếu ta hiểu cách thức search engine tổ chức thơng tin, thực thi một câu truy vấn
và đặc trưng của ngơn ngữ mà search engine sẽ tiếp cận thì ta có thể tối ưu hố cơ hội
nhận được các thơng tin hữu ích. Đây là mục tiêu chính của luận văn.
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt
Lê Th Ngọc - 0012745 2 Đỗ Mỹ Nhung - 0012624
Phần 1 : TÌM HIỂU VẤN ĐỀ
Chương 1:
TỔNG QUAN VỀ HỆ THỐNG SEARCH ENGINE
1. Các bộ phận cấu thành hệ thống search engine
1.1 Bộ thu thập thơng tin – Robot
Robot là một chương trình tự động duyệt qua các cấu trúc siêu liên kết để thu
thập tài liệu & một cách đệ quy nó nhận về tất cả tài liệu có liên kết với tài liệu này.
Robot được biết đến dưới nhiều tên gọi khác nhau : spider, web wanderer hoặc
web worm,… Những tên gọi này đơi khi gây nhầm lẫn, như từ ‘spider’, ‘wanderer’ làm
người ta nghĩ rằng robot tự nó di chuyển và từ ‘worm’ làm người ta liên tưởng đến
virus. Về bản chất robot chỉ là một chương trình duyệt và thu thập thơng tin từ các site
theo đúng giao thức web. Những trình duyệt thơng thường khơng được xem là robot do
thiếu tính chủ động, chúng chỉ duyệt web khi có sự tác động của con người.
1.2 Bộ lập chỉ mục – Index
Hệ thống lập chỉ mục hay còn gọi là hệ thống phân tích và xử lý dữ liệu, thực
hiện việc phân tích, trích chọn những thơng tin cần thiết (thường là các từ đơn , từ
ghép , cụm từ quan trọng) từ những dữ liệu mà robot thu thập được và tổ chức thành cơ
sở dữ liệu riêng để có thể tìm kiếm trên đó một cách nhanh chóng, hiệu quả. Hệ thống
chỉ mục là danh sách các từ khố, chỉ rõ các từ khố nào xuất hiện ở trang nào, địa chỉ
nào.
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt
Lê Th Ngọc - 0012745 3 Đỗ Mỹ Nhung - 0012624
1.3 Bộ tìm kiếm thơng tin – Search Engine
Search engine là cụm từ dùng chỉ tồn bộ hệ thống bao gồm bộ thu thập thơng
tin, bộ lập chỉ mục & bộ tìm kiếm thơng tin. Các bộ này hoạt động liên tục từ lúc khởi
động hệ thống, chúng phụ thuộc lẫn nhau về mặt dữ liệu nhưng độc lập với nhau về
mặt hoạt động.
Search engine tương tác với user thơng qua giao diện web, có nhiệm vụ tiếp
nhận & trả về những tài liệu thoả u cầu của user.
Nói nơm na, tìm kiếm từ là tìm kiếm các trang mà những từ trong câu truy vấn
(query) xuất hiện nhiều nhất, ngoại trừ stopword (các từ q thơng dụng như mạo từ a,
an, the,…). Một từ càng xuất hiện nhiều trong một trang thì trang đó càng được chọn
để trả về cho người dùng. Và một trang chứa tất cả các từ trong câu truy vấn thì tốt hơn
là một trang khơng chứa một hoặc một số từ. Ngày nay, hầu hết các search engine đều
hỗ trợ chức năng tìm cơ bản và nâng cao, tìm từ đơn, từ ghép, cụm từ, danh từ riêng,
hay giới hạn phạm vi tìm kiếm như trên đề mục, tiêu đề, đoạn văn bản giới thiệu về
trang web,…
Ngồi chiến lược tìm chính xác theo từ khố, các search engine còn cố gắng ‘
hiểu ‘ ý nghĩa thực sự của câu hỏi thơng qua những câu chữ do người dùng cung cấp.
Điều này được thể hiện qua chức năng sửa lỗi chính tả, tìm cả những hình thức biến
đổi khác nhau của một từ. Ví dụ : search engine sẽ tìm những từ như speaker, speaking,
spoke khi người dùng nhập vào từ speak.
2. Ngun lý hoạt động
Search engine điều khiển robot đi thu thập thơng tin trên mạng thơng qua các
siêu liên kết ( hyperlink ). Khi robot phát hiện ra một site mới, nó gởi tài liệu (web
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt
Lê Th Ngọc - 0012745 4 Đỗ Mỹ Nhung - 0012624
page) về cho server chính để tạo cơ sở dữ liệu chỉ mục phục vụ cho nhu cầu tìm kiếm
thơng tin.
Bởi vì thơng tin trên mạng ln thay đổi nên robot phải liên tục cập nhật các site
cũ. Mật độ cập nhật phụ thuộc vào từng hệ thống search engine. Khi search engine
nhận câu truy vấn từ user, nó sẽ tiến hành phân tích, tìm trong cơ sở dữ liệu chỉ mục &
trả về những tài liệu thoả u cầu.
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt
Lê Th Ngọc - 0012745 5 Đỗ Mỹ Nhung - 0012624
Chương 2:
BỘ THU THẬP THƠNG TIN – ROBOT
1. Ứng dụng của Robot
Robot thường được sử dụng cho những mục đích sau :
1.1 Phân tích, thống kê – Statistical Analysis
Robot đầu tiên được dùng để đếm số lượng web server, số tài liệu trung bình
của một server, tỉ lệ các dạng file khác nhau, kích thước trung bình của một trang web,
độ kết dính, …
1.2 Duy trì siêu liên kế - Maintenance
Một trong những khó khăn của việc duy trì một siêu liên kết là nó liên kết với
những trang bị hỏng (dead links) khi những trang này bị thay đổi hoặc thậm chí bị xóa.
Thật khơng may vẫn chưa có cơ chế nào cảnh báo các bộ duy trì về sự thay đổi này.
Trên thực tế khi các tác giả nhận ra tài liệu của mình chứa những liên kết hỏng, họ sẽ
thơng báo cho nhau, hoặc thỉnh thoảng độc giả thơng báo cho họ bằng email.
Một số robot, chẳng hạn MOMspider có thể trợ giúp tác giả phát hiện các liên
kết hỏng cũng như duy trì các cấu trúc siêu liên kết cùng nội dung của một trang web.
Chức năng này lặp lại liên tục mỗi khi một tài liệu được cập nhật, nhờ đó mọi vấn đề
xảy ra sẽ được giải quyết nhanh chóng.
1.3 Ánh xạ địa chỉ web - Mirroring
Mirroring là một kỹ thuật phổ biến trong việc duy trì các kho dữ liệu của FPT.
Một ánh xạ (mirror) sẽ sao chép tồn bộ cấu trúc cây thư mục và thường xun cập
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt
Lê Th Ngọc - 0012745 6 Đỗ Mỹ Nhung - 0012624
nhật những file bị thay đổi. Điều này cho phép nhiều người cùng truy xuất một nguồn
dữ liệu, giảm số liên kết bị thất bại, nhanh hơn và ít chi phí hơn so với truy cập trực
tiếp vào site thực sự chứa các dữ liệu này.
1.4 Phát hiện tài ngun – Resource Discovery
Có lẽ ứng dụng thú vị nhất của robot là dùng nó để phát hiện tài ngun. Con
người khơng thể kiểm sốt nổi một khối lượng thơng tin khổng lồ trong mơi trường
mạng. Robot sẽ giúp thu thập tài liệu, tạo và duy trì cơ sở dữ liệu, phát hiện và xố bỏ
các liên kết hỏng nếu có, kết hợp với cơng cụ tìm kiếm cung cấp thơng tin cần thiết cho
con người.
1.5 Kết hợp các cơng dụng trên- Combined uses
Một robot có thể đảm nhận nhiều chức năng. Ví dụ RBSE Spider [4] vừa thống
kê số lượng tài liệu thu được vừa tạo cơ sở dữ liệu. Tuy nhiên những ứng dụng như thế
còn khá ít ỏi.
2. Robot chỉ mục – Robot Indexing
Trong q trình thu thập thơng tin phục vụ cho bộ lập chỉ mục, ta cần giải quyết
những vấn đề sau :
Một là : Trong mơi trường mạng, robot lấy thơng tin từ các site. Vậy robot sẽ
bắt đầu từ site nào ? Điều này hồn tồn phụ thuộc vào robot. Mỗi robot khác nhau sẽ
có những chiến lược khác nhau. Thường thì robot sẽ viếng thăm các site phổ biến hoặc
những site có nhiều liên kết dẫn đến nó.
Hai là : Ai sẽ cung cấp địa chỉ của các site này cho robot ?
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
Tìm hiểu về Search Engine và xây dựng ứng dụng minh hoạ cho Search Engine tiếng Việt
Lê Th Ngọc - 0012745 7 Đỗ Mỹ Nhung - 0012624
Có 2 nguồn :
Robot nhận các URL ban đầu từ user.
Robot phân tích các trang web để lấy các URL mới, đến lượt các URL này trở
thành địa chỉ đầu vào cho robot. Q trình này được lặp lại liên tục.
Ba là : Chọn dữ liệu nào trong tài liệu để lập chỉ mục ?
Quyết định chọn dữ liệu nào trong tài liệu cũng hồn tồn phụ thuộc vào robot,
thường thì những từ được liệt kê như sau được xem là quan trọng :
Ở góc cao của tài liệu.
Trong các đề mục
Được in đậm (inktomi)
Trong URL.
Trong tiêu đề (quan trọng)
Trong phần miêu tả trang web (description) .
Trong các thẻ dành cho hình ảnh (ALT graphisc).
Trong các thẻ chứa từ khóa.
Trong các text liên kết.
Một số robot lập chỉ mục trên tiêu đề, hoặc một số đoạn văn bản đầu tiên hoặc
tồn bộ tài liệu (full text). Một số khác lại lập chỉ mục trên các thẻ META(META tags)
hoặc các thẻ ẩn, nhờ vậy tác giả của trang web được quyền ấn định từ khố cho tài liệu
của mình. Tuy nhiên chức năng này bị lạm dụng q nhiều do đó các thẻ META khơng
còn giữ được giá trị ban đầu của chúng nữa.
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
Không có nhận xét nào:
Đăng nhận xét