Báo cáo Xây dựng Phần mềm tối ưu chí phí quảng cáo trực tuyến Easy – Op

g web lớn do việc lấy các trang web về diễn ra đồng thời. Các trang web không liên quan đến nhau sẽ được lấy về cùng một lúc. Đó là nguyên tắc hoạt động chung của crawler, tất nhiên việc crawler không chỉ phụ thuộc vào nguyên tắc hoạt động, cấu trúc của nó mà còn phụ thuộc vào các yêu tố khác trên các trang web mà nó cần phải giải quyết. Một vấn đề điển hình đó là việc lấy về các trang web sẽ sinh ra những lưu lượng lớn trên đường truyền, và sẽ chẳng thú vị gì nếu những người chủ các site đó phải trả tiền cho băng thông của họ. Một cách tự nhiên, có những luật đã được phát triển để quy định phương thức hoạt động của crawler, tuy không có ai chịu trách nhiệm hay đứng ra bảo đảm cho những luật này nhưng các crawler tốt đều chấp nhận và thực hiện đúng theo nó. Thời gian trễ Như chúng ta đã đặt vấn đề ở trên, việc tìm ra thời gian chạy một vòng lặp là rất quan trọng, nó phục thuộc vào kích thước và băng thông của mỗi site. Các site có kích thước và băng thông chênh lệch nhau quá lớn không thể có cùng một thời gian chạy các vòng lặp. Thông thường đối với mỗi site, crawler sẽ lưu thông tin về thời gian trễ tương ứng với site đó ở chính trong danh sách URL khởi tạo. Ví dụ như mặc định của thời gian trễ của webBase crawler là 5 giây cho các trang web thương mại lớn và 20 giây cho các trang web nhỏ. Tuy nhiên điều này không cố định, các chủ nhân của site đó có thể liên lạc và thỏa thuận với quản trị của search engine về thời gian trễ này. Các quy định đối với từng Server Khi một quản trị web không muốn một số trang của họ bị crawl, họ sẽ sử dụng một công cụ đặc biệt đó là giao thức Robots Exclusion. Giao thức này bắt buộc tất cả các crawler sẽ phải tìm file robots.txt ở thư mục gốc của site đó. File này sẽ liệt kê một danh sách các URL mà crawler không được lấy về và một crawler tốt sẽ tuân theo quy định này. Một trong những nhược điểm của crawler song song đó là vấn đề các trang cô lập địa phương. Bởi vì các site crawler không theo các link tới các trang ở ngoài site đó nên có thể có nhiều site sẽ không được lấy về. Hình 1.2c chỉ rõ vấn đề này. Hai Website S1 và S2 được download bởi hai site crawler C1 và C2. Vì trang d chỉ có thể đến thông qua link từ site S2 nên các trang d và e sẽ không bao giờ được download bởi bất cứ crawler nào. Bằng cách kiểm tra các nhanh các trang có được trong lần crawl trước. Nếu một trang trong lần kiểm tra trước có một link tới trang d, nhưng trang d không tồn tại trong lần kiểm tra này, trang d sẽ được cho vào bộ phân phối URL khởi tạo cho lần crawl tiếp theo. Hình 1.2c - Các site bị khuất Crawler đơn tiến trình Một cách tiếp cận thiết kế điển hình như trên là mô hình thiết kế một tiến trình gắn với một site (process-per-site). Cách thiết kế này sẽ thực hiện mỗi site crawler như một tiến trình độc lập, nó sẽ trút gánh nặng quản lý song song vào bộ phận điều khiển tiến trình của hệ điều hành. Trong khi đó, thiết kế crawl đơn tiến trình (single-crawl-process) gói tất cả các site crawler vào một tiến trình duy nhất và quản lý các yêu cầu như một vòng lặp sự kiện. Trong thiết kế này, vòng lặp được tạo ra các sự kiện site request một cách tuần tự sau khi đã có thời gian trễ. Cách tiếp cận này được chỉ ra trong hình 1.2d. Hình 1.2d - Crawl nhiều site trên một tiến trình Hình trên cho thấy 2 crawler chạy trên cùng một tiến trình. Ngược lại với thiết kế ở hình 1.2a, việc cài đặt crawl đơn tiến trình đưa ra một bộ đếm thời gian trước khi lấy về các trang từ URLsToVisit. Bộ đếm thời gian này sẽ quyết định độ trễ trước mỗi một lần request trang đó. Vòng lặp sự kiện trung tâm sẽ điều khiển việc đồng bộ các crawler. 2.2. Indexing: Khối Indexer được dùng để xây dựng và bảo trì các chỉ mục phục vụ cho các truy vấn. Khối Indexer xây dựng 3 chỉ mục cơ bản: chỉ mục offset (offset index), chỉ mục text (text index) và chỉ mục link/graph (link/graph index). Offset index ghi nhận vị trí vật lý của mỗi trang web trong cơ sở dữ liệu, nơi mà lưu trữ các trang web đã được nén. Chỉ mục này cho phép truy xuất ngẫu nhiên tới 1 web cho phép trong cơ sở dữ liệu. Text index cho phép truy vấn hướng nội dung, sử dụng các chỉmục ngược để sung cấp tìm kiếm theo từ khóa trong cơ sở dữ liệu. Cuối cùng, link index cung cấp truy vấn hướng liên kết (VD: Gọi đến tập các trang mà trang X trỏ tới ). Sử dụng 3 chỉ mục cơ sở này và các trang web, khối Phân Tích sẽ xây dựng lên các chỉ mục gốc khác nhau. Ví dụ, sử dụng chỉ mục liên kết và các thuật toán lặp PageRank, khối phân tích sẽ tính toán và lưu trữ PageRank của mỗi trang trong cơ sở dữ liệu ( chỉ mục PageRank ). Tương tự, bằng cách kết hợp thông tin liên kết và nội dung của trang web, khối phân tích có thể xây dựng một chỉ mục tương tự mà ánh xạ mỗi trang tới 1 tập các trang tương tự. Thiết kế chiến lược Ảnh hưởng to lớn bởi số lượng khổng lồ các trang Web trên mạng, chúng ta phải thiết kế một lược đồ xây dựng và cấu trúc biểu diễn mới cho rất nhiều chỉ mục được sử dụng. Thiết kế này có các đặc điểm sau: - Chỉ mục được xây dựng song song và phân tán. Do kích cỡ khổng lồ của mạng không cho phép thực hiện trực tiếp lược đồ xây dựng chỉ mục tuần tự đơn giản mà áp dụng rất tốt cho các tập hợp dữ liệu vừa và nhỏ ( khoảng vài triệu văn bản hoặc hình ảnh của vài nghìn node ). Cách thực hiện song song và phân tán các tính toán tích kiệm lớn chi phí và thời gian thực hiện. - Nén và bộ đệm của cấu trúc chỉ mục. Nhiều chỉ mục trên mạng quá đồ sộ để có thể chứa trong bộ nhớ chính. Vì vậy, chỉ mục được nén và lưu đệm là giải pháp nhằm giảm thiểu thời gian truy cập các chỉ mục. - Định danh trang đặc tả chỉ mục. Điều này cấn thiết cho mỗi cấu trúc chỉ mục để tận dụng các định danh đặc tả chỉ mục của chính nó để giảm thiểu thời gian truy nhập và kích cỡ chỉ mục. Chỉ mục văn bản ( Text index) Để cung cấp dịch vụ hướng văn bản cơ sở, chúng ta xây dựng các chỉ mục ngược thông qua tập các trang web trong cơ sở dữ liệu. Kích cỡ của cơ sở dữ liệu các trang web lưu trữ và sự cần thiết của việc thu thập định kì và xây dựng lại chỉ mục yêu cầu chúng ta xây dựng một lược đồ xây dựng chỉ mục tin cậy và hiệu quả cao. Việc xây dựng các chỉ mục ngược tăng tối đa tốc độ và khối lượng sử lý index cho hệ thống. Do đó các hệ thống hiện nay đều sử dụng phương pháp này để tiết kiệm tài nguyên. Hình 1.2e - Chỉ mục văn bản Chỉ mục ngược xây dựng hệ thống kiến trúc không chia sẻ phân tán như hình trên. Chỉ mục ngược được xây dựng thành 2 giai đoạn. Giai đoạn đầu tiên, mỗi một chỉ mục nhận một tập con tách rời của trang web. Khối Indexer sẽ phân tích và trích dẫn các đoạn từ trang web, sắp xếp các đoạn vào trong bộ nhớ, và chuyển chúng vào cấu trúc hiện tại trên đĩa. Trong giai đoạn thứ hai, các cấu trúc này được trộn lẫn nhau để tạo ra một hoặc nhiều file phân tán. Hai chức năng chính của hệ thống là đánh chỉ mục song song mức độ cao và việc sử dụng hệ thống cơ sở dữ liệu nhúng để lưu trữ và quản lý các file chỉ mục ngược. Đánh chỉ mục song song mức độ cao. Chúng ta chia quá trình sắp xếp thành ba pha: pha tải (một số trang được đọc từ luồng đầu vào và được lưu trong bộ nhớ), pha xử lý (các trang được phân tích và đánh dấu để sinh ra các đoạn, mà sau đó được sắp xếp thứ tự), và pha ghi (sắp xếp các đoạn và đĩa). Khối đánh chỉ mục được thiết kế như là một phần mềm ống đa tiến trình mà sử dụng một vài bộ nhớ đệm mỗi ống, với mỗi bộ đệm trong một pha. Hình dưới biểu diễn ảnh hưởng của đường ống đến thời gian thực hiện tiến trình và sắp xếp với một vài kích thước đầu vào. Hình 1.2f - Hiệu năng của xử lý đường ống Chú ý rằng với một tập nhỏ các trang web thì hiệu năng thu được thông qua xử lý đường ống là không đáng kể. Bởi vì với một tập nhỏ thì chỉ yêu cầu một vài đường ống và thời gian thực thi tổng thể bằng thời gian yêu cầu lúc khởi động và kết thúc. Với một tập lớn thì xử lý tuần tự chậm hơn khoảng 30-40% so với xử lý song song. Lưu trữ chỉ mục ngược trong hệ thống cơ sở dữ liệu nhúng. Một số các hệ thống hiện nay có sử dụng hệ thống cơ sở dữ liệu nhúng gọi là Berkeley DB để lưu trữ và quản lý các file chỉ mục ngược. Cơ sở dữ liệu nhúng cung cấp các phương thức truy nhập cơ sở dữ liệu bao gồm B-trees, bộ đệm và những cải tiến lưu vết so với hệ cơ sở dữ liệu client-server. Tuy nhiên, khó khăn là phải thiết kế một khuôn khổ lưu trữ chỉ mục ngược mà cung cấp các đầy đủ các chức năng của một hệ cơ sở dữ liệu. Tổ chức cơ bản của một B-tree dựa trên cơ sở file chỉ mục ngược bao gồm lưu trữ các chỉ mục trong B-tree với những con trỏ trỏ tới danh sách các chỉ mục ngược được lưu trữ riêng lẻ. 2.3. PageRank: PageRank là gì? PageRank là một thuật toán được sử dụng trong công cụ tìm kiếm Google, được phát triển tại Đại học Stanford bởi Larry Page và Sergey Brin trong nghiên cứu của họ “The Anatomy of a Large-Scale Hypertextual Web Search Engine”. Thuật toán dựa trên 1 giả thuyết phổ biến trong giới hàn lâm, đó là tầm quan trọng 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”. Hình 1.2g - Minh họa liên kết giữa các site sử dụng trong PageRank 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ự 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. Google tính điểm cho các trang web trên mạng từ 0-10. 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. Thuật toán PageRank. Trích từ Google, PageRank được định nghĩa như sau: Coi trang A có các trang T1, T2, …, Tn trỏ tới nó. Tham số cản d có thể được đặt giá trị trong khoảng 0 đến 1. Chúng ta thường đặt d= 0.85. C(A) được định nghĩa là số link mà trang A trỏ đến. PageRank của trang A được tính theo công thức: PR(A) = (1-d) + d( PR(T1)/C(T1) + …+ PR(Tn)/C(Tn) ) Chú ý rằng tổng tất cả PageRank của tất cả các trang web là một số cố định. PageRank PR(A) có thể được tính toán bằng cách sử dụng 1 thuật toán lặp đơn giản. Trong đó: PR(A) - PageRank của trang A PR(Tn) - PageRank của trang Tn C(Tn) - Số các link đi ra của trang Tn (1-d) - Thể hiện rằng tổng PageRank tất cả các trang web là một số cố định. Ngoài ra còn có ý nghĩa là nếu 1 trang web mà không có trang nào trỏ tới nó thì nó sẽ có PR < 0.15 Ta thấy PageRank của một trang web được tính bằng tổng của PageRank của tất cả các trang trỏ tới nó (incoming links), chia cho số các link đi ra của trang đó ( outgoing links) Ý nghĩa thuật toán. Trên quan điểm của Search Engine, đị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 của bạn trên Google. Đó là: - Số lượng các link đi đến ( incoming links): Thông thường thì càng nhiều link đi đến càng tốt. Có 1 điểm đáng chú ý mà thuật toán chỉ ra đó là: Nếu 1 trang không có link trỏ đến có thể gây ra ảnh hưởng ngược lại đến PageRank của trang web mà nó trỏ tới ( C(T) = 0 ). - Số lượng các link đi ra của các trang web trỏ tới ( outgoing links): Càng ít càng tốt, có nghĩa là nếu có 2 trang web trỏ tới trang cần tính PageRank, 1 trang có 5 link đi ra và 1 trang có 10 link đi ra thì PageRank được tính từ trang có 5 link đi ra sẽ gấp đôi trang có 10 link đi ra. Có thể thấy thuật toán PageRank không liên quan gì đến các câu truy vấn tìm kiếm. Nó chỉ đơn thuần là một phần của thuật toán xếp hạng của Google. Có lẽ cách tốt nhất để xem xét PageRank là coi nó như là 1 yếu tố bổ sung, được xử lý trên các kết quả tìm kiếm của Google sau khi tất cả các tính toán khác đã hoàn tất. Thuật toán tìm kiếm của Google trước tiên sẽ tiến hành tìm kiếm trên các trang mà nó đã đánh chỉ mục, sau đó sẽ tính toán PageRank trên các trang kết quả tìm kiếm để đưa ra danh sách kết quả có sắp xếp cuối cùng. Các trang có PageRank cao hơn sẽ được sắp xếp ở vị trí cao hơn. PageRank được tính toán như thế nào. Đây là công việc khá phức tạp. PageRank của mỗi trang phụ thuộc vào PageRank của các trang trỏ tới nó. Nhưng ta lại không thể biết PageRank của các trang đó cho đến khi tính được PageRank của các trang trỏ tới các trang đó…Có thể thấy dường như thuật toán tạo thành 1 vòng lặp vô tận mà không thể tính toán được. Nhưng thực tế chúng ta không làm như vậy. Chúng ta sẽ tính toán PageRank của 1 trang mà không cần biết giá trị cuối cùng của PageRank của trang đó. Điều này nghe có vẻ không hợp lý, nhưng về cơ bản, mỗi lần chạy thuật toán chúng ta sẽ đến gần hơn với giá trị ước lượng cuối cùng. Vì vậy tất cả công việc phải làm là ghi nhớ giá trị mỗi lần tính toán và lặp lại phép toán cho đến khi kết quả thay đổi trong một giá trị đủ nhỏ cho phép. Hãy xem xét một ví dụ đơn giản nhất: có 2 trang web, mỗi trang lại trỏ đến trang kia. Page B Page A Mỗi trang có 1 link đi ra ( outgoing links). C(A) = C(B) = 1. Trường hợp 1 Ban đầu chúng ta chưa biết được PageRank của từng trang, vì thế ta sẽ đặt bằng 1, sau đó thực hiện phép tính: d = 0.85 PR(A) = (1-d) + d(PR(B)/1) PR(B) = (1-d) + d(PR(A)/1) Theo ví dụ trên ta tính được: PR(A) = 0.15 + 0.85*1 = 1 PR(B) = 0.15 + 0.85*1 = 1 Nhận thấy kết quả không thay đổi so với PageRank đã ước lượng, cho thấy PageRank dự đoán ban đầu là chính xác. Trường hợp 2 Nếu chúng ta ước lượng sai, giả sử ước lượng ban đầu PageRank của 2 trang đều bằng 0, khi đó thực hiện phép tính: PR(A) = 0.15 + 0.85*0 = 0.15 PR(B) = 0.15 + 0.85*0.15 = 0.2775 Chú ý: Ta tính được giá trị tốt hơn cho PR(A) sau phép tính thứ nhất, vì thế ta sẽ sử dụng kết quả này trong phép tính thứ 2 Lặp lại: PR(A) = 0.15 + 0.85*0.2775 = 0.385875 PR(B) = 0.15 + 0.85*0.385875 = 0.47799375 Lặp lại: PR(A) = 0.15 + 0.85*0.47799375 = 0.5562946875 PR(B) = 0.15 + 0.85*0.5562946875 = 0.622850484375 Cứ tiếp tục như vậy, giá trị của PageRank của mỗi trang sẽ liên tục thay đổi sau mỗi lần tính toán. Vấn đề đặt ra là có thực sự PageRank của mỗi trang sẽ tiến đến 1.0? Liệu có thể PageRank của mỗi trang có thể vượt quá 1.0 hay không? Chúng ta có thể kiểm tra kết quả bài toán tại phần phụ lục. Sau các bước lặp thì PageRank của A và B đều tiến tới ổn định và PageRank trung bình bằng 1. Trường hợp 3 Chúng ta sẽ thử lại với 1 giá trị ước lượng ban đầu lớn hơn cho PageRank của mỗi trang. Giả sử ước lượng PageRank của mỗi trang ban đầu là 40. Quá trình tính toán qua mỗi vòng lặp: PR(A) = 0.15 + 0.85*40 = 34.15 PR(B) = 0.15 + 0.85*34.15 = 29.1775 Lặp lại: PR(A) = 0.15 + 0.85*29.1775 = 24.950875 PR(B) = 0.15 + 0.85*24.950875 = 21.35824375 Thấy rằng các giá trị này đều giảm dần và sẽ tiến tới 1.0. Nhận xét. Không phụ thuộc vào giá trị ước lượng ban đầu, khi thuật toán PageRank ổn định thì giá trị trung bình của PageRank của tất cả các trang bằng 1.0 Tức là: Thứ nhất, mặc dù chúng ta không thể thay đổi tổng PageRank của tất cả các trang web nhưng chúng ta có thể tác động đến PageRank riêng biệt của từng trang. Ví dụ, ta muốn hầu hết lượt truy cập vào site thông qua trang chủ của mình, tức là ta muốn trang chủ có PageRank cao hơn so với những trang khác trong site. Cho rằng tất cả PageRank của các trang đều hợp lệ và được chia đều cho các link đi ra của trang. Khi đó điều ta mong muốn là bất kì trang nào với nhiều liên kết ngoài ( external link) sẽ có PageRank thấp hơn so với các trang khác trong site, nhằm giảm tối thiểu số PageRank bị “thất thoát” ra các site ngoài. Thứ hai, nếu cho rằng bất kì một trang mới nào trong chỉ mục của Google đều bắt đầu với PageRank bằng 1, do đó có 1 cách làm tăng tổng PageRank của site, đó là tăng số lượng trang. 1 site với 10 trang sẽ có PageRank bằng 10, sau đó sẽ được phân phối lại qua các hyperlink của nó. 1 site với 12 trang sẽ có PageRank bằng 12. Vì vậy chúng ta có thể tăng PageRank của 1 site một cách tổng thể bằng cách tạo ra các nội dung mới (ví dụ: thêm trang), sau đó điều khiển sự phân bố tổng PageRank này qua các chiến lược liên kết nội giữa các trang trong site. 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. 2.4. Searching Ứng dụng lớn nhất của PageRank là tìm kiếm (searching). Chúng em giới thiệu một công cụ tìm kiếm toàn bộ văn bản ( full text search engine ), đó là Google. Google sử dụng 1 số các tham số để sắp xếp kết quả tìm kiếm, bao gồm đơn vị đo IR chuẩn, proximity, văn bản móc nối, PageRank. Lợi ích của PageRank trong tìm kiếm là rất lớn. Chẳng hạn, khi ta tìm kiếm với từ khóa “Stanford University”, sẽ cho ra bất kì trang web nào có liên quan đến Stanford đối với những hệ thống tìm kiếm thông thường không sử dụng PageRank. Còn nếu hệ thống sử dụng PageRank thì trang chủ của trường Stanford sẽ được sắp xếp đầu tiên. Mục tiêu của việc tìm kiếm là cung cấp các kết quả tìm kiếm có chất lượng và hiệu quả. Nhiều khi kết quả tìm kiếm không phù hợp với mong muốn tìm kiếm của người dùng, gây ra sự chán nản và lãng phí thời gian. Nhiều search engine thương mại hóa lớn đã có những tiến bộ lớn trong việc nâng cao hiệu quả tìm kiếm. Google được thiết kế nhằm cung cấp tìm kiếm chất lượng cao trong khi tiếp tục nâng cao tốc độ. Google đi đầu trong việc nâng cao chất lượng tìm kiếm bằng cách đưa vào các giải thuật nhằm sắp xếp vị trí các kết quả tìm kiếm. Quy trình xử lý truy vấn của search engine: Phân loại các truy vấn Chuyển các từ sang chỉ mục từ ( wordIDs ). Tìm kiếm từ đầu của danh sách văn bản trong một giới hạn hẹp Tìm kĩ qua danh sách văn bản đến khi có 1 văn bản phù hợp với tất cả các mục tìm kiếm Tính toán thứ hạng của văn bản cho câu truy vấn Nếu đang tìm kiếm theo 1 giới hạn hẹp và đã tìm đên cuối của danh sách văn bản mà chưa có kết quả thì sẽ quay lại mục 4 và tiến hành tìm kiếm không giới hạn. Nếu kết thúc không ở cuối bất kì 1 danh sách văn bản nào thì quay lại bước 4 Sắp xếp văn bản phù hợp với thứ hạng và đưa ra k kết quả đầu tiên. Nhằm giới hạn thời gian đáp ứng, khi một số văn bản phù hợp đã được tìm thấy ( thường là 40.000 ) thì máy tìm kiếm sẽ tự động chuyển đến bước 8. Điều đó có nghĩa là có thể có khả năng chỉ một phần của kết quả được in ra. Quá trình tìm kiếm. Hệ thống lưu trữ các thông tin về trang web bao gồm vị trí, font chữ, thông tin hoạt động, liên kết, PageRank. Kết hợp tất cả các thông tin này thành 1 thứ hạng là rất khó, vì vậy chúng ta thiết kế chức năng xếp hạng sao cho không 1 thành phần nào có ảnh hưởng quá lớn đến thứ hạng của trang web. Đầu tiên, xét trường hợp đơn giản nhất đó là câu truy vấn chỉ có 1 từ đơn. Với mục đích sắp xếp các văn bản với câu truy vấn 1 từ đơn, Google sẽ tìm trên danh sách chỉ mục của mình từ khóa đó, tính điểm các thuộc tính ( tiêu đề, liên kết, URL,…) trên những kết quả phù hợp, mỗi thuộc tính có điểm của riêng nó. Các điểm thuộc tính tạo thành 1 vector chỉ mục theo kiểu thuộc tính. Google sẽ đếm số lượng các kết quả phù hợp và gọi là điểm số lượng. Sau đó sử dụng 2 điểm này để tính ra điểm IR cho văn bản. Cuối cùng, điểm IR kết hợp với PageRank để đưa ra kết quả cuối cùng. Với trường hợp tìm kiếm với nhiều từ khóa, trường hợp này phức tạp hơn. Khi đó nhiều danh sách chỉ mục phải được xem xét đồng thời, vì thế những trang mà có các từ khóa xuất hiện đồng thời sẽ có điểm cao hơn so với những trang chỉ chứa 1 phần của các từ khóa. Vì vậy, các trang liên quan đến nhau sẽ được kết hợp lại với nhau. Với mỗi một tập các trang kết hợp với nhau như thế, “proximity” sẽ được tính toán. Proximity được tính toán dựa trên việc xem xét các trang liên quan có chặt chẽ với nhau hay không, được chia làm 10 mức. Lúc này, số lượng các kết quả phù hợp không chỉ bao gồm các trang có kết quả phù hợp mà còn bao gồm cả các tập có kết qủa phù hợp. Sử dụng 2 điểm này để tính điểm IR cho văn bản, kết hợp với PageRank để cho ra kết quả cuối cùng. Hiệu năng tìm kiếm. Hiệu năng của quá trình tìm kiếm phụ thuộc vào nhiều yếu tố. Chúng ta có thể tăng hiệu năng của quá trình tìm kiếm bằng cách tổ chức phân tán, nâng cấp phần cứng, phần mềm, cải tiến thuật toán. 3. Google Search Engine 3.1. Kiến trúc tổng quan của Google Tổng quan toàn bộ hệ thống làm việc của Google có thể được biểu diễn như hình dưới: URL Server Crawler Store Server Repository Anchors URL Resolver Indexer Lexicon Barrels Sorter Searcher Pagerank Links Doc Index Hình 1.3a - Kiến trúc Google mức cao Trong kiến trúc của Google, quá trình thu thập trang web được thực hiện bởi một vài web crawler khác nhau. Có 1 khối URLserver để gửi danh sách các URL mà crawler cần thu thập. Trang web cần thu thập sẽ được lưu trữ trong khối StoreServer. Sau đó StoreServer sẽ nén và lưu trữ các trang web trong cơ sở dữ liệu. Mỗi trang web có một ID để truy nhập gọi là docID. Chức năng đánh chỉ mục được thực hiện bởi khối Indexer và Sorter. Khối Indexer thực hiện một số chức năng. Nó sẽ đọc cơ sở dữ liệu, giải nén các tài liệu và phân tích chúng. Mỗi một tài liệu được chuyển thành 1 tập các từ gọi là hit. Các hit ghi các từ, vị trí của văn bản, và một số các thông tin khác như kích cỡ font, hoạt động của trang… Khối Indexer sẽ phân các hit này thành 1 tập các Barrel, tạo thành các tiền chỉ mục được sắp xếp. Khối Indexer còn thực hiện một chức năng quan trọng khác là nó sẽ phân tích tất cả các link trong các trang web và lưu trữ thông tin quan trọng về chúng vào 1 file móc nối. File này chứa thông tin để xác định mỗi một link xuất phát từ đâu, trỏ đến đâu, và text của liên kết. Khối URLresolver sẽ đọc các File móc nối và chuyển các URL tương đối thành các URL nguyên thủy và hướng vào docID. Nó đặt các text của liên kết vào tiền chỉ mục, báo với docID rằng có liên kết trỏ tới nó. Nó cũng sinh ra cơ sở dữ liệu các link là một cặp docID. Cơ sở dữ liệu link sẽ được sử dụng để tính PageRank cho tất cả các văn bản. Khối Sorter lấy dữ liệu từ khối Barrel, mà đã được sắp xếp theo docID, và sắp xếp lại chúng theo wordID để sinh ra chỉ mục ngược. Việc này chỉ yêu cầu một bộ nhớ tạm rất nhỏ. Khối Sorter cũng sinh ra danh sách các worldID và đưa vào chỉ mục ngược. Một chương trình được gọi là DumpLexicon lấy danh sách này cùng với kết quả của khối Indexer để sinh ra một “từ điển” mới cho khối tìm kiếm sử dụng. Khối tìm kiếm sẽ chạy bởi web server và sử dụng từ điển được xây dựng bởi DumpLexicon cùng với chỉ mục ngược và PageRank để đưa ra kết quả của quá trình tìm kiếm. 3.2 Cấu trúc dữ liệu chính. Cấu trúc dữ liệu của Google cho phép những văn bản lớn có thể được craw, đánh chỉ mục, và tìm kiếm với chi phí nhỏ nhất. Mặc dù tốc độ CPU và tốc độ vào ra dữ liệu phát triển liên tục qua từng năm nhưng việc tìm kiếm trên đĩa vẫn cần 10ms để hoàn thành. Google được thiết kế nhằm tránh tối đa việc tìm kiếm trên đĩa. Việc này có ảnh hưởng đáng kể bởi việc thiết kế cấu trúc dữ liệu Big Files BigFiles là 1 file ảo, mở rộng của hệ thống đa file và được đánh địa chỉ bằng các số nguyên 64 bit. Sự phân phối giữa các hệ thống đa file được điều khiển một cách tự động Kho chứa ( Cơ sở dữ liệu ) Kho chứa bao gồm các trang thuần HTML của các trang web. Mỗi trang được nén theo chuẩn zlib ( RFC1950 ). Việc lựa chọn công nghệ nén phải cân bằng giữa tốc độ và tỉ số nén. Trong kho chứa, mỗi trang được lưu trữ 1 lần và được thêm vào các tiền tố docID, độ dài, URL, như hình dưới Hình 1.3b - Cấu trúc dữ liệu trong kho chứa Kho chứa không yêu cầu bất cứ một cấu trúc dữ liệu nào khác để truy nhập đến nó. Việc này giúp cho dữ liệu ổn định và là cho việc phát triển trở lên dễ dàng hơn. Chúng ta có thể xây dựng lại dễ dàng các cấu trúc dữ liệu khác từ kho chứa. Chỉ mục văn bản Chỉ mục văn bản lưu giữ thông tin về mỗi văn bản. Nó là 1 chỉ mục ISAM có chiều rộng cố định, được sắp xếp bởi docID. Thông tin được lưu trữ trong mỗi thực thể bao gồm trạng thái hiện tại của văn bản, con trỏ đến cơ sở dữ liệu, một hàm kiểm tra tổng của văn bản, và một số thông tin khác. Nếu văn bản được thu thập, sẽ có 1 con t