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:
Nguyễn Huy Triển
Nguyễn Hữu Khánh
Trần Quốc Huy
Lưu Mạnh Linh
Hà Nội – 04/2012
Mục Lục
A. Mở Đầu
B. Tổng quan về hệ thống Google Search Engine
I. Thành phần quan trọng trong hệ thống Google search
engine
1.Google Bot
2.Đánh chỉ mục
3.Bộ tìm kiếm thông tin
II. Nguyên lý hoạt động của Google Search Engine
C.Ranking
I. Ranking là gì
II. Các yếu tố ảnh hưởng đến Ranking
III. Các Kỹ thuật sử dụng trong Ranking
IV. PageRank
1.PageRank là gì
2.Công thức thuật toán PageRank
3.yếu tố ảnh hưởng đến pageRank

sàng lọc là bao nhiêu?
Google sàng lọc thông tin dựa trên một list các danh sách link ( URLs) trên mỗi
website. Đó là lý do vì sao chúng ta nên tạo sitemap cho các website. Tạo sitemap
đảm bảo cho Google Bot có thể sàng lọc được lượng thông tin nhanh và nhiều nhất
trên mỗi website. Khi Google Bot “ghé thăm” mỗi website, chúng “đọc” – Tìm
kiếm các đường link trên site, tất nhiên chúng có thể đọc được tất cả các đường
link bên trong mỗi trang (SRC- Nguồn của bức ảnh và HREF- Đường link dẫn
trong các thẻ <a>) và thêm những link này vào danh sách các URLs sẽ được sàng
lọc thông tin và tất nhiên nó sẽ tiếp tục tìm kiếm, chắt lọc các thông tin từ nguồn
dữ liệu của các đường link này chỉ tới.
Hãy chú ý một điều rằng, vì một lý do nào đó các link trên site của bạn bị thay đổi
không “trỏ” đúng vị trí, Google luôn luôn cập nhật thông tin do vậy các link cũ của
bạn sẽ được gọi là link “chết”, bạn nên hạn chế điều này vì Google bot “không
thích” chắt lọc thông tin từ những link “không có gì”. Thực ra chúng ta có thể khắc
phục vấn đề link “chết” này
Google Bot truy cập vào website của bạn như thế nào?
4
Google xây dựng rất nhiều Google Bot phân rải trên các website để tăng hiệu suất
sàng lọc và cập nhật thông tin. Nếu một website có lượng thông tin thường xuyên
thay đổi, số lượng Google Bot thường xuyên lưu trú sẽ lớn hơn. Google Bot lưu trú
sẽ cập nhật những thay đổi trên website của bạn về kho dữ liệu Google, đó là lý do
vì sao người dùng có thể tìm thấy thông tin hữu ích khi search trên Google.com.
2. Đánh chỉ mục
Trong hơn chục năm phát triển Có rất nhiều Thuật toán mà google đưa ra nhằm
cải thiện bộ máy tìm kiếm của mình một trong số thuật toán gần đây đó là Google
sử dụng hệ thống search index (đánh chỉ mục) website có tên là GoogleCaffeine.
Caffeine mang lại nhiều hơn 50% kết quả tìm kiếm cấp nhật nhất so với hệ thống
cũ, nó là tập hợp nội dung web lớn nhất được cung cấp. Nếu blog, forum của bạn
có bài post mới bạn có thể tìm thấy ngay trên kết quả tìm kiếm trong thời gian
nhanh hơn nhiều so với trước đây.

phải tiêu tốn của Google một lượng tài nguyên cũng rất “khủng”. Theo tính toán
của Google một giây hệ thống Caffeine có khả năng phân tích và index tầm 100
ngàn trang trong cùng 1 thời điểm. Nếu tính sơ sơ mỗi trang trên website là 1 tờ
giấy A4 thì mỗi giây caffeine sẽ làm cho đống giấy này dài thêm 3 … dặm. Hệ
thống Caffeine chiềm gần 100 triệu Gigabye lữu trữ trong một cơ sở dữ liệu và nó
lớn lên theo tộc độ hằng trăm ngàn gigabyte mỗi này. Bạn sẽ cần 625.000 chiếc
Ipod lớn nhất để lưu trữ thông tin một ngày caffeine cập nhật.
Sự thật thì các kỹ sư của Google muốn xây dựng Caffeine như là một hệ thống có
khả năng hoạt động tốt trong tương lai 5 đên 10 năm nữa. Khi mà khối lượng thông
tin trên internet và sự khó tính của người dùng đòi hỏi Google phải trở thành một
bộ máy tìm kiếm nhanh, mạnh và toàn diện hơn nữa mới có thể đám ứng đủ nhu
cầu.
3. Bộ tìm kiếm thông tin
6
Bộ tìm kiếm thông tin là một thành phần xử lý các truy vấn từ phía người sử
dụng (user), tiếp nhận các yêu cầu tìm kiếm (câu truy vấn query),phân tích từ, tìm
kiếm trong Cơ sở dữ liệu chỉ mục, so khớp các từ khóa, lấy về kết quả phù hợp, sau
đó trả lại những kết quả đó cho người sử dụng thông qua giao diện GUI.
Nói chung, bộ tìm kiếm thông tin hoạt động độc lập với các thành phần
khác, song lại phụ thuộc với nhau về mặt dữ liệu.
II.Nguyên lý hoạt động của Google Search Engine
1.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.
2.Robots phát hiện ra website mới, nó gửi tài liệu webpage về cho server
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.
7

còn lại hoặc 1 nhóm các từ như các liên kết. Tác dụng của việc này chính là giúp
cho các trang đích được xếp hạng bới bất cứ từ khóa cụ thể
9
+Các trang không liên kết với trang khác
(orphan page – dịch là các trang mồ côi nghe cũng hơi ngang nên cứ dịch là trang
không liên kết với trang khác)Nếu bạn muốn một trang được xếp hạng thì đừng
quá chặt chẽ với các liên kết. Coi dòng liên kết như các dòng chảy tầng của nước
(giống như một thác nước) và 10 cốc rượu sâm panh sẽ được đổ đầy từ một cốc
rượu ở phía trên cùng từ một dòng chảy
III. 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á theo địa chỉ của trang.
Đây là một cách đánh giá độ quan trọng của từ khóa với mỗi trang Web và
thường có trọng số khá cao. Thay vì từ khóa nằm trong bài viết thì nó lại nằm trong
đường dẫn URL hay tên miền của trang Web (domain name).
2. Đánh giá bằng từ khoá quan trọng.
Web Page là tài liệu có định dạng hiển thị. Thông dụng nhất là chuẩn
HTML. Dựa vào cấu trúc định dạng đó, thuật toán cho điểm cao hơn với từ khóa
nằm trong các thẻ đặc biệt. Cách thông thường nhất mà Search Engine hay áp dụng
chính là cho điểm cao với từ khoá nằm trong anchor text(liên kết), các thẻ tiêu đề,
meta keyword, H1, H2, H3, H4, H5, H6 hoặc từ khoá được in đậm, viết hoa.
Chúng ta đã biết một bài văn thường bao gồm ba phần: mở bài, thân bài và kết
luận. Trong đó, phần mở bài gần như một tóm tắt hoặc giới thiệu nội dung cho cả
bài viết. Nếu chúng ta xác định được đâu là mở bài và cho điểm cao hơn với những
từ khóa nằm trong đó thì kết quả search chính xác hơn rất nhiều. Mặt khác, với một
từ "Việt Nam", nếu xuất hiện ở đầu bài viết, giữa hay cuối bài viết thì nó cũng có
những trọng lượng khác nhau.
Trong một bài viết, các từ khóa có độ quan trọng khác nhau còn tùy thuộc vào vị

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.
11
5. Đá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
trọng sẽ được ưu tiên hiện trước trong danh sách kết quả tìm kiếm. Chúng tôi luôn
tìm cách đánh giá một cách hữu hiệu nhất để tăng chất lượng kết quả tìm kiếm và
tạo ra một sản phẩm có ích, và công nghệ PageRank của chúng tôi sử dụng tính
cộng đồng trên Internet để xác định độ quan trọng của một trang web."
Đây là một phương thức hay và có hiệu quả.Nhưng tại thời điểm hiện nay, số
lượng trang web ngày càng bùng nổ theo cấp số nhân Hiện tại, chất lượng Page
Rank đã giảm nhiều so với thời kỳ đầu.
6. Đánh giá theo truy vấn vùng.
Cùng một từ khóa tìm kiếm, kết quả trả về cho người Mỹ sẽ khác với kết
quả trả về cho người Việt. Ngoài việc ưu tiên những nội dung tiếng Việt lên đầu,
Search Engine còn cần phải loại bỏ các kết quả không phù hợp với văn hóa và xã
hội Việt Nam.
Tính toàn cầu của Internet cũng cần phải thỏa mãn tính bản địa khi truy vấn đến từ
nhiều nơi khác nhau. Local Ranking là phương pháp căn cứ vào dải ip truy cập của
người dùng rồi đánh giá lại tập nội dung, cho điểm những kết quả phù hợp hơn với
người dùng đến từ nước, vùng, khu vực đó.
7.Đánh giá bởi con người và trình duyệt.
Phương pháp thống kê nhờ theo dõi hành vi người dùng để đưa ra đánh giá
về chất lượng của một trang Web. Phương thức này chỉ có thể triển khai khi một
Search Engine có số lượng người dùng lớn như Google hoặc Yahoo. Một phương

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.
14
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:
PR(A)=(1-d)+d*( +…+ )
Trong đó:
PR

( A ) là PageRank của trang A.
t1…tn:là các trang trỏ hay link tới trang A.
C(t):số trang trỏ tới hay link trang t.
Tham số giảm sóc d có giá trị xấp xỉ 0.85
3.Yếu tố ảnh hưởng tới pageRank
- Theo định nghĩa thuật toán PageRank cho ta thấy có 2 yếu tố ảnh hưởng đến
vị trí của trang web trên Google. Đó là:
• Số lượng các link đi đến ( inbound links): Thông thường thì càng nhiều link
đi đến càng tốt.
• Số lượng các link đi ra của các trang web trỏ tới ( outbound links): Càng ít
càng tốt.

Nếu người dùng tìm thấy những nội dung hữu ích và đáp ứng đúng nhu cầu
của họ, khả năng họ ở lại trên website để tìm những thông tin liên quan là rất
cao. Do đó các trang web mà người dùng giành nhiều thời gian để đọc và
tìm những bài viết trên website sẽ được Google đánh giá cao.
 Tỷ lệ Bounce Rate
Thuật toán Google đưa ra là khi một website người dùng thường xuyên truy
cập sẽ là website có giá trị.
 Tỷ lệ khách hàng quay trở lại
Một cách tuyệt vời để biết được trang web đang có thứ hạng cao trên bảng
tìm kiếm của Google có hữu ích hay không chính là tỷ lệ khách hàng quay
trở lại website. Google tin rằng chỉ có chất lượng website mới khiến người
dùng quay trở lại website thường xuyên hơn.
 Mạng xã hội
Mục đích của Google Panda là để giúp chọn lọc ra các website hoạt động
thực sự bởi con người chứ không phải máy móc (Auto post). Do đó những
mạng xã hội là tiêu chí đánh giá khá quan trọng khi tại đây những yếu tố
tương tác rất mạnh chỉ có con người mới có thể làm được như trên Facbook,
Youtube, Twister…
 Lượng nội dung gốc trên site hoặc mỗi trang.
 Số lượng các link trỏ đến trang web.
 Số lượng các từ không tự nhiên trên trang
 Tỷ lệ người dùng kích qua các trang kết quả của Google (cho trang hoặc
site)
 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
17
D. Tài liệu tham khảo
1. http://www.slideshare.net/GenioAladino/pagerank-and-markov-chain
2. http://www.stanford.edu/~sdkamvar/papers/adaptive.pdf
3. http://research.ijcaonline.org/volume35/number11/pxc3976214.pdf