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

i ưu chí phí quảng cáo trực tuyến Easy – Op GV Hướng dẫn : Ts. Phạm Hoàng Duy Ths. Nguyễn Thị Ngọc Vinh Hà Nội, Tháng 11 năm 2011 Table of Contents LỜI MỞ ĐẦU Sự đổi mới không ngừng của khoa học kỹ thuật công nghệ, nhiều lĩnh vực đã và đang phát triển vượt bậc đặc biệt là lĩnh vực công nghệ thông tin. Thành công lớn nhất có thể kể đến là sự ra đời của chiếc máy tính. Máy tính được coi là một phương tiện trợ giúp đắc lực cho con người trong nhiều công việc đặc biệt là công tác quản lý. Mạng máy tính được sinh từ nhu cầu muốn chia sẻ và dùng chung dữ liệu. Máy tính cá nhân là công cụ tuyệt vời giúp tạo dữ liệu, bảng tính, hình ảnh, và nhiều dạng thông tin khác, nhưng không cho phép chia sẻ dữ liệu bạn đã tạo nên. Sự bùng nổ dịch vụ Internet cũng như bùng nổ số lượng người sử dụng khi công nghệ trở nên thân thiện với con người, các cơ hội đã được mở ra với một thị trường cực kì rộng lớn cho các doanh nghiệp, các sản phẩm, dịch vụ được phân phối và cung cấp rộng khắp, nhanh chóng và cực kì tiện lợi. Để thông tin về sản phẩm của mình, các doanh nghiệp thường sử dụng các hình thức quảng cáo, tuy nhiên với chi phí đắt đỏ, cho dù mang lại hiểu quả cao nhưng các hình thức quảng cáo trên truyền hình, báo chí chưa thực sự tối ưu. Từ thực tế đó, các hình thức quảng cáo qua thư điện tử, máy tìm kiếm thông tin trên mạng đã dần có được sự quan tâm đặc biệt. Với những doanh nghiệp mới thành lập, quảng cáo trực tuyến là một sự lựa chọn hoàn hảo để cân bằng giá và hiệu quả. Đã có rất nhiều doanh nghiệp sử dụng các hình thức quảng cáo trực tuyến để mang sản phẩm và dịch vụ của mình đến người tiêu dung với chi phí thấp. Điều quan trọng của loại hình quảng cáo qua máy tìm kiếm là khi được lựa chọn kĩ càng và tối ưu, chi phí sẽ giảm xuống rất nhiều. Chính vì đó em đã chọn đề tài Xây dựng phầm mềm tối ưu hóa chi phí quảng cáo trực tuyến. Nhưng do thời gian và kiến thức có hạn nên bài viết còn hạn chế, rất mong được sự góp ý của các thầy cô giáo và chung em xin chân thành cảm ơn TS.Phạm Hoàng Duy, ThS. Nguyễn Thị Ngọc Vinh đã giúp đỡ để em hoàn thành đề tài này. CHƯƠNG I :TỔNG QUAN VỀ E - MARKETING E-marketing (Internet marketing hay online marketing), hay tiếp thị qua mạng, tiếp thị trực tuyến là hoạt động cho sản phẩm và dịch vụ thông qua mạng kết nối toàn cầu Internet. Sự xuất hiện của Internet đã đem lại nhiều lợi ích như chi phí thấp để truyền tải thông tin và truyền thông (media) đến số lượng lớn đối tượng tiếp nhận, thông điệp được truyền tải dưới nhiều hình thức khác nhau như văn bản, hình ảnh, âm thanh, phim, trò chơi,... Với bản chất tương tác của E-marketing, đối tượng nhận thông điệp có thể phản hồi tức khắc hay giao tiếp trực tiếp với đối tượng gửi thông điệp. Đây là lợi thế lớn của E-marketing so với các loại hình khác. E-marketing kết hợp tính sáng tạo và kỹ thuật của Internet, bao gồm thiết kế, phát triển, quảng cáo và bán hàng. Các hoạt động của E-marketing bao gồm: search engine marketing, web display advertising, e-mail marketing, affiliate marketing, interactive advertising, blog marketing và viral marketing. Một trong những lợi thế của E-marketing là sự sẵn sàng của lượng lớn thông tin. Người tiêu dùng có thể truy cập thông tin sản phẩm và thực hiện giao dịch, mua bán mọi lúc mọi nơi. Doanh nghiệp sử dụng e-makerting có thể tiết kiệm được chi phí bán hàng như chi phí thuê mặt bằng, giảm số lượng nhân viên bán hàng,.. E-marketing còn giúp doanh nghiệp tiếp cận với thị trường rộng lớn cũng như phát triển ra toàn cầu. Ngoài ra, so sánh với các phương tiện khác như in ấn, báo đài,  truyền hình, e-marketing có lơi thế rất lớn về chi phí thấp. E-marketing đã và đang có ảnh hưởng rộng lớn với nhiều ngành công nghiệp như âm nhạc, ngân hàng, thương mại, cũng như bản thân ngành công nghiệp quảng cáo. Trong ngành công nghiệp âm nhạc, nhiều khách hàng mua và tải các bản nhạc qua Internet thay vì mua CD. Ngày càng nhiều ngân hàng cung cấp các dịch vụ trực tuyến. Dịch vụ ngân hàng trực tuyến được cho rằng sẽ hấp dẫn khách hàng hơn khi họ không phải đến các chi nhánh ngân hàng để thực hiện. Hiện tại, hơn 150 triệu người Mỹ sử dụng dịch vụ ngân hàng trực tuyến và tốc độ tăng trưởng ngày càng cao. Sự cải thiện tốc độ kết nối Internet là nguyên nhân chính cho sự tăng trưởng này. 44% những cá nhân sử dụng Internet thực hiện các giao dịch với ngân hàng qua Internet. Đấu giá qua Internet cũng đang trở nên phổ biến. Những mặt hàng hiếm trước đây chỉ có thể tìm ở các chợ trời nay đang được rao bán trên eBay. Trang Web nay cũng có ảnh hưởng mạnh đến giá cả. Người mua và người bán thường tham khảo giá trên eBay trước khi đến chợ trời và giá trên eBay thường trở thành giá mà sản phẩm được bán. Ngày càng nhiều người bán hàng ở chợ trời rao bán hàng trên eBay và điều hành công việc kinh doanh ở nhà. Sự ảnh hưởng của E-marketing lên nền công nghiệp quảng cáo ngày càng lớn. Chỉ trong vài năm, quảng cáo trực tuyến tăng trưởng đều đặn đến hàng chục tỷ USD. Theo báo cáo của Pricewaterhouse Coopers, thị trường E-marketing Mỹ trị giá tổng cộng 16,9 tỷ USD trong năm 2006. Trong tất cả các công cụ của E – Marketing, Seach Engine Marketing và thiết kế web là một trong những công cụ không thể thiểu đế tạo nên thành công của chiến dịch Marketing. Trong xu thế phát triển của mạng Internet như hiện nay. Mọi thứ đều có thể được đưa lên mạng để cùng chia sẻ. Người tiêu dùng đã mặc nhiên coi Google là một công cụ tìm kiếm hữu hiệu và với họ. Họ mặc định rằng mọi thứ muốn tìm kiếm thì cứ lên trang Google tìm là có. Do vậy việc đòi hỏi tối ưu hóa công cụ tìm kiếm cũng như các hình thức quảng cáo trên máy tìm kiếm là rất cần thiết trong môi trường đầy cạnh tranh hiện nay. CHƯƠNG II: GIỚI THIỆU CÔNG CỤ TÌM KIẾM 1. Công cụ tìm kiếm là gì? Công cụ tìm kiếm(Search Engine) là một hệ thống thu thập thông tin được thiết kế để giúp cho việc tìm kiếm thông tin lưu trữ trên một hệ thống máy tính. Công cụ tìm kiếm tối thiểu hóa thời gian cần thiết để tìm kiếm thông tin bằng việc lưu trữ và xử lý thông tin theo nhiều cách. Dạng phổ biến nhất của công cụ tìm kiếm đó là công cụ tìm kiếm Web (Web Search Engine) . vd: Google Search, Yahoo Search, … Công cụ tìm kiếm cung cấp một giao diện giúp cho người dùng có thể chọn thông tin cần tìm và có cơ chế xử lý và tìm được thông tin tương ứng. Thông tin cần tìm sẽ tương ứng với một câu truy vấn. 2. Nguyên tắc hoạt động của công cụ tìm kiếm. Một công cụ tìm kiếm được gọi là thành công nếu nó thỏa mãn được 3 điều kiện: - Cho phép tìm kiếm trong một tập hợp lớn các trang web. - Đưa ra kết quả gần với mong muốn của người sử dụng nhất. - Tốc độ tìm kiếm chấp nhận được. Để đạt được các mục đích trên, các công cụ tìm kiếm hiện đại đều tiến hành lần lượt theo bốn bước: web crawler, indexing, rank page và searching. Sau đây ta sẽ đi chi tiết vào từng phần. 2.1. Web crawler: Web crawler là bộ phận chịu trách nhiệm download các trang web và lưu trữ chúng dưới dạng nén ở trong kho dữ liệu. Mục đích thiết kế của web crawler là làm cho nó download được số lượng trang web nhiều nhất trong khả năng đáp ứng của tài nguyên mạng và tốc độ, khả năng lưu trữ của máy. Hình1.2a - Hoạt động của web crawler Tất cả các công cụ tìm kiếm đều dựa trên mô hình web crawler như hình 1.2a Một Webcrawler sẽ sử dụng hai hàng đợi để quản lý các URL, đó là URLsToVisit (URL sẽ tới) và VisitedURLs (URL đã tới). Hàng đợi VisitedURL chứa danh sách các trang đã được download. Danh sách này rất quan trọng đối với các crawler để tránh việc download một trang nhiều lần. Trong khi đó hàng đợi URLsToVisit chứa danh sách các trang sẽ được download. Nội dung ban đầu của hàng đợi URLsToVisit được gọi là seed list (danh sách hạt giống). Danh sách này sẽ ngày càng mở rộng theo thời gian. Trước khi crawler chạy lần đầu tiên, danh sách URLs hạt giống này sẽ được khởi tạo một cách thủ công hoặc có thể được lấy từ một số nguồn khác. Danh sách khởi tạo này lúc đầu có thể là một tập các web site bất kỳ, hoặc có thể là một tập các web site có chủ đề nhất định do người khởi tạo quyết định. Webcrawler hoạt động dưới dạng các vòng lặp nối tiếp nhau. Một vòng lặp sẽ bắt đầu với việc lấy một URL từ hàng đợi URLsToVisit, tiếp đó webcrawler sẽ download trang web tương ứng với URL đó, lưu trữ trang web đó vào trong kho và đẩy URL đó vào trong hàng đợi VisitedURLs. Trong mỗi vòng lặp, webcrawler sẽ trích tất cả các link mà trang web vừa được lấy về, chuyển nó từ dạng link tương đối sang dạng link tuyệt đối, rồi kiểm tra ở hàng đợi VisitedURLs xem các trang này đã được download về chưa. Nếu URL nào đã được download về rồi, nó sẽ bỏ qua URL đó còn nếu chưa được download, nó sẽ chuyển URL đó vào hàng đợi URLsToVisit. Quá trình này sẽ được lặp đi lặp lại cho đến khi nào hàng đợi URLsToVisit rỗng hoặc nó được dừng lại một cách có mục đích bởi người điều khiển. Nếu việc lấy về một URL thất bại, crawler sẽ chuyển URL đó ngược lại vào hàng đợi URLsToVisit để thử lại lần sau. Nếu như việc lấy một URL thất bại trong nhiều lần, crawler sẽ bỏ qua nó vì rất có thể webserver chứa URL đó đã không còn hoạt động nữa. Theo cách này, một crawler có thể lấy về một số lượng lớn các trang web chỉ từ một lượng rất nhỏ URL trong danh sách khởi tạo (seed list). Để có thể hiểu kỹ hơn về webcrawler, ta sẽ tìm hiểu những thiết kế và những rủi ro tiềm ẩn có thể gặp phải trong việc cài đặt và điều hành một webcrawler mức độ lớn. Crawler song song Hình 1.2a chỉ nêu nguyên tắc hoạt động chung của 1 crawler riêng biệt, nó chỉ sử dụng một hàng đợi URLsToVisit và một hàng đợi VisitedURLs. Mô hình trên là tổng quát cho các crawler nhưng có các nhược điểm sau: - Dung lượng của bộ nhớ chính sẽ giới hạn kích thước của các hàng đợi URL, khi số trang web tăng lên rất lớn, một crawler riêng lẻ sẽ có thể bị quá tải và hiệu năng sẽ không cao. - Tốc độ download các trang web về sẽ chậm do tiến trình download diễn ra một cách tuần tự. Để giải quyết vấn đề trên, người ta đưa ra mô hình crawler song song (parallelism) Web site – đơn vị cho quá trình crawler song song Trước hết ta định nghĩa: một web site là một tập các trang web có cùng một tên miền đầy đủ trong URL của nó. VD: các trang và trang sẽ thuộc cùng một website trong khi đó trang sẽ không thuộc cùng một Site với hai trang trên. Vì vậy các link tương đối chắc chắn sẽ nằm trên cùng một site với trang đang xét còn các link tuyệt đối sẽ cần phải kiểm tra trước. Hình 1.2b - Mô hình crawler song song Tiếp theo ta sẽ làm rõ mô hình crawler song song. Hình 1.2b cho chúng ta thấy mô hình chung của một webcrawler song song. Mô hình này thực chất là một tập hợp các phần tử của mô hình crawler riêng biệt trong đó mỗi một crawler sẽ chịu trách nhiệm lấy về các trang web của chỉ duy nhất một Site và tiến trình lấy về các trang web này sẽ được diễn ra một cách đồng thời giữa các crawler trong mô hình. Một điểm đáng lưu ý là mô hình trên đưa ra một bộ phân phối các URL khởi tạo (seed-URL dispenser). Bộ phân phối trên chứa danh sách tất cả các URL khởi tạo cho tất cả các tiến trình crawl. Mỗi một phần tử trong danh sách trên chứa các URL khởi tạo cho chỉ một Website, thông thường nó chứa URL gốc của site đó. Trong mô hình trên, mỗi một site crawler sẽ bắt đầu bằng việc lấy về URL khởi tạo cho một Website từ bộ phân phối URL và sử dụng nó để khởi tạo cho hàng đợi URLsToVisit. Crawler sẽ đẩy vào hàng đợi URLsToVisit các URL mà nó lấy được trong site đó. Nguyên tắc của nó là nếu gặp các link ở trong site đó, nó sẽ lấy về còn nếu gặp các link ở ngoài site đó, nó sẽ bỏ qua. Việc sử dụng crawler song song có giải quyết được các nhược điểm của crawler riêng biệt. - Dung lượng của bộ nhớ chính sẽ không còn là vấn đề vì mỗi một site crawler chỉ lấy về các trang web có URL nằm trong site đó, do đó kích thước của các hàng đợi URLsToVisit và VisitedURLs không quá lớn. - Tốc độ download các trang 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 trỏ trỏ tới biến chiều rộng của file gọi là biến docinfo bao gồm URL và tiêu đề của trang web được thu thập. Nếu không con trỏ sẽ trỏ tới URLlist chỉ bao gồm các URL. Thiết kế này được sử dụng với mong muốn có được 1 cấu trúc dữ liệu chặt chẽ hợp lý và có thể đưa ra bản ghi trong quá trình tìm kiếm. Ngoài ra có 1 file được sử dụng để chuyển URL sang docID. Đó là 1 danh sách các kiểm tra tổng của URL với docID tương ứng của URL đó được sắp xếp bởi hàm kiểm tra tổng. Với mong muốn tìm ra 1 docID của 1 URL, hàm kiểm tra tổng của URL được tính toán và 1 quá trình tìm kiếm nhị phân được thực hiện trên file kiểm tra tổng để tìm ra docID. URL có thể được chuyển thành docID theo khối bằng cách trộn file này. Đây là công nghệ mà khối URLresolver sử dụng để chuyển URL sang docID. Khối này là khối rất quan trọng bởi nếu không chúng ta phải thực hiện 1 lần tìm kiếm cho tất cả các liên kết. Việc này sẽ mất hơn 1 tháng nếu chúng ta có 322 triệu link. Từ điển Từ điển có nhiều dạng khác nhau. Một thay đổi quan trọng so với các hệ thông trước đây là từ điển được chưa vừa trong bộ nhớ có giá cả hợp lý. Hiện tại, từ điển có thể được chứa vừa trong bộ nhớ chính 256MB. Từ điển này chưa 14 triệu từ. Nó được chia làm 2 phần, danh mục các từ ( được nối với nhau hoặc được phân chia ) và bảng băm các con trỏ. Danh sách Hit (Hit Lists). Danh sách các hit tương ứng với một danh sách các từ xuất hiện trong văn bản, bao gồm vị trí, font, các thông tin bổ sung. Hit list là không gian sử dụng của cả tiền chỉ mục và chỉ mục ngược. Vì vậy, điều quan trọng là biểu diễn chúng một cách có hiệu quả nhất. Chúng ta có một số lựa chọn cho việc mã hóa các thông tin của hit list đó là: mã hóa đơn giản ( bộ 3 số nguyên ), mã hóa chặt ( sử dụng các bit ) và mã hóa Huffman. Google lựa chọn mã hóa chặt sử dụng các bit vì nó sử dụng ít bộ nhớ hơn mã hóa đơn giản và không phải tính toán trên bit nhiều như mã hóa Huffman. Hình 1.3c - Tiền chỉ mục, chỉ mục ngược và từ điển Cách mã hóa chặt sử dụng 2 bytes cho mỗi hit. Có 2 loại hit: hit dẫn xuất ( fancy hit ) và hit nguyên thủy ( plain hit ). Hit dẫn xuất bao gồm URL, tiêu đề, móc nối, và các meta-tag. Hit nguyên thủy bao gồm tất cả các thuộc tính. Hit nguyên thủy bao gồm 1 bit ý nghĩa, kích cỡ font, và 12 bit biểu diễn vị trí của từ trong văn bản ( tất cả các vị trí lớn hơn 4095 được biểu diễn bằng 4096 ). Kích cỡ font sử dụng 3 bit ( nhưng chỉ có 7 giá trị được sử dụng vì 111 là cờ hiệu của Hit dẫn xuất). Hit dẫn xuất bao gồm bit ý nghĩa, kích cỡ font được đặt bằng 111 để biểu thị đây là Hit dẫn xuất, 4 bit để mã hóa loại Hit dẫn xuất, và 8 bit cho vị trí của từ trong văn bản. Chiều dài của Hit List được lưu trữ trước khi Hit List thực sự được lưu. Để tiết kiệm không gian nhớ, chiều dài của Hit List được kết hợp với worldID trong tiền chỉ mục và docID trong chỉ mục ngược. Điều này giới hạn nó ở 8 và 5 bit thứ tự (có một số thủ thuật cho phép mượn 8 bit từ worldID). Nếu chiều dài lớn hơn một mã giải pháp được sử dụng cho các bit thừa và 2 bytes tiếp theo chứa chiều dài thực sự Tiền chỉ mục. Tiền chỉ mục thực sự đã thực hiện sắp xếp một phần. Nó tiến hành sắp xếp trên 1 số barrels ( thường là 64 ). Mỗi barrel lưu 1 khoảng worldID. Nếu một văn bản bao gồm những từ rơi vào barrel hiện tại thì docID sẽ được ghi nhận vào barrel, theo sau là 1 danh sách các worldID với các hit list tương ứng với các từ đó. Chỉ mục ngược. Chỉ mục ngược gồm những barrel tương ứng với tiền chỉ mục, ngoại trừ việc chúng đã được xử lý bởi bộ Sorter. Với mỗi worldID hợp lệ, từ điển sẽ gồm 1 con trỏ tới barrel mà worldID rơi vào. Nó trỏ tới 1 danh sách văn bản của các docID với hit list tương ứng. Danh sách văn bản này biểu diễn tất cả các từ xuất hiện trong văn bản. Vấn đề đặt ra là thứ tự sắp xếp các docID như thế nào. Một giải pháp đơn giản là lưu chúng theo cách sắp xếp theo docID. Cách này cho phép thực hiện ghép trộn dễ dàng giữa các danh sách văn bản khác nhau trong một truy vấn với nhiều từ khóa. Lựa chọn khác là lưu giữ chúng theo cách sắp xếp bởi thứ tự xuất hiện của các từ trong văn bản. Điều này giúp cho việc trả lời các truy vân với 1 từ khóa trở lên đơn giản và làm cho kết quả của các truy vấn với nhiều từ khóa có thứ tự giống như ban đầu. Tuy nhiên cách này làm cho việc ghép trộn trở lên khó khăn. Đồng thời phương pháp này làm cho việc phát triển trở lên khó khăn bởi bất cứ một thay đổi nào trong thứ tự sắp xếp các từ đều phải xây dựng lại chỉ mục. Google lựa chọn giải pháp lai ghép giữa 2 lựa chọn trên, lưu trữ 2 tập chỉ mục ngược, 1 tập các hit list bao gồm tiêu đề hoặc các hit móc nối và 1 tập chứa toàn bộ các hit list. Theo cách này, ta sẽ kiểm tra tập đầu tiên của barrel đầu tiên và nếu không có kết quả phù hợp ta sẽ kiểm tra tiếp với giới hạn lớn hơn. 4. Lợi ích khi quảng cáo trên máy tìm kiếm Google 4.1 Lợi ích về góc nhìn của người dùng thường để ý đến Trong hình vẽ sau sẽ mô tả chi tiết tầm mắt người dùng thường để ý đến khi quan sát trong trình duyệt : Và với một trang nội dung thong thường. Người dùng sẽ thường quét mắt theo thứ tự như trong hình vẽ sau: Và khi đặt quảng cáo thì vị trí của chúng là: Vị trí này rất thuận lợi cho việc chuyển thong điệp đến người sử dụng và điều quan trọng hơn là quảng cáo có vị trí ngay trên cả kết quả tìm kiếm tự nhiên và như vậy kích thích người đọc sử dụng và tiếp nhận thông tin bạn đưa vào 4.2. Lợi ích về chi phí Google bán những vị trí quảng cáo dựa trên các câu truy vấn của người dùng thong qua một phiên đấu giá. Và đưa ra rất nhiều loại hình quảng cáo. Từ 24/24 cho đến theo clicks… Trong đó quảng cáo trả phí theo click tỏ ra hiệu quả nhất. Vì khả năng đo lường và tối ưu hóa được của nó. Và việc của Người làm quảng cáo là phải giải quyết một tổ hợp các công việc tối ưu hóa các vấn đề về quảng cáo của mình để có thể thu lại được kết quả tốt nhất (số clicks lớn nhất và giá hợp lý nhất). Google cung cấp một bảng thống kê các chiến dịch quảng cáo và hiệu quả của chúng trong cả quá trình diễn ra chiến dịch. Khi phải tối ưu hóa các quảng cáo bằng tay thông thường, người làm quảng cáo sẽ phải xem lại các số liệu cũ và đưa ra các hướng phát triển theo hướng mới. Việc làm này rất mất thời gian vì số lượng từ khóa trong một chiến dịch rất lớn. Có thể hàng trăm hoặc hàng ngàn từ. Vì vậy ý tưởng về một phần mềm tối ưu hóa chi phí quảng cáo được đưa ra để giúp tăng tốc công việc cho các Marketer. 4.3. Lợi ích tăng Page Rank Hiển nhiên khi website được vào nhiều thì Page Rank của nó cũng đươc tăng page rank do các hoạt động của người dùng trên trang web đó. Và khi dùng quảng cáo trực tuyến trên máy tím kiếm google. Với những người chưa làm quen với các hình thức marketing thì sẽ vẫn luôn nghĩ rằng đó chính là link mà máy tìm kiếm tìm kiếm tự nhiên ra (do thói quen sử dụng). Nên tạo hiệu quả rất cao khi bán hàng hoặc tiếp thị trên trang web CHƯƠNG III: PHẦN MỀM TỐI ƯU CHI PHÍ QUẢNG CÁO TRỰC TUYẾN EASY- OP Tổng quan về phần mềm Dựa trên những kiến thức em nghiên cứu được, cho thấy việc tối ưu hóa quảng cáo trên máy tìm kiếm Google phải được thực hiện bằng việc tối ưu mục mô tả quảng cao và thống kê những từ khóa có số lượng clicks lớn nhất, số cost bé nhất. người dùng chọn một file đầu vào là một file CSV được convert từ kết quả chiến dịch. Và màn hình sẽ hiển thị những từ khóa ứng với yêu cầu là nhiều clicks nhất và chi phí (cost) thấp nhất. Kiến trúc của hệ thống được xây dựng dựa theo các thành phần sau: FileLoader: Đọc file CSV để lấy dữ liệu đầu vào. KeywordProcess: Xử lý và chọn keywords, tính toán trong cả bộ từ khóa, tìm ra keywords có click nhiều nhất, mức cost thấp nhất, liệt kê theo ngày và đưa ra mức bid hợp lý nhất Xuất kết quả ra màn hình. FileLoader: Đọc file CSV để lấy dữ liệu đầu vào. Với một chương trình mang tính thống kê, việc sử đụng được các file có tính thống kê như Excel hay các chương trình bảng tính thông thường. Chức năng này được hoàn thiện bởi sử dụng phương thức đọc theo dấu phấy, lấy dấu phẩy là quy ước ngăn cách, và ngăn cách theo dòng. while ((thisLine = myInput.readLine()) != null) { //while ((thisLine = myInput.readUTF()) != null) { //beginning of outer while loop count ++; if (count == 1) continue; DataSource buffer = new DataSource(); StringTokenizer st =new StringTokenizer(thisLine,",");// read the current line try { // Set Date DateFormat formatter = new SimpleDateFormat("m/d/y"); buffer.SetDate(formatter.parse(st.nextToken())); } catch (ParseException e) { System.out.println("Exception :" + e); } buffer.SetKeyword(st.nextToken()); buffer.SetQualityScore(new Integer(st.nextToken())); buffer.SetCPC(new Double(st.nextToken().substring(1))); buffer.SetImpression(new Integer(st.nextToken())); buffer.SetClicks(new Integer(st.nextToken())); String a = st.nextToken(); a = a.substring(0, a.length() - 1); Double b = new Double(a) * 100; b = b.intValue() * 0.0001; buffer.SetCTR(b); buffer.SetAvgCPC(new Double(st.nextToken().substring(1))); buffer.SetCost(new Double(st.nextToken().substring(1))); buffer.SetPosition(new Double(st.nextToken())); dataSource.add(buffer); } KeywordProcess: Xử lý, chọn Keywords, tính toán cả bộ từ khóa, tìm ra keywords có clicks nhiều nhất, mức cost thấp nhất, liệt kê theo ngày, đưa ra mức bid hợp lý nhất. Bằng thuật toán quy hoạch động. Với yêu cầu lấy được bộ keywords với số lượng clicks lớn nhất và mức cost nhỏ nhất ứng với ngân sách budget cho sẵn public static ArrayList optimizationRound(int budget, ArrayList listSource) { if (budget > 10000) return null; for (int i = 0; i < listSource.size(); i++) { listSource.get(i).SetCost(Math.ceil(listSource.get(i).GetCost())); } int[][] opt = new int[listSource.size() + 1][budget + 1]; boolean[][] sol = new boolean[listSource.size() + 1][budget + 1]; for (int n = 1; n <= listSource.size(); n++) { for (int w = 1; w <= budget; w++) { // don't take item n int option1 = opt[n-1][w]; // take item n int option2 = Integer.MIN_VALUE; if ((int)listSource.get(n - 1).GetCost() <= w) option2 = listSource.get(n - 1).GetClicks() + opt[n-1][w - (int)listSource.get(n - 1).GetCost()]; // select better of two options opt[n][w] = Math.max(option1, option2); sol[n][w] = (option2 > option1); } } Và sau đó đưa vào Mảng để chờ xuất ra // determine which items to take boolean[] take = new boolean[listSource.size() + 1]; for (int n = listSource.size(), w = budget; n > 0; n--) { if (sol[n][w]) { take[n] = true; w = w - (int)listSource.get(n - 1).GetCost(); } else { take[n] = false; } } int size = listSource.size(); for (int n = size; n > 0; n--) { if (!take [n]) listSource.remove(n - 1); } return listSource; } Mức bid sẽ chính bằng trung bình cost chia cho trung bình clicks Bid = avrgCost1/avrgClicks1; Ngày và tháng được xuất ra cùng dòng với keyword for (int i = 0; i < result.size(); i ++) { System.out.println("-----------------------------------------"); result.get(i).Display(); Chương IV : THỬ NGHIỆM KẾT QUẢ. Trong thời gian nghiên cứu và hoàn thiện chương trình, em đã thử nghiệm trong các dự án: “Điện thoại cho người già – dienthoaichonguoigia.com”, “học guitar – hocguitar.net”, “spa – oceanspa.vn”,”dịch vụ marketing online – marnet.vn” cùng nhiều dự án khác và thấy kết quả đúng như mong muốn. Từ khóa spa, Quảng cáo đứng đầu Từ khóa “hoc guitar o dau” kết quả đứng thứ 2 Kết Luận Với sự phát triển của mạng Internet và các công cụ tìm kiếm, chúng ta có thể thấy được tầm quan trọng của Search Engine đối với mạng Internet. Xu hướng phát triển của Search Engine là tìm kiếm chất lượng và hiệu quả. Vì vậy đề tài đã giải quyết được một số vấn đề giúp người sử dụng có thể làm quen với việc sử dụng tối ưu và hiệu quả công cụ quảng cáo trực tuyến trongE - Marketing. Đề tài có thể được mở rộng, phát triển để trở thành một công cụ tối ưu chi phí chuyên nghiệp, phục vụ nhu cầu tối ưu hóa các chi phí. Trong quá trình làm việc, đề tài còn nhiều thiếu sót mong các thầy cô giáo xem xét và góp ý sửa chữa để chúng em có thể hoàn thiện và phát triển hơn nữa ạ. Em xin chân thành cảm ơn khoa và các thầy cô giáo đã tạo điều kiện giúp đỡ chúng em hoàn thành đề tài này Tài liệu tham khảo : Andrew Goodman: Winning Result with Google Adswords – Mc GrawHill John Feldman, Martin Pál, Cliff Stein, S.Muthurishnan: Budget Optimization in Search-Based Advertising Auctions Thomas S. Fergurson: Linear Programming Judy Strauss, Raymond Frost : E - Marketing (5th Ed), Pearson Pretince Hall Brad Geddes: Advanced Google, Wiley