1
Trường Đại học Bách Khoa Hà Nội
Viện Công Nghệ Thông Tin và Truyền Thông
BÁO CÁO BÀI TẬP LỚN
XỬ LÝ NGÔN NGỮ TỰ NHIÊN
Đề tài: Tìm hiểu cấu trúc hệ thống tìm kiếm thông tin Google hiện tại và các kỹ thuật
xử lý trong tìm kiếm thông tin của Google
Giáo viên hướng dẫn: PGS. Lê Thanh Hương
Nhóm sinh viên thực hiện:
Ngô Ngọc Đức 20080738
Bùi Tuấn Điệp 20080663
Nguyễn Huy Dưỡng 20080575
Nguyễn Văn Dương 20086082
Nguyễn Văn Kiên 20081453
Hà Nội – 04/2012
Mục Lục
2
A.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 nguyên 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 toà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 nguyên 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.
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 hoá cơ hội
nhận được các thông tin hữu ích.
3
B.Tổng quan về hệ thống Search Engine
I.Các bộ phận cấu thành hệ thống search engine

chính để tạo CSDL chỉ mục phục vụ cho nhu cầu tìm kiếm thông tin. (*Robots
phải liên tục cập nhật dữ liệu trên mạng, mật độ cập nhật phụ thuộc vào từng hệ
thống tìm kiếm (Search engine)).
3.Search engine nhận yêu cầu truy vấn từ User, nó sẽ tiến hành phân tích,
tìm trong CSDL chỉ mục và trả về những tài liệu thỏa yêu cầu.
5
C.Ranking
I.Ranking là gì?
Trong lĩnh vực tìm kiếm, ranking là kỹ thuật đánh giá giá trị từng kết quả
trong tập trả về mỗi khi người dùng truy vấn. Bằng cách thức cho điểm, danh sách
kết quả sẽ được sắp xếp theo thứ tự trước sau tương ứng với số điểm.
Với việc bùng nổ dữ liệu trên internet, việc đánh giá xem một trang web nào là
chất lượng với một từ khóa thực sự khó khăn. Do đó tầm quan trọng của ranking
trong tìm kiếm ngày càng cao. Nó đòi hỏi phải kết hợp nhiều thuật toán để cho ra
được kết quả tốt nhất mà người dùng mong muốn.
II.Các kỹ thuật sử dụng trong ranking
Google cho biết họ sử dụng kết quả của hơn 200 phương pháp khác nhau để đánh
giá toàn thể cấu trúc Web và xác định những trang nào là quan trọng nhất.
Sau đây là một số thuật toán cơ bản trong Ranking:
1. Đánh giá bằng thống kê.
Thuật toán dựa vào những yếu tố sau để cho điểm một từ khoá trong một trang
Web:
• Số lần xuất hiện của từ khoá trong bài viết. Ví dụ: từ "Việt Nam" xuất hiện
hai lần trong bài viết A và 3 lần trong bài viết B. Như vậy bài viết B sẽ có
điểm cao hơn khi truy vấn bằng từ khoá "Việt Nam".
• Tỉ lệ tần suất xuất hiện từ khoá với độ dài của bài viết. Ví dụ: từ khoá "Việt
Nam" xuất hiện hai lần trong bài viết A và 3 lần trong bài viết B. Nhưng nếu
bài viết A dài 1 trang và bài viết B dài 2 trang thì trong trường hợp này, bài
viết A sẽ có điểm số cao hơn bài viết B ứng với từ khóa "Việt Nam".
Thuật toán chỉ mang tính chất thống kê và tương đối. Trong một môi trường thực,

chứa cụm từ "công nghệ thông tin". Kết hợp với từ điển, phân tích ngữ nghĩa sẽ
giúp phân tích sâu hơn về cấu trúc, tóm tắt hay gạn lọc lại những ý chính của bài
viết.
4.Đánh giá bởi các từ gần nhau.
Thuật toán cho phép tính toán độ gần nhau giữa các từ khoá. Các Search
Engine cho phép người tìm kiếm chỉ định độ gần nhau của các từ bằng câu lệnh
7
tìm kiếm dạng "ca sỹ mỹ tâm"~5. Lệnh search này sẽ trả về tập bài viết có các từ
"ca", "sỹ", "mỹ", "tâm" và khoảng cách giữa các từ thường không quá năm từ. Đây
là thuật toán khá hay và tương đối dễ cài đặt. Thuật toán này có thể kết hợp với các
phương thức phân tích cao cấp để xác định vấn đề quan trọng trong bài viết nhằm
tăng điểm cao hơn cho các câu hoặc cụm từ giá trị trong nội dung.
5. Đánh giá theo ngày tháng.
Thông thường, người tìm kiếm có xu hướng tìm kiếm những vấn đề hay sự
kiện mới xảy ra. Chẳng hạn, với từ khoá "Ronaldo", người ta sẽ quan tâm đến
những vấn đề như Ronaldo gần đây cặp kè với ai, đá cho đội nào hay mức lương
bao nhiêu? Phương thức ranking này là dễ, rẻ nhất và khá hiệu quả. Nếu ta quan sát
kết quả Google ở nhiều thời điểm khác nhau với một từ khóa ta sẽ thấy thứ hạng
trả về của kết quả thay đổi. Nhưng phương thức xác định thời gian của nội dung
không hề đơn giản. Nếu chỉ căn cứ vào thời gian Crawler (máy quét) lấy về thì
không chính xác tuyệt đối. Ví dụ, một bài viết xuất hiện trên trang Web A đã lâu
nhưng được trang Web B copy lại nội dung. Như vậy, thời gian mà Crawler lấy về
chỉ mang tính tương đối. Trường hợp khác, bài viết đề cập tới chiến tranh Việt
Nam hay những sự kiện từ thập niên 50 được đăng tải, chúng ta không thể căn cứ
vào thời gian cập nhật để xác định thời gian của nội dung.
6. Đánh giá theo độ nổi tiếng của trang.
"PageRank của Google đánh giá độ quan trọng của một trang web dựa trên
phương pháp xử lí gọi là thuật toán phân tích liên kết (Link Analysis Algorithm).
Phương pháp này đánh giá độ quan trọng của một trang Web dựa trên những liên
kết trên Internet. Và Google cho biết: "trang nào được chúng tôi đánh giá quan

của một bài báo được quyết định bởi số các trích dẫn từ bài báo đó của các bài báo
khác. Brin và Page đã đơn giản giả thuyết này để dùng cho trang Web: “Tầm quan
trọng của một trang Web được quyết định bởi số lượng các hyperlink trỏ đến nó từ
các trang Web khác”.
Chỉ số PageRank của một trang web là kết quả bầu chọn của tất cả các trang web
khác trên toàn thế giới cho website đó về mức độ quan trọng của trang. Mỗi 1 liên
kết ngược là 1 phiếu bầu. Các phiếu bầu này có mức độ ảnh hưởng khác nhau, sự
9
khác nhau đó phụ thuộc vào chất lượng ( hay tính quan trọng ) của mỗi trang đặt
liên kết ngược.
Một trang được liên kết đến bởi các trang có PageRank cao sẽ nhận được
PageRank cao. Nếu 1 trang web không có liên kết nào đến thì sẽ không có phiếu
bầu nào.
Chỉ số PageRank này cho biết trang web có quan trọng hay không theo cách nhìn
nhận của Google. Website nào có chỉ số PageRank cao chứng tỏ website đó có chất
lượng cao và quan trọng. Vì thế, khi tìm kiếm, Google sẽ ưu tiên cho các site có
PageRank cao.
Tất nhiên khi tìm kiếm không phải cứ website có PageRank cao là sẽ được xếp ở
trang đầu tiên, điều này còn phụ thuộc vào việc bạn muốn tìm kiếm gì và nhiều yếu
tố khác. Google kết hợp PageRank với một số heuristics khác để cho ra kết quả
phù hợp nhất.
2.Công thức thuật toán PageRank.
Giá trị PageRank của trang P
i
được tính như sau:
10
Trong đó:
P
1
,P

4. PageRank được tính toán như thế nào.
PageRank có thể được tính toán bằng phương pháp lặp hoặc dùng đại số:
a.Phương pháp lặp:
Tại t=0 Giả sử phân bố xác suất ban đầu là:
11
Tại mỗi bước, ta tính theo công thức:
,
Hoặc công thức :
(*)
Trong đó
là một ma trận N*1 gồm toàn các số 1
Ma trận được định nghĩa như sau:
M
ij
=1/L(p
j
) nếu trang j có link tới trang i
M
ij
=0 trường hợp còn lại
Thuật toán kết thúc khi:
b.Phương pháp đại số
Cho (Khi trạng thái ổn định) Phương trình (*) trở thành:
. (**)
Do đó ta tính được R như sau:
,
Với là ma trận đơn vị cấp n.
12
c.Phương pháp “Power Method”
 Chuỗi Markov

M
ii
=0 trong mọi trường hợp
M
ij
=1/n j=1 n Nếu trang i không có link đến trang nào
E là ma trận chỉ chứa 1
5.Kết luận.
Thuật toán PageRank trên thực tế rất đơn giản. Nhưng khi một phép tính đơn
giản được thực hiện hàng nghìn ( hoặc hàng tỉ) lần thì thuật toán trở lên rất phức
tạp.
PageRank chỉ là 1 phần trong chiến lược sắp xếp thứ tự kết quả tìm kiếm của
Google. Nhưng nó là một tiêu chí không thể thiếu trong việc sắp xếp thứ tự dữ liệu.
14
IV. Google Panda Algorithm
Tháng 11-2011 Google chính thức thay đổi thuật toán Ranking của mình lấy
tên là Panda. Đây là một sự thay đổi mạnh mẽ của Google. Thuật toán Panda có tư
tưởng chủ đạo là “ Content is King”. Nó loại bỏ hoặc giảm chỉ số xếp hạng của các
trang web có nội dung kém chất lượng, sao chép nội dung, và các trang web có nội
dung chủ yếu được sưu tập từ các trang khác, tăng chỉ số xếp hạng của các trang có
nội dung nguồn chất chất lượng
Thuật toán Panda cố gắng xác định nguồn gốc, tác giả của nội dung và tăng thứ
hạng cho trang đó, đồng thời hạ thứ hạng của tất cả các trang có nội dung trùng lặp
với nội dung trên.
Thuật toán Panda
Google tung ra Google Panda để thay thế cho Google Cafein. Nó là tập hợp của
các thuật toán phức tạp. Với tầm nhìn rõ ràng của Google Panda là loại bỏ những
nội dung rác, nội dung copy, loại bỏ những website có thương hiệu kém…Google
Panda là bộ lọc quan trọng để cải tiến các kết quả tìm kiếm mới của Google .
Sau đây là những tiêu chí chính trong thuật toán Google Panda:

 Tỷ lệ nội dung không trung thực (như nhau trên tất cả các trang).
 Số lượng các quảng cáo trên trang web
16
D. Tài liệu tham khảo
1. http://en.wikipedia.org/wiki/PageRank
2. http://vi.wikipedia.org/wiki/X%C3%ADch_Markov
3. http://infolab.stanford.edu/~backrub/google.html
4. http://www.slideshare.net/GenioAladino/pagerank-and-markov-chain
5. http://www.stanford.edu/~sdkamvar/papers/adaptive.pdf
6. http://research.ijcaonline.org/volume35/number11/pxc3976214.pdf
7. http://www14.informatik.tu-
muenchen.de/konferenzen/Jass05/courses/6/Papers/07.pdf
17